52 found
Order:
Disambiguations
Carl G. Jockusch [49]Carl Jockusch [11]Carl G. Jockusch Jr [4]
  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   56 citations  
  2.  60
    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   46 citations  
  3.  43
    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  
     
    Export citation  
     
    Bookmark   27 citations  
  4.  73
    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.
  5.  25
    A degree-theoretic definition of the ramified analytical hierarchy.Carl G. Jockusch & Stephen G. Simpson - 1976 - Annals of Mathematical Logic 10 (1):1-32.
  6.  41
    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   23 citations  
  7.  15
    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   9 citations  
  8.  44
    (1 other version)Double Jumps of Minimal Degrees.Carl G. Jockusch & David B. Posner - 1978 - Journal of Symbolic Logic 43 (4):715 - 724.
  9.  62
    Ramsey's Theorem and Cone Avoidance.Damir D. Dzhafarov & Carl G. Jockusch - 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 of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  10.  35
    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   13 citations  
  11.  15
    (1 other version)The degrees of bi‐immune sets.Carl G. Jockusch - 1969 - Mathematical Logic Quarterly 15 (7‐12):135-140.
  12.  54
    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 (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  13. Uniformly introreducible sets.Carl G. Jockusch - 1968 - Journal of Symbolic Logic 33 (4):521-536.
  14.  38
    Correction to “a cohesive set which is not high”.Carl Jockusch & Frank Stephan - 1997 - Mathematical Logic Quarterly 43 (4):569-569.
  15.  24
    Diagonally non-computable functions and bi-immunity.Carl G. Jockusch & Andrew E. M. Lewis - 2013 - Journal of Symbolic Logic 78 (3):977-988.
  16. (1 other version)[Omnibus Review].Carl Jockusch - 1990 - Journal of Symbolic Logic 55 (1):358-360.
  17.  25
    Asymptotic density and the Ershov hierarchy.Rod Downey, Carl Jockusch, Timothy H. McNicholl & Paul Schupp - 2015 - Mathematical Logic Quarterly 61 (3):189-195.
    We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for, a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any.
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  18.  54
    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   6 citations  
  19.  30
    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  
  20. Stability and Posets.Carl G. Jockusch, 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  
  21.  41
    Generalized cohesiveness.Tamara Hummel & Carl 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  
  22.  36
    Π10 classes and Boolean combinations of recursively enumerable sets.Carl G. Jockusch - 1974 - Journal of Symbolic Logic 39 (1):95-96.
  23.  58
    Encodability of Kleene's O.Carl G. Jockusch & Robert I. Soare - 1973 - Journal of Symbolic Logic 38 (3):437 - 440.
  24.  14
    (1 other version)Upward Closure of bi‐Immune Degrees.Carl G. Jockusch - 1972 - Mathematical Logic Quarterly 18 (16‐18):285-287.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   3 citations  
  25. 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  
  26. The degrees of hyperhyperimmune sets.Carl G. Jockusch - 1969 - Journal of Symbolic Logic 34 (3):489-493.
  27.  66
    $\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 (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  28.  34
    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   2 citations  
  29.  29
    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  
  30.  50
    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  
  31.  24
    An application of Σ40 determinacy to the degrees of unsolvability.Carl G. Jockusch - 1973 - Journal of Symbolic Logic 38 (2):293-294.
  32.  68
    A minimal pair of Π1 0 classes.Carl G. Jockusch & Robert I. Soare - 1971 - Journal of Symbolic Logic 36 (1):66-78.
  33.  14
    (1 other version)Completely Autoreducible Degrees.Carl G. Jockusch & Michael S. Paterson - 1976 - Mathematical Logic Quarterly 22 (1):571-575.
  34. In Memoriam: Joseph R. Shoenfield 1927–2000.Carl G. Jockusch - 2001 - Bulletin of Symbolic Logic 7 (3):393-396.
  35.  17
    Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics.Denis R. Hirschfeldt, Carl G. Jockusch & Paul E. Schupp - 2023 - Journal of Mathematical Logic 24 (2).
    For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  36.  33
    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.  54
    Generalized R-Cohesiveness and the Arithmetical Hierarchy: A Correction to "Generalized Cohesiveness".Carl Jockusch & Tamara 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.  41
    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.
  39.  45
    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.
  40.  22
    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 (4 more)  
     
    Export citation  
     
    Bookmark  
  41.  51
    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.
  42.  63
    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 (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  43.  51
    Ramsey's theorem for computably enumerable colorings.Tamara Hummel & Carl 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  
  44. 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  
  45.  50
    Fine Degrees of Word Problems of Cancellation Semigroups.Carl G. Jockusch - 1980 - Mathematical Logic Quarterly 26 (1-6):93-95.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  46. Free sets and reverse mathematics.Carl G. Jockusch Jr - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001. Association for Symbolic Logic. pp. 104.
     
    Export citation  
     
    Bookmark  
  47.  8
    REVIEWS-Defining the Turing jump.R. Shore, T. Slaman & Carl G. Jockusch Jr - 2001 - Bulletin of Symbolic Logic 7 (1):73-74.
  48.  21
    Corrigendum to: "On the Strength of Ramsey's Theorem for Pairs".Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (4):1438 - 1439.
  49.  26
    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 (7 more)  
     
    Export citation  
     
    Bookmark  
  50.  11
    (1 other version)Lachlan A. H.. Some notions of reducibility and productiveness. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 11 , pp. 17–44. [REVIEW]Carl G. Jockusch - 1970 - Journal of Symbolic Logic 35 (3):478-478.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
1 — 50 / 52