Open questions from Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions: the Rudin–Keisler position of the Martin measure, the hyperarithmetic degrees, and ZF provability

Lutz and Siskind proved part 1 of Martin's Conjecture — the statement, under ZF+AD, that every Turing-invariant function on the reals is either constant on a cone of Turing degrees or above the identity on a cone — for all measure-preserving functions and all order-preserving functions, and showed that, under AD plus uniformization for relations on reals, part 1 is equivalent to a statement about the Rudin–Keisler (RK) order on ultrafilters on the Turing degrees: every nonprincipal ultrafilter RK-below the Martin measure $U_M$ is equal to $U_M$. Their paper closes with six open questions that demarcate the remaining frontier: (1) does the order-preserving dichotomy extend to the hyperarithmetic degrees; (2) is part 1 for Borel measure-preserving functions provable in ZF, given that all known proofs use Π^1_1-determinacy, which exceeds ZF; (3) is there a nonprincipal ultrafilter on the Turing degrees strictly RK-below $U_M$; (4) is there an ultrafilter other than $U_M$ itself weakly RK-equivalent to $U_M$; (5) are the Lebesgue or Baire ultrafilters RK-below $U_M$; (6) is there an ultrafilter strictly RK-above $U_M$. Negative answers to (3) and (4) together would prove part 1 of Martin's Conjecture in full.

Background

The Turing degrees $\mathcal{D}_T$ are the equivalence classes of infinite binary sequences (reals) under Turing reducibility $x ≤_T y$, which means that $x$ is computable by a Turing machine with oracle access to $y$. A function $f : 2^ω → 2^ω$ on Cantor space is Turing-invariant if $x ≡_T y$ implies $f(x) ≡_T f(y)$, so that $f$ induces a function on $\mathcal{D}_T$. Martin's Conjecture, formulated by Donald A. Martin in the late 1970s, is a proposed classification of all reasonably definable Turing-invariant functions, formalized in the theory ZF + AD + DC_R. Here AD (the Axiom of Determinacy) asserts that every two-player game with integer moves is determined; it contradicts the full Axiom of Choice and is the standard ambient theory for structural results about the degrees, while DC_R (Dependent Choice for reals) is a weak choice principle. Part 1 of the conjecture states that every Turing-invariant function is either constant on a cone or above the identity on a cone, i.e. $f(x) ≥_T x$ holds for every $x$ on some cone; part 2 states that every Turing-invariant function above the identity is equal, on a cone, to some transfinite iterate of the Turing jump — the operation $x ↦ x'$ sending a real to its relativized halting problem, which is the canonical way to produce a real strictly more complicated than $x$. A cone is a set of degrees of the form $\{ \deg(y) : y ≥_T x \}$ for some fixed real $x$; a property holds on a cone if it holds on some cone. By Martin's cone theorem (provable in ZF+AD), every set of Turing degrees either contains a cone or is disjoint from one, so the cones generate a countably complete ultrafilter $U_M$ on $\mathcal{D}_T$, the Martin measure (or cone measure): $A ∈ U_M$ if and only if $A$ contains a cone. Being constant on a cone is thus convergence with respect to this measure. The conjecture is open in general and is motivated by the goal of explaining the special role of the Turing jump among all natural operations on degrees; Montalbán's 2019 survey in the Notices of the AMS gives an overview.

Before 2023 the principal known cases were: Martin's Conjecture for regressive functions (functions with $f(x) ≤_T x$ for all $x$; Slaman and Steel, in ZF+AD), for uniformly Turing-invariant functions (functions whose invariance is witnessed uniformly by a single map on indices of oracle computation procedures; Steel, and Slaman and Steel), and part 2 of the conjecture for Borel (Borel-measurable) order-preserving functions (Slaman and Steel). A function is order-preserving if $x ≤_T y$ implies $f(x) ≤_T f(y)$.

Lutz and Siskind proved part 1 of Martin's Conjecture for all order-preserving functions. Their route introduces a class of functions well behaved with respect to the Martin measure: a Turing-invariant function $f$ is measure-preserving (a computability-theoretic notion, unrelated to measure-preserving transformations in ergodic theory) if for every real $a$ there is a real $b$ such that $f(x) ≥_T a$ whenever $x ≥_T b$ — that is, every real is below $f$ on a cone. They proved, first, that part 1 holds for all measure-preserving functions in ZF+AD+DC_R (by two proofs, one of which uses uniformization for relations on reals — the principle that every binary relation on the reals contains a function with the same domain, denoted Uniformization_R); and second, that every order-preserving function is either constant on a cone or measure-preserving. For Borel functions they calibrated the determinacy needed. Borel determinacy (determinacy of games whose payoff set is Borel) is provable in ZF alone (Martin, 1975), whereas Π^1_1-determinacy (determinacy of games with coanalytic payoff) follows from the existence of a measurable cardinal (Martin, 1970) and is not provable in ZF. When their proof of part 1 for measure-preserving functions is restricted to Borel functions, it still requires Π^1_1-determinacy: to give a measure-preserving $f$ a modulus (an increasing function $g$ with $g(x) ≥_T x$ such that $f(y) ≥_T x$ whenever $y ≥_T g(x)$) one must uniformize a coanalytic relation, and the Kondô–Addison uniformization theorem (every coanalytic relation on the reals has a coanalytic uniformization) yields only a Π^1_1 modulus, so determinacy must subsequently be applied to sets defined from a non-Borel object. For order-preserving Borel functions the paper gives a separate argument that works in ZF, but for measure-preserving Borel functions no ZF proof is known — this is the source of Question 2.

