Switch to: References

Add citations

You must login to add citations.
  1. 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Definable properties of the computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.
    Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating ∄-definable properties (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • 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.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • 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.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Definable encodings in the computably enumerable sets.Peter A. Cholak & Leo A. Harrington - 2000 - Bulletin of Symbolic Logic 6 (2):185-196.
    The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.We will work in the structure of the computably enumerable sets. The language is just inclusion, (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations