62 found
Order:
Disambiguations
Carl G. Jockusch [50]Carl Jockusch [12]Carl G. Jockusch Jr [5]Carl Jockusch Jr [2]
  1. On the Strength of Ramsey's Theorem for Pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
    We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   38 citations  
  2.  30
    Ramsey's Theorem and Recursion Theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   29 citations  
  3.  37
    Pseudo-Jump Operators. II: Transfinite Iterations, Hierarchies and Minimal Covers.Carl G. Jockusch & Richard A. Shore - 1984 - Journal of Symbolic Logic 49 (4):1205 - 1236.
  4.  19
    A Cohesive Set Which is Not High.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
    We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   24 citations  
  5.  22
    Double Jumps of Minimal Degrees.Carl G. Jockusch & David B. Posner - 1978 - Journal of Symbolic Logic 43 (4):715 - 724.
  6.  21
    Asymptotic Density and Computably Enumerable Sets.Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp - 2013 - Journal of Mathematical Logic 13 (2):1350005.
    We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is a (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  7.  11
    Degrees of Orderings Not Isomorphic to Recursive Linear Orderings.Carl G. Jockusch & Robert I. Soare - 1991 - Annals of Pure and Applied Logic 52 (1-2):39-64.
    It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  8.  44
    Ramsey's Theorem and Cone Avoidance.Damir Dzhafarov & Carl Jockusch Jr - 2009 - Journal of Symbolic Logic 74 (2):557 - 578.
    It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$ , where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every computable 2-coloring (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  9.  6
    A Degree-Theoretic Definition of the Ramified Analytical Hierarchy.Carl G. Jockusch & Stephen G. Simpson - 1976 - Annals of Mathematical Logic 10 (1):1-32.
  10.  23
    The Degrees of Bi-Immune Sets.Carl G. Jockusch - 1969 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 15 (7-12):135-140.
  11.  18
    Countable Thin Π01 Classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.
    Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that no (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  12.  11
    Asymptotic Density and the Ershov Hierarchy.Rod Downey, Carl Jockusch, Timothy H. McNicholl & Paul Schupp - 2015 - Mathematical Logic Quarterly 61 (3):189-195.
    No categories
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  13.  9
    Diagonally Non-Computable Functions and Bi-Immunity.Carl G. Jockusch & Andrew E. M. Lewis - 2013 - Journal of Symbolic Logic 78 (3):977-988.
  14. Uniformly Introreducible Sets.Carl G. Jockusch - 1968 - Journal of Symbolic Logic 33 (4):521-536.
  15.  5
    The Degrees of Bi‐Immune Sets.Carl G. Jockusch - 1969 - Mathematical Logic Quarterly 15 (7‐12):135-140.
  16.  7
    Coarse Reducibility and Algorithmic Randomness.Denis R. Hirschfeldt, Carl G. Jockusch, Rutger Kuyper & Paul E. Schupp - 2016 - Journal of Symbolic Logic 81 (3):1028-1046.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  17.  22
    Correction to “a Cohesive Set Which is Not High”.Carl Jockusch & Frank Stephan - 1997 - Mathematical Logic Quarterly 43 (4):569-569.
  18. Stability and Posets.Carl Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693 - 711.
    Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite $\Pi _1^0 $ chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  19.  14
    Π10 Classes and Boolean Combinations of Recursively Enumerable Sets.Carl G. Jockusch - 1974 - Journal of Symbolic Logic 39 (1):95-96.
  20. Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
    It is shown that for any computable field K and any r.e. degree a there is an r.e. set A of degree a and a field F ≅ K with underlying set A such that the field operations of F (including subtraction and division) are extendible to (total) recursive functions. Further, it is shown that if a and b are r.e. degrees with b ≤ a, there is a 1-1 recursive function $f: \mathbb{Q} \rightarrow \omega$ such that f(Q) ∈ a, (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  21.  20
    Upward Closure of Bi-Immune Degrees.Carl G. Jockusch - 1972 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 18 (16-18):285-287.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  22.  18
    Generalized Cohesiveness.Tamara Hummel & Carl G. Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
    We study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive (respectively, n-r-cohesive) if A is almost homogeneous for every computably enumerable (respectively, computable) 2-coloring of the n-element sets of natural numbers. (Thus the 1-cohesive and 1-r-cohesive sets coincide with the cohesive and r-cohesive sets, respectively.) We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  23.  10
    An Application of Σ40 Determinacy to the Degrees of Unsolvability.Carl G. Jockusch - 1973 - Journal of Symbolic Logic 38 (2):293-294.
  24.  34
    Boolean Algebras, Stone Spaces, and the Iterated Turing Jump.Carl G. Jockusch & Robert I. Soare - 1994 - Journal of Symbolic Logic 59 (4):1121 - 1138.
    We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, A is a countable structure with finite signature, and d is a degree, we say that A has αth-jump degree d if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of A with universe ω in (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  25.  32
    Encodability of Kleene's O.Carl G. Jockusch & Robert I. Soare - 1973 - Journal of Symbolic Logic 38 (3):437 - 440.
  26.  38
    Chains and Antichains in Partial Orderings.Valentina S. Harizanov, Carl G. Jockusch & Julia F. Knight - 2009 - Archive for Mathematical Logic 48 (1):39-53.
    We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  27.  4
    Upward Closure of Bi‐Immune Degrees.Carl G. Jockusch - 1972 - Mathematical Logic Quarterly 18 (16‐18):285-287.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  28.  27
    Weakly Semirecursive Sets.Carl G. Jockusch & James C. Owings - 1990 - Journal of Symbolic Logic 55 (2):637-644.
    We introduce the notion of "semi-r.e." for subsets of ω, a generalization of "semirecursive" and of "r.e.", and the notion of "weakly semirecursive", a generalization of "semi-r.e.". We show that A is weakly semirecursive iff, for any n numbers x 1 ,...,x n , knowing how many of these numbers belong to A is equivalent to knowing which of these numbers belong to A. It is shown that there exist weakly semirecursive sets that are neither semi-r.e. nor co-semi-r.e. On the (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  29. The Degrees of Hyperhyperimmune Sets.Carl G. Jockusch - 1969 - Journal of Symbolic Logic 34 (3):489-493.
  30.  24
    $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations.John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey - 2007 - Journal of Symbolic Logic 72 (3):1003 - 1018.
    We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  31.  8
    Post's Problem and His Hypersimple Set.Carl G. Jockusch & Robert I. Soare - 1973 - Journal of Symbolic Logic 38 (3):446 - 452.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  32.  14
    On Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Carl Jockusch & Joseph S. Miller - 2006 - Annals of Pure and Applied Logic 138 (1):52-76.
    The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  33.  33
    2001 Annual Meeting of the Association for Symbolic Logic.Joan Feigenbaum, Haim Gaifman, Jean-Yves Girard, C. Ward Henson, Denis Hirschfeldt, Carl G. Jockusch Jr, Saul Kripke, Salma Kuhlmann, John C. Mitchell & Ernest Schimmerling - 2001 - Bulletin of Symbolic Logic 7 (3):420-435.
  34.  17
    Completely Autoreducible Degrees.Carl G. Jockusch & Michael S. Paterson - 1976 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 22 (1):571-575.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  35.  4
    Completely Autoreducible Degrees.Carl G. Jockusch & Michael S. Paterson - 1976 - Mathematical Logic Quarterly 22 (1):571-575.
  36.  16
    Annual Meeting of the Association for Symbolic Logic Denver, 1983.Carl G. Jockusch, Richard Laver, Donald Monk, Jan Mycielski & Jon Pearce - 1984 - Journal of Symbolic Logic 49 (2):674 - 682.
  37.  31
    Generalized R-Cohesiveness and the Arithmetical Hierarchy: A Correction to "Generalized Cohesiveness".Carl G. Jockusch & Tamara J. Lakins - 2002 - Journal of Symbolic Logic 67 (3):1078 - 1082.
    For $X \subseteq \omega$ , let $\lbrack X \rbrack^n$ denote the class of all n-element subsets of X. An infinite set $A \subseteq \omega$ is called n-r-cohesive if for each computable function $f: \lbrack \omega \rbrack^n \rightarrow \lbrace 0, 1 \rbrace$ there is a finite set F such that f is constant on $\lbrack A - F \rbrack^n$ . We show that for each n ≥ 2 there is no $\prod_n^0$ set $A \subseteq \omega$ which is n-r-cohesive. For n = (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  38. In Memoriam: Joseph R. Shoenfield 1927–2000.Carl G. Jockusch - 2001 - Bulletin of Symbolic Logic 7 (3):393-396.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  39.  18
    Meeting of the Association for Symbolic Logic: St. Louis 1972.Carl G. Jockusch, Joseph S. Ullian & Robert B. Barrett - 1972 - Journal of Symbolic Logic 37 (4):775-782.
  40.  17
    Meeting of the Association for Symbolic Logic, Chicago, 1977.Carl G. Jockusch, Robert I. Soare, William Tait & Gaisi Takeuti - 1978 - Journal of Symbolic Logic 43 (3):614 - 619.
  41.  7
    Difference Sets and Computability Theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
    For a set A of non-negative integers, let D be the set of non-negative differences of elements of A. Clearly, if A is computable, then D is computably enumerable. We show that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference set of the complement of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  42.  14
    Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1.Rod Downey & Carl G. Jockusch - 1999 - Journal of Symbolic Logic 64 (1):45-52.
    We show that there is a computable Boolean algebra $\mathscr{B}$ and a computably enumerable ideal I of $\mathscr{B}$ such that the quotient algebra $\mathscr{B}/I$ is of Cantor-Bendixson rank 1 and is not isomorphic to any computable Boolean algebra. This extends a result of L. Feiner and is deduced from Feiner's result even though Feiner's construction yields a Boolean algebra of infinite Cantor-Bendixson rank.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  43.  18
    Annual Meeting of the Association for Symbolic Logic, New York City, December 1987.Nicholas Goodman, Harold T. Hodes, Carl G. Jockusch & Kenneth McAloon - 1988 - Journal of Symbolic Logic 53 (4):1287-1299.
  44. On Notions of Computability-Theoretic Reduction Between Π21 Principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.
    Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  45.  23
    Ramsey's Theorem for Computably Enumerable Colorings.Tamara J. Hummel & Carl G. Jockusch - 2001 - Journal of Symbolic Logic 66 (2):873-880.
    It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best possible in (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  46. A Letter From.Carl G. Jockusch Jr - 1996 - In Piergiorgio Odifreddi (ed.), Kreiseliana. About and Around Georg Kreisel. A K Peters.
    No categories
     
    Export citation  
     
    Bookmark  
  47.  29
    A Minimal Pair of Π0 1 Classes.Carl G. Jockusch Jr & Robert I. Soare - 1971 - Journal of Symbolic Logic 36 (1):66 - 78.
  48.  10
    A Minimal Pair of Π1 0 Classes.Carl G. Jockusch & Robert I. Soare - 1971 - Journal of Symbolic Logic 36 (1):66-78.
  49.  4
    Double Jumps of Minimal Degrees.Carl G. Jockusch, David B. Posner, Richard L. Epstein & Richard A. Shore - 1985 - Journal of Symbolic Logic 50 (2):550-552.
    Direct download  
     
    Export citation  
     
    Bookmark  
  50.  5
    Fine Degrees of Word Problems of Cancellation Semigroups.Carl G. Jockusch - 1980 - Mathematical Logic Quarterly 26 (1‐6):93-95.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 62