Martin’s Conjecture for Borel Turing-Invariant Functions
OPENMajorConjectureProposed c. 1978 · Standard version
Canonical statement
Let be the set of subsets of , identified with the reals, and let , , and denote Turing reducibility, Turing equivalence, and the Turing jump. A map is Turing-invariant if implies . A Turing cone is a set . For Borel Turing-invariant maps define
and write when both and . Then: 1. Every Borel Turing-invariant is either constant in Turing degree on a cone, or . 2. The quotient by of the maps satisfying is well-ordered by , and the immediate successor of is represented by .
View source LaTeX
Let \(2^\omega\) be the set of subsets of \(\mathbb N\), identified with the reals, and let \(\le_T\), \(\equiv_T\), and \(x'\) denote Turing reducibility, Turing equivalence, and the Turing jump. A map \(f:2^\omega\to2^\omega\) is Turing-invariant if \(x\equiv_Ty\) implies \(f(x)\equiv_Tf(y)\). A Turing cone is a set \(C_z=\{x:z\le_Tx\}\). For Borel Turing-invariant maps define
\[
f\le_M g
\quad\Longleftrightarrow\quad
(\exists z)(\forall x\in C_z)\ f(x)\le_Tg(x),
\]
and write \(f\equiv_Mg\) when both \(f\le_Mg\) and \(g\le_Mf\). Then:
1. Every Borel Turing-invariant \(f\) is either constant in Turing degree on a cone, or \(\operatorname{id}\le_Mf\).
2. The quotient by \(\equiv_M\) of the maps satisfying \(\operatorname{id}\le_Mf\) is well-ordered by \(\le_M\), and the immediate successor of \([f]\) is represented by \(x\mapsto f(x)'\).Notes
Slaman and Steel proved major regressive, uniformly invariant, and order-preserving cases, and later work proves Part 1 for broader measure-preserving and order-preserving classes. The two-part classification is still unknown for arbitrary Borel Turing-invariant maps.
Martin proposed the conjecture in the late 1970s, and it first appeared in print in the 1978 Victoria Delfino problem list, so the date is approximate. The unrestricted formulation for all Turing-invariant maps is normally stated under determinacy axioms; restricting to Borel maps gives a precise ZFC version, which is the definable form recorded here.
References (4)
- [KechrisMoschovakis1978VictoriaDelfino]
Appendix: The Victoria Delfino problems
Open ↗Alexander S. Kechris and Yiannis N. Moschovakis, eds. · 1978 · misc
- [SlamanSteel1988DefinableDegrees]
Definable functions on degrees
Open ↗Theodore A. Slaman and John R. Steel · 1988 · misc
- [Montalban2019Martin]
Martin’s Conjecture: A Classification of the Naturally Occurring Turing Degrees
Open ↗Antonio Montalbán · 2019 · misc
- [LutzSiskind2024Martin]
Part 1 of Martin’s Conjecture for order-preserving and measure-preserving functions
Open ↗Patrick Lutz and Benjamin William Siskind · 2024 · misc
The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.