Martin's Conjecture for Borel Turing-invariant functions in ZFC and the unconditional fate of its cone-ergodicity consequences for countable Borel equivalence relations

Simon Thomas (2009) proved that Martin's conjecture on degree-invariant Borel maps — which entails the dichotomy asserting that every Borel Turing-invariant function on Cantor space is either constant on some Turing cone or dominates the identity on some cone — would completely restructure the descriptive-set-theoretic theory of countable Borel equivalence relations: every countable Borel equivalence relation would be either weakly universal or separated from Turing equivalence by ergodicity with respect to Martin measure; there would be continuum many pairwise Borel-incomparable weakly universal countable Borel equivalence relations; Turing equivalence would fail Borel boundedness; and the complexity of a weakly universal relation would concentrate on null sets. Every one of these statements is conditional, and the underlying conjecture itself remains open in ZFC, with only special classes of invariant functions settled (order-preserving, measure-preserving, regressive, uniformly invariant). The problem asks for a ZFC determination of Martin's conjecture for Borel Turing-invariant functions — a proof or an explicit counterexample; the four derived structural statements are recorded as consequences that remain open in ZFC.

Background

Two reals $x,y\in 2^{\mathbb{N}}$ are Turing equivalent, written $x\equiv_T y$, when each is computable from the other by an oracle Turing machine, i.e., a machine allowed to read the bits of one real as an oracle while computing the other. Turing equivalence is a Borel equivalence relation with countable classes on Cantor space, hence a countable Borel equivalence relation (CBER), and its quotient, the Turing degrees, is the central object of global computability theory; Dougherty and Kechris framed the study of $\equiv_T$ within the Borel-reducibility hierarchy of CBERs. A Turing cone with base $y$ is the upward-closed set $\{x: y\leq_T x\}$ of reals computing a fixed real $y$; cones generate Martin measure (the cone measure), a countably complete ultrafilter on the $\sigma$-algebra of Turing-invariant Borel sets — a theorem of ZFC obtained from Borel determinacy, Martin's theorem that infinite games with Borel winning conditions are determined. A property holds 'on a cone' if it holds on some Turing cone, i.e., Martin-measure almost everywhere.

Martin's conjecture, posed by Donald A. Martin in the late 1970s, asserts that degree-invariant functions on the Turing degrees are generically trivial. In its original form (formulated over ZF+DC+AD, the axiom of determinacy) it says: (I) if a Turing-invariant $f:2^{\mathbb{N}}\to 2^{\mathbb{N}}$ is not increasing almost everywhere (meaning there is no cone on which $f(x)\geq_T x$ holds for all of its elements), then $f$ is constant almost everywhere; and (II) the preordering '$f\leq_m g$ iff $f(x)\leq_T g(x)$ on a cone' prewellorders the invariant functions that are increasing almost everywhere, with the iterated Turing jump (the relativized halting problem, iterated) as its backbone. The ZFC formulation relevant here — 'Martin's conjecture on degree invariant Borel maps', the restriction of both parts to Borel homomorphisms $f:2^{\mathbb{N}}\to 2^{\mathbb{N}}$ from $\equiv_T$ to $\equiv_T$, i.e., Borel Turing-invariant functions, and the hypothesis used in the countable-Borel-equivalence-relation applications — is equivalent, by a theorem of Slaman and Steel, to the assertion that every such $f$ is either constant almost everywhere or satisfies $f(x)\equiv_T x^{(\alpha)}$ almost everywhere for some ordinal $\alpha<\omega_1$. It entails the Part-I dichotomy for such functions: (i) $f$ maps some cone into a single $\equiv_T$-class, or (ii) $x\leq_T f(x)$ for all $x$ in some cone. Four decades of work have settled only restricted classes in ZFC: Slaman and Steel (1988) proved Part II for order-preserving Borel functions (those preserving Turing reducibility) and that $\equiv_T$ is not hyperfinite (not a countable increasing union of finite Borel equivalence relations); Lutz and Siskind (published 2025) proved Part I for all order-preserving functions, introducing a class of functions they call measure-preserving, so both parts are now known for order-preserving functions; Lutz (published 2025) verified the analogous statement for regressive functions on the hyperarithmetic degrees (the degrees obtained by iterating the jump along computable ordinals); and the uniformly invariant analogs are classified (Kihara–Montalbán 2018; Bard 2020).

