Martin's Conjecture: the classification of Turing-invariant functions under the axiom of determinacy (parts 1 and 2)

Martin's conjecture, formulated by Donald A. Martin in the 1970s, proposes a complete classification of Turing-invariant functions — functions on the reals that respect Turing equivalence and hence induce functions on the Turing degrees — under the axiom of determinacy (ZF + DC + AD). Part 1 asserts that every such function is either constant on a cone of Turing degrees or computes the identity on a cone; part 2 asserts that the Martin order (Turing reducibility on a cone), restricted to functions above the identity, is a prewellorder in which the successor operation is the Turing jump, so that every non-constant Turing-invariant function is, on a cone, a transfinite iterate of the jump. As of August 2026 the conjecture is open in full generality. Part 1 is proved only for restricted classes — regressive, uniformly Turing-invariant, order-preserving, and measure-preserving functions (the last two due to Lutz and Siskind, Journal of the AMS 2024) — and part 2 only for uniformly invariant and Borel order-preserving functions. The surviving core of part 1 consists of functions 'off to the side' of the constant functions in the Martin order, and part 2 is open even at the level of comparability for arbitrary functions above the identity. The conjecture is false in ZFC, so the determinacy-free versions make sense only for definable (e.g., Borel) functions, and those remain open as well.

Background

A real here means an element x of Cantor space $2^\omega$, the set of infinite binary sequences. One real is Turing reducible to another, written $x \le_T y$, if x can be computed by a Turing machine allowed to consult y as an oracle; $x \equiv_T y$ means each computes the other, and the equivalence classes are the Turing degrees. A function $f : 2^\omega \to 2^\omega$ is Turing-invariant if $x \equiv_T y$ implies $f(x) \equiv_T f(y)$, so that f induces a function on the Turing degrees. The familiar constructions that turn a real into another real — the identity, the Turing jump $x \mapsto x'$ (the halting problem relativized to x), its transfinite iterates $x \mapsto x^{(\alpha)}$ for countable ordinals $\alpha$, and relatives such as the hyperjump (the analogue of the jump for $\Pi^1_1$ predicates) — are all Turing-invariant, and the empirical lore of computability theory is that the natural Turing-invariant functions are exactly the jump and its iterates. Martin's conjecture is the proposed precise theorem behind this lore: modulo behavior on a set of degrees so large that its complement is negligible, the only Turing-invariant functions should be the constants, the identity, and the transfinite iterates of the jump. Beyond its intrinsic interest for the structure theory of the Turing degrees, the conjecture would explain the unique role of the Turing jump, would sharply constrain definable degree-invariant solutions to Post's problem (the classical problem of producing an intermediate effectively enumerable degree between the computable degrees and the halting problem), and — through its Borel instance — yield ergodicity and universality dichotomies for Turing equivalence viewed as a countable Borel equivalence relation, as recounted in the survey of Marks, Slaman, and Steel.

The conjecture is stated in the theory ZF + DC + AD rather than ZFC. AD, the axiom of determinacy, asserts that in every two-player game in which the players alternately choose natural numbers and the winner is decided by membership of the resulting real in a predetermined payoff set, one of the players has a winning strategy; AD contradicts the full axiom of choice but is equiconsistent with the existence of infinitely many Woodin cardinals, and DC (dependent choice) is the amount of choice needed for basic analysis. The 'negligible' sets are described by cones: the cone above a real a is the set of all x with $x \ge_T a$. Under AD, Martin's cone theorem states that every set of Turing degrees either contains a cone or is disjoint from one, so the cones define a countably complete 0-1-valued measure — Martin measure — on the Turing-invariant sets, and 'on a cone' plays the role of 'almost everywhere'. The choice axiom cannot be dropped: with a well-ordering of the reals one can define pathological Turing-invariant functions, and the failure is explicit — Chong and Yu constructed uniformly Turing-invariant $\Pi^1_1$ counterexamples to the conjecture in ZFC + V = L, and Lutz and Siskind construct, in ZFC alone, an order-preserving counterexample. Determinacy-free versions of the conjecture therefore make sense only for definable (e.g., Borel) functions. The metamathematics calibrates how much determinacy is needed: Chong, Wang, and Yu proved that the restriction of Steel's uniform part-2 theorem (part 2 for uniformly Turing-invariant functions) to $\Pi^1_{2n+1}$ functions is equivalent to $\Sigma^1_{2n+2}$ determinacy for every $n$.

