On the orbits of computably enumerable sets

Cholak, Peter ¹   ; Downey, Rodney ²   ; Harrington, Leo ³

¹ Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
² School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
³ Department of Mathematics, University of California, Berkeley, California 94720-3840

Journal of the American Mathematical Society, Tome 21 (2008) no. 4, pp. 1105-1135

Résumé

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

Détail

DOI : 10.1090/S0894-0347-08-00604-8

Bibliographie

[1] Ash, C. J., Knight, J. Computable structures and the hyperarithmetical hierarchy 2000

[2] Cholak, Peter A., Harrington, Leo A. Extension theorems, orbits, and automorphisms of the computably enumerable sets Trans. Amer. Math. Soc. 2008 1759 1791

[3] Cholak, Peter A., Harrington, Leo A. On the definability of the double jump in the computably enumerable sets J. Math. Log. 2002 261 296

[4] Cholak, Peter A., Harrington, Leo A. Isomorphisms of splits of computably enumerable sets J. Symbolic Logic 2003 1044 1064

[5] Cholak, Peter, Downey, Rod, Herrmann, Eberhard Some orbits for ℰ Ann. Pure Appl. Logic 2001 193 226

[6] Downey, R. G., Stob, Michael Automorphisms of the lattice of recursively enumerable sets: orbits Adv. Math. 1992 237 265

[7] Goncharov, Sergey S., Harizanov, Valentina S., Knight, Julia F., Shore, Richard A. Π¹₁ relations and paths through 𝒪 J. Symbolic Logic 2004 585 611

[8] Harrington, Leo, Soare, Robert I. Codable sets and orbits of computably enumerable sets J. Symbolic Logic 1998 1 28

[9] Harrington, Leo, Soare, Robert I. Post’s program and incomplete recursively enumerable sets Proc. Nat. Acad. Sci. U.S.A. 1991 10242 10246

[10] Harrington, Leo, Soare, Robert I. The Δ⁰₃-automorphism method and noninvariant classes of degrees J. Amer. Math. Soc. 1996 617 666

[11] Hirschfeldt, Denis R., White, Walker M. Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures Notre Dame J. Formal Logic 2002

[12] Lachlan, A. H. On the lattice of recursively enumerable sets Trans. Amer. Math. Soc. 1968 1 37

[13] Maass, Wolfgang On the orbits of hyperhypersimple sets J. Symbolic Logic 1984 51 62

[14] Rogers, Hartley, Jr. Theory of recursive functions and effective computability 1967

[15] Sacks, Gerald E. Higher recursion theory 1990

[16] Soare, Robert I. Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets Ann. of Math. (2) 1974 80 120

[17] Soare, Robert I. Recursively enumerable sets and degrees 1987