The paper's second conceptual contribution is an ultrafilter reformulation of part 1. For ultrafilters $U$ on a set $X$ and $V$ on a set $Y$, $U$ is Rudin–Keisler (RK) below $V$, written $U ≤_{RK} V$, if $U = f_*(V)$ for some function $f : Y → X$, where $f_*(V)$ is the pushforward ultrafilter $\{ A ⊆ X : f^{-1}(A) ∈ V \}$; $U$ and $V$ are weakly RK-equivalent if each is RK-below the other. In classical ZFC ultrafilter theory, the normal ultrafilters on a measurable cardinal are exactly the minimal nonprincipal ultrafilters on that cardinal, and the reformulation casts part 1 of Martin's Conjecture as the analogous minimality statement for the Martin measure: in ZF+AD+Uniformization_R, part 1 is equivalent to the statement that every nonprincipal ultrafilter $V$ on $\mathcal{D}_T$ with $V ≤_{RK} U_M$ is equal to $U_M$ (Theorem 5.15 of the paper). Under AD, Lebesgue measure on $2^ω$ and the Baire (comeager) filter each induce countably complete ultrafilters $U_L$ and $U_B$ on $\mathcal{D}_T$, by Kolmogorov's zero–one law together with the regularity of all sets of reals under AD; the paper proves that neither $U_L$ nor $U_B$ is RK-above $U_M$, but whether either is RK-below $U_M$ is open — a question first raised by Andrew Marks and Adam Day independently of Lutz and Siskind. The paper also records that every ultrafilter on an ordinal below Θ (the least ordinal that is not a surjective image of the reals, a well-behaved cardinal under AD) is RK-below $U_M$, so the question of what lies RK-below $U_M$ is genuinely a question about ultrafilters on the Turing degrees themselves.

Finally, the paper studies other degree structures. The hyperarithmetic degrees are the degrees induced by hyperarithmetic reducibility $≤_h$ (uniform relative computability through all computable ordinals; the analog of the Turing jump there is the hyperjump), and the arithmetic degrees are induced by arithmetical reducibility (computability relative to any finite Turing-jump iteration, with the ω-jump as jump operator). Both satisfy the analog of Martin's cone theorem, so a version of Martin's Conjecture can be stated in each. The picture is uneven: for uniformly invariant functions the conjecture fails in the arithmetic degrees (Marks–Slaman–Steel) but holds in the hyperarithmetic degrees (an unpublished observation of Slaman and Steel cited in their Cabal Seminar paper); for regressive functions it holds in the hyperarithmetic degrees (Lutz, 2023) and is open in the arithmetic degrees; and part 1 for order-preserving functions is outright false in the arithmetic degrees (an unpublished construction of Slaman and Steel, reported as Theorem 6.3 of Lutz–Siskind). Lutz and Siskind show that their measure-preserving results transfer to these structures, but the implication from order-preserving to constant-or-measure-preserving has no known hyperarithmetic analog, which is exactly what leaves part 1 for order-preserving functions on the hyperarithmetic degrees open.

Problem Statement

The problem is to answer the six open questions posed in Section 7 of Lutz–Siskind (2024), which together chart the remaining routes to part 1 of Martin's Conjecture. Throughout, $\mathcal{D}_T$ denotes the Turing degrees, $U_M$ the Martin measure, $≤_{RK}$ the Rudin–Keisler order on ultrafilters, and 'weakly RK-equivalent' means mutually RK-below; 'above the identity on a cone' means that $f(x) ≥_T x$ (or $f(x) ≥_h x$ for hyperarithmetic reducibility) holds for every $x$ on some cone; all ultrafilters in Questions 3–6 are nonprincipal ultrafilters on $\mathcal{D}_T$, considered in the ambient theory ZF+AD (with dependent choice for reals as needed).

Question 1 (hyperarithmetic degrees). Does part 1 of Martin's Conjecture hold for all order-preserving functions on the hyperarithmetic degrees? That is, in the analog of the usual ambient theory for the hyperarithmetic degrees, is every hyperarithmetically invariant function $f : 2^ω → 2^ω$ that is order-preserving for hyperarithmetic reducibility ($x ≤_h y$ implies $f(x) ≤_h f(y)$) either constant on a cone of hyperarithmetic degrees or above the identity on a cone of hyperarithmetic degrees?

