On the orbits of computably enumerable sets
HTML articles powered by AMS MathViewer
- by Peter A. Cholak, Rodney Downey and Leo A. Harrington
- J. Amer. Math. Soc. 21 (2008), 1105-1135
- DOI: https://doi.org/10.1090/S0894-0347-08-00604-8
- Published electronically: April 17, 2008
- PDF | Request permission
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
- C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842 [Cholak(2006)]2006:c Peter Cholak. The Computably Enumerable Sets: the Past, the Present and the Future. Theory and Applications of Models of Computation, 2006, Beijing China, 2006.
- Peter A. Cholak and Leo A. Harrington, Extension theorems, orbits, and automorphisms of the computably enumerable sets, Trans. Amer. Math. Soc. 360 (2008), no. 4, 1759–1791. MR 2366962, DOI 10.1090/S0002-9947-07-04025-1
- Peter A. Cholak and Leo A. Harrington, On the definability of the double jump in the computably enumerable sets, J. Math. Log. 2 (2002), no. 2, 261–296. MR 1938925, DOI 10.1142/S0219061302000151
- Peter A. Cholak and Leo A. Harrington, Isomorphisms of splits of computably enumerable sets, J. Symbolic Logic 68 (2003), no. 3, 1044–1064. MR 2000492, DOI 10.2178/jsl/1058448453
- Peter Cholak, Rod Downey, and Eberhard Herrmann, Some orbits for $\scr E$, Ann. Pure Appl. Logic 107 (2001), no. 1-3, 193–226. MR 1807845, DOI 10.1016/S0168-0072(00)00060-9
- R. G. Downey and Michael Stob, Automorphisms of the lattice of recursively enumerable sets: orbits, Adv. Math. 92 (1992), no. 2, 237–265. MR 1155466, DOI 10.1016/0001-8708(92)90065-S
- Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight, and Richard A. Shore, $\Pi ^1_1$ relations and paths through $\scr O$, J. Symbolic Logic 69 (2004), no. 2, 585–611. MR 2058190, DOI 10.2178/jsl/1082418544
- Leo Harrington and Robert I. Soare, Codable sets and orbits of computably enumerable sets, J. Symbolic Logic 63 (1998), no. 1, 1–28. MR 1610758, DOI 10.2307/2586583
- Leo Harrington and Robert I. Soare, Post’s program and incomplete recursively enumerable sets, Proc. Nat. Acad. Sci. U.S.A. 88 (1991), no. 22, 10242–10246. MR 1133585, DOI 10.1073/pnas.88.22.10242
- Leo Harrington and Robert I. Soare, The $\Delta ^0_3$-automorphism method and noninvariant classes of degrees, J. Amer. Math. Soc. 9 (1996), no. 3, 617–666. MR 1311821, DOI 10.1090/S0894-0347-96-00181-6
- 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 (2002), no. 1, 51–64 (2003). MR 2033315, DOI 10.1305/ndjfl/1071505769
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
- Wolfgang Maass, On the orbits of hyperhypersimple sets, J. Symbolic Logic 49 (1984), no. 1, 51–62. MR 736602, DOI 10.2307/2274090
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109 [Slaman and Woodin(1989)]Slaman.Woodin:conjecture Theodore A. Slaman and W. Hugh Woodin. Slaman-Woodin conjecture. Personal communication, 1989.
- Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2) 100 (1974), 80–120. MR 360235, DOI 10.2307/1970842
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7 [White(2000)]walkerwhite:00 Walker M. White. Characterizations for Computable Structures. PhD thesis, Cornell University, Ithaca, NY, USA, 2000.
Bibliographic Information
- Peter A. Cholak
- Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
- MR Author ID: 290865
- ORCID: 0000-0002-6547-5408
- 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
- MR Author ID: 59535
- 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
- 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 - © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: J. Amer. Math. Soc. 21 (2008), 1105-1135
- MSC (2000): Primary 03D25
- DOI: https://doi.org/10.1090/S0894-0347-08-00604-8
- MathSciNet review: 2425182