The regressive case of Martin's conjecture on the arithmetic degrees

Martin's conjecture, a proposed classification of functions on the Turing degrees under the axiom of determinacy, is known for regressive functions — those with $f(x)\leq_T x$ for all $x$ — by a theorem of Slaman and Steel (1988), and Lutz (2025) extended this to hyperarithmetic reducibility, answering a question of Slaman and Steel. Lutz's paper explicitly poses this remaining intermediate case, the arithmetic degrees, as an open problem. Here $y\leq_A x$ (arithmetic reducibility) means that $y$ is first-order definable from $x$, equivalently computable from finitely many iterates of the Turing jump of $x$, and $x\equiv_A y$ is mutual arithmetic reducibility. The problem is to determine, in $\mathsf{ZF}+\mathsf{AD}$, whether every arithmetically invariant function $f:2^\omega\to2^\omega$ — one with $x\equiv_A y$ implies $f(x)\equiv_A f(y)$ — such that $f(x)\leq_A x$ for all $x$ is either constant on a cone of arithmetic degrees or satisfies $f(x)\equiv_A x$ on a cone of arithmetic degrees — or to construct a counterexample. The question is delicate: Marks, Slaman and Steel showed that the general analogue of Martin's conjecture fails on the arithmetic degrees, and Lutz and Siskind record an unpublished Slaman–Steel counterexample for order-preserving functions there, while the measure-preserving part of the conjecture does hold on the arithmetic degrees.

Background

Two reals $x,y\in 2^\omega$ (infinite binary sequences) satisfy $y\leq_T x$ if $y$ is computable from $x$ by a Turing machine with oracle $x$; Turing equivalence $x\equiv_T y$ is mutual reducibility, and its equivalence classes are the Turing degrees. A function $f:2^\omega\to2^\omega$ is Turing-invariant if $x\equiv_T y$ implies $f(x)\equiv_T f(y)$, so that $f$ induces a function on the degrees. This problem lives on two coarsenings of this structure. Arithmetic reducibility, written $y\leq_A x$, holds when $y$ is first-order definable in the language of arithmetic with $x$ as a parameter — equivalently, when $y$ is computable from $x$ together with finitely many iterates of the Turing jump of $x$ (the jump $x'$ of $x$ encodes the halting problem relative to $x$); arithmetic equivalence $x\equiv_A y$ is mutual arithmetic reducibility, and its equivalence classes are the arithmetic degrees. Hyperarithmetic reducibility, written $y\leq_H x$, further allows jump-iterations of transfinite length along any $x$-computable ordinal; its equivalence classes are the hyperarithmetic degrees. Since $y\leq_T x$ implies $y\leq_A x$, which in turn implies $y\leq_H x$, each of these degree structures coarsens the previous one. Under the axiom of determinacy ($\mathsf{AD}$, which contradicts the full axiom of choice but under which all sets of reals have regularity properties), Martin showed that the cones — sets of the form $\{x : x\geq_T a\}$ — generate a countably complete ultrafilter on the Turing degrees, called the Martin measure. Consequently the eventual behavior of every Turing-invariant function can be read off modulo this measure. Martin's conjecture classifies Turing-invariant functions: very roughly, every such function is either constant on a cone, equal to the identity on a cone, or equal to some transfinite iterate of the Turing jump on a cone. The conjecture is open in general and is usually stated in $\mathsf{ZF}+\mathsf{AD}$, where pathologies are excluded; surveys by Montalbán and by Marks, Slaman and Steel give overviews.

Both the Slaman–Steel and the Lutz theorems are proved by first reducing $f$ to a continuous function on a pointed perfect tree — a perfect subtree $T$ of $2^{<\omega}$, i.e. one whose paths form a set with no isolated points, such that every path through $T$ computes $T$ — and then running a coding argument: Slaman and Steel code $x$ into $f(y)$ for some $y\equiv_T x$, while Lutz's coding argument relies on the $\Sigma^1_1$-bounding theorem, the classical descriptive-set-theoretic result that every analytic collection of well-orderings is bounded by a computable ordinal. The reduction to a continuous function generalizes to the arithmetic degrees, but neither coding argument has been adapted to arithmetic reducibility.

Problem Statement

Work in $\mathsf{ZF}+\mathsf{AD}$. Write $y\leq_A x$ if the real $y$ is arithmetically reducible to the real $x$ — that is, $y$ is first-order definable in the language of arithmetic with $x$ as a parameter, equivalently $y$ is computable from finitely many iterates of the Turing jump of $x$ — and $x\equiv_A y$ for mutual arithmetic reducibility; the equivalence classes of $\equiv_A$ are the arithmetic degrees, and a cone of arithmetic degrees is a set of the form $\{x\in 2^\omega : x\geq_A a\}$ for some real $a$. Let $f:2^\omega\to2^\omega$ be arithmetically invariant, i.e. $x\equiv_A y$ implies $f(x)\equiv_A f(y)$ for all reals $x,y$, and regressive for arithmetic reducibility, i.e. $f(x)\leq_A x$ for every $x$. Must $f$ either be constant on a cone of arithmetic degrees — $f(x)\equiv_A c$ for all $x\geq_A a$, for some reals $a$ and $c$ — or satisfy $f(x)\equiv_A x$ for all $x$ in some cone of arithmetic degrees? Equivalently: either prove this arithmetic-degrees regressive case of Martin's conjecture, or construct a counterexample — an arithmetically invariant $f$ with $f(x)\leq_A x$ for all $x$ that is neither constant on any cone of arithmetic degrees nor arithmetically equivalent to the identity on any cone of arithmetic degrees.

References

1. Patrick Lutz, "Martin's conjecture for regressive functions on the hyperarithmetic degrees", Journal of Mathematical Logic 25(2), Article 2450015 (2025). DOI: 10.1142/S0219061324500156, https://doi.org/10.1142/S0219061324500156; arXiv:2306.05746, https://arxiv.org/abs/2306.05746 (source of the open question)
2. 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
3. Andrew Marks, Theodore A. Slaman, and John R. Steel, "Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations", in Ordinal Definability and Recursion Theory: The Cabal Seminar Volume III, Lecture Notes in Logic 43, Association for Symbolic Logic / Cambridge University Press, 2016, pp. 493–520. DOI: 10.1017/CBO9781139519694.017, https://doi.org/10.1017/CBO9781139519694.017; arXiv:1109.1875, https://arxiv.org/abs/1109.1875
4. 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(2), 319–367 (2025). DOI: 10.1090/jams/1046, https://doi.org/10.1090/jams/1046; arXiv:2305.19646, https://arxiv.org/abs/2305.19646
5. Adam Day and Andrew Marks, "On a question of Slaman and Steel", Transactions of the American Mathematical Society, Series B 13(11), 379–402 (2026). DOI: 10.1090/btran/253, https://doi.org/10.1090/btran/253; arXiv:2004.00174, https://arxiv.org/abs/2004.00174
6. Antonio Nakid Cordero, "Martin's Conjecture in the Enumeration Degrees", preprint (2025). arXiv:2510.19147, https://arxiv.org/abs/2510.19147
7. Antonio Montalbán, "Martin's conjecture: a classification of the naturally occurring Turing degrees", Notices of the American Mathematical Society 66(8), 1209–1215 (2019). DOI: 10.1090/noti1940, https://doi.org/10.1090/noti1940