The descriptive-set-theoretic side concerns the classification of CBERs under Borel reducibility: $E\leq_B F$ if a Borel map $f$ satisfies $x\,E\,y\iff f(x)\,F\,f(y)$, embedding the quotient of $E$ into that of $F$. There are $\leq_B$-maximal CBERs — the universal ones, such as the orbit relation $E_\infty$ of the shift action of the free group $F_2$. Thomas's paper works with the weaker weak Borel reducibility $E\leq_B^w F$: there exists a countable-to-one Borel homomorphism $f$ (a Borel map whose point-fibers $f^{-1}(z)$ are all countable and which satisfies $x\,E\,y\Rightarrow f(x)\,F\,f(y)$); a CBER is weakly universal if every CBER is weakly reducible to it. Ergodicity is likewise taken with respect to Martin measure: $\equiv_T$ is $E$-ergodic (Thomas's E-m-ergodicity) if every Borel homomorphism from $\equiv_T$ to $E$ maps some cone into a single $E$-class. This is cone-based ergodicity, not the classical measure-theoretic strong ergodicity of countable equivalence relations, which $\equiv_T$ fails trivially since the eventual-difference relation $E_0$ on $2^{\mathbb{N}}$ is Borel reducible to $\equiv_T$ and $E_0$ is not strongly ergodic. Finally, a CBER $E$ on $X$ is Borel bounded, in the sense of Boykin and Jackson, if for every Borel $\varphi:X\to\mathbb{N}^{\mathbb{N}}$ there is a Borel homomorphism $g$ from $E$ to eventual equality $=^*$ with $\varphi(x)\leq^* g(x)$ for all $x$; boundedness is connected to the long-open increasing-union problem for hyperfinite equivalence relations, and no CBER failing Borel boundedness is known in ZFC.

Thomas (2009) proved that the conjecture for Borel functions would completely restructure this landscape. Under it: (1) every CBER $E$ satisfies exactly one of '$E$ is weakly universal' and '$\equiv_T$ is $E$-ergodic with respect to Martin measure'; (2) there are $2^{\aleph_0}$ pairwise $\leq_B$-incomparable weakly universal CBERs — products $\equiv_T\times E_\alpha$ where the $E_\alpha$ are mutually Lebesgue-ergodic non-weakly-universal CBERs obtained via Popa cocycle superrigidity, a rigidity theorem for measure-preserving group actions stating that certain actions admit no nontrivial measurable cocycles; (3) $\equiv_T$ is not Borel bounded; and (4) weak universality concentrates on null sets: for every weakly universal CBER $E$ and every Borel probability measure $\mu$, some $\mu$-conull Borel set carries a restriction that is not weakly universal. All four conclusions are conditional; none is known in ZFC. The surrounding ZFC picture is deliberately contrastive: Kechris asked whether $\equiv_T$ is universal; Marks–Slaman–Steel observed that MC implies it is not, while Marks (2016) proved that the finer resource-bounded equivalences (e.g., polynomial-time Turing equivalence) are universal, and Marks (2017) proved unconditional analogs of the concentration and cofinality phenomena in the stricter uniformly universal setting (universality witnessed uniformly by a fixed Borel generating sequence for the relation). Marks–Slaman–Steel emphasize that all other known techniques for distinguishing non-hyperfinite CBERs are measure-theoretic, so the Martin-measure route — which currently depends on the unproven conjecture — is the missing tool.

Problem Statement

The problem concerns the ZFC status of the Martin-measure (cone) structure theory of Turing equivalence; its target is Martin's conjecture restricted to Borel functions, and the derived components below are conditional consequences of it whose unconditional ZFC status remains open.

