Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

On the orbits of computably enumerable sets


Authors: Peter A. Cholak, Rodney Downey and Leo A. Harrington
Journal: J. Amer. Math. Soc. 21 (2008), 1105-1135
MSC (2000): Primary 03D25
DOI: https://doi.org/10.1090/S0894-0347-08-00604-8
Published electronically: April 17, 2008
MathSciNet review: 2425182
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The goal of this paper is to show there is a single orbit of the c.e. sets with inclusion, $ \mathcal{E}$, 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 $ \mathcal{E}$ is $ \omega_1^{{CK}}+1$; not all orbits are elementarily definable; there is no arithmetic description of all orbits of $ \mathcal{E}$; for all finite $ \alpha \geq 9$, there is a properly $ \Delta^0_\alpha$ orbit (from the proof).


References [Enhancements On Off] (What's this?)

  • 1. C. J. Ash and J. Knight.
    Computable structures and the hyperarithmetical hierarchy, volume 144 of Studies in Logic and the Foundations of Mathematics.
    North-Holland Publishing Co., Amsterdam, 2000.
    ISBN 0-444-50072-3. MR 1767842 (2001k:03090)
  • 2. Peter Cholak.
    The Computably Enumerable Sets: the Past, the Present and the Future.
    Theory and Applications of Models of Computation, 2006, Beijing China, 2006.
  • 3. Peter Cholak and Leo A. Harrington.
    Extension theorems, orbits, and automorphisms of the computably enumerable sets.
    Trans. Amer. Math. Soc., 360(4):1759-1791, 2008. MR 2366962
  • 4. Peter Cholak and Leo A. Harrington.
    On the definability of the double jump in the computably enumerable sets.
    J. Math. Log., 2(2):261-296, 2002.
    ISSN 0219-0613. MR 1938925 (2003h:03063)
  • 5. Peter Cholak and Leo A. Harrington.
    Isomorphisms of splits of computably enumerable sets.
    J. Symbolic Logic, 68(3):1044-1064, 2003.
    ISSN 0022-4812. MR 2000492 (2004f:03077)
  • 6. Peter Cholak, Rod Downey, and Eberhard Herrmann.
    Some orbits for $ \mathcal{E}$.
    Ann. Pure Appl. Logic, 107(1-3):193-226, 2001.
    ISSN 0168-0072. MR 1807845 (2001k:03086)
  • 7. R. G. Downey and M. Stob.
    Automorphisms of the lattice of recursively enumerable sets: Orbits.
    Adv. in Math., 92:237-265, 1992. MR 1155466 (93g:03038)
  • 8. Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight, and Richard A. Shore.
    $ \Pi^1_1$ relations and paths through $ \mathcal{O}$.
    J. Symbolic Logic, 69(2):585-611, 2004.
    ISSN 0022-4812. MR 2058190 (2005d:03083)
  • 9. Leo Harrington and Robert I. Soare.
    Codable sets and orbits of computably enumerable sets.
    J. Symbolic Logic, 63(1):1-28, 1998.
    ISSN 0022-4812. MR 1610758 (99j:03031)
  • 10. Leo A. Harrington and Robert I. Soare.
    Post's program and incomplete recursively enumerable sets.
    Proc. Nat. Acad. Sci. U.S.A., 88:10242-10246, 1991. MR 1133585 (92k:03019)
  • 11. Leo A. Harrington and Robert I. Soare.
    The $ {\Delta}\sp 0\sb 3$-automorphism method and noninvariant classes of degrees.
    J. Amer. Math. Soc., 9(3):617-666, 1996.
    ISSN 0894-0347. MR 1311821 (96j:03060)
  • 12. Denis R. Hirschfeldt and Walker M. White.
    Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures.
    Notre Dame J. Formal Logic, 43(1):51-64 (2003), 2002.
    ISSN 0029-4527. MR 2033315 (2005d:03084)
  • 13. Alistair H. Lachlan.
    On the lattice of recursively enumerable sets.
    Trans. Amer. Math. Soc., 130:1-37, 1968. MR 0227009 (37:2594)
  • 14. W. Maass.
    On the orbit of hyperhypersimple sets.
    J. Symbolic Logic, 49:51-62, 1984. MR 736602 (85k:03025)
  • 15. H. Rogers, Jr.
    Theory of Recursive Functions and Effective Computability.
    McGraw-Hill, New York, 1967. MR 0224462 (37:61)
  • 16. Gerald Sacks.
    Higher Recursion Theory.
    Perspectives in Mathematical Logic. Springer-Verlag, Heidelberg, 1990. MR 1080970 (92a:03062)
  • 17. Theodore A. Slaman and W. Hugh Woodin.
    Slaman-Woodin conjecture.
    Personal communication, 1989.
  • 18. Robert I. Soare.
    Automorphisms of the lattice of recursively enumerable sets I: maximal sets.
    Ann. of Math. (2), 100:80-120, 1974. MR 0360235 (50:12685)
  • 19. Robert I. Soare.
    Recursively Enumerable Sets and Degrees.
    Perspectives in Mathematical Logic, Omega Series. Springer-Verlag, Heidelberg, 1987. MR 882921 (88m:03003)
  • 20. Walker M. White.
    Characterizations for Computable Structures.
    PhD thesis, Cornell University, Ithaca, NY, USA, 2000.

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 03D25

Retrieve articles in all journals with MSC (2000): 03D25


Additional Information

Peter A. Cholak
Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
Email: Peter.Cholak.1@nd.edu

Rodney Downey
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: Rod.Downey@vuw.ac.nz

Leo A. Harrington
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840
Email: leo@math.berkeley.edu

DOI: https://doi.org/10.1090/S0894-0347-08-00604-8
Received by editor(s): April 6, 2007
Published electronically: April 17, 2008
Additional Notes: The first author’s research was partially supported by NSF Grants DMS-96-34565, 99-88716, 02-45167
The second author’s research was partially supported by the Marsden Fund of New Zealand
Some of the work involved was done partially while the first and second authors were visiting the Institute for Mathematical Sciences, National University of Singapore in 2005. These visits were supported by the Institute.
The third author’s research was partially supported by DMS-96-22290 and DMS-99-71137
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society