The partial order R\mathbf{R} of recursively enumerable (r.e., equivalently computably enumerable) Turing degrees is a central structure of classical computability theory, and it is unknown whether it has any nontrivial automorphism. Ambos-Spies (2018), publishing with full proofs results first announced in 1982, proved that every nontrivial initial segment of R\mathbf{R} — in particular every principal ideal R(⩽a)\mathbf{R}(\leqslant\mathbf{a}) with a>0\mathbf{a}>\mathbf{0} — is an automorphism base, i.e. any automorphism of R\mathbf{R} is determined by its values on it. The paper poses as its principal open problem the dual question: does there exist a nonzero r.e. degree a\mathbf{a} such that the upper cone R(⩾a)={b∈R:b⩾a}\mathbf{R}(\geqslant\mathbf{a})=\{\mathbf{b}\in\mathbf{R}:\mathbf{b}\geqslant\mathbf{a}\} is an automorphism base of R\mathbf{R}, and in particular is this true for every degree 0<a<0′\mathbf{0}<\mathbf{a}<\mathbf{0}'? The source argues, citing definability work of Nies, that a positive answer would yield a finite automorphism base for R\mathbf{R} and would be a step toward biinterpretability of R\mathbf{R} with first-order arithmetic in a parameter (a mutual definability condition that would tie the automorphisms of R\mathbf{R} to arithmetic). A secondary open question asks for structural constraints on any nontrivial automorphism stronger than the incomparability constraint proved in the paper — for instance, whether some degree must be mapped to one forming a minimal pair with it. As of 2026 no published work is known to settle either question, and the finite-automorphism-base results for the enumeration degrees and for D(⩽0′)\mathbf{D}(\leqslant\mathbf{0}') (Slaman–Soskova) do not transfer to R\mathbf{R}.

Background

A set of natural numbers is recursively enumerable (r.e., now usually called computably enumerable) if it is the domain of a partial computable function, and it is Turing reducible to another set (A⩽TBA\leqslant_T B) if AA is computable with oracle BB. The r.e. Turing degrees — equivalence classes of r.e. sets under ≡T\equiv_T — form a countable dense partial order R\mathbf{R} with least element 0\mathbf{0} (the computable degree) and greatest element 0′\mathbf{0}' (the degree of the halting problem); R\mathbf{R} is an upper semilattice under the join a∨b\mathbf{a}\vee\mathbf{b}, while meets (greatest lower bounds) exist only partially. Since the 1950s a central theme of degree theory has been how much symmetry this order has: no nontrivial automorphism of R\mathbf{R} has ever been constructed, yet rigidity of R\mathbf{R} has never been proved, and Cooper's announced construction of nontrivial automorphisms of the Turing universe (1990s preprints and papers) is generally treated as incomplete and disputed.

A subset B⊆R\mathbf{B}\subseteq\mathbf{R} is an automorphism base of R\mathbf{R} if every automorphism of (R,⩽)(\mathbf{R},\leqslant) that fixes all elements of B\mathbf{B} pointwise is the identity. Since automorphisms preserve joins and existing meets, any class that generates R\mathbf{R} under these lattice operations is automatically an automorphism base. Two nonzero degrees form a minimal pair if their (existing) meet is 0\mathbf{0}, so that neither carries any information about the other. The Turing jump a′\mathbf{a}' of a degree a\mathbf{a} is the degree of the halting problem relativized to an oracle of degree a\mathbf{a}; a degree is low if its jump equals 0′\mathbf{0}'. The noncappable degrees (those not half of any minimal pair) coincide with the promptly simple degrees (degrees of promptly simple c.e. sets, a class singled out by a time-sensitive enumeration property) and are first-order definable in R\mathbf{R} (Ambos-Spies, Jockusch, Shore and Soare, 1984), hence invariant under every automorphism.