For Turing-invariant f and g, write $f \le_M g$ if $f(x) \le_T g(x)$ on a cone (the Martin order) and $f \equiv_M g$ if they are Turing equivalent on a cone. Martin's conjecture, first stated in print in the 1978 Cabal Seminar proceedings (Cabal Seminar 76–77, Lecture Notes in Mathematics 689, p. 281; the original citation is reproduced in the Marks–Slaman–Steel survey), asserts, assuming ZF + DC + AD:

Part 1. Every Turing-invariant $f : 2^\omega \to 2^\omega$ is either constant on a cone (Turing equivalent to a fixed real on a cone) or above the identity on a cone ($f(x) \ge_T x$ on a cone).

Part 2. The Martin order restricted to Turing-invariant functions that are above the identity on a cone is a prewellorder — a well-founded, linear quasi-order, that is, linear on $\equiv_M$-classes with no infinite descending chains — in which the successor of any f is the jump $x \mapsto f(x)'$; informally, every Turing-invariant function above the identity is equal on a cone to the $\alpha$-th transfinite iterate of the Turing jump, the comparison between two such functions being given by the comparison of their ordinals.

Part 1 is known for four classes of functions, none of which covers the general case. A function is regressive if $f(x) \le_T x$ for all x; the regressive case (such an f is either $\equiv_M$ the identity or constant on a cone) is due to Slaman and Steel, refining an unpublished argument of Martin for the regressive measure-preserving subcase. A function is uniformly Turing-invariant if a single function u on indices converts every pair (i, j) of indices witnessing $x \equiv_T y$ into a pair of indices witnessing $f(x) \equiv_T f(y)$; the uniform case of part 1 is due to Slaman and Steel. A function is order-preserving if $x \le_T y$ implies $f(x) \le_T f(y)$, and — in the sense relevant here — measure-preserving if for every real a, $f(x) \ge_T a$ on a cone, i.e. the function 'goes to infinity' in the degree ordering. Lutz and Siskind (Journal of the American Mathematical Society, 2024) proved part 1 for all measure-preserving functions and showed that every non-trivial order-preserving function is measure-preserving, thereby settling part 1 for all order-preserving functions.

Part 2 is known for uniformly Turing-invariant functions (Steel 1982, who also computed the ranks of the standard jump operators) and for Borel (definable by countable set operations) order-preserving functions (Slaman and Steel 1988: such an f satisfies $f(x) \equiv_T x^{(\alpha)}$ on a cone for some countable $\alpha$), the latter via a generalization of the Posner–Robinson theorem — the theorem that for every noncomputable real x there is a real y with $x \oplus y \equiv_T y'$ — through all countable iterates of the jump. Lutz and Siskind add a comparability result in the direction of part 2: if f and g are Turing-invariant and above the identity and g is constant on the fibers of f (whenever $f(x) \equiv_T f(y)$ also $g(x) \equiv_T g(y)$), then $f \le_M g$.

