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 _\textrm {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.