Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

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


Authors: Peter A. Cholak and Leo A. Harrington
Journal: Trans. Amer. Math. Soc. 360 (2008), 1759-1791
MSC (2000): Primary 03D25
Published electronically: October 29, 2007
MathSciNet review: 2366962
Full-text PDF Free Access

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 [Enhancements On Off] (What's this?)


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: http://dx.doi.org/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
Published electronically: 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.
Article copyright: © Copyright 2007 American Mathematical Society