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

HTML articles powered by AMS MathViewer

- by Rachel Epstein PDF
- Trans. Amer. Math. Soc.
**365**(2013), 1305-1345 Request permission

## 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

- Peter Cholak,
*Automorphisms of the lattice of recursively enumerable sets*, Mem. Amer. Math. Soc.**113**(1995), no. 541, viii+151. MR**1227497**, DOI 10.1090/memo/0541 - Peter A. Cholak and Leo A. Harrington,
*On the definability of the double jump in the computably enumerable sets*, J. Math. Log.**2**(2002), no. 2, 261–296. MR**1938925**, DOI 10.1142/S0219061302000151 - Leo Harrington and Robert I. Soare,
*Definability, automorphisms, and dynamic properties of computably enumerable sets*, Bull. Symbolic Logic**2**(1996), no. 2, 199–213. MR**1396855**, DOI 10.2307/421110 - Leo Harrington and Robert I. Soare,
*The $\Delta ^0_3$-automorphism method and noninvariant classes of degrees*, J. Amer. Math. Soc.**9**(1996), no. 3, 617–666. MR**1311821**, DOI 10.1090/S0894-0347-96-00181-6 - Leo Harrington and Robert I. Soare,
*Definable properties of the computably enumerable sets*, Ann. Pure Appl. Logic**94**(1998), no. 1-3, 97–125. Conference on Computability Theory (Oberwolfach, 1996). MR**1640265**, DOI 10.1016/S0168-0072(97)00069-9 - A. H. Lachlan,
*Degrees of recursively enumerable sets which have no maximal supersets*, J. Symbolic Logic**33**(1968), 431–443. MR**236016**, DOI 10.2307/2270328 - A. H. Lachlan,
*On some games which are relevant to the theory of recursively enumerable sets*, Ann. of Math. (2)**91**(1970), 291–310. MR**284333**, DOI 10.2307/1970579 - Donald A. Martin,
*Classes of recursively enumerable sets and degrees of unsolvability*, Z. Math. Logik Grundlagen Math.**12**(1966), 295–310. MR**224469**, DOI 10.1002/malq.19660120125 - André Nies, Richard A. Shore, and Theodore A. Slaman,
*Definability in the recursively enumerable degrees*, Bull. Symbolic Logic**2**(1996), no. 4, 392–404. MR**1460314**, DOI 10.2307/421171 - Emil L. Post,
*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284–316. MR**10514**, DOI 10.1090/S0002-9904-1944-08111-1 - J. R. Shoenfield,
*Degrees of classes of RE sets*, J. Symbolic Logic**41**(1976), no. 3, 695–696. MR**485293**, DOI 10.2307/2272046 - Gerald E. Sacks,
*Recursive enumerability and the jump operator*, Trans. Amer. Math. Soc.**108**(1963), 223–239. MR**155747**, DOI 10.1090/S0002-9947-1963-0155747-3 - Robert I. Soare,
*Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets*, Ann. of Math. (2)**100**(1974), 80–120. MR**360235**, DOI 10.2307/1970842 - Robert I. Soare,
*Automorphisms of the lattice of recursively enumerable sets. II. Low sets*, Ann. Math. Logic**22**(1982), no. 1, 69–108. MR**661478**, DOI 10.1016/0003-4843(82)90016-X - Robert I. Soare,
*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921**, DOI 10.1007/978-3-662-02460-7

## Additional Information

**Rachel Epstein**- Affiliation: Department of Mathematics, Faculty of Arts and Sciences, Harvard University, 1 Oxford Street, Cambridge, Massachusetts 02138
- Email: repstein@math.harvard.edu
- 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.
- © Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**365**(2013), 1305-1345 - MSC (2010): Primary 03D25
- DOI: https://doi.org/10.1090/S0002-9947-2012-05600-5
- MathSciNet review: 3003266