Question 2 (ZF provability). Is part 1 of Martin's Conjecture for measure-preserving functions, restricted to Borel functions, provable in ZF? Concretely: must every Borel Turing-invariant measure-preserving function be above the identity on a cone, provably using only Borel determinacy? The known proofs require Π^1_1-determinacy, which is not provable in ZF.

Question 3 (below the Martin measure). Is there any ultrafilter on the Turing degrees which is strictly below the Martin measure in the Rudin–Keisler order — that is, a nonprincipal ultrafilter $V$ on $\mathcal{D}_T$ with $V ≤_{RK} U_M$ that is not weakly RK-equivalent to $U_M$ (in particular $V ≠ U_M$)?

Question 4 (other weak equivalents). Is there any ultrafilter on the Turing degrees besides the Martin measure itself which is weakly Rudin–Keisler equivalent to the Martin measure?

Question 5 (the Lebesgue and Baire ultrafilters). Are the Lebesgue ultrafilter $U_L$ or the Baire ultrafilter $U_B$ on the Turing degrees below the Martin measure in the Rudin–Keisler order? This is a special case of Question 3.

Question 6 (above the Martin measure). Is there any ultrafilter on the Turing degrees which is strictly above the Martin measure in the Rudin–Keisler order — a nonprincipal ultrafilter $V$ on $\mathcal{D}_T$ with $U_M ≤_{RK} V$ that is not weakly RK-equivalent to $U_M$ (in particular $V ≠ U_M$)?

Logical relationships, as stated in the source: a negative answer to Questions 3 and 4 together would imply part 1 of Martin's Conjecture (indeed, in ZF+AD+Uniformization_R, part 1 is equivalent to the statement that every nonprincipal ultrafilter on $\mathcal{D}_T$ that is RK-below $U_M$ is equal to $U_M$); Question 5 is a special case of Question 3; Question 6 has no direct bearing on Martin's Conjecture but concerns the same structure. The common objective is to determine the position of the Martin measure in the Rudin–Keisler order on ultrafilters on the Turing degrees — which, by the reformulation above, is the ultrafilter-theoretic content of part 1 of Martin's Conjecture — and to settle the two robustness questions (Questions 1 and 2) left open by the Lutz–Siskind proof.

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):319–367 (published online April 2024), DOI 10.1090/jams/1046; preprint arXiv:2305.19646. https://doi.org/10.1090/jams/1046
2. Patrick Lutz, Martin's conjecture for regressive functions on the hyperarithmetic degrees, preprint (2023), arXiv:2306.05746. https://arxiv.org/abs/2306.05746
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, pages 493–520, Cambridge University Press (2016), DOI 10.1017/CBO9781139519694.017; preprint arXiv:1109.1875 (2011). https://doi.org/10.1017/CBO9781139519694.017
4. 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
5. John R. Steel, A classification of jump operators, Journal of Symbolic Logic 47(2):347–358 (1982), DOI 10.2307/2273146. https://doi.org/10.2307/2273146
6. Theodore A. Slaman and John R. Steel, Definable functions on degrees, in Cabal Seminar 81–85, Lecture Notes in Mathematics, Springer (1988), DOI 10.1007/bfb0084969. https://doi.org/10.1007/bfb0084969
7. Donald A. Martin, Borel Determinacy, Annals of Mathematics 102(2):363–371 (1975), DOI 10.2307/1971035. https://doi.org/10.2307/1971035
8. Donald A. Martin, Measurable cardinals and analytic games, Fundamenta Mathematicae 66:287–291 (1970), DOI 10.4064/fm-66-3-287-291. https://doi.org/10.4064/fm-66-3-287-291
9. Matthew Harrison-Trainor and Syed Akbari, Computable learning of natural hypothesis classes, preprint (2024), arXiv:2407.16663. https://arxiv.org/abs/2407.16663
10. Douglas Blue, Can Philosophy do Anything for Set Theory?, Journal of Philosophical Logic (published online March 2026), DOI 10.1007/s10992-026-09829-7. https://doi.org/10.1007/s10992-026-09829-7
11. James Walsh, On the Hierarchy of Natural Theories, Bulletin of Symbolic Logic 32(1):47–81 (published online December 2025), DOI 10.1017/bsl.2025.10137. https://doi.org/10.1017/bsl.2025.10137
12. Kojiro Higuchi and Patrick Lutz, A Note on a Conjecture of Sacks: It is Harder to Embed Height Three Partial Orders than Height Two Partial Orders, preprint (2023), arXiv:2309.01876. https://arxiv.org/abs/2309.01876
13. Antonio Nakid Cordero, Martin's Conjecture in the Enumeration Degrees, preprint (2025), arXiv:2510.19147. https://arxiv.org/abs/2510.19147
14. Ashutosh Kumar, Set theory and Turing degrees, in Selected Topics in Combinatorial Analysis, Part II (Zbornik radova), pages 357–373, Mathematical Institute of the Serbian Academy of Sciences and Arts (2025), DOI 10.64191/zr24040410110. https://doi.org/10.64191/zr24040410110