The nonlow computably enumerable degrees are not invariant in
Author:
Rachel Epstein
Journal:
Trans. Amer. Math. Soc. 365 (2013), 13051345
MSC (2010):
Primary 03D25
Published electronically:
July 18, 2012
Fulltext 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 latticetheoretic 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 (95f:03064), http://dx.doi.org/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
(2003h:03063), http://dx.doi.org/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
(97d:03057), http://dx.doi.org/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
(96j:03060), http://dx.doi.org/10.1090/S0894034796001816
 5.
Leo
Harrington and Robert
I. Soare, Definable properties of the computably enumerable
sets, Ann. Pure Appl. Logic 94 (1998), no. 13,
97–125. Conference on Computability Theory (Oberwolfach, 1996). MR 1640265
(99f:03055), http://dx.doi.org/10.1016/S01680072(97)000699
 6.
A.
H. Lachlan, Degrees of recursively enumerable sets which have no
maximal supersets., 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.
Donald
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.
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 (98g:03105), http://dx.doi.org/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
(6,29f), http://dx.doi.org/10.1090/S000299041944081111
 11.
J.
R. Shoenfield, Degrees of classes of RE sets, J. Symbolic
Logic 41 (1976), no. 3, 695–696. MR 0485293
(58 #5140)
 12.
Gerald
E. Sacks, Recursive enumerability and the jump
operator, Trans. Amer. Math. Soc. 108 (1963), 223–239. MR 0155747
(27 #5681), http://dx.doi.org/10.1090/S00029947196301557473
 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 (50 #12685)
 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
(83k:03048), http://dx.doi.org/10.1016/00034843(82)90016X
 15.
Robert
I. Soare, Recursively enumerable sets and degrees,
Perspectives in Mathematical Logic, SpringerVerlag, Berlin, 1987. A study
of computable functions and computably generated sets. MR 882921
(88m:03003)
 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), 261296. 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), 199213. MR 1396855 (97d:03057)
 4.
 L. Harrington and R. I. Soare, The automorphism method and noninvariant classes of degrees, J. Amer. Math. Soc., 9 (1996), 617666. 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), 97125. MR 1640265 (99f:03055)
 6.
 A. H. Lachlan, Degrees of recursively enumerable sets which have no maximal superset, J. Symbolic Logic 33 (1968), 431443. 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), 291310. MR 0284333 (44:1562)
 8.
 D. A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math., 12 (1966), 295310. 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), 392404. MR 1460314 (98g:03105)
 10.
 S. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc., 50 (1944), 284316. Reprinted in Davis (1965), 304337. MR 0010514 (6:29f)
 11.
 J. R. Shoenfield, Degrees of classes of r.e. sets, J. Symbolic Logic 41 (1976), 695696. MR 0485293 (58:5140)
 12.
 G. E. Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223239. 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), 80120. 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), 69107. MR 661478 (83k:03048)
 15.
 R. I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, SpringerVerlag, 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
Email:
repstein@math.harvard.edu
DOI:
http://dx.doi.org/10.1090/S000299472012056005
PII:
S 00029947(2012)056005
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.
