Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The nonlow computably enumerable degrees are not invariant in $ \mathcal{E}$

Author: Rachel Epstein
Journal: Trans. Amer. Math. Soc. 365 (2013), 1305-1345
MSC (2010): Primary 03D25
Published electronically: July 18, 2012
MathSciNet review: 3003266
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the structure of the computably enumerable (c.e.) sets, which form a lattice $ \mathcal {E}$ under set inclusion. The upward closed jump classes $ \overline {\mathbf {L}}_n$ and $ \mathbf {H}_n$ have all been shown to be definable by a lattice-theoretic formula, except for $ \overline {\mathbf {L}}_{1}$, the nonlow degrees. We say a class of c.e. degrees is invariant if it is the set of degrees of a class of c.e. sets that is invariant under automorphisms of $ \mathcal E$. All definable classes of degrees are invariant. We show that $ \overline {\mathbf {L}}_{1}$ is not invariant, thus proving a 1996 conjecture of Harrington and Soare that the nonlow degrees are not definable, and completing the problem of determining the definability of each jump class. We prove this by constructing a nonlow c.e. set $ D$ such that for all c.e. $ A\leq _{\rm T} D$, there is a low set $ B$ such that $ A$ can be taken by an automorphism of $ \mathcal {E}$ to $ B$.

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

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D25

Retrieve articles in all journals with MSC (2010): 03D25

Additional Information

Rachel Epstein
Affiliation: Department of Mathematics, Faculty of Arts and Sciences, Harvard University, 1 Oxford Street, Cambridge, Massachusetts 02138

Keywords: Computably enumerable, recursively enumerable, definability, automorphisms, invariance
Received by editor(s): January 28, 2011
Received by editor(s) in revised form: April 8, 2011
Published electronically: July 18, 2012
Additional Notes: The author would like to thank Bob Soare for many helpful comments and conversations.
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.