Available in electronic format
Available in print format
Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Extension theorems, orbits, and automorphisms of the computably enumerable sets

Author(s): Peter A. Cholak; Leo A. Harrington
Journal: Trans. Amer. Math. Soc. 360 (2008), 1759-1791.
MSC (2000): Primary 03D25
Posted: October 29, 2007
Retrieve article in: PDF DVI PostScript

Abstract | References | Similar articles | Additional information

Abstract: We prove an algebraic extension theorem for the computably enumerable sets, $ \mathcal{E}$. Using this extension theorem and other work we then show if $ A$ and $ \widehat{A}$ are automorphic via $ \Psi$, then they are automorphic via $ \Lambda$ where $ \Lambda \restriction \mathcal{L}^*(A) = \Psi$ and $ \Lambda \restriction \mathcal{E}^*(A)$ is $ \Delta^0_3$. We give an algebraic description of when an arbitrary set $ \widehat{A}$ is in the orbit of a computably enumerable set $ A$. We construct the first example of a definable orbit which is not a $ \Delta^0_3$ orbit. We conclude with some results which restrict the ways one can increase the complexity of orbits. For example, we show that if $ A$ is simple and $ \widehat{A}$ is in the same orbit as $ A$, then they are in the same $ \Delta^0_6$-orbit and, furthermore, we provide a classification of when two simple sets are in the same orbit.


References:

1.
P. Cholak.
Boolean algebras and orbits of the lattice of r. e. sets modulo the finite sets.
J. Symbolic Logic, 55:744-760, 1990. MR 1056386 (91j:03055)

2.
P. Cholak.
The translation theorem.
Arch. Math. Logic, 33:87-108, 1994. MR 1271429 (95d:03074)

3.
Peter Cholak.
Automorphisms of the lattice of recursively enumerable sets.
Mem. Amer. Math. Soc., 113(541):viii+151, 1995.
ISSN 0065-9266. MR 1227497 (95f:03064)

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

5.
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.
http://www.nd.edu/$ ^\sim$cholak/papers/doublejump.pdf. MR 1938925 (2003h:03063)

6.
Peter Cholak and Leo A. Harrington.
Isomorphisms of splits of computably enumerable sets.
J. Symbolic Logic, 68(3):1044-1064, 2003.
ISSN 0022-4812.
http://www.nd.edu/$ ^\sim$cholak/papers/splits.pdf. MR 2000492 (2004f:03077)

7.
Peter A. Cholak.
The global structure of computably enumerable sets.
In Computability theory and its applications (Boulder, CO, 1999), volume 257 of Contemp. Math., pages 61-72, Providence, RI, 2000. Amer. Math. Soc. MR 1770734 (2001d:03099)

8.
Peter A. Cholak and Leo A. Harrington.
Definable encodings in the computably enumerable sets.
Bull. Symbolic Logic, 6(2):185-196, 2000.
A copy can be found at http://www.nd.edu/$ ^\sim$cholak. MR 1781624 (2001k:03085)

9.
Peter A. Cholak and André Nies.
Atomless $ r$-maximal sets.
Israel J. Math., 113:305-322, 1999.
ISSN 0021-2172. MR 1729452 (2001a:03087)

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

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.
Eberhard Herrmann and Martin Kummer.
Diagonals and $ \mathcal{{D}}$-maximal sets.
J. Symbolic Logic, 59(1):60-72, 1994. MR 1264963 (95f:03066)

13.
Martin Kummer.
Diagonal and semihyperhypersimple sets.
J. Symbolic Logic, 56:1068-1074, 1991. MR 1129168 (93b:03071)

14.
Steffen Lempp, André Nies, and D. Reed Solomon.
On the filter of computably enumerable supersets of an $ r$-maximal set.
Arch. Math. Logic, 40(6):415-423, 2001.
ISSN 0933-5846. MR 1854893 (2002h:03093)

15.
W. Maass.
On the orbit of hyperhypersimple sets.
J. Symbolic Logic, 49:51-62, 1984. MR 736602 (85k:03025)

16.
Robert I. Soare.
The new extension theorem.
To appear.

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

18.
Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic, Omega Series. Springer-Verlag, Heidelberg, 1987. MR 882921 (88m:03003)

19.
Robert I. Soare.
Extensions, automorphisms, and definability.
In Computability theory and its applications (Boulder, CO, 1999, volume 257 of Contemp. Math., pages 279-307. Amer. Math. Soc., 2000. MR 1770749 (2001e:03075)

20.
Rebecca Weber.
A definable relation between c.e. sets and ideals.
Ph.D. thesis, University of Notre Dame, 2004.


Similar Articles:

Retrieve articles in Transactions 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

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

DOI: 10.1090/S0002-9947-07-04025-1
PII: S 0002-9947(07)04025-1
Received by editor(s): September 7, 2004
Received by editor(s) in revised form: August 31, 2005
Posted: October 29, 2007
Additional Notes: This research was partially supported by NSF Grants DMS-96-34565, 99-88716, 02-45167 (first author), DMS-96-22290 and DMS-99-71137 (second author). We would like to thank Bob Soare and Mike Stob for their interest and helpful comments.
Copyright of article: Copyright 2007, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google