Is every automorphism of the Turing degrees enumeration extendible? (Cai–Ganchev–Lempp–Miller–Soskova, Question 3.12)

The paper "Defining totality in the enumeration degrees" (Cai, Ganchev, Lempp, Miller, Soskova, J. Amer. Math. Soc. 2016) proved that the total enumeration degrees are first-order definable in the enumeration degrees, and used this to relate automorphisms of the two main degree structures. Its Question 3.12 asks: is every automorphism $\pi$ of the Turing degrees $\mathcal{D}_T$ enumeration extendible, i.e., does there exist a function $P:2^\omega\to2^\omega$ such that for every set $A\subseteq\omega$ and every Turing degree $\mathbf{x}$, $A$ is computably enumerable in $\mathbf{x}$ if and only if $P(A)$ is computably enumerable in $\pi(\mathbf{x})$? By Proposition 3.11 of the same paper, a positive answer is equivalent to every automorphism of $\mathcal{D}_T$ extending to an automorphism of the enumeration degrees $\mathcal{D}_e$, so that $\mathrm{Aut}(\mathcal{D}_e)\cong\mathrm{Aut}(\mathcal{D}_T)$. A negative answer would produce the first known nontrivial automorphism of the Turing degrees; a positive answer would yield first-order definability of the relation "c.e. in" in $\mathcal{D}_T$. The question is open as of Soskova's 2020 survey.

Background

Computability theory measures the relative difficulty of sets of natural numbers by reducibilities. Turing reducibility $A\le_T B$ holds when membership in $A$ can be decided by an algorithm with oracle $B$; the resulting equivalence classes form the Turing degrees $\mathcal{D}_T$, a partial order (in fact an upper semilattice with least element $\mathbf{0}_T$). Enumeration reducibility $A\le_e B$, introduced by Friedberg and Rogers in 1959, captures a positive-information notion: there is a computably enumerable (c.e.) set $\Phi$ of pairs such that $A=\{n:(\exists u)[(n,u)\in\Phi \wedge D_u\subseteq B]\}$, where $D_u$ ranges over the finite sets — informally, any enumeration of $B$ can be effectively transformed into an enumeration of $A$. Its equivalence classes form the enumeration degrees $\mathcal{D}_e$. The map $\iota$ sending the Turing degree of a set $A$ to the enumeration degree of $A\oplus\bar A$ (where $A\oplus B=\{2n:n\in A\}\cup\{2n+1:n\in B\}$ is the effective join of two sets and $\bar A$ is the complement of $A$) is an order embedding of $\mathcal{D}_T$ into $\mathcal{D}_e$ whose image is the class of total enumeration degrees; totality reflects having both positive and negative information about a set available. Between the two reducibilities sits relative computable enumerability: a set $A$ is c.e. in a set $B$ if $A$ is the domain of a partial function computable from $B$, equivalently $A\le_e B\oplus\bar B$; and $A$ is c.e. in a Turing degree $\mathbf{x}$ if $A$ is c.e. in some (equivalently every) set in $\mathbf{x}$. A useful classical fact of Selman (1971) states that $A\le_e B$ if and only if every Turing degree in which $B$ is c.e. is also a degree in which $A$ is c.e.

The source paper proved a landmark definability result: the total enumeration degrees are first-order definable in $\mathcal{D}_e$ — a nonzero enumeration degree is total if and only if it is the join of a nontrivial maximal $\mathcal{K}$-pair. (A $\mathcal{K}$-pair, or Kalimullin pair, is a pair of sets $A,B$ for which some c.e. set $W$ separates $A\times B$ from $\bar A\times\bar B$, i.e. $A\times B\subseteq W$ and $W\cap(\bar A\times\bar B)=\emptyset$; Kalimullin introduced this class in his proof that the enumeration jump — the analogue for $\mathcal{D}_e$ of the Turing jump, which sends a set to its relativized halting problem — is first-order definable in $\mathcal{D}_e$.) This answered a longstanding question of Hartley Rogers, Jr. on whether the Turing degrees can be singled out inside the enumeration degrees by a first-order property. As consequences, the image under $\iota$ of the relation "c.e. in" between Turing degrees is first-order definable in $\mathcal{D}_e$, and so is the image of the array nonrecursive degrees (a class of Turing degrees arising from domination questions); the paper stresses that definability of these notions in $\mathcal{D}_T$ itself was, and remains, unknown.

