Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

On the orbits of computably enumerable sets


Authors: Peter A. Cholak, Rodney Downey and Leo A. Harrington
Journal: J. Amer. Math. Soc. 21 (2008), 1105-1135
MSC (2000): Primary 03D25
Published electronically: April 17, 2008
MathSciNet review: 2425182
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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


References [Enhancements On Off] (What's this?)


Similar Articles

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

Rodney Downey
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: Rod.Downey@vuw.ac.nz

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/S0894-0347-08-00604-8
PII: S 0894-0347(08)00604-8
Received by editor(s): April 6, 2007
Published electronically: April 17, 2008
Additional Notes: The first author’s research was partially supported by NSF Grants DMS-96-34565, 99-88716, 02-45167
The second author’s research was partially supported by the Marsden Fund of New Zealand
Some of the work involved was done partially while the first and second authors were visiting the Institute for Mathematical Sciences, National University of Singapore in 2005. These visits were supported by the Institute.
The third author’s research was partially supported by DMS-96-22290 and DMS-99-71137
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.