Martin’s Conjecture for Borel Turing-Invariant Functions

OPENMajorConjectureProposed c. 1978 · Standard version

Canonical statement

Let 2ω2^\omega be the set of subsets of N\mathbb N, identified with the reals, and let T\le_T, T\equiv_T, and xx' denote Turing reducibility, Turing equivalence, and the Turing jump. A map f:2ω2ωf:2^\omega\to2^\omega is Turing-invariant if xTyx\equiv_Ty implies f(x)Tf(y)f(x)\equiv_Tf(y). A Turing cone is a set Cz={x:zTx}C_z=\{x:z\le_Tx\}. For Borel Turing-invariant maps define
fMg(z)(xCz) f(x)Tg(x), f\le_M g \quad\Longleftrightarrow\quad (\exists z)(\forall x\in C_z)\ f(x)\le_Tg(x),
and write fMgf\equiv_Mg when both fMgf\le_Mg and gMfg\le_Mf. Then: 1. Every Borel Turing-invariant ff is either constant in Turing degree on a cone, or idMf\operatorname{id}\le_Mf. 2. The quotient by M\equiv_M of the maps satisfying idMf\operatorname{id}\le_Mf is well-ordered by M\le_M, and the immediate successor of [f][f] is represented by xf(x)x\mapsto f(x)'.
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)'\).
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.

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.