Martin's Conjecture in the enumeration degrees: the Wadge order on the Scott domain, jump-skip iterates, non-uniform regressive functions, and cone theories under Turing Determinacy

Martin's Conjecture proposes to classify, under determinacy, all definable degree-invariant functions on the Turing degrees: up to behaviour on a cone, every such function is constant or an iterate of the Turing jump. Nakid Cordero's preprint "Martin's Conjecture in the Enumeration Degrees" (arXiv:2510.19147, 2025) transfers this program to the enumeration degrees, where no Cone Theorem holds and two jump-like operators - the enumeration jump and the skip - replace the Turing jump, and it closes with four open questions that jointly delimit the remaining structure theory: (1) whether the preorder of uniformly e-invariant functions under enumeration reducibility on a cone is isomorphic to the Wadge order on the Scott domain $P\omega$; (2) a classification of the order types realized by the finite compositions of the jump and the skip on a single enumeration degree; (3) whether a regressive e-invariant function can fail to be locally constant once uniformity is dropped; and (4) whether, under Turing Determinacy, some cone of enumeration degrees has a common first-order theory of the cones above all of its cototal elements.

Background

The Turing-degree background. Martin's Conjecture is a proposed classification of all "natural" constructions on sets of natural numbers. A function $f:\mathcal{P}(\omega)\to\mathcal{P}(\omega)$ is Turing-invariant if $A\equiv_T B$ implies $f(A)\equiv_T f(B)$. Under the Axiom of Determinacy (AD), the conjecture states that every definable Turing-invariant function is either constant or increasing on a cone - a cone is the family of all degrees above some fixed degree - and that the increasing ones are, up to equivalence on a cone, exactly the iterates of the Turing jump (Martin; Steel; Slaman-Steel). The set-theoretic engine is the Cone Theorem: under AD, every set of reals closed under Turing equivalence contains or is disjoint from a cone; the weaker principle TD (Turing Determinacy) suffices for many applications. For uniformly Turing-invariant functions - those where an index witnessing $f(A)\equiv_T f(B)$ can be computed from an index witnessing $A\equiv_T B$ by a uniformity function - Steel and Slaman-Steel proved the full conjecture. Becker completed the global picture: the preorder $\leq_T^{\nabla}$ of reducibility on a cone, restricted to uniformly Turing-invariant functions and with dual classes identified, is isomorphic to the Wadge order on Cantor space $2^{\omega}$, that is, to the preorder of subsets of $2^{\omega}$ under Wadge reduction $A\leq_W B$ (meaning $A=f^{-1}(B)$ for some continuous $f$); Kihara-Montalban extended the classification to many-one-invariant functions. A long-standing conjecture of Steel asserts that every Turing-invariant function is equivalent on a cone to a uniformly invariant one.

Enumeration degrees. Enumeration reducibility, introduced by Friedberg-Rogers, is the positive-information counterpart of Turing reducibility: $A\leq_e B$ if and only if there is a computably enumerable set $\Gamma$ of axioms of the form "if the finite set $D$ is contained in $B$, enumerate $n$ into $A$" such that $A=\Gamma(B)$; such a $\Gamma$ is an enumeration operator (e-operator). The quotient of $\mathcal{P}(\omega)$ by $\equiv_e$ is the structure $\mathcal{D}_e$ of enumeration degrees. It extends the Turing degrees: the map $A\mapsto A\oplus\overline{A}$ embeds $\mathcal{D}_T$ into $\mathcal{D}_e$, and its image - the total degrees, those containing a set $A$ with $A\geq_e\overline{A}$ - is first-order definable in $\mathcal{D}_e$ (Cai-Ganchev-Lempp-Miller-Soskova). Unlike $\mathcal{D}_T$, the structure $\mathcal{D}_e$ admits no Cone Theorem: both the total and the non-total degrees are cofinal, so no Martin-style asymptotic dichotomy holds. A degree is cototal if it contains a set $A$ with $A\leq_e\overline{A}$; cototality, introduced by Andrews-Ganchev-Kuyper-Lempp-Miller-Soskova-Soskova together with the skip operator, is a cofinal widening of totality. Between totality and cototality sit the continuous degrees (the enumeration degrees of points in Hilbert's cube $[0,1]^{\omega}$, shown first-order definable in $\mathcal{D}_e$ by Andrews-Igusa-Miller-Soskova), and more generally every effective second-countable $T_0$ topological space determines a class of enumeration degrees (Kihara-Ng-Pauly).

Two jump-like operators. Writing $K_A=\{\langle i,n\rangle: n\in\Gamma_i(A)\}$ for the e-operator halting set, the enumeration jump of Cooper is $A'=K_A\oplus\overline{K_A}$ and the skip is $A^{\diamond}=\overline{K_A}$. Both are uniformly e-invariant, but they behave differently: the jump is increasing and always lands in total degrees, while the skip is not monotone, satisfies Friedberg jump inversion, and can be cyclic (there are skip 2-cycles with $A^{\diamond\diamond}\equiv_e A$). For cototal degrees the two operators interact mildly ($A^{\diamond}\equiv_e A'$ when $A$ is cototal), but in general their compositions diverge.