After these results, the Martin order under AD has the following known shape. The constant functions form an initial segment isomorphic to the Turing degrees, and the Lutz–Siskind measure-preserving theorem says precisely that the identity function is a least upper bound of the constants: any function Martin-above every constant function is above the identity. Above the identity sits the jump hierarchy, whose order type part 2 asserts to be a prewellorder with the jump as successor. What remains of part 1 is exactly the 'off to the side' case: a priori a Turing-invariant function could be Martin-incomparable with (some or all) nonzero constant functions — neither eventually constant, nor eventually below a fixed constant, nor dominating every fixed degree. Two further markers delimit the difficulty. First, Steel conjectured that every Turing-invariant f is $\equiv_M$ to some uniformly Turing-invariant g; this uniformization conjecture would imply the full conjecture and is open, while Day and Marks showed that a positive answer to an old question of Slaman and Steel (whether Turing equivalence is an increasing union of Borel equivalence relations, none containing a uniformly computable infinite sequence) would produce a $(\equiv_T, \equiv_m)$-invariant function that is not uniformly invariant on any pointed perfect set (a closed set of reals all of whose members compute the tree defining it) — evidence that the uniformization route is delicate. Second, Lutz and Siskind proved that, under AD together with the uniformization principle for reals, part 1 is equivalent to a statement about ultrafilters: writing $U \le_{RK} V$ (Rudin–Keisler below) when U is the pushforward of V along some function, part 1 holds if and only if every nonprincipal ultrafilter on the Turing degrees that is Rudin–Keisler below the Martin measure is literally equal to the Martin measure.

The conjecture has also been tested against neighboring degree structures, with informative results. Kihara and Montalbán proved the many-one-degrees analogue of the uniform case (a one-to-one correspondence with the Wadge degrees, the degrees of sets of reals under continuous preimage reduction). Lutz verified the regressive case on the hyperarithmetic degrees (the degree structure of hyperarithmetic reducibility, where computations may run along computable well-orderings), answering a question of Slaman and Steel. Kihara proved a Weihrauch-degree analogue (Weihrauch reducibility compares mathematical problems by uniform computable transformations; the relevant variant is parallelized continuous strong Weihrauch reducibility on single-valued real functions), showing under AD that these degrees are well-ordered with the Turing jump as successor; the classical conjecture remains open (the paper calls it one of the most prominent open problems in computability theory), as does the question of whether such well-ordering results hold in ZFC beyond the Borel and projective classes. Nakid Cordero (2025) showed that in the enumeration degrees (an extension of the Turing degrees based on enumeration reducibility, where information is transmitted by enumerating positive facts) the analogue admits a much wider spectrum of behavior even for uniformly invariant functions, with the main positive result that such functions are locally constant, increasing, or above the skip, a jump-like operator specific to the enumeration degrees. None of these touches the general Turing-degree case, which remains one of the central open problems of computability theory; Montalbán's 2019 Notices of the AMS article gives a general-audience account.

Problem Statement

Assume ZF + DC + AD. Let f and g range over Turing-invariant functions $f : 2^\omega \to 2^\omega$ (functions respecting Turing equivalence, hence inducing functions on the Turing degrees). Recall that f is constant on a cone if $f(x) \equiv_T y_0$ for some fixed real $y_0$ and all x in some cone {x : $x \ge_T a$}; f is above the identity on a cone if $f(x) \ge_T x$ on some cone; and $f \le_M g$ if $f(x) \le_T g(x)$ on some cone (the Martin order).

Part 1. Is every Turing-invariant function either constant on a cone or above the identity on a cone?

Part 2. Is the Martin order $\le_M$, restricted to Turing-invariant functions that are above the identity on a cone, a prewellorder in which the successor of any f is the jump $x \mapsto f(x)'$? The standard informal consequence would be that every Turing-invariant function above the identity is equal on a cone to the $\alpha$-th transfinite iterate of the Turing jump for some ordinal $\alpha$, with the comparison of two such functions given by the comparison of their ordinals.

