Rigidity of the enumeration degrees: existence of a nontrivial automorphism of $\mathcal{D}_e$

The upper semilattice $\mathcal{D}_e$ of enumeration degrees extends the Turing degrees via the substructure $\mathcal{TOT}$ of total degrees. Soskova's analysis of $\operatorname{Aut}(\mathcal{D}_e)$ (Ann. Pure Appl. Logic, 2016) proved that every automorphism of $\mathcal{D}_e$ is arithmetically definable, that $\operatorname{Aut}(\mathcal{D}_e)$ is at most countable, that every automorphism fixes the cone above $\mathbf{0}_e^{(4)}$, and that $\mathcal{TOT}$ is an automorphism base first-order definable from one parameter, while leaving open Rogers' question whether $\mathcal{TOT}$ is parameter-free definable, and whether any nontrivial automorphism of $\mathcal{D}_e$ exists. The definability half has since been resolved: Cai, Ganchev, Lempp, Miller and Soskova (J. Amer. Math. Soc., 2016) proved that a nonzero enumeration degree is total if and only if it is the join of a nontrivial maximal Kalimullin pair, answering Rogers' question and superseding the one-parameter definition. The surviving open core is the rigidity question: does $\mathcal{D}_e$ admit a nontrivial automorphism? Equivalently, since the total degrees are now known to be definable and to form an automorphism base, does the Turing-degree structure admit a nontrivial enumeration-induced automorphism? Both a positive and a negative answer would be landmark results for degree theory.

Background

Two sets of natural numbers are compared by enumeration reducibility, written $A\leq_e B$, when there is a computably enumerable set $W$ of pairs $\langle n,D\rangle$ (with $D$ a finite set) such that $A=\{n:(\exists D\subseteq B)\,\langle n,D\rangle\in W\}$: intuitively, $A$ can be enumerated from any enumeration of $B$, using only positive information about $B$. Here 'computably enumerable' (c.e.) means listable by a Turing machine. Because only positive information is used, $\leq_e$ is not closed under complement, and the equivalence classes of mutual $\leq_e$-reducibility form a structure strictly larger than the Turing degrees: the enumeration degrees $\mathcal{D}_e$, an upper semilattice (every two elements have a least upper bound, the join $\vee$) with least element $\mathbf{0}_e$, the degree of the c.e. sets.

An enumeration degree is total if it contains a set together with its complement; the total degrees $\mathcal{TOT}$ form a substructure isomorphic to the Turing degrees $\mathcal{D}_T$ via the standard embedding $\iota(\mathbf{d}_T(A))=\mathbf{d}_e(A\oplus\overline{A})$, and $\mathcal{TOT}$ is a proper substructure of $\mathcal{D}_e$. Rogers asked in 1967 whether this canonical copy of the Turing degrees is first-order definable in $\mathcal{D}_e$: definability would let questions about $\mathcal{D}_T$ be transferred to, and studied within, the richer structure $\mathcal{D}_e$.

The study of such questions is driven by the deep connection between definability and automorphisms. For the Turing degrees, Slaman and Woodin proved via set-theoretic coding that the automorphism group $\operatorname{Aut}(\mathcal{D}_T)$ is at most countable and that each automorphism is arithmetically definable; the analogous analysis of $\mathcal{D}_e$ was begun in their 1997 paper, which includes a coding theorem: countable relations on $\mathcal{D}_e$ can be coded by finitely many degree parameters. A structure is rigid if its only automorphism is the identity, and a subset $B$ of a structure is an automorphism base if every automorphism fixing each element of $B$ pointwise is the identity. The definability toolkit specific to $\mathcal{D}_e$ comes from Kalimullin: the enumeration jump (the analogue of the Turing jump) is first-order definable in $\mathcal{D}_e$, and so is the class of Kalimullin pairs ($\mathcal{K}$-pairs), pairs $\{A,B\}$ separable by a c.e. set $W$ with $A\times B\subseteq W$ and $\overline{A}\times\overline{B}\subseteq\overline{W}$; in degree terms, $\{\mathbf{a},\mathbf{b}\}$ is a $\mathcal{K}$-pair if and only if for every degree $\mathbf{x}$ the greatest lower bound of $\mathbf{a}\vee\mathbf{x}$ and $\mathbf{b}\vee\mathbf{x}$ exists and equals $\mathbf{x}$. $\mathcal{K}$-pairs became the workhorse of definability arguments in $\mathcal{D}_e$ (Ganchev-Soskova).

