Open problems on automorphisms and definability of the Turing degrees: cone isomorphism, the rigidity threshold, jump classes, and the definability of the computably enumerable and n-c.e. degrees

The 1990 survey 'Definability and global degree theory' by S. B. Cooper closed with six problems that jointly ask how much of the external apparatus of computability theory - the Turing jump hierarchy, enumeration of sets, oracles - is recoverable from the bare first-order order structure of the Turing degrees, and how symmetric that structure is. Concretely: (1) are two cones $\boldsymbol{D}(\geq\mathbf{a})$ and $\boldsymbol{D}(\geq\mathbf{b})$ with distinct bases ever isomorphic; (2) can the theorem that every automorphism of the degrees is the identity above $\mathbf{0}^{(3)}$ be improved to fixation above $\mathbf{0}'$; (3) do the local structures $\boldsymbol{D}(\leq\mathbf{0}')$ and the computably enumerable degrees $\boldsymbol{R}$ admit nontrivial automorphisms; (4) are the low-level jump classes $\mathrm{High}_1,\mathrm{High}_2,\mathrm{Low}_1,\mathrm{Low}_2$ first-order definable in $\boldsymbol{D}(\leq\mathbf{0}')$; (5) whether there exist computably enumerable degrees other than the endpoints $\mathbf{0}$ and $\mathbf{0}'$ that are definable in $\boldsymbol{D}(\leq\mathbf{0}')$ or in $\boldsymbol{R}$, and conversely whether some c.e. degrees are provably not definable; and (6) are the n-c.e. degrees definable in $\boldsymbol{D}(\leq\mathbf{0}')$, and the c.e. degrees below $\mathbf{a}$ definable in $\boldsymbol{D}(\leq\mathbf{a})$? The six problems themselves, now unified by the biinterpretability conjectures for the degree structures, remain open and central to computability theory.

Background

A set $A$ of natural numbers is Turing reducible to $B$ ($A\leq_TB$) if $A$ can be computed by an algorithm allowed to consult $B$ as an oracle. This preordering partitions the power set of $\mathbb{N}$ into Turing degrees - equivalence classes of sets of equal computational power - which form an upper semilattice $\boldsymbol{D}=\langle\mathcal{D},\leq,\vee\rangle$ under the induced order and join. The Turing jump $\mathbf{a}\mapsto\mathbf{a}'$ sends a degree to that of the halting problem relative to any set in it, yielding a canonical hierarchy $\mathbf{0},\mathbf{0}',\mathbf{0}'',\mathbf{0}^{(3)},\dots$ above the degree $\mathbf{0}$ of computable sets. Two local substructures are central: $\boldsymbol{D}(\leq\mathbf{0}')$, the degrees below the halting problem (exactly the $\Delta^0_2$ degrees of the arithmetical hierarchy), and $\boldsymbol{R}$, the degrees of computably enumerable (c.e., recursively enumerable) sets. A set is n-c.e. (n-r.e.) if it is obtainable from the empty set by n successive symmetric differences with c.e. sets; the 2-c.e. (d-c.e.) degrees sit strictly between the c.e. and all $\Delta^0_2$ degrees. An REA set is one c.e. in and Turing-above a given set; every d-c.e. degree is a 2-REA degree (a fact due to Lachlan).

Because $\boldsymbol{D}$ is defined by an external computational notion, one asks which of its features are internal - first-order expressible in the pure order language. A class or relation on degrees is definable (with parameters) if some first-order formula of $\langle\mathcal{D},\leq\rangle$ picks it out (allowing finitely many named degrees); parameter-free definability names nothing. An automorphism of $\boldsymbol{D}$ is a bijection of the degrees preserving $\leq$ and $\vee$; the structure is rigid if every automorphism is the identity. For a degree $\mathbf{a}$, the cone above it, $\boldsymbol{D}(\geq\mathbf{a})$, is the substructure of degrees $\geq\mathbf{a}$; Rogers' homogeneity conjecture asserted that every cone looks like $\boldsymbol{D}$ itself. The jump classes stratify $\boldsymbol{D}(\leq\mathbf{0}')$: $\mathrm{High}_n$ consists of degrees $\mathbf{x}\leq\mathbf{0}'$ with $\mathbf{x}^{(n)}=\mathbf{0}^{(n+1)}$ and $\mathrm{Low}_n$ of those with $\mathbf{x}^{(n)}=\mathbf{0}^{(n)}$.

The decisive machinery is the Slaman-Woodin coding theorem: every countable relation on degrees is definable from finitely many parameters, via degrees coding models of arithmetic into the order structure. It yields that $\boldsymbol{D}$ is biinterpretable with second-order arithmetic relative to finitely many parameters, that every automorphism is the identity above $\mathbf{0}^{(3)}$, that the automorphism group of $\boldsymbol{D}$ is countable with each member arithmetically presentable (Slaman and Woodin 1986; 2005), and - combined with an analysis of the double jump - that the jump itself is first-order definable in $\boldsymbol{D}$ without parameters (Shore and Slaman 1999). The strongest modern conjecture is biinterpretability: $\boldsymbol{D}$ (with second-order arithmetic), and $\boldsymbol{D}(\leq\mathbf{0}')$ and $\boldsymbol{R}$ (with first-order arithmetic), should be mutually interpretable through definable maps that match each degree exactly with the coded copies of the sets in it, not merely up to double-jump equivalence. Rigidity of $\boldsymbol{D}$ is equivalent to parameter-free biinterpretability with second-order arithmetic (Slaman and Woodin, Theorem 7.5.3 of the 2005 preprint). Weaker 'up to double jump' versions are known: $\boldsymbol{R}$ (Nies, Shore and Slaman 1996, 1998) and $\boldsymbol{D}(\leq\mathbf{z})$ for $\mathbf{z}\leq\mathbf{0}'$ with $\mathbf{z}''>\mathbf{0}''$ (Shore 2014) are biinterpretable with first-order arithmetic up to double jump, and Slaman and Soskova (2018) proved that $\boldsymbol{D}(\leq\mathbf{0}')$ has a finite automorphism base, with countable arithmetic automorphism group, and that its rigidity is equivalent to biinterpretability with first-order arithmetic. These results delimit but do not settle the six problems below.

Problem Statement

The problem is to determine the symmetry and the internal expressive power of the Turing degree structures, as posed by the six closing questions of Cooper's Logic Colloquium 1990 survey (retaining the source's generality; together they ask how far the biinterpretability program for the degree structures can be pushed from the known 'up to double jump' statements to the full parameter-free versions). Throughout, definability of a class or of an individual degree means parameter-free first-order definability: with finitely many parameters allowed, definability is already characterized - by the Slaman-Woodin coding theorem and its full parameter characterization for $\boldsymbol{D}$, and by the analogous parameter results for the local structures (Slaman and Soskova 2018 for $\boldsymbol{D}(\leq\mathbf{0}')$, Nies, Shore and Slaman 1996, 1998 for $\boldsymbol{R}$) - so only the parameter-free reading is informative. The questions:

(1) Cone isomorphism: do there exist distinct degrees $\mathbf{a}\neq\mathbf{b}$ such that the cones $\boldsymbol{D}(\geq\mathbf{a})$ and $\boldsymbol{D}(\geq\mathbf{b})$ are isomorphic as upper semilattices?

(2) Rigidity threshold: is every automorphism of $\boldsymbol{D}$ the identity already above $\mathbf{0}'$ - i.e. can the established fixation-above-$\mathbf{0}^{(3)}$ threshold be lowered to $\mathbf{0}'$?

(3) Local automorphisms: do nontrivial automorphisms exist for $\boldsymbol{D}(\leq\mathbf{0}')$ or for $\boldsymbol{R}$, or are these local structures rigid?

(4) Jump classes: are $\mathrm{High}_1$, $\mathrm{High}_2$, $\mathrm{Low}_1$, $\mathrm{Low}_2$ definable in $\boldsymbol{D}(\leq\mathbf{0}')$?

(5) Definable c.e. degrees: do there exist computably enumerable degrees other than $\mathbf{0}$ and $\mathbf{0}'$ that are definable in $\boldsymbol{D}(\leq\mathbf{0}')$, in $\boldsymbol{R}$, or in both; and, conversely, are there c.e. degrees provably not definable in $\boldsymbol{D}(\leq\mathbf{0}')$ or in $\boldsymbol{R}$? The existence half and the non-definability half are posed independently, and each may be answered on its own.

(6) Ershov-hierarchy definability: for each $n\geq 2$, is the class of n-c.e. degrees definable in $\boldsymbol{D}(\leq\mathbf{0}')$; and for which c.e. degrees $\mathbf{a}>\mathbf{0}$ is $\boldsymbol{R}\cap\boldsymbol{D}(\leq\mathbf{a})$ (the c.e. degrees below $\mathbf{a}$) definable in $\boldsymbol{D}(\leq\mathbf{a})$?

A full solution of the underlying program - biinterpretability of $\boldsymbol{D}$ with second-order arithmetic and of $\boldsymbol{D}(\leq\mathbf{0}')$ and $\boldsymbol{R}$ with first-order arithmetic, without parameters - would settle questions (2)-(6) at once: it would make these degree structures rigid, settling question (2) and the rigidity alternative of question (3), would characterize exactly which relations on them are definable, and would answer each local definability question by the corresponding statement of arithmetic. Question (1) is not known to follow from this program: an isomorphism between cones $\boldsymbol{D}(\geq\mathbf{a})\cong\boldsymbol{D}(\geq\mathbf{b})$ with $\mathbf{a}\neq\mathbf{b}$ is not an automorphism of $\boldsymbol{D}$, so neither rigidity nor biinterpretability visibly excludes it. Each of (1)-(6) is posed independently: a resolution of the task is a resolution of any one of the six questions, and the biinterpretability program just described is context motivating the list, not an additional deliverable.

References

1. Cooper, S. B. Definability and global degree theory. In: Logic Colloquium '90 (Lecture Notes in Logic), pp. 25-45. Springer, 1993; reissued Cambridge University Press, 2017. doi:10.1017/9781316718254.005. https://doi.org/10.1017/9781316718254.005
2. Shore, R. A. The homogeneity conjecture. Proceedings of the National Academy of Sciences 76(9), 4218-4219, 1979. doi:10.1073/pnas.76.9.4218. https://doi.org/10.1073/pnas.76.9.4218
3. Shore, R. A. On homogeneity and definability in the first-order theory of the Turing degrees. Journal of Symbolic Logic 47(1), 8-16, 1982. doi:10.2307/2273376. https://doi.org/10.2307/2273376
4. Slaman, T. A. and Woodin, W. H. Definability in the Turing degrees. Illinois Journal of Mathematics 30(2), 320-334, 1986. doi:10.1215/ijm/1256044641. https://doi.org/10.1215/ijm/1256044641
5. Shore, R. A. Defining jump classes in the degrees below 0'. Proceedings of the American Mathematical Society 104(1), 287-292, 1988. doi:10.1090/S0002-9939-1988-0958085-4. https://doi.org/10.1090/S0002-9939-1988-0958085-4
6. Nies, A., Shore, R. A. and Slaman, T. A. Definability in the recursively enumerable degrees. Bulletin of Symbolic Logic 2(4), 392-404, 1996. doi:10.2307/421171. https://doi.org/10.2307/421171
7. Shore, R. A. and Slaman, T. A. Defining the Turing jump. Mathematical Research Letters 6(6), 711-722, 1999. doi:10.4310/MRL.1999.v6.n6.a10. https://doi.org/10.4310/MRL.1999.v6.n6.a10
8. Shore, R. A. and Slaman, T. A. A splitting theorem for n-REA degrees. Proceedings of the American Mathematical Society 129(12), 3721-3728, 2001. doi:10.1090/S0002-9939-01-06015-4. https://doi.org/10.1090/S0002-9939-01-06015-4
9. Nies, A., Shore, R. A. and Slaman, T. A. Interpretability and definability in the recursively enumerable degrees. Proceedings of the London Mathematical Society 77(2), 241-291, 1998. doi:10.1112/S002461159800046X. https://doi.org/10.1112/S002461159800046x
10. Shore, R. A. Biinterpretability up to double jump in the degrees below 0'. Proceedings of the American Mathematical Society 142(1), 351-360, 2014. doi:10.1090/S0002-9939-2013-11719-3. https://doi.org/10.1090/S0002-9939-2013-11719-3
11. Shore, R. A. The Turing degrees: an introduction. In: Forcing, Iterated Ultrapowers, and Turing Degrees (Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore), pp. 39-121. World Scientific, 2015. doi:10.1142/9789814699952_0002. https://doi.org/10.1142/9789814699952_0002
12. Slaman, T. A. and Woodin, W. H. Definability in degree structures. Preprint, version of 21 July 2005. https://math.berkeley.edu/~slaman/talks/sw.pdf (unpublished preprint, no DOI)
13. Slaman, T. A. and Soskova, M. I. The Delta^0_2 Turing degrees: Automorphisms and Definability. Transactions of the American Mathematical Society 370(2), 1351-1375, 2018. doi:10.1090/tran/7187. https://doi.org/10.1090/tran/7187
14. Downey, R. and Greenberg, N. A hierarchy of computably enumerable degrees. Bulletin of Symbolic Logic 24(1), 53-89, 2018. doi:10.1017/bsl.2017.41. https://doi.org/10.1017/bsl.2017.41
15. Arslanov, M. M. and Yamaleev, M. M. On the problem of definability of the computably enumerable degrees in the difference hierarchy. Lobachevskii Journal of Mathematics 39(5), 634-638, 2018. doi:10.1134/S1995080218050037. https://doi.org/10.1134/S1995080218050037
16. Cooper, S. B. and Li, A. Splitting and cone avoidance in the d.c.e. degrees. Science in China (Series A: Mathematics) 45(9), 1135-1146, 2002. doi:10.1360/02ys9124. https://doi.org/10.1360/02ys9124
17. Slaman, T. A. and Shore, R. A. A discrete splitting theorem for the 2-REA degrees. Unpublished note. http://www.math.cornell.edu/~shore/papers/pdf/dsplit5.pdf (unpublished note, no DOI)