Primary component. Determine, in ZFC, the truth of Martin's conjecture restricted to Borel functions — 'Martin's conjecture on degree invariant Borel maps', the hypothesis under which Thomas proved the structural theorems below: every Borel homomorphism $f:2^{\mathbb{N}}\to 2^{\mathbb{N}}$ from $\equiv_T$ to $\equiv_T$ — equivalently, every Borel Turing-invariant function — is either constant almost everywhere with respect to Martin measure, i.e., maps some Turing cone into a single $\equiv_T$-class, or there is an ordinal $\alpha<\omega_1$ such that $f(x)\equiv_T x^{(\alpha)}$ for almost every $x$ (this jump characterization is the Slaman–Steel formulation, equivalent to the restriction of both parts of the conjecture to Borel functions). This hypothesis entails the Part-I dichotomy: every Borel Turing-invariant $f$ satisfies at least one of (i) there is a Turing cone $C$ such that $f$ maps $C$ into a single $\equiv_T$-class; (ii) there is a Turing cone $C$ such that $x\leq_T f(x)$ for all $x\in C$. (This is the ZFC formulation used in the countable-Borel-equivalence-relation applications, not the full original conjecture under the axiom of determinacy for arbitrary degree-invariant functions.) By Thomas's theorems, a proof of this statement would convert all four derived statements below into ZFC theorems.

Derived components. Each of the following statements was proved by Thomas from Martin's conjecture on degree invariant Borel maps and remains open in ZFC; each is a conditional consequence of that conjecture. (a) Weak-universality spectrum: in ZFC, do there exist $2^{\aleph_0}$ pairwise not Borel-bireducible — indeed pairwise $\leq_B$-incomparable — weakly universal countable Borel equivalence relations? Marks–Slaman–Steel also record, as a separate open question, whether there is more than one weakly universal countable Borel equivalence relation up to Borel reducibility at all — equivalent to a negative answer to Hjorth's question (whether a universal countable Borel equivalence relation $E$ with $E\subseteq F$ forces $F$ universal). (b) Cone dichotomy: in ZFC, is it true that every countable Borel equivalence relation $E$ satisfies exactly one of: $E$ is weakly universal; $\equiv_T$ is $E$-ergodic with respect to Martin measure, i.e., every Borel homomorphism from $\equiv_T$ to $E$ maps some cone into a single $E$-class? (c) Borel boundedness: in ZFC, is $\equiv_T$ not Borel bounded (in the sense of Boykin and Jackson)? Marks–Slaman–Steel likewise record, as a separate open question, whether any countable Borel equivalence relation at all fails Borel boundedness. (d) Concentration: in ZFC, is it true that whenever $E$ is a weakly universal countable Borel equivalence relation on a standard Borel space $X$ and $\mu$ is a Borel probability measure on $X$, there is a $\mu$-conull Borel set $Y\subseteq X$ (i.e., $\mu(X\setminus Y)=0$) such that $E|_Y$ is not weakly universal?

Completion boundary: a ZFC determination of Martin's conjecture for Borel Turing-invariant functions consists of a proof of the conjecture for Borel functions, or of an explicit Borel Turing-invariant counterexample together with a ZFC proof that it violates the conjecture. The derived statements (a)–(d), and the weaker unconditional questions noted under (a) and (c), lie outside the target: settling any of them does not settle the conjecture, and after a refutation of the conjecture the derived statements would stand or fall independently.

References

1. Simon Thomas, Martin's conjecture and strong ergodicity, Archive for Mathematical Logic 48(8), 749–759 (2009). DOI: 10.1007/s00153-009-0148-0, https://doi.org/10.1007/s00153-009-0148-0
2. Andrew Marks, Theodore A. Slaman, 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, Cambridge University Press (2016), pp. 493–520. DOI: 10.1017/CBO9781139519694.017, https://doi.org/10.1017/CBO9781139519694.017; preprint arXiv:1109.1875, https://arxiv.org/abs/1109.1875
3. Andrew S. Marks, The universality of polynomial time Turing equivalence, Mathematical Structures in Computer Science 28(3), 448–456 (published online 2016; print issue 2018). DOI: 10.1017/S0960129516000232, https://doi.org/10.1017/S0960129516000232; preprint arXiv:1601.03343, https://arxiv.org/abs/1601.03343
4. Andrew S. Marks, Uniformity, universality, and computability theory, Journal of Mathematical Logic 17(1), 1750003 (2017). DOI: 10.1142/S0219061317500039, https://doi.org/10.1142/S0219061317500039; preprint arXiv:1606.01976, https://arxiv.org/abs/1606.01976
5. Adam Day, 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; preprint arXiv:2004.00174 (revised February 2026), https://arxiv.org/abs/2004.00174
6. Samuel Coskey, Scott Schneider, Cardinal characteristics and countable Borel equivalence relations, Mathematical Logic Quarterly 63(3-4), 211–227 (2017). DOI: 10.1002/malq.201400111, https://doi.org/10.1002/malq.201400111; preprint arXiv:1103.2312, https://arxiv.org/abs/1103.2312
7. Patrick Lutz, 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; preprint arXiv:2305.19646, https://arxiv.org/abs/2305.19646
8. Patrick Lutz, Martin's conjecture for regressive functions on the hyperarithmetic degrees, Journal of Mathematical Logic 25(2), 2450015 (2025). DOI: 10.1142/S0219061324500156, https://doi.org/10.1142/S0219061324500156; preprint arXiv:2306.05746, https://arxiv.org/abs/2306.05746
9. Antonio Nakid Cordero, Martin's Conjecture in the Enumeration Degrees, preprint (2025). arXiv:2510.19147, https://arxiv.org/abs/2510.19147
10. Vittorio Bard, Uniform Martin's conjecture, locally, Proceedings of the American Mathematical Society 148, 5369–5380 (2020). DOI: 10.1090/proc/15159, https://doi.org/10.1090/proc/15159; preprint arXiv:1907.10766, https://arxiv.org/abs/1907.10766
11. Takayuki Kihara, Antonio Montalbán, The uniform Martin's conjecture for many-one degrees, Transactions of the American Mathematical Society 370, 9025–9044 (2018). DOI: 10.1090/tran/7519, https://doi.org/10.1090/tran/7519; preprint arXiv:1608.05065, https://arxiv.org/abs/1608.05065
12. Theodore A. Slaman, John R. Steel, Definable functions on degrees, in Cabal Seminar 81–85, Lecture Notes in Mathematics 1333, Springer, Berlin (1988), pp. 37–55. Zbl 0677.03038, https://zbmath.org/0677.03038 (reprinted in Ordinal Definability and Recursion Theory: The Cabal Seminar, Volume III, DOI: 10.1017/CBO9781139519694.015)
13. Petr Naryshkin, Andrea Vaccaro, Hyper-u-amenability and Hyperfiniteness of Treeable Equivalence Relations, Forum of Mathematics, Sigma 14, e29 (2026). DOI: 10.1017/fms.2026.10171, https://doi.org/10.1017/fms.2026.10171; preprint arXiv:2507.07891, https://arxiv.org/abs/2507.07891
14. Balázs Bursics, Zoltán Vidnyánszky, Hyperfiniteness on topological Ramsey spaces, Annals of Pure and Applied Logic 177(6), 103715 (2026). DOI: 10.1016/j.apal.2025.103715, https://doi.org/10.1016/j.apal.2025.103715; preprint arXiv:2412.01315, https://arxiv.org/abs/2412.01315
15. Alexander S. Kechris, The Theory of Countable Borel Equivalence Relations, Cambridge Tracts in Mathematics 234, Cambridge University Press (2024, online; print 2025). DOI: 10.1017/9781009562256, https://doi.org/10.1017/9781009562256
16. Charles M. Boykin, Steve Jackson, Borel boundedness and the lattice rounding property, in Advances in Logic, Contemporary Mathematics 425, American Mathematical Society, Providence, RI (2007), pp. 113–126. DOI: 10.1090/conm/425/08121, https://doi.org/10.1090/conm/425/08121
17. Randall Dougherty, Alexander S. Kechris, How many Turing degrees are there?, in Computability Theory and its Applications (Boulder, CO, 1999), Contemporary Mathematics 257, American Mathematical Society, Providence, RI (2000), pp. 83–94. DOI: 10.1090/conm/257/04029, https://doi.org/10.1090/conm/257/04029
18. Jay Williams, Isomorphism of finitely generated solvable groups is weakly universal, Journal of Pure and Applied Algebra 219(5), 1639–1644 (2015). DOI: 10.1016/j.jpaa.2014.07.002, https://doi.org/10.1016/j.jpaa.2014.07.002
19. Filippo Calderoni, Adam Clay, The isomorphism problem for finitely generated bi-orderable groups, preprint (2025). arXiv:2510.10673, https://arxiv.org/abs/2510.10673