Geodesic
On the orbits of computably enumerable sets
Cholak, Peter1 ; Downey, Rodney2 ; Harrington, Leo3
1 Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
2 School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
3 Department of Mathematics, University of California, Berkeley, California 94720-3840
Journal of the American Mathematical Society, Tome 21 (2008) no. 4, pp. 1105-1135

Voir la notice de l'article provenant de la source American Mathematical Society

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).
DOI : 10.1090/S0894-0347-08-00604-8

Cholak, Peter 1 ; Downey, Rodney 2 ; Harrington, Leo 3

1 Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556-5683
2 School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
3 Department of Mathematics, University of California, Berkeley, California 94720-3840 
@article{10_1090_S0894_0347_08_00604_8,
     author = {Cholak, Peter and Downey, Rodney and Harrington, Leo},
     title = {On the orbits of computably enumerable sets},
     journal = {Journal of the American Mathematical Society},
     pages = {1105--1135},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2008},
     doi = {10.1090/S0894-0347-08-00604-8},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-08-00604-8/}
}
TY  - JOUR
AU  - Cholak, Peter
AU  - Downey, Rodney
AU  - Harrington, Leo
TI  - On the orbits of computably enumerable sets
JO  - Journal of the American Mathematical Society
PY  - 2008
SP  - 1105
EP  - 1135
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-08-00604-8/
DO  - 10.1090/S0894-0347-08-00604-8
ID  - 10_1090_S0894_0347_08_00604_8
ER  - 
%0 Journal Article
%A Cholak, Peter
%A Downey, Rodney
%A Harrington, Leo
%T On the orbits of computably enumerable sets
%J Journal of the American Mathematical Society
%D 2008
%P 1105-1135
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-08-00604-8/
%R 10.1090/S0894-0347-08-00604-8
%F 10_1090_S0894_0347_08_00604_8
Cholak, Peter; Downey, Rodney; Harrington, Leo. On the orbits of computably enumerable sets. Journal of the American Mathematical Society, Tome 21 (2008) no. 4, pp. 1105-1135. doi: 10.1090/S0894-0347-08-00604-8

[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

Cité par Sources :