The problem is resolved by proving both parts in this generality — for all Turing-invariant functions, with no uniformity, order-preservation, measure-preservation, Borelness, or other definability hypothesis — or by refuting either part under ZF + DC + AD with a Turing-invariant counterexample (for part 1: a function neither constant on any cone nor above the identity on any cone; for part 2: a failure of the prewellordering or of the jump-successor clause). The classes already settled — regressive, uniformly Turing-invariant, order-preserving, and measure-preserving functions for part 1, and uniformly invariant and Borel order-preserving functions for part 2 — do not count toward closure: the open core of part 1 is the case of functions 'off to the side' of the constant functions (Martin-incomparable with the nonzero constants, neither eventually constant nor measure-preserving), and part 2 is open for arbitrary functions above the identity, including their mere comparability in the Martin order. Steel's uniformization conjecture and the Borel/determinacy-free versions (for instance, whether part 1 for Borel measure-preserving functions is provable in ZF alone) are natural derived sub-questions of the same program and are recorded as surrounding context; resolving them is not required for closure of the conjecture itself.

References

1. 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), pp. 319-367 (published online 2 April 2024; print issue April 2025). DOI: 10.1090/jams/1046. Preprint arXiv:2305.19646. https://doi.org/10.1090/jams/1046
2. 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-519. DOI: 10.1017/cbo9781139519694.017. Preprint arXiv:1109.1875. https://doi.org/10.1017/cbo9781139519694.017
3. Theodore A. Slaman and John R. Steel, 'Definable functions on degrees', in Cabal Seminar 81-85, Lecture Notes in Mathematics 1333, Springer, Berlin/Heidelberg (1988), pp. 37-55. DOI: 10.1007/bfb0084969 (reprinted in Ordinal Definability and Recursion Theory: The Cabal Seminar Volume III, DOI: 10.1017/cbo9781139519694.015). https://doi.org/10.1007/bfb0084969
4. John R. Steel, 'A classification of jump operators', Journal of Symbolic Logic 47(2) (1982), pp. 347-358. DOI: 10.2307/2273146. https://doi.org/10.2307/2273146
5. C. T. Chong and Liang Yu, 'A $\Pi^1_1$-uniformization principle for reals', Transactions of the American Mathematical Society 361(8) (2009), pp. 4233-4245. DOI: 10.1090/s0002-9947-09-04783-7. https://doi.org/10.1090/s0002-9947-09-04783-7
6. C. T. Chong, Wei Wang, and Liang Yu, 'The strength of the projective Martin conjecture', Fundamenta Mathematicae 207(1) (2010), pp. 21-27. DOI: 10.4064/fm207-1-2. https://doi.org/10.4064/fm207-1-2
7. Takayuki Kihara, 'Topological reducibilities for discontinuous functions and their structures', Israel Journal of Mathematics 252(1) (2022), pp. 461-500. DOI: 10.1007/s11856-022-2367-6. Preprint arXiv:1906.10573. https://doi.org/10.1007/s11856-022-2367-6
8. Patrick Lutz, 'Martin's conjecture for regressive functions on the hyperarithmetic degrees', Journal of Mathematical Logic 25(2), article 2450015 (published online 2024). DOI: 10.1142/s0219061324500156. Preprint arXiv:2306.05746. https://doi.org/10.1142/s0219061324500156
9. Antonio Nakid Cordero, 'Martin's Conjecture in the Enumeration Degrees', preprint arXiv:2510.19147 (2025, v2 November 2025). https://arxiv.org/abs/2510.19147
10. Adam Day and Andrew Marks, 'On a question of Slaman and Steel', preprint arXiv:2004.00174 (2020; v2 revised 16 February 2026). https://arxiv.org/abs/2004.00174
11. Vittorio Bard, 'Uniform Martin's conjecture, locally', preprint arXiv:1907.10766 (2019). https://arxiv.org/abs/1907.10766
12. Takayuki Kihara and Antonio Montalbán, 'The uniform Martin's conjecture for many-one degrees', Transactions of the American Mathematical Society 370(12) (2018), pp. 9025-9044. DOI: 10.1090/tran/7519. Preprint arXiv:1608.05065. https://doi.org/10.1090/tran/7519
13. Antonio Montalbán, 'Martin's Conjecture: A Classification of the Naturally Occurring Turing Degrees', Notices of the American Mathematical Society 66(8) (September 2019), pp. 1209-1215. DOI: 10.1090/noti1940. https://doi.org/10.1090/noti1940