Soskova (2016) transferred the Slaman-Woodin automorphism analysis to $\mathcal{D}_e$: every automorphism of $\mathcal{D}_e$ is arithmetically definable (so $\operatorname{Aut}(\mathcal{D}_e)$ is at most countable); every automorphism fixes every degree above $\mathbf{0}_e^{(4)}$, the fourth enumeration jump of $\mathbf{0}_e$; $\mathcal{TOT}$ is an automorphism base, with single-element bases such as the degree of an 8-generic total function (a total function meeting every dense $\Sigma^0_8$ set of Cohen forcing conditions); and $\mathcal{TOT}$ is first-order definable from the single parameter $\bar{\mathbf{g}}$, an 8-generic degree. The paper left open whether that parameter can be eliminated — Rogers' question — and, crucially, whether any nontrivial automorphism of $\mathcal{D}_e$ exists at all.

The parameter was eliminated almost immediately: Cai, Ganchev, Lempp, Miller and Soskova proved that a nonzero enumeration degree is total if and only if it is the join of a nontrivial maximal $\mathcal{K}$-pair (maximal among $\mathcal{K}$-pairs under componentwise ordering), giving a parameter-free first-order definition of $\mathcal{TOT}$ in $\mathcal{D}_e$ and answering Rogers' question. This transformed the automorphism question: since $\mathcal{TOT}$ is definable, every automorphism of $\mathcal{D}_e$ maps $\mathcal{TOT}$ onto itself and therefore restricts to an automorphism of $\mathcal{D}_T$; since $\mathcal{TOT}$ is an automorphism base, that restriction is nontrivial exactly when the automorphism is. Hence rigidity of $\mathcal{D}_T$ implies rigidity of $\mathcal{D}_e$, and a nontrivial automorphism of $\mathcal{D}_e$ would automatically be a nontrivial automorphism of the Turing degrees. Ganchev and Sariev (2021) additionally proved that the jump is definable in the $\omega$-enumeration degrees $\mathcal{D}_\omega$ (degrees of sequences of sets under uniform enumeration reducibility) and deduced $\operatorname{Aut}(\mathcal{D}_e)\cong\operatorname{Aut}(\mathcal{D}_\omega)$. Whether $\mathcal{D}_e$ is rigid remains open.

Problem Statement

Determine whether the structure $\langle\mathcal{D}_e,\leq\rangle$ of the enumeration degrees admits a nontrivial automorphism; equivalently, decide whether $\mathcal{D}_e$ is rigid, i.e. whether every automorphism $\pi$ of $\mathcal{D}_e$ satisfies $\pi(\mathbf{a})=\mathbf{a}$ for all degrees $\mathbf{a}$.

In light of the results now available, the question has precise equivalent forms:

(1) Because $\mathcal{TOT}$ is first-order definable in $\mathcal{D}_e$ and is an automorphism base, every automorphism of $\mathcal{D}_e$ induces an automorphism of $\mathcal{D}_T$, and a nontrivial automorphism of $\mathcal{D}_e$ exists if and only if some nontrivial automorphism of the Turing degrees is enumeration induced, i.e. is the restriction of an automorphism of $\mathcal{D}_e$. The related open Question 3.12 of Cai-Ganchev-Lempp-Miller-Soskova asks whether every automorphism $\pi$ of $\mathcal{D}_T$ is enumeration extendible, meaning that there is a map $P:2^\omega\to2^\omega$ with $A$ c.e. in $\mathbf{x}$ if and only if $P(A)$ is c.e. in $\pi(\mathbf{x})$ for every set $A$ and Turing degree $\mathbf{x}$ (here '$A$ is c.e. in $\mathbf{x}$' abbreviates: $A$ is computably enumerable in some, equivalently every, set of Turing degree $\mathbf{x}$).

(2) Via the isomorphism $\operatorname{Aut}(\mathcal{D}_e)\cong\operatorname{Aut}(\mathcal{D}_\omega)$ of Ganchev-Sariev, the question is equally whether the automorphism group of the $\omega$-enumeration degrees contains a nontrivial element.

Any answer must respect the known constraints: $\operatorname{Aut}(\mathcal{D}_e)$ is at most countable, each of its elements is arithmetically definable and fixes every degree above $\mathbf{0}_e^{(4)}$, and rigidity of $\mathcal{D}_T$ would imply rigidity of $\mathcal{D}_e$. Neither the existence of a nontrivial automorphism nor rigidity is currently known.