The source paper. Nakid Cordero transfers the Martin-Steel program to $\mathcal{D}_e$. Call $f:\mathcal{P}(\omega)\to\mathcal{P}(\omega)$ e-invariant if $A\equiv_e B$ implies $f(A)\equiv_e f(B)$, and uniformly e-invariant if, moreover, a computable uniformity function $u$ maps every pair of e-operator indices $\langle i,j\rangle$ witnessing $A\equiv_e B$ to a pair witnessing $f(A)\equiv_e f(B)$. Write $f\leq_e^{\nabla} g$ if $f(X)\leq_e g(X)$ for all $X$ in some cone; $f$ is regressive if $f(A)<_e A$ for every non-c.e. set $A$ (following the source paper, whose Corollary 3.4 imposes $f(A)<_e A$ on every non-c.e. $A$; the least enumeration degree $\boldsymbol{0}_e$, the degree of the c.e. sets, bounds every c.e. set and so admits no strict $\leq_e$-predecessor); $f$ is locally constant if its restriction to every enumeration degree is constant. The paper proves that the global preorder $\leq_e^{\nabla}$ is wild - it embeds $\mathcal{D}_e$ itself, is not locally countable, and has infinite antichains even among injective uniformly e-invariant functions - but that locally the Martin picture survives: a non-locally-constant uniformly e-invariant function on a degree $\deg_e(A)$ satisfies $A\leq_e f(A)$ or $A^{\diamond}\leq_e f(A)$ (Theorem 5.1, adapting Bard's local version of the uniform Martin's conjecture), so every regressive uniformly e-invariant function is locally constant (Corollary 5.4). Using Kalimullin $\mathcal{K}$-pairs (pairs of sets $\{A,B\}$ for which there is a computably enumerable $W$ with $A\times B\subseteq W$ and $\overline{A}\times\overline{B}\subseteq\overline{W}$; a notion generalizing semicomputable sets, first-order definable in $\mathcal{D}_e$ by Ganchev-Kalimullin-Miller-Soskova), the paper also constructs a Borel e-invariant function not equivalent on any cone to any Borel uniformly e-invariant function (Theorem 6.6), so Steel's uniformity conjecture fails outright for e-invariance.

The Scott domain. The Wadge order on Cantor space, which classifies uniformly Turing-invariant functions through Becker's isomorphism, has as its enumeration-degree counterpart the Scott domain $P\omega=\mathcal{P}(\omega)$ with the Scott topology, whose basic opens are $[D]=\{X\subseteq\omega: D\subseteq X\}$ for finite $D$. This space is universal for the quasi-Polish spaces of de Brecht (the countably based $T_0$ spaces that embed as $\Pi^0_2$ subsets of $P\omega$, a class containing all Polish spaces), and the enumeration operators relativized to an oracle are exactly the Scott-continuous maps $P\omega\to P\omega$, which is why $P\omega$ is the natural arena for a Wadge-style analysis of e-invariant functions. The Wadge order on $P\omega$ is known to be ill-founded and to have infinite antichains (Duparc-Vuilleumier) - far wilder than on Cantor space - but its exact isomorphism type is unknown, as is that of $\leq_e^{\nabla}$.

