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

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?)

  • 1. P. A. Cholak, Automorphisms of the Lattice of Recursively Enumerable Sets, Mem. Amer. Math. Soc. 113 (1995). MR 1227497 (95f:03064)
  • 2. P. A. Cholak and L. A. Harrington, On the Definability of the Double Jump in the Computably Enumerable Sets, J. Math. Log. 2 (2002), 261-296. MR 1938925 (2003h:03063)
  • 3. L. Harrington and R. I. Soare, Definability, automorphisms, and dynamic properties of computably enumerable sets, Bull. Symbolic Logic, 2 (1996), 199-213. MR 1396855 (97d:03057)
  • 4. L. Harrington and R. I. Soare, The $ \Delta ^0_3$ automorphism method and noninvariant classes of degrees, J. Amer. Math. Soc., 9 (1996), 617-666. MR 1311821 (96j:03060)
  • 5. L. Harrington and R. I. Soare, Definable properties of the computably enumerable sets, Proceedings of the Oberwolfach Conference on Computability Theory, Ann. Pure Appl. Logic, 94 (1998), 97-125. MR 1640265 (99f:03055)
  • 6. A. H. Lachlan, Degrees of recursively enumerable sets which have no maximal superset, J. Symbolic Logic 33 (1968), 431-443. MR 0236016 (38:4314)
  • 7. 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 0284333 (44:1562)
  • 8. D. A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math., 12 (1966), 295-310. MR 0224469 (37:68)
  • 9. A. Nies, R. A. Shore, and T. A. Slaman. Definability in the recursively enumerable degrees. Bull. Symbolic Logic 2 (1996), 392-404. MR 1460314 (98g:03105)
  • 10. S. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc., 50 (1944), 284-316. Reprinted in Davis (1965), 304-337. MR 0010514 (6:29f)
  • 11. J. R. Shoenfield, Degrees of classes of r.e. sets, J. Symbolic Logic 41 (1976), 695-696. MR 0485293 (58:5140)
  • 12. G. E. Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223-239. MR 0155747 (27:5681)
  • 13. R. I. Soare, Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets, Ann. of Math. (2) 100 (1974), 80-120. MR 0360235 (50:12685)
  • 14. R. I. Soare, Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets, Ann. Math. Logic 22 (1982), 69-107. MR 661478 (83k:03048)
  • 15. R. I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Heidelberg, 1987. MR 882921 (88m:03003)

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.

American Mathematical Society