|
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, . Using this extension theorem and other work we then show if and are automorphic via , then they are automorphic via where and is . We give an algebraic description of when an arbitrary set is in the orbit of a computably enumerable set . We construct the first example of a definable orbit which is not a orbit. We conclude with some results which restrict the ways one can increase the complexity of orbits. For example, we show that if is simple and is in the same orbit as , then they are in the same -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 . 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/ 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/ 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/ cholak. MR 1781624 (2001k:03085) - 9.
- Peter A. Cholak and André Nies.
Atomless -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 -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 -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 -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
|