8 found
Sort by:
  1. Peter A. Cholak, Damir D. Dzhafarov & Jeffry L. Hirst (2012). On Mathias Generic Sets. In S. Barry Cooper (ed.), How the World Computes. 129--138.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Peter A. Cholak, Peter M. Gerdes & Karen Lange (2012). On N-Tardy Sets. Annals of Pure and Applied Logic 163 (9):1252-1270.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Peter A. Cholak, Rodney Downey & Leo A. Harrington (2008). The Complexity of Orbits of Computably Enumerable Sets. Bulletin of Symbolic Logic 14 (1):69 - 87.
    The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  4. Peter A. Cholak & Leo A. Harrington (2003). Isomorphisms of Splits of Computably Enumerable Sets. Journal of Symbolic Logic 68 (3):1044-1064.
    We show that if A and $\widehat{A}$ are automorphic via Φ then the structures $S_{R}(A)$ and $S_{R}(\widehat{A})$ are $\Delta_{3}^{0}-isomorphic$ via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  5. Peter A. Cholak & Leo A. Harrington (2002). On the Definability of the Double Jump in the Computably Enumerable Sets. Journal of Mathematical Logic 2 (02):261-296.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman (2001). On the Strength of Ramsey's Theorem for Pairs. 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 (7 more)  
     
    My bibliography  
     
    Export citation  
  7. Peter A. Cholak & Leo A. Harrington (2000). Definable Encodings in the Computably Enumerable Sets. Bulletin of Symbolic Logic 6 (2):185-196.
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  8. Peter A. Cholak & Peter G. Hinman (1994). Iterated Relative Recursive Enumerability. Archive for Mathematical Logic 33 (5):321-346.
    A result of Soare and Stob asserts that for any non-recursive r.e. setC, there exists a r.e.[C] setA such thatA⊕C is not of r.e. degree. A setY is called [of]m-REA (m-REA[C] [degree] iff it is [Turing equivalent to] the result of applyingm-many iterated ‘hops’ to the empty set (toC), where a hop is any function of the formX→X ⊕W e X . The cited result is the special casem=0,n=1 of our Theorem. Form=0,1, and any (m+1)-REA setC, ifC is not ofm-REA (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation