28 found
Order:
Disambiguations
Peter Cholak [27]Peter A. Cholak [11]
  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  
     
    My bibliography   24 citations  
  2. A Computably Stable Structure with No Scott Family of Finitary Formulas.Peter Cholak, Richard A. Shore & Reed Solomon - 2006 - Archive for Mathematical Logic 45 (5):519-538.
  3.  11
    Automorphisms of the Lattice of Recursively Enumerable Sets.Peter Cholak - 1995 - 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  
     
    Export citation  
     
    My bibliography   6 citations  
  4.  13
    Reverse Mathematics and the Equivalence of Definitions for Well and Better Quasi-Orders.Peter Cholak, Alberto Marcone & Reed Solomon - 2004 - Journal of Symbolic Logic 69 (3):683-712.
  5.  10
    Computably Categorical Structures and Expansions by Constants.Peter Cholak, Sergey Goncharov, Bakhadyr Khoussainov & Richard A. Shore - 1999 - Journal of Symbolic Logic 64 (1):13-37.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  6.  15
    Uniform Almost Everywhere Domination.Peter Cholak, Noam Greenberg & Joseph S. Miller - 2006 - 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 (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  7.  17
    On the Definability of the Double Jump in the Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2002 - Journal of Mathematical Logic 2 (02):261-296.
  8.  42
    An Almost Deep Degree.Peter Cholak, Marcia Groszek & Theodore Slaman - 2001 - 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 (8 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  9.  3
    On Mathias Generic Sets.Peter A. Cholak, Damir D. Dzhafarov & Jeffry L. Hirst - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 129--138.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  10.  14
    Some Orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.
    In this article we establish the existence of a number of new orbits in the automorphism group of the computably enumerable sets. The degree theoretical aspects of these orbits also are examined.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  11.  26
    Definable Encodings in the Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2000 - Bulletin of Symbolic Logic 6 (2):185-196.
  12.  17
    The Complexity of Orbits of Computably Enumerable Sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - 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)  
     
    Export citation  
     
    My bibliography   1 citation  
  13.  13
    On the Cantor-Bendixon Rank of Recursively Enumerable Sets.Peter Cholak & Rod Downey - 1993 - 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 (7 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  14.  17
    Iterated Relative Recursive Enumerability.Peter A. Cholak & Peter G. Hinman - 1994 - 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  15.  17
    The Translation Theorem.Peter Cholak - 1994 - 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.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  16.  7
    Introduction to the Special Issue on Vaught's Conjecture.Peter Cholak - 2007 - Notre Dame Journal of Formal Logic 48 (1):1-2.
  17.  17
    The Dense Simple Sets Are Orbit Complete with Respect to the Simple Sets.Peter Cholak - 1998 - Annals of Pure and Applied Logic 94 (1-3):37-44.
    We prove conjectures of Herrmann and Stob by showing that the dense simple sets are orbit complete w.r.t. the simple sets.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  18.  20
    Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - 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 (8 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  19.  8
    Lattice Nonembeddings and Intervals of the Recursively Enumerable Degrees.Peter Cholak & Rod Downey - 1993 - Annals of Pure and Applied Logic 61 (3):195-221.
    Let b and c be r.e. Turing degrees such that b>c. We show that there is an r.e. degree a such that b>a>c and all lattices containing a critical triple, including the lattice M5, cannot be embedded into the interval [c, a].
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  20.  20
    Isomorphisms of Splits of Computably Enumerable Sets.Peter A. Cholak & Leo A. Harrington - 2003 - 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 (9 more)  
     
    Export citation  
     
    My bibliography  
  21.  15
    Boolean Algebras and Orbits of the Lattice of R.E. Sets Modulo the Finite Sets.Peter Cholak - 1990 - Journal of Symbolic Logic 55 (2):744-760.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  22.  7
    Participants and Titles of Lectures.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 - Annals of Pure and Applied Logic 94 (1):3-6.
    No categories
    Direct download  
     
    Export citation  
     
    My bibliography  
  23.  4
    Simpson Stephen G.. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin, Heidelberg, New York, Etc., 1999, Xiv + 445 Pp. [REVIEW]Peter Cholak - 1999 - Journal of Symbolic Logic 64 (3):1356-1357.
  24.  5
    Reverse Mathematics and Infinite Traceable Graphs.Peter Cholak, David Galvin & Reed Solomon - 2012 - Mathematical Logic Quarterly 58 (1-2):18-28.
    We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  25.  1
    ${\Cal D}$-Maximal Sets.Peter A. Cholak, Peter Gerdes & Karen Lange - 2015 - Journal of Symbolic Logic 80 (4):1182-1210.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  26.  1
    Corrigendum To: “On the Strength of Ramsey's Theorem for Pairs”.Peter Cholak, Jr} {Jockusch & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (4):1438-1439.
  27.  1
    Review: Stephen G. Simpson, Subsystems of Second Order Arithmetic. [REVIEW]Peter Cholak - 1999 - Journal of Symbolic Logic 64 (3):1356-1357.
  28. On N -Tardy Sets.Peter A. Cholak, Peter M. Gerdes & Karen Lange - 2012 - Annals of Pure and Applied Logic 163 (9):1252-1270.