The nonlow computably enumerable degrees are not invariant in ℰ

Epstein, Rachel

doi:10.1090/S0002-9947-2012-05600-5

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