Determinacy in $\mathcal{D}_e$. A classical consequence of TD is that some cone of Turing degrees has, at every base $\boldsymbol{d}$ of the cone, the same first-order theory - the set of first-order sentences in the language of the partial order that hold in the structure - for the upper cone $\mathcal{D}_T(\geq\boldsymbol{d})$; the same relativized argument works for the cones $\mathcal{D}_e(\geq\boldsymbol{d})$ above total bases $\boldsymbol{d}$. It fails for arbitrary bases: cones above total degrees have no minimal degrees, while by Calhoun-Slaman's non-density theorem, above every total degree there is a degree $\boldsymbol{a}$ such that $\mathcal{D}_e(\geq\boldsymbol{a})$ has a minimal degree, so first-order theories of upper cones genuinely vary. Lempp-Slaman-Soskova have studied definable fragments of the first-order theory of $\mathcal{D}_e$. Whether a TD-driven common theory exists along a cone of cototal bases is the paper's fourth question.

Problem Statement

Resolve the four questions posed at the end of Nakid Cordero's "Martin's Conjecture in the Enumeration Degrees" (arXiv:2510.19147), with all notation as in the Background: $\leq_e$ is enumeration reducibility, $\mathcal{D}_e$ the enumeration degrees, $A'=K_A\oplus\overline{K_A}$ the enumeration jump, $A^{\diamond}=\overline{K_A}$ the skip, $f\leq_e^{\nabla} g$ enumeration reducibility on a cone, and "regressive" means $f(A)<_e A$ for every non-c.e. $A\subseteq\omega$. These four questions are independent open problems posed in the closing section of the source paper.

(Q1) Is the Wadge order on the Scott domain $P\omega$ - the preorder of subsets of $P\omega$ under Wadge reduction by Scott-continuous (equivalently, enumeration-operator) maps - isomorphic, as a preorder, to the preorder $\leq_e^{\nabla}$ on uniformly e-invariant functions $f:\mathcal{P}(\omega)\to\mathcal{P}(\omega)$?

(Q2) For $\boldsymbol{a}\in\mathcal{D}_e$, determine the possible order types of $JS(\boldsymbol{a})=\{\boldsymbol{a}^{\sigma}\mid\sigma\in\{\diamond,\prime\}^{<\omega}\},$ the set of degrees obtained from $\boldsymbol{a}$ by all finite compositions of the skip and the enumeration jump, partially ordered by $\leq_e$.

(Q3) Is there an e-invariant (not necessarily uniformly e-invariant) function $f:\mathcal{P}(\omega)\to\mathcal{P}(\omega)$ such that $f$ is regressive and, for every $A\subseteq\omega$, the restriction $f\upharpoonright_{\deg_e(A)}$ is not constant?

(Q4) Assume Turing Determinacy (TD). Is there a cone $\mathcal{C}$ of enumeration degrees such that, for every cototal degree $\boldsymbol{a}\in\mathcal{C}$, the upper cone $\mathcal{D}_e(\geq\boldsymbol{a})$ has the same first-order theory in the language of partial orders?

These four questions are the explicit open problems posed in the source paper's closing section, and they share one scientific objective: to determine how much of the Martin-Steel picture of degree-invariant functions and of determinacy survives in the enumeration degrees, where no Cone Theorem holds.

References

1. Antonio Nakid Cordero (2025). Martin's Conjecture in the Enumeration Degrees. Preprint, arXiv:2510.19147 [math.LO] (v2, 7 November 2025). DOI: 10.48550/arXiv.2510.19147. URL: https://arxiv.org/abs/2510.19147
2. Donald A. Martin (1968). The axiom of determinateness and reduction principles in the analytical hierarchy. Bulletin of the American Mathematical Society 74(4). DOI: 10.1090/S0002-9904-1968-11995-0. URL: https://doi.org/10.1090/S0002-9904-1968-11995-0
3. John R. Steel (1982). A classification of jump operators. Journal of Symbolic Logic 47(2). DOI: 10.2307/2273146. URL: https://doi.org/10.2307/2273146
4. Theodore A. Slaman and John R. Steel (1988). Definable functions on degrees. In Cabal Seminar 81-85, Lecture Notes in Mathematics, Springer. DOI: 10.1007/BFb0084969. URL: https://doi.org/10.1007/BFb0084969
5. Howard Becker (1988). A characterization of jump operators. Journal of Symbolic Logic 53(3). DOI: 10.2307/2274567. URL: https://doi.org/10.2307/2274567
6. Takayuki Kihara and Antonio Montalban (2018). The uniform Martin's conjecture for many-one degrees. Transactions of the American Mathematical Society 370(12). DOI: 10.1090/tran/7519. URL: https://doi.org/10.1090/tran/7519
7. Vittorio Bard (2020). Uniform Martin's conjecture, locally. Proceedings of the American Mathematical Society 148(12). DOI: 10.1090/proc/15159. URL: https://doi.org/10.1090/proc/15159
8. Richard M. Friedberg and Hartley Rogers (1959). Reducibility and completeness for sets of integers. Mathematical Logic Quarterly 5. DOI: 10.1002/malq.19590050703. URL: https://doi.org/10.1002/malq.19590050703
9. Uri Andrews, Hristo Ganchev, Rutger Kuyper, Steffen Lempp, Joseph Miller, Alexandra Soskova, and Mariya Soskova (2019). On cototality and the skip operator in the enumeration degrees. Transactions of the American Mathematical Society 372(3). DOI: 10.1090/tran/7604. URL: https://doi.org/10.1090/tran/7604
10. Mingzhong Cai, Hristo Ganchev, Steffen Lempp, Joseph Miller, and Mariya Soskova (2016). Defining totality in the enumeration degrees. Journal of the American Mathematical Society 29(4). DOI: 10.1090/jams/848. URL: https://doi.org/10.1090/jams/848
11. Jacques Duparc and Louis Vuilleumier (2020). The Wadge order on the Scott domain is not a well-quasi-order. Journal of Symbolic Logic 85(1). DOI: 10.1017/jsl.2019.51. URL: https://doi.org/10.1017/jsl.2019.51
12. Matthew de Brecht (2013). Quasi-Polish spaces. Annals of Pure and Applied Logic 164(3). DOI: 10.1016/j.apal.2012.11.001. URL: https://doi.org/10.1016/j.apal.2012.11.001
13. William C. Calhoun and Theodore A. Slaman (1996). The $\Pi^0_2$ enumeration degrees are not dense. Journal of Symbolic Logic 61(4). DOI: 10.2307/2275821. URL: https://doi.org/10.2307/2275821
14. Takayuki Kihara, Keng Meng Ng, and Arno Pauly. Enumeration degrees and non-metrizable topology. Preprint, arXiv:1904.04107 (v2, 17 September 2020); accepted for publication in Memoirs of the American Mathematical Society. URL: https://arxiv.org/abs/1904.04107
15. Hristo A. Ganchev, Iskander Sh. Kalimullin, Joseph S. Miller, and Mariya I. Soskova (2022). A structural dichotomy in the enumeration degrees. Journal of Symbolic Logic 87(2). DOI: 10.1017/jsl.2019.72. URL: https://doi.org/10.1017/jsl.2019.72
16. Uri Andrews, Gregory Igusa, Joseph S. Miller, and Mariya I. Soskova (2019). Characterizing the continuous degrees. Israel Journal of Mathematics 234(2). DOI: 10.1007/s11856-019-1943-x. URL: https://doi.org/10.1007/s11856-019-1943-x
17. Steffen Lempp, Theodore A. Slaman, and Mariya I. Soskova (2021). Fragments of the theory of the enumeration degrees. Advances in Mathematics 383, Article 107686. DOI: 10.1016/j.aim.2021.107686. URL: https://doi.org/10.1016/j.aim.2021.107686
18. Josiah Jacobsen-Grocott (2026). A topological classification of classes of enumeration degrees. Journal of Symbolic Logic (published online 11 June 2026). DOI: 10.1017/jsl.2026.10221. URL: https://doi.org/10.1017/jsl.2026.10221