Steel's uniformization conjecture for Turing-invariant functions: the global form of Martin's conjecture

Under the axiom of determinacy (ZF+DC+AD), Martin's conjecture predicts that every Turing-invariant function on the reals is either constant on a cone or is a transfinite iterate of the Turing jump, and that the resulting hierarchy is prewellordered. Slaman and Steel (1988) confirmed the conjecture for uniformly Turing-invariant functions, those for which a single pair of indices witnesses all instances of invariance, and Steel conjectured (Conjecture 1.4 of Marks–Slaman–Steel) that every Turing-invariant function agrees, on a cone, with a uniformly Turing-invariant one — the uniformization core that would complete the full classification. Despite substantial recent progress — Part 1 for order-preserving and measure-preserving functions (Lutz–Siskind), the case of regressive functions on the hyperarithmetic degrees, the degrees obtained by relativizing computation along computable ordinals (Lutz), and uniform analogues for other degree notions — the conjecture for arbitrary Turing-invariant functions remains open, and the analogous statements are known to fail for arithmetic equivalence and, as shown in 2025, for the enumeration degrees, the degree structure of enumeration reducibility, in which a set is reduced to another by computably enumerating its members rather than deciding them.

Background

Write a real as an element $x$ of Cantor space $2^\omega$, the set of infinite binary sequences. A real $x$ is Turing reducible to a real $y$, written $x\le_T y$, if $x$ is computable by a Turing machine with oracle $y$; Turing equivalence $x\equiv_T y$ means mutual reducibility, and the quotient by it is the upper semilattice of Turing degrees. Saying $x\equiv_T y$ via $(i,j)$ means that the $i$-th partial recursive function computes $y$ from $x$ and the $j$-th computes $x$ from $y$. A function $f:2^\omega\to2^\omega$ is Turing invariant if $x\equiv_T y$ implies $f(x)\equiv_T f(y)$; in the language of descriptive set theory, such an $f$ is a homomorphism from Turing equivalence to itself.

The conjecture is studied under the axiom of determinacy AD (every infinite two-player game with integer moves has a winning strategy for one of the players), which is inconsistent with the full axiom of choice but consistent with the axiom of dependent choice DC; the base theory is ZF+DC+AD. Under AD, Martin's cone theorem says that every Turing-invariant set of reals either contains or is disjoint from a cone $\{x : x\ge_T y\}$. Consequently Martin measure, which assigns value 1 to invariant sets containing a cone and 0 to their complements, is a countably additive probability measure on the Turing-invariant sets, and almost everywhere (a.e.) statements about Turing-invariant objects mean on-a-cone statements. For Turing-invariant $f$ and $g$, write $f\le_m g$ if $f(x)\le_T g(x)$ a.e. and $f\equiv_m g$ if $f(x)\equiv_T g(x)$ a.e. The Turing jump $x\mapsto x'$ maps a real to its relativized halting problem, is strictly increasing in Turing degree, and can be iterated transfinitely, giving reals $x^{(\alpha)}$ for countable ordinals $\alpha<\omega_1$.

Martin's conjecture (posed by D. A. Martin in the 1970s) states, under ZF+DC+AD: (I) if $f$ is Turing-invariant and not increasing a.e. (i.e. it is not the case that $f(x)\ge_T x$ a.e.), then $f$ is constant a.e.; and (II) $\le_m$ prewellorders the Turing-invariant functions that are increasing a.e., with the jump operator $f\mapsto f'$ acting as the successor on the $\le_m$-ranks. Informally: the only definable non-constant functions on the Turing degrees are the transfinite iterates of the jump, and they are linearly ordered by strength. The conjecture formalizes the rigidity of the degree structure; without a definability restriction the statement is only plausible under AD, which supplies the cone regularity (indeed Chong and Yu built uniformly Turing-invariant $\Pi^1_1$ (coanalytic) counterexamples under ZFC+V=L).

