Journal of the American Mathematical Society

Author(s): Peter A. Cholak; Rodney Downey; Leo A. Harrington
Journal: J. Amer. Math. Soc. 21 (2008), 1105-1135.
MSC (2000): Primary 03D25
Posted: April 17, 2008
Retrieve article in: PDF DVI PostScript

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).

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.

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

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: 10.1090/S0894-0347-08-00604-8
PII: S 0894-0347(08)00604-8
Received by editor(s): April 6, 2007
Posted: 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 of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN: 1088-6834(e) ISSN: 0894-0347(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS