Natural many-one degrees and the optimal set-theoretic hypotheses for the uniform Martin conjecture on m-degrees

Kihara and Montalban (Trans. AMS 370, 2018) proved a many-one-degree analogue of the uniform Martin conjecture: under $AD^+$ (or $AD+DC$ in the two-valued case), the degrees of uniformly $(\equiv_T,\equiv_m)$-invariant functions $\omega^\omega\to Q^\omega$, compared by many-one reducibility on a cone, are isomorphic to the $Q$-Wadge degrees for every better quasi-order $Q$. Interpreting "natural" many-one degrees through relativization, this classifies the natural m-degrees as the mirror of the Wadge hierarchy. The paper explicitly acknowledges that no formal mathematical definition of a natural m-degree exists, and that the classification rests on the explicitly empirical claim that natural m-degrees induce uniformly degree-invariant functions under relativization. The set-theoretic cost of the theorem is uncalibrated — the full bqo-valued isomorphism is known under $AD^+$, with only restricted versions in weaker theories (ZFC for Borel functions, $PD+DC$ for projective functions, and $\Gamma$-determinacy plus $\Gamma$-Ramsey assumptions for countable-range $\Gamma$-functions), and it is open which determinacy/Ramsey hypotheses are actually needed, and whether they can be weakened or shown necessary. No resolution of either matter is known in the literature to date; both remain open.

Background

Computability theory measures the intrinsic difficulty of sets of natural numbers by reducibilities. A set $A\subseteq\omega$ is many-one reducible to $B$ (written $A\leq_m B$) if some computable function $\psi:\omega\to\omega$ converts membership in $A$ into membership in $B$, i.e. $n\in A\iff\psi(n)\in B$; it is Turing reducible to $B$ ($A\leq_T B$) if $A$ is computable with oracle access to $B$. Each reducibility induces an equivalence relation and a degree structure: the m-degrees and the Turing degrees. The Turing jump $X\mapsto X'$, which relativizes the halting problem to an oracle $X$, acts as a successor operation on the Turing degrees. Both degree structures are wild in general — every countable partially ordered set embeds into the m-degrees, and the first-order theory of the m-degrees is as complicated as second-order arithmetic — yet the degrees that occur in ordinary mathematical practice (the computable degree, the complete computably enumerable set, the complete d.c.e. set, i.e. the difference of two computably enumerable sets, the complete $\Sigma^0_2$ set for the second level of the arithmetic hierarchy of definable sets, and Kleene's $\mathcal{O}$, his system of notations for computable ordinals) appear to line up in a simple hierarchy. Computability theorists have long observed, for instance, that no natural m-degree of a computably enumerable set is known that is neither complete nor computable, although infinitely many such degrees exist.

Martin's conjecture, formulated by D. A. Martin in the late 1970s, is the classical proposal to explain this phenomenon for the Turing degrees: every Borel degree-invariant function on the reals is either constant on a cone or, on a cone, equivalent to a (possibly transfinite) iterate of the Turing jump, so the natural Turing degrees are essentially the transfinite iterates of the jump. Here functions are compared "on a cone": a Turing cone is a set of reals of the form $\{X:X\geq_T C\}$, and Martin's measure (which under determinacy is a countably additive measure on the degree-invariant sets) makes "almost every degree" meaningful. A function $f:\omega^\omega\to\omega^\omega$ is $(\equiv_T,\equiv_T)$-invariant if $X\equiv_T Y$ implies $f(X)\equiv_T f(Y)$, and uniformly invariant if the programs witnessing $X\equiv_T Y$ can be computably converted into programs witnessing $f(X)\equiv_T f(Y)$. Slaman and Steel (1988), building on Steel (1982), proved the uniform version of Martin's conjecture: the uniformly Turing-invariant functions are well-ordered by comparability on a cone, with the jump as the successor operation. Becker (1988) characterized the natural nonzero Turing degrees as those obtained as the universal set of a reasonable pointclass (a set to which every set in the pointclass reduces), up to relativization; the source paper connects this characterization to m-degrees only indirectly, via the observation that the jump of a natural Turing degree is a natural m-degree.

Kihara and Montalban proved the corresponding statement one level finer. A function $f:\omega^\omega\to 2^\omega$ is $(\equiv_T,\equiv_m)$-UI (uniformly invariant from Turing equivalence to many-one equivalence) if there is a computable conversion $u$ such that whenever $X\equiv_T Y$ via programs $(i,j)$, then $f(X)\equiv_m f(Y)$ via $u(i,j)$; replacing both occurrences of "$\equiv$" by "$\leq$" in this definition gives the companion notion of a uniformly order-preserving function, abbreviated $(\leq_T,\leq_m)$-UOP. Such functions are compared by $f\leq_m^\nabla g$, meaning $f(X)\leq_m g(X)$ relative to a common oracle on a Turing cone. On the other side, Wadge reducibility $A\leq_w B$ between sets of reals is many-one reducibility via a continuous function, and under determinacy the Wadge degrees are semi-well-ordered (well-founded, with antichains of size at most two). The theorem is stated for functions valued in $Q^\omega$ where $Q$ is a better quasi-order (bqo) — a quasi-order $Q$ such that every continuous $f:[\omega]^\omega\to Q$ has some infinite set $X$ with $f(X)\leq_Q f(X^-)$, the class of orders closed under the constructions needed for Wadge-type hierarchy theory. Kihara and Montalban proved, under $AD^+$ for arbitrary bqo $Q$ (and under $AD+DC$ for $Q=2$), that the $\equiv_m^\nabla$-degrees of $(\equiv_T,\equiv_m)$-UI functions $\omega^\omega\to Q^\omega$ are isomorphic to the $Q$-Wadge degrees of functions $\omega^\omega\to Q$. The general-$Q$ theory is also entangled with the study of countable Borel equivalence relations (Borel-defined equivalence relations on the reals with countable classes): Marks proved that many-one equivalence on $3^\omega$ is a uniformly universal countable Borel equivalence relation, i.e. one to which every other such relation reduces by uniformly chosen reductions, while this fails for $2^\omega$. Here $AD$ is the axiom of determinacy (every two-player game in which the players alternately choose natural numbers, producing a real, is determined, i.e. one of the players has a winning strategy), $DC$ is dependent choice (we write $AD+DC$ for the theory $AD$ together with $DC$), and $AD^+$ is the slightly stronger axiom (adding closure properties such as $DC_{\mathbb{R}}$, dependent choice for relations on the reals) under which the Cabal-seminar structure theory of the reals is developed; $PD$ is projective determinacy, the restriction of $AD$ to the projective sets (those obtained from Borel sets by continuous images and complementation).

Reading "natural" through the observation that all proofs in computability theory relativize, this theorem yields a complete description of the natural many-one degrees: they mirror the Wadge hierarchy. But the paper is explicit that this reading is not mathematical: "We do not have a formal mathematical definition of what it means to be a natural m-degree", so the argument contains an empirical, non-mathematical claim — that natural m-degrees induce uniformly degree-invariant functions under relativization. Furthermore, the axiomatic assumptions are not calibrated. In Section 1.3 the authors show the main theorems hold for Borel functions in ZFC, for projective functions under $DC+PD$, and for functions in a pointclass $\Gamma$ (a class of sets of reals containing the Borel sets and closed under countable unions, finite intersections, and continuous substitutions) with countable range, under the assumption that all sets in $\Gamma$ are determined and Ramsey (a set $A$ of infinite subsets of $\omega$ is Ramsey if there is an infinite set $H\subseteq\omega$ such that either every infinite subset of $H$ lies in $A$ or none does). The $\Gamma$-Ramsey hypothesis is used only to ensure that every bqo is a $\Gamma$-bqo (via a theorem of Louveau and Simpson); for $Q=2$ it can be dropped under $AD+DC$; and the countable-range restriction can be removed under full determinacy. What the weakest hypotheses for the general theorems are — and whether the determinacy and Ramsey assumptions can be weakened, or are genuinely necessary — is left open.

Problem Statement

The problem consists of two linked parts concerning Kihara and Montalban's "The uniform Martin's conjecture for many-one degrees" (Trans. AMS 370 (2018), 9025–9044). Part (A) is the definitional gap the paper explicitly acknowledges; part (B) asks for the set-theoretic hypotheses used in the source's Section 1.3 analysis to be calibrated. Their common objective is to place the classification of the natural many-one degrees on a fully formal and axiomatically optimal foundation.

(A) Formalize natural m-degrees. Provide a formal, intrinsic mathematical definition of the class of natural m-degrees, together with a mathematical justification that it captures the informal notion used by computability theorists. Because the correspondence between natural m-degrees and natural Turing-to-many-one degree-invariant operators is exactly the content of the empirical relativization claim, it must be established by the formalization rather than stipulated. Such a definition must provably include the standard examples (the degrees of $\emptyset$, $\omega$, the complete computably enumerable set, the complete d.c.e. set, the complete $\Sigma^0_2$ set, and Kleene's $\mathcal{O}$) and must exclude m-degrees manufactured by pure diagonalization or priority construction (the standard stage-by-stage construction techniques of computability theory) without invariant meaning; since this exclusion criterion is intensional, mirroring the informal character of the source's notion of "natural", exclusion is to be demonstrated at least on the standard such constructions, namely members of the continuum-size antichains and the embedded copies of arbitrary countable posets. It must also either prove the empirical claim on which the current classification rests — that every natural m-degree induces, under relativization, a uniformly $(\equiv_T,\equiv_m)$-invariant function in the sense of the source paper's Definition 2 — or explicitly discharge that claim by replacing this empirical foundation with a formal argument.

(B) Calibrate the set-theoretic hypotheses. Determine the weakest assumptions under which the Kihara-Montalban isomorphism theorems hold in full generality. Concretely: (i) are Theorems 8 and 9 of the source paper — the isomorphism between the $\equiv_m^\nabla$-degrees of uniformly $(\equiv_T,\equiv_m)$-invariant functions $\omega^\omega\to Q^\omega$ and the $Q$-Wadge degrees, and the normalization of every such function to a uniformly order-preserving one, for every better quasi-order $Q$ — provable under $AD+DC$ or under determinacy assumptions strictly weaker than $AD^+$? (ii) In the pointclass-restricted version, is the hypothesis that all sets in $\Gamma$ are Ramsey genuinely necessary when $Q\neq 2$, given that it is dispensable for $Q=2$ under $AD+DC$? (iii) Can the countable-range restriction on $\Gamma$-functions be removed under hypotheses weaker than full determinacy? (iv) Where a hypothesis cannot be weakened or eliminated, can its necessity be established?

Answers to (A) and (B) together would convert the current empirical classification of natural many-one degrees into a theorem with precise scope and known axiomatic cost; the two parts may be answered separately.

References

1. Takayuki Kihara and Antonio Montalbán, “The uniform Martin's conjecture for many-one degrees”, Transactions of the American Mathematical Society 370 (2018), no. 12, 9025–9044. DOI: 10.1090/tran/7519; preprint arXiv:1608.05065. https://doi.org/10.1090/tran/7519
2. Antonio Montalbán, “Martin's Conjecture: A Classification of the Naturally Occurring Turing Degrees”, Notices of the American Mathematical Society 66 (2019), no. 8, 1209–1215. DOI: 10.1090/NOTI1940. https://doi.org/10.1090/NOTI1940
3. Adam R. Day and Andrew S. Marks, “On a question of Slaman and Steel”, Transactions of the American Mathematical Society, Series B 13 (2026), no. 11, 379–402. DOI: 10.1090/btran/253; preprint arXiv:2004.00174. https://doi.org/10.1090/btran/253
4. Andrew S. Marks, “Uniformity, universality, and computability theory”, Journal of Mathematical Logic 17 (2017), no. 1, Article 1750003. DOI: 10.1142/S0219061317500039. https://doi.org/10.1142/S0219061317500039
5. Vittorio Bard, “Uniform Martin's conjecture, locally”, Proceedings of the American Mathematical Society 148 (2020), no. 12, 5369–5380. DOI: 10.1090/proc/15159; preprint arXiv:1907.10766. https://doi.org/10.1090/proc/15159
6. Takayuki Kihara, “The Arithmetical Hierarchy: A Realizability-Theoretic Perspective”, preprint (2024), arXiv:2410.15795. https://arxiv.org/abs/2410.15795
7. Takayuki Kihara, “Many-one reducibility with realizability”, The Journal of Symbolic Logic (2025), 1–39. DOI: 10.1017/jsl.2024.68; preprint arXiv:2403.16027. https://doi.org/10.1017/jsl.2024.68
8. Antonio Nakid Cordero, “Martin's Conjecture in the Enumeration Degrees”, preprint (2025), arXiv:2510.19147. https://arxiv.org/abs/2510.19147
9. Patrick Lutz and Benjamin Siskind, “Part 1 of Martin's conjecture for order-preserving and measure-preserving functions”, Journal of the American Mathematical Society 38 (2025), no. 2, 319–367. DOI: 10.1090/jams/1046; preprint arXiv:2305.19646. https://doi.org/10.1090/jams/1046
10. Patrick Lutz, “Martin's conjecture for regressive functions on the hyperarithmetic degrees”, Journal of Mathematical Logic 25 (2025), no. 2, Article 2450015. DOI: 10.1142/S0219061324500156; preprint arXiv:2306.05746. https://doi.org/10.1142/S0219061324500156
11. Takayuki Kihara and Antonio Montalbán, “On the structure of the Wadge degrees of BQO-valued Borel functions”, Transactions of the American Mathematical Society 371 (2019), no. 11, 7885–7923. DOI: 10.1090/tran/7621; preprint arXiv:1705.07802. https://doi.org/10.1090/tran/7621
12. Takayuki Kihara and Victor Selivanov, “Wadge-like degrees of Borel BQO-valued functions”, Proceedings of the American Mathematical Society 150 (2022), no. 9, 3989–4003. DOI: 10.1090/proc/15930; preprint arXiv:1909.10835. https://doi.org/10.1090/proc/15930
13. Victor Selivanov, “Non-collapse of the effective Wadge hierarchy”, Computability 11 (2022), no. 3–4, 335–358. DOI: 10.3233/COM-210376. https://doi.org/10.3233/COM-210376
14. Theodore A. Slaman and John R. Steel, “Definable functions on degrees”, in Cabal Seminar 81–85, Lecture Notes in Mathematics 1333, Springer, Berlin, 1988, pp. 37–55. DOI: 10.1007/BFb0084969. https://doi.org/10.1007/bfb0084969
15. John R. Steel, “A classification of jump operators”, The Journal of Symbolic Logic 47 (1982), no. 2, 347–358. DOI: 10.2307/2273146. https://doi.org/10.2307/2273146
16. Howard Becker, “A characterization of jump operators”, The Journal of Symbolic Logic 53 (1988), no. 3, 708–728. DOI: 10.2307/2274567. https://doi.org/10.2307/2274567
17. George Barmpalias, Su Gao, Jialiang He, Takayuki Kihara, Andre Nies, David Schrittesser, Theodore Slaman, Chieu-Minh Tran, Daniel Turetsky, Philip Welch, Liang Yu, and Hang Zhang, “Open Problems in Mathematical Logic” (Tianyuan Workshop on Definability and Computation, June 2026), preprint (2026), arXiv:2608.26628. https://arxiv.org/abs/2608.26628
18. Linus Richter, Frank Stephan, and Xiaoyan Zhang, “Chains and Antichains inside Many-One Degrees and Variants”, preprint (2026), arXiv:2607.06218. https://arxiv.org/abs/2607.06218
19. Patrizio Cintioli, “A computably enumerable many-one degree with no least finite-one degree”, preprint (2026), arXiv:2604.10879. https://arxiv.org/abs/2604.10879