A function $f$ is uniformly Turing invariant if there is a single function $u:\omega^2\to\omega^2$ such that whenever $x\equiv_T y$ via $(i,j)$, one has $f(x)\equiv_T f(y)$ via $u(i,j)$: one fixed pair of program indices witnesses every instance of the invariance. Slaman and Steel proved Part I, and Steel Part II, of Martin's conjecture for all uniformly Turing-invariant functions (building on Steel's classification of jump operators), and the same circle of ideas shows that Martin's conjecture restricted to Borel functions is equivalent to the statement that every Borel Turing-invariant $f$ is constant a.e. or equal a.e. to $x\mapsto x^{(\alpha)}$ for some $\alpha<\omega_1$, and also to the assertion that every Borel Turing-invariant $f$ is $\equiv_m$-equivalent to a uniformly Turing-invariant $g$ (Theorem 1.8 of the source paper). Steel's Conjecture 1.4 extends this last, uniformization form to all Turing-invariant functions: he conjectured that every Turing-invariant $f$ is $\equiv_m$-equivalent to a uniformly Turing-invariant $g$ defined a.e. By the Slaman–Steel theorems, an affirmative answer would complete the full Martin classification; Becker's characterization of the increasing uniformly invariant functions as the maps $x\mapsto$ the universal $\Gamma(x)$ set for reasonable pointclasses $\Gamma$ shows that this uniformization form precisely captures the heuristic that the jump and its iterates are the only non-trivial definable degree-invariant maps.

The conjecture also matters outside recursion theory. Turing equivalence is a countable Borel equivalence relation (CBER): a Borel equivalence relation with countable classes on a Polish space. A CBER $E$ is universal if every CBER Borel reduces to it (a reduction is a Borel map taking $E$-equivalent points to equivalent points and conversely); universal CBERs exist. Kechris asked whether Turing equivalence itself is universal; an affirmative answer would contradict Martin's conjecture, while Martin's conjecture implies Turing equivalence is not universal, and it would convert several conditional dichotomy theorems of Thomas about weakly universal CBERs (universal up to countable-to-one Borel homomorphisms) and about the ideal of non-weakly-universal Borel sets for Turing equivalence into unconditional ones. The source paper presents, with a proof, a long-unpublished companion result of Slaman and Steel that arithmetic equivalence ($x$ arithmetically definable from $y$ and conversely) is a universal CBER, and that the analogue of Martin's conjecture for arithmetic equivalence is false — a warning that the conjecture is tied to specific features of Turing reducibility.

Problem Statement

Work in ZF+DC+AD. Let $2^\omega$ be Cantor space and let Martin measure be the measure on Turing-invariant subsets of $2^\omega$ induced by Martin's cone theorem; 'a.e.' means on a cone $\{x : x\ge_T y\}$. Recall that a function $f:2^\omega\to2^\omega$ is Turing invariant if $x\equiv_T y$ implies $f(x)\equiv_T f(y)$, and that $f\equiv_m g$ means $f(x)\equiv_T g(x)$ a.e.; $f$ is uniformly Turing invariant if there is a function $u:\omega^2\to\omega^2$ such that whenever $x\equiv_T y$ via $(i,j)$ (that is, the $i$-th partial recursive function maps $x$ to $y$ and the $j$-th maps $y$ to $x$), then $f(x)\equiv_T f(y)$ via $u(i,j)$.

Steel's uniformization conjecture (Conjecture 1.4 of Marks-Slaman-Steel, the central open question isolated by the source paper): is every Turing-invariant function $f:2^\omega\to2^\omega$ $\equiv_m$-equivalent to a uniformly Turing-invariant function $g$ that is defined a.e.? That is, does there exist a uniformly Turing-invariant $g$, defined on some cone, with $f(x)\equiv_T g(x)$ a.e.?

An affirmative answer, combined with the Slaman-Steel theorems for the uniform case, would prove the full Martin conjecture (parts I and II) for all Turing-invariant functions: every Turing-invariant $f$ is constant a.e. or $f(x)\ge_T x$ a.e., $\le_m$ prewellorders the increasing-a.e. Turing-invariant functions, and the jump acts as successor on the $\le_m$-ranks. A negative answer is any Turing-invariant $f$, in a model of ZF+DC+AD or in a specified consistent strengthening, for which no a.e.-defined uniformly Turing-invariant $g$ satisfies $f\equiv_m g$; note that a refutation of Martin's conjecture itself would also refute the conjecture, since the conjecture implies Martin's. In the restriction to Borel functions the statement is equivalent to Borel Martin's conjecture (Theorem 1.8 of the source paper), but the problem as posed here concerns arbitrary Turing-invariant functions under ZF+DC+AD.