References

1. Mariya I. Soskova, "The automorphism group of the enumeration degrees", Annals of Pure and Applied Logic 167 (2016), no. 10, 982-999. DOI: 10.1016/j.apal.2014.01.007, https://doi.org/10.1016/j.apal.2014.01.007.
2. Mingzhong Cai, Hristo A. Ganchev, Steffen Lempp, Joseph S. Miller, Mariya I. Soskova, "Defining totality in the enumeration degrees", Journal of the American Mathematical Society 29 (2016), no. 4, 1051-1067. DOI: 10.1090/jams/848, https://doi.org/10.1090/jams/848.
3. Hristo Ganchev, Andrey C. Sariev, "The automorphism group and definability of the jump operator in the omega-enumeration degrees", Archive for Mathematical Logic 60 (2021), no. 7-8, 909-925. DOI: 10.1007/s00153-021-00766-7, https://doi.org/10.1007/s00153-021-00766-7.
4. Theodore A. Slaman, W. Hugh Woodin, "Definability in the enumeration degrees", Archive for Mathematical Logic 36 (1997), 255-267. DOI: 10.1007/s001530050064, https://doi.org/10.1007/s001530050064.
5. I. Sh. Kalimullin, "Definability of the jump operator in the enumeration degrees", Journal of Mathematical Logic 3 (2003), no. 2, 257-267. DOI: 10.1142/S0219061303000285, https://doi.org/10.1142/S0219061303000285.
6. Hristo A. Ganchev, Mariya I. Soskova, "Definability via Kalimullin pairs in the structure of the enumeration degrees", Transactions of the American Mathematical Society 367 (2015), no. 7, 4873-4893. DOI: 10.1090/S0002-9947-2014-06157-6, https://doi.org/10.1090/S0002-9947-2014-06157-6.
7. Theodore A. Slaman, Mariya I. Soskova, "The enumeration degrees: local and global structural interactions", Contemporary Mathematics 690 (2017), 31-67. DOI: 10.1090/conm/690/13862, https://doi.org/10.1090/conm/690/13862.
8. Mariya Soskova, "The theory of the enumeration degrees, definability, and automorphisms", in: Adrian Rezus (ed.), Contemporary Logic and Computing (Landscapes in Logic 1), College Publications, London, 2020, pp. 706-730. zbMATH record Zbl 1505.03087, https://zbmath.org/?q=an:1505.03087, ISBN 978-1-84890-340-1.
9. Mariya I. Soskova, "The relationship between local and global structure in the enumeration degrees", in: Unity of Logic and Computation (Lecture Notes in Computer Science), Springer, 2023, pp. 17-22. DOI: 10.1007/978-3-031-36978-0_2, https://doi.org/10.1007/978-3-031-36978-0_2.
10. Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967. MR0224462, https://mathscinet.ams.org/mathscinet-getitem?mr=2244462; zbMATH record Zbl 0183.01401, https://zbmath.org/?q=an:0183.01401.
11. Bjorn Kjos-Hanssen, "Permutations of the integers induce only the trivial automorphism of the Turing degrees", arXiv:1603.00525 (2016); also Bulletin of Symbolic Logic 24 (2018), no. 2, 165-174. DOI: 10.1017/bsl.2018.15, https://doi.org/10.1017/bsl.2018.15, https://arxiv.org/abs/1603.00525.
12. Steffen Lempp, Theodore A. Slaman, Mariya I. Soskova, "Fragments of the theory of the enumeration degrees", Advances in Mathematics 383 (2021), 107686. DOI: 10.1016/j.aim.2021.107686, https://doi.org/10.1016/j.aim.2021.107686.
13. Thomas F. Kent, Keng Meng Ng, Andrea Sorbi, "The singleton degrees of the $\Sigma^0_2$ sets are not dense", Annals of Pure and Applied Logic 176 (2025), no. 9, 103616. DOI: 10.1016/j.apal.2025.103616, https://doi.org/10.1016/j.apal.2025.103616; also arXiv:2412.18991, https://arxiv.org/abs/2412.18991.
14. Antonio Nakid Cordero, "Martin's Conjecture in the Enumeration Degrees", arXiv:2510.19147 (2025). https://arxiv.org/abs/2510.19147.