Martin's Conjecture

• A Turing invariant function is a function $f\colon 2^\mathbb{N} \to 2^\mathbb{N}$ such that for all $x, y \in 2^\mathbb{N}$, if $x \equiv_T y$ then $f(x) \equiv_T f(y)$.
• A cone of Turing degrees is a set $A \subseteq 2^\mathbb{N}$ of the form $\{y \in 2^\mathbb{N} \mid x \leq_T y\}$ for some fixed $x$.
• The Martin order, denoted $\leq_M$, is the partial order on Turing invariant functions defined by setting $f \leq_M g$ if there is some cone of Turing degrees such that for all $x$ in the cone, $f(x) \leq_T g(x)$.
• Turing invariant functions $f, g \colon 2^\mathbb{N} \to 2^\mathbb{N}$ are Turing equivalent if $f \leq_M g$ and $g \leq_M f$. Equivalently, if for all $x$ in some cone of Turing degrees, $f(x) \equiv_T g(x)$.
• $\mathsf{AD}$ refers to the Axiom of Determinacy. $\mathsf{DC}$ refers to the Axiom of Dependent Choice.

• Steel proved the second part of the conjecture for functions which are uniformly Turing invariant. Later, Slaman and Steel proved the first part of the conjecture for such functions [SS88].
• Slaman and Steel proved the conjecture for "regressive" functions—i.e. functions $f$ such that for all $x$ in some cone of Turing degrees, $f(x) \leq_T x$.
• Slaman and Steel proved the second part of the conjecture functions which are order-preserving and Borel measurable. Later, Lutz and Siskind proved the first part of the conjecture for functions which are order-preserving.
• Slaman and Steel constructed a counterexample to a version of Martin's Conjecture for the arithmetic degrees.

Martin's Conjecture was first posed by Donald Martin in the 1960s or 1970s and is one of the five original "Victoria Delfino" problems in descriptive set theory. It is sometimes claimed that it explains the phenomenon that all "naturally occurring" Turing degrees are simply the Halting Problem or its iterates.

There are several other well-known conjectures that either imply or contradict Martin's Conjecture, including Steel's Conjecture (which states that every Turing invariant function is Martin equivalent to a uniformly Turing invariant function) and Kechris's Conjecture (which states that Turing equivalence is a universal countable Borel equivalence relation and which is known to contradict Martin's Conjecture).