Definability interacts closely with automorphisms. A structure is rigid if it has no nontrivial automorphisms; whether $\mathcal{D}_T$ is rigid has been a central open problem of degree theory for decades, and Slaman and Woodin proved rigidity of $\mathcal{D}_T$ equivalent to the Bi-interpretability Conjecture, which asserts that $\mathcal{D}_T$ is bi-interpretable with second-order arithmetic (the degree structure and the standard model of second-order arithmetic mutually define copies of one another). Classical automorphism analysis of $\mathcal{D}_T$, as recorded in the source paper and in later surveys by Soskova, shows that $\mathcal{D}_T$ has at most countably many automorphisms, that every automorphism fixes the cone above $\mathbf{0}_T''$ (the second iterate of the Turing jump applied to the least degree $\mathbf{0}_T$), and that relations on $\mathcal{D}_T$ induced by second-order-arithmetic-definable relations that are invariant under all automorphisms are first-order definable in $\mathcal{D}_T$. Because every enumeration degree is the infimum of two total degrees, the total degrees are an automorphism base for $\mathcal{D}_e$ (two automorphisms agreeing on them coincide), so their definability implies that every automorphism of $\mathcal{D}_e$ induces an automorphism $\pi_T=\iota^{-1}\circ\pi_e\circ\iota$ of $\mathcal{D}_T$, and that the induced map $\mathrm{Aut}(\mathcal{D}_e)\to\mathrm{Aut}(\mathcal{D}_T)$ is injective. The source paper defines an automorphism $\pi$ of $\mathcal{D}_T$ to be enumeration induced if $\pi=\iota^{-1}\circ\pi_e\circ\iota$ for some automorphism $\pi_e$ of $\mathcal{D}_e$, and — the notion at issue here — enumeration extendible if there exists a function $P:2^\omega\to2^\omega$ (where $2^\omega$ denotes the set of all subsets of $\omega$) such that for every set $A$ and every Turing degree $\mathbf{x}$, $A$ is c.e. in $\mathbf{x}$ if and only if $P(A)$ is c.e. in $\pi(\mathbf{x})$. Every enumeration induced automorphism is enumeration extendible (a presentation of $\pi_e$ witnesses $P$), and Proposition 3.11 of the paper gives the near-converse: if $\pi$ and $\pi^{-1}$ are both enumeration extendible, then $\pi$ is enumeration induced (the proof uses Selman's theorem to show $P$ preserves $\le_e$). Since $\pi^{-1}$ is an automorphism whenever $\pi$ is, the universal question below is equivalent to asking whether every automorphism of $\mathcal{D}_T$ extends to an automorphism of $\mathcal{D}_e$, that is, whether the natural injection $\mathrm{Aut}(\mathcal{D}_e)\to\mathrm{Aut}(\mathcal{D}_T)$ is surjective.

Problem Statement

Question 3.12 of Cai–Ganchev–Lempp–Miller–Soskova, "Defining totality in the enumeration degrees" (2016): Is every automorphism of the Turing degrees enumeration extendible?

Write $\omega$ for the set of natural numbers and $2^\omega$ for the set of all subsets of $\omega$. Let $\mathcal{D}_T$ be the structure of Turing degrees: the equivalence classes of subsets of $\omega$ under Turing reducibility ($A\le_T B$ if membership in $A$ is decidable by an algorithm with oracle $B$), partially ordered by the induced reducibility, and let $\mathrm{Aut}(\mathcal{D}_T)$ denote its automorphisms. A set $A\subseteq\omega$ is computably enumerable (c.e.) in a Turing degree $\mathbf{x}$ if $A$ is the domain of a partial function computable with oracle $B$ for some — equivalently every — set $B$ of degree $\mathbf{x}$. Let $\mathcal{D}_e$ be the enumeration degrees, the corresponding equivalence classes under enumeration reducibility ($A\le_e B$ if some effective procedure transforms any enumeration of $B$ into an enumeration of $A$), and let $\iota:\mathcal{D}_T\to\mathcal{D}_e$ be the standard embedding sending the Turing degree of a set $A$ to the enumeration degree of $A\oplus\bar A$ (the effective join of $A$ with its complement).

Call an automorphism $\pi\in\mathrm{Aut}(\mathcal{D}_T)$ enumeration extendible if there exists a function $P:2^\omega\to2^\omega$ such that for every set $A\subseteq\omega$ and every Turing degree $\mathbf{x}$,

$$A \text{ is c.e. in } \mathbf{x} \iff P(A) \text{ is c.e. in } \pi(\mathbf{x}).$$

The problem is to determine whether every automorphism $\pi\in\mathrm{Aut}(\mathcal{D}_T)$ admits such a single uniform translation $P$ of the "c.e. in" relation. By Proposition 3.11 of the source paper applied to $\pi$ and to $\pi^{-1}$, a positive answer is equivalent to each of the following: every automorphism of $\mathcal{D}_T$ is enumeration induced, i.e. of the form $\iota^{-1}\circ\pi_e\circ\iota$ for some automorphism $\pi_e$ of $\mathcal{D}_e$; every automorphism of $\mathcal{D}_T$ extends to an automorphism of $\mathcal{D}_e$; and the natural injection $\mathrm{Aut}(\mathcal{D}_e)\to\mathrm{Aut}(\mathcal{D}_T)$ is surjective (hence an isomorphism). The question must be answered for the class of all automorphisms with no restriction (for example, restricting to arithmetically presented automorphisms or to a local substructure would be a different problem), and the uniformity of $P$ may not be weakened (for example, allowing $P$ to depend on $\mathbf{x}$ or on $A$ would not answer the question as posed).

References

1. 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 (author preprint at https://people.math.wisc.edu/~jsmiller8/Papers/totality.pdf)
2. Richard M. Friedberg, Hartley Rogers, Jr., "Reducibility and completeness for sets of integers", Zeitschrift für mathematische Logik und Grundlagen der Mathematik 5 (1959), 117–125. DOI: 10.1002/malq.19590050703, https://doi.org/10.1002/malq.19590050703; zbMATH: https://zbmath.org/3176049
3. Hartley Rogers, Jr., "Theory of recursive functions and effective computability", McGraw-Hill, New York, 1967. zbMATH: https://zbmath.org/3291134
4. Alan L. Selman, "Arithmetical reducibilities I", Zeitschrift für mathematische Logik und Grundlagen der Mathematik 17 (1971), 335–350. DOI: 10.1002/malq.19710170139, https://doi.org/10.1002/malq.19710170139; zbMATH: https://zbmath.org/3363530
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; zbMATH: https://zbmath.org/2063112
6. Theodore A. Slaman, Mariya I. Soskova, "The enumeration degrees: local and global structural interactions", in Foundations of Mathematics: Logic at Harvard (Contemporary Mathematics 690), American Mathematical Society, Providence, 2017, 31–67. DOI: 10.1090/conm/690/13862, https://doi.org/10.1090/conm/690/13862
7. Mariya I. Soskova, "The theory of the enumeration degrees, definability, and automorphisms", in Adrian Rezuș (ed.), Contemporary Logic and Computing (Landscapes in Logic 1), College Publications, London, 2020, 706–730. ISBN 978-1-84890-340-1, zbMATH: https://zbmath.org/7377992
8. 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, Cham, 2023, 17–22. DOI: 10.1007/978-3-031-36978-0_2, https://doi.org/10.1007/978-3-031-36978-0_2
9. 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
10. Maryanthe Malliaris, Saharon Shelah, "The Turing degrees and Keisler's order", Journal of Symbolic Logic 89 (2024), no. 1, 331–341. DOI: 10.1017/jsl.2022.63, https://doi.org/10.1017/jsl.2022.63
11. Antonio Nakid Cordero, "Martin's Conjecture in the Enumeration Degrees", arXiv:2510.19147 (2025), https://arxiv.org/abs/2510.19147