For the global Turing degrees D\mathbf{D} and for the local structure D(⩽0′)\mathbf{D}(\leqslant\mathbf{0}') (the degrees below the halting problem) the automorphism-base picture is largely settled: Jockusch and Posner (1981) showed that the minimal degrees (nonzero degrees with no degree strictly between them and 0\mathbf{0}), and every comeager or measure-one class (a class topologically or measure-theoretically large in the standard topology and measure on degrees), generate D\mathbf{D}; Slaman and Woodin (1986) proved that every countable relation on D\mathbf{D} is first-order definable with finitely many parameters (and that R\mathbf{R} is parameter-definable inside D(⩽0′)\mathbf{D}(\leqslant\mathbf{0}')); and Slaman and Soskova (2017, 2018) showed that the enumeration degrees (the degree structure induced by enumeration reducibility, under which AA is reducible to BB when a computable procedure enumerates the elements of AA from any enumeration of BB) have a finite automorphism base and that D(⩽0′)\mathbf{D}(\leqslant\mathbf{0}') has a finite automorphism base with countable automorphism group. In contrast, for R\mathbf{R} itself it is open whether any finite automorphism base exists, and prior to 2018 only scattered classes were known to be bases.

Ambos-Spies's 2018 paper (in a special issue in memory of S. B. Cooper) changed the supply of known bases for R\mathbf{R}: every nonzero principal ideal R(⩽a)\mathbf{R}(\leqslant\mathbf{a}) — indeed every nontrivial downward-closed class — is an automorphism base; the low degrees are a base; classes of low degrees incomparable with a fixed incomplete degree are bases; and a general sufficient criterion and a generation lemma are given. A corollary of the main theorem is a structural constraint: any nontrivial automorphism of R\mathbf{R} must move some degree to an incomparable degree. The paper then poses, as its principal remaining problem, the dual of the main theorem — whether upper cones R(⩾a)\mathbf{R}(\geqslant\mathbf{a}) are automorphism bases — noting that the case a=0′\mathbf{a}=\mathbf{0}' degenerates to the singleton {0′}\{\mathbf{0}'\}, so that instance coincides with rigidity of R\mathbf{R}, and that Cooper's 1999 paper 'Upper cones as automorphism bases' addresses the theme only for the global degrees (its reviewed content shows the complete degrees D(⩾0′)\mathbf{D}(\geqslant\mathbf{0}') fail to be a base of D\mathbf{D}). The definability results of Nies (2002, 2003) — e.g. uniform parameter-definability of sufficiently high arithmetical relations in nontrivial intervals of R\mathbf{R} and interpretability of arithmetic in R\mathbf{R} — are the basis for the source's expectation that a positive upper-cone answer would have strong model-theoretic consequences: biinterpretability of R\mathbf{R} with first-order arithmetic using parameters is a mutual definability condition under which R\mathbf{R} and the standard model of arithmetic define faithful copies of each other up to parameters, so that the automorphisms of R\mathbf{R} would be controlled by definability in arithmetic.

Problem Statement

Let R\mathbf{R} denote the partial order (upper semilattice) of recursively enumerable (computably enumerable) Turing degrees — the degrees of sets of natural numbers enumerable by a partial computable function — with least element 0\mathbf{0} (the computable degree) and greatest element 0′\mathbf{0}' (the degree of the halting problem). Determine whether there exists a nonzero r.e. degree a\mathbf{a} such that the upper cone

R(⩾a)={b∈R:b⩾a}\mathbf{R}(\geqslant\mathbf{a})=\{\mathbf{b}\in\mathbf{R}:\mathbf{b}\geqslant\mathbf{a}\}

is an automorphism base of R\mathbf{R}, i.e. such that every automorphism of (R,⩽)(\mathbf{R},\leqslant) fixing all degrees in R(⩾a)\mathbf{R}(\geqslant\mathbf{a}) pointwise is the identity. In particular, determine whether this holds for every degree a\mathbf{a} with 0<a<0′\mathbf{0}<\mathbf{a}<\mathbf{0}'. (For a=0′\mathbf{a}=\mathbf{0}' the cone is the singleton {0′}\{\mathbf{0}'\}, so that instance is exactly the rigidity of R\mathbf{R}.)

As a closely linked secondary target of the same objective — constraining the automorphisms of R\mathbf{R} — strengthen the known incomparability constraint: whereas Ambos-Spies (2018) proved that any nontrivial automorphism of R\mathbf{R} must move some degree to an incomparable degree, determine whether it must in fact move some degree b\mathbf{b} to a degree f(b)f(\mathbf{b}) such that b\mathbf{b} and f(b)f(\mathbf{b}) form a minimal pair (their meet exists and equals 0\mathbf{0}, with both nonzero), or establish any other structural constraint on the images of degrees under a nontrivial automorphism strictly stronger than incomparability.

Within the primary target, the existence determination — whether at least one nonzero r.e. degree a\mathbf{a} has R(⩾a)\mathbf{R}(\geqslant\mathbf{a}) an automorphism base — is the primary question; the universal case, for every degree 0<a<0′\mathbf{0}<\mathbf{a}<\mathbf{0}', is the stronger question emphasized by the source and subsumes the existence determination when answered positively. The secondary minimal-pair determination is a closely linked, independently answerable target, as is any other named structural constraint on the images of degrees under a nontrivial automorphism that is strictly stronger than incomparability.

References

  1. Klaus Ambos-Spies, 'Automorphism bases for the recursively enumerable degrees', Computability 7(2-3), 237-258 (2018). DOI: 10.3233/COM-180088. https://doi.org/10.3233/COM-180088
  2. Klaus Ambos-Spies, 'Automorphism bases for the r.e. degrees' (abstract), in Extended Abstracts of Short Talks of the 1982 Summer Institute on Recursion Theory Held at Cornell University (I. Kalantari, ed.), Special Publication of the Recursive Function Theory Newsletter, pp. 3-4 (1982). No DOI. https://doi.org/10.3233/COM-180088
  3. S. B. Cooper, 'Upper cones as automorphism bases', Siberian Advances of Mathematics 9(3), 17-77 (1999). No DOI; Zbl 0937.03051, zbMATH 1439070 (review by A. S. Morozov). https://zbmath.org/1439070
  4. Carl G. Jockusch Jr. and David B. Posner, 'Automorphism bases for degrees of unsolvability', Israel Journal of Mathematics 40, 150-164 (1981). DOI: 10.1007/BF02761906. https://doi.org/10.1007/BF02761906
  5. Theodore A. Slaman and W. Hugh Woodin, 'Definability in the Turing degrees', Illinois Journal of Mathematics 30(2), 320-334 (1986). DOI: 10.1215/ijm/1256044641; Zbl 0592.03030 (zbMATH 3950507). https://doi.org/10.1215/ijm/1256044641
  6. Theodore A. Slaman and Mariya I. Soskova, 'The enumeration degrees: local and global structural interactions', in Foundations of Mathematics: Logic at Harvard (Contemporary Mathematics 690), American Mathematical Society, pp. 31-67 (2017). DOI: 10.1090/conm/690/13862. https://doi.org/10.1090/conm/690/13862
  7. Theodore A. Slaman and Mariya I. Soskova, 'The Δ20\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
  8. André Nies, 'Global properties of degree structures', in In the Scope of Logic, Methodology and Philosophy of Science (Synthese Library 315), Kluwer Academic Publishers, pp. 65-80 (2002). No DOI; Zbl 1042.03032 (zbMATH 1984267), ISBN 1-4020-0929-1. https://zbmath.org/1984267
  9. André Nies, 'Parameter definability in the recursively enumerable degrees', Journal of Mathematical Logic 3(1), 37-65 (2003). DOI: 10.1142/S0219061303000236. https://doi.org/10.1142/S0219061303000236
  10. Klaus Ambos-Spies, Carl G. Jockusch Jr., Richard A. Shore and Robert I. Soare, 'An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees', Transactions of the American Mathematical Society 281, 109-128 (1984). DOI: 10.1090/S0002-9947-1984-0719661-8. https://doi.org/10.1090/S0002-9947-1984-0719661-8
  11. Rod Downey, Noam Greenberg and Ellen Hammatt, 'A hierarchy of computably enumerable degrees, II: Some recent developments and new directions', New Zealand Journal of Mathematics 52, 175-231 (2021). DOI: 10.53733/133. https://doi.org/10.53733/133
  12. Mariya I. Soskova, 'The relationship between local and global structure in the enumeration degrees', in Unity of Logic and Computation (CiE 2023, Lecture Notes in Computer Science 13967), Springer, pp. 17-22 (2023). DOI: 10.1007/978-3-031-36978-0_2. https://doi.org/10.1007/978-3-031-36978-0_2
  13. Hristo Ganchev and Andrey C. Sariev, 'The automorphism group and definability of the jump operator in the ω\omega-enumeration degrees', Archive for Mathematical Logic 60(7-8), 909-925 (2021). DOI: 10.1007/s00153-021-00766-7. https://doi.org/10.1007/s00153-021-00766-7
  14. Dávid Natingga, 'Alpha degrees as an automorphism base for the alpha-enumeration degrees', arXiv:1812.11308 (2018). https://arxiv.org/abs/1812.11308