The nonlow computably enumerable degrees are not invariant in

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 under set inclusion. The upward closed jump classes and have all been shown to be definable by a lattice-theoretic formula, except for , 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 . All definable classes of degrees are invariant. We show that 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 such that for all c.e. , there is a low set such that can be taken by an automorphism of to .

**1.**Peter Cholak,*Automorphisms of the lattice of recursively enumerable sets*, Mem. Amer. Math. Soc.**113**(1995), no. 541, viii+151. MR**1227497**, 10.1090/memo/0541**2.**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**, 10.1142/S0219061302000151**3.**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**, 10.2307/421110**4.**Leo Harrington and Robert I. Soare,*The Δ⁰₃-automorphism method and noninvariant classes of degrees*, J. Amer. Math. Soc.**9**(1996), no. 3, 617–666. MR**1311821**, 10.1090/S0894-0347-96-00181-6**5.**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**, 10.1016/S0168-0072(97)00069-9**6.**A. H. Lachlan,*Degrees of recursively enumerable sets which have no maximal supersets.*, J. Symbolic Logic**33**(1968), 431–443. MR**0236016****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****8.**Donald A. Martin,*Classes of recursively enumerable sets and degrees of unsolvability*, Z. Math. Logik Grundlagen Math.**12**(1966), 295–310. MR**0224469****9.**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**, 10.2307/421171**10.**Emil L. Post,*Recursively enumerable sets of positive integers and their decision problems*, Bull. Amer. Math. Soc.**50**(1944), 284–316. MR**0010514**, 10.1090/S0002-9904-1944-08111-1**11.**J. R. Shoenfield,*Degrees of classes of RE sets*, J. Symbolic Logic**41**(1976), no. 3, 695–696. MR**0485293****12.**Gerald E. Sacks,*Recursive enumerability and the jump operator*, Trans. Amer. Math. Soc.**108**(1963), 223–239. MR**0155747**, 10.1090/S0002-9947-1963-0155747-3**13.**Robert I. Soare,*Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets*, Ann. of Math. (2)**100**(1974), 80–120. MR**0360235****14.**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**, 10.1016/0003-4843(82)90016-X**15.**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**

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

Email:
repstein@math.harvard.edu

DOI:
https://doi.org/10.1090/S0002-9947-2012-05600-5

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.