26 found
Sort by:
Disambiguations:
Peter Cholak [18]Peter A. Cholak [9]
  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 Cholak, David Galvin & Reed Solomon (2012). Reverse Mathematics and Infinite Traceable Graphs. Mathematical Logic Quarterly 58 (1‐2):18-28.
    No categories
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  4. Peter Cholak, Jr} {Jockusch & Theodore A. Slaman (2009). Corrigendum To: “On the Strength of Ramsey's Theorem for Pairs”. Journal of Symbolic Logic 74 (4):1438-1439.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. 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  
  6. Peter Cholak (2007). Introduction to the Special Issue on Vaught's Conjecture. Notre Dame Journal of Formal Logic 48 (1):1-2.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Peter Cholak, Noam Greenberg & Joseph S. Miller (2006). Uniform Almost Everywhere Domination. Journal of Symbolic Logic 71 (3):1057 - 1072.
    We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Peter Cholak, Richard A. Shore & Reed Solomon (2006). A Computably Stable Structure with No Scott Family of Finitary Formulas. Archive for Mathematical Logic 45 (5):519-538.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  9. Peter Cholak, Alberto Marcone & Reed Solomon (2004). Reverse Mathematics and the Equivalence of Definitions for Well and Better Quasi-Orders. Journal of Symbolic Logic 69 (3):683-712.
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  10. 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  
  11. 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  
  12. Peter Cholak, Rod Downey & Stephen Walk (2002). Maximal Contiguous Degrees. Journal of Symbolic Logic 67 (1):409-437.
    A computably enumerable (c.e.) degree is a maximal contiguous degree if it is contiguous and no c.e. degree strictly above it is contiguous. We show that there are infinitely many maximal contiguous degrees. Since the contiguous degrees are definable, the class of maximal contiguous degrees provides the first example of a definable infinite anti-chain in the c.e. degrees. In addition, we show that the class of maximal contiguous degrees forms an automorphism base for the c.e. degrees and therefore for the (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  13. 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  
  14. Peter Cholak, Rod Downey & Eberhard Herrmann (2001). Some Orbits For. Annals of Pure and Applied Logic 107 (1-3):193-226.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Peter Cholak, Marcia Groszek & Theodore Slaman (2001). An Almost Deep Degree. Journal of Symbolic Logic 66 (2):881-901.
    We show there is a non-recursive r.e. set A such that if W is any low r.e. set, then the join W $\oplus$ A is also low. That is, A is "almost deep". This answers a question of Jockusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.).
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  16. 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  
  17. Peter Cholak (1999). Review: Stephen G. Simpson, Subsystems of Second Order Arithmetic. [REVIEW] Journal of Symbolic Logic 64 (3):1356-1357.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  18. Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore (1999). Computably Categorical Structures and Expansions by Constants. Journal of Symbolic Logic 64 (1):13-37.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  19. Klaus Ambos-Spies, Marat Arslanov, Douglas Cenzer, Peter Cholak, Chi Tat Chong, Decheng Ding, Rod Downey, Peter A. Fejer, Sergei S. Goncharov & Edward R. Griffor (1998). Participants and Titles of Lectures. Annals of Pure and Applied Logic 94:3-6.
    No categories
     
    My bibliography  
     
    Export citation  
  20. Peter Cholak (1998). The Dense Simple Sets Are Orbit Complete with Respect to the Simple Sets. Annals of Pure and Applied Logic 94 (1-3):37-44.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  21. Peter Cholak (1995). Automorphisms of the Lattice of Recursively Enumerable Sets. American Mathematical Society.
    Chapter 1: Introduction. S = <{We}c<w; C,U,n,0,w> is the substructure formed by restricting the lattice <^P(w); C , U, n,0,w> to the re subsets We of the ...
    Direct download  
     
    My bibliography  
     
    Export citation  
  22. Peter Cholak (1994). The Translation Theorem. Archive for Mathematical Logic 33 (2):87-108.
    We state and prove the Translation Theorem. Then we apply the Translation Theorem to Soare's Extension Theorem, weakening slightly the hypothesis to yield a theorem we call the Modified Extension Theorem. We use this theorem to reprove several of the known results about orbits in the lattice of recursively enumerable sets. It is hoped that these proofs are easier to understand than the old proofs.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  23. 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  
  24. Peter Cholak & Rod Downey (1993). Lattice Nonembeddings and Intervals of the Recursively Enumerable Degrees. Annals of Pure and Applied Logic 61 (3):195-221.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  25. Peter Cholak & Rod Downey (1993). On the Cantor-Bendixon Rank of Recursively Enumerable Sets. Journal of Symbolic Logic 58 (2):629-640.
    The main result of this paper is to show that for every recursive ordinal α ≠ 0 and for every nonrecursive r.e. degree d there is a r.e. set of rank α and degree d.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  26. Peter Cholak (1990). Boolean Algebras and Orbits of the Lattice of R.E. Sets Modulo the Finite Sets. Journal of Symbolic Logic 55 (2):744-760.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation