52 found
Order:
Disambiguations
Carl G. Jockusch [49]Carl G. Jockusch Jr [5]
  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   36 citations  
  2.  10
    Asymptotic Density and Computably Enumerable Sets.Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp - 2013 - Journal of Mathematical Logic 13 (2):1350005.
  3.  13
    Π10 Classes and Boolean Combinations of Recursively Enumerable Sets.Carl G. Jockusch - 1974 - Journal of Symbolic Logic 39 (1):95-96.
  4.  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  
  5.  13
    Richard A. Shore and Theodore A. Slaman. Defining the Turing Jump. Mathematical Research Letters, Vol. 6 , Pp. 711–722.Carl G. Jockusch - 2001 - Bulletin of Symbolic Logic 7 (1):73-75.
  6.  3
    Diagonally Non-Computable Functions and Bi-Immunity.Carl G. Jockusch & Andrew E. M. Lewis - 2013 - Journal of Symbolic Logic 78 (3):977-988.
  7.  7
    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.  26
    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.
  9.  28
    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   27 citations  
  10.  9
    An Application of Σ40 Determinacy to the Degrees of Unsolvability.Carl G. Jockusch - 1973 - Journal of Symbolic Logic 38 (2):293-294.
  11. 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  
  12. The Degrees of Hyperhyperimmune Sets.Carl G. Jockusch - 1969 - Journal of Symbolic Logic 34 (3):489-493.
  13.  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.
  14. Uniformly Introreducible Sets.Carl G. Jockusch - 1968 - Journal of Symbolic Logic 33 (4):521-536.
  15.  12
    Double Jumps of Minimal Degrees.Carl G. Jockusch & David B. Posner - 1978 - Journal of Symbolic Logic 43 (4):715 - 724.
  16.  20
    The Degrees of Bi-Immune Sets.Carl G. Jockusch - 1969 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 15 (7-12):135-140.
  17.  4
    The Degrees of Bi‐Immune Sets.Carl G. Jockusch - 1969 - Mathematical Logic Quarterly 15 (7‐12):135-140.
  18. 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  
  19.  17
    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  
  20.  36
    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 (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  29
    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  
  22.  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  
  23.  31
    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.
  24.  8
    $\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  
  25.  23
    Encodability of Kleene's O.Carl G. Jockusch & Robert I. Soare - 1973 - Journal of Symbolic Logic 38 (3):437 - 440.
  26.  15
    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  
  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.  29
    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 (8 more)  
     
    Export citation  
     
    Bookmark  
  29.  16
    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  
  30.  7
    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  
  31.  15
    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.
  32.  17
    Fine Degrees of Word Problems of Cancellation Semigroups.Carl G. Jockusch - 1980 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 26 (1-6):93-95.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  33.  14
    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.
  34.  4
    Completely Autoreducible Degrees.Carl G. Jockusch & Michael S. Paterson - 1976 - Mathematical Logic Quarterly 22 (1):571-575.
  35.  16
    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.
  36.  16
    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  
  37.  24
    A Minimal Pair of Π0 1 Classes.Carl G. Jockusch Jr & Robert I. Soare - 1971 - Journal of Symbolic Logic 36 (1):66 - 78.
  38.  5
    A Minimal Pair of Π1 0 Classes.Carl G. Jockusch & Robert I. Soare - 1971 - Journal of Symbolic Logic 36 (1):66-78.
  39.  5
    Mathematical Research Letters.Carl G. Jockusch - 2001 - Bulletin of Symbolic Logic 7 (1):73-75.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  40.  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  
  41.  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  
  42.  12
    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.
  43.  3
    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  
  44.  3
    Lerman Manuel. Degrees of Unsolvability. Local and Global Theory. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, Heidelberg, New York, and Tokyo, 1983, Xiii + 307 Pp. [REVIEW]Carl G. Jockusch - 1985 - Journal of Symbolic Logic 50 (2):549-550.
  45.  2
    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)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  46.  3
    Review: A. H. Lachlan, Lower Bounds for Pairs of Recursively Enumerable Degrees. [REVIEW]Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (3):611-611.
  47.  2
    Review: A. H. Lachlan, Some Notions of Reducibility and Productiveness. [REVIEW]Carl G. Jockusch - 1970 - Journal of Symbolic Logic 35 (3):478-478.
  48. 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  
  49. 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  
  50. Free Sets and Reverse Mathematics.Carl G. Jockusch Jr - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001. pp. 104.
1 — 50 / 52