References

1. Andrew Marks, Theodore Slaman, John Steel, 'Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations', arXiv:1109.1875 (2011, v2 2012); published in 'Ordinal Definability and Recursion Theory: The Cabal Seminar Volume III', Cambridge University Press, 2016, pp. 493-520, DOI 10.1017/cbo9781139519694.017, https://arxiv.org/abs/1109.1875 (source paper)
2. John R. Steel, 'A classification of jump operators', Journal of Symbolic Logic 47 (1982), no. 2, 347-358, DOI 10.2307/2273146, https://doi.org/10.2307/2273146
3. Theodore A. Slaman, John R. Steel, 'Definable functions on degrees', in 'Cabal Seminar 81-85', Lecture Notes in Mathematics 1333, Springer, 1988, pp. 37-55, DOI 10.1007/bfb0084969, https://doi.org/10.1007/bfb0084969
4. Patrick Lutz, Benjamin Siskind, 'Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions', arXiv:2305.19646 (2023); Journal of the American Mathematical Society 38 (2025), 319-367, DOI 10.1090/jams/1046, https://arxiv.org/abs/2305.19646
5. Patrick Lutz, 'Martin's conjecture for regressive functions on the hyperarithmetic degrees', arXiv:2306.05746 (2023); Journal of Mathematical Logic 25 (2025), no. 2, article 2450015, DOI 10.1142/s0219061324500156, https://arxiv.org/abs/2306.05746
6. Patrick Lutz, 'Results on Martin's Conjecture', Bulletin of Symbolic Logic 27 (2021), no. 2, 219-220, DOI 10.1017/bsl.2021.27, https://doi.org/10.1017/bsl.2021.27
7. Antonio Nakid Cordero, 'Martin's Conjecture in the Enumeration Degrees', arXiv:2510.19147 (2025), https://arxiv.org/abs/2510.19147
8. Adam Day, Andrew 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, arXiv:2004.00174, https://arxiv.org/abs/2004.00174
9. Andrew S. Marks, 'Uniformity, universality, and computability theory', Journal of Mathematical Logic 17 (2017), no. 1, DOI 10.1142/s0219061317500039, arXiv:1606.01976, https://arxiv.org/abs/1606.01976
10. Andrew S. Marks, 'The universality of polynomial time Turing equivalence', arXiv:1601.03343 (2016), https://arxiv.org/abs/1601.03343
11. Takayuki Kihara, Antonio Montalban, '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, arXiv:1608.05065, https://arxiv.org/abs/1608.05065
12. Simon Thomas, 'Martin's conjecture and strong ergodicity', Archive for Mathematical Logic 48 (2009), no. 8, 749-759, DOI 10.1007/s00153-009-0148-0, https://doi.org/10.1007/s00153-009-0148-0
13. S. Jackson, A. S. Kechris, A. Louveau, 'Countable Borel equivalence relations', Journal of Mathematical Logic 2 (2002), no. 1, 1-80, DOI 10.1142/s0219061302000138, https://doi.org/10.1142/s0219061302000138
14. Howard Becker, 'A characterization of jump operators', Journal of Symbolic Logic 53 (1988), no. 3, 708-728, DOI 10.2307/2274567, https://doi.org/10.2307/2274567
15. C. T. Chong, Liang Yu, 'A Pi^1_1-uniformization principle for reals', Transactions of the American Mathematical Society 361 (2009), no. 8, 4233-4245, DOI 10.1090/s0002-9947-09-04783-7, https://doi.org/10.1090/s0002-9947-09-04783-7
16. C. T. Chong, Wei Wang, Liang Yu, 'The strength of the projective Martin conjecture', Fundamenta Mathematicae 207 (2010), no. 1, 21-27, DOI 10.4064/fm207-1-2, https://doi.org/10.4064/fm207-1-2
17. Joshua Frisch, Alexander Kechris, Forte Shinko, Zoltan Vidnyanszky, 'Realizations of countable Borel equivalence relations', arXiv:2109.12486 (2021, revised through 2025), https://arxiv.org/abs/2109.12486