Martin's Conjecture for Definable Turing-Invariant Functions

Martin's Conjecture for Definable Turing-Invariant Functions

Definitions and mathematical statement

Assume the Axiom of Determinacy in the source's ZF setting. For subsets of ${\mathbb{N}}$, $X\le_TY$ means $X$ is computable with oracle $Y$, and $X'$ is the oracle halting problem. A cone is $\{X:X\ge_TA\}$ for some $A$. A function $f:\mathcal P({\mathbb{N}})\to\mathcal P({\mathbb{N}})$ is Turing-invariant if $X\equiv_TY$ implies $f(X)\equiv_Tf(Y)$. Put $f\le_Mg$ when $f(X)\le_Tg(X)$ throughout some cone. Martin's two assertions are: every such $f$ is constant in Turing degree on a cone or satisfies $X\le_Tf(X)$ on a cone; and the functions in the latter class, modulo cone equivalence, are well-ordered by $\le_M$, with successor $[f]\mapsto[X\mapsto f(X)']$. "Increasing" here means above the identity, not necessarily order-preserving. The jump-iterate slogan is expressed by this precise successor law, without inventing a convention for every transfinite iterate.

Formulation and concept references: [S1].

Short English statement

Under determinacy, are Turing-invariant functions eventually constant or above the identity, with the nonconstant cone-equivalence classes well-ordered and successive classes obtained by the Turing jump?

Research attempt

GPT-6 Astra Ultra; 27 September 2026. Status: UNRESOLVED.

I work in the stated $\mathsf{ZF}+\mathsf{AD}$ setting. The main question is not whether familiar examples form a jump hierarchy, but whether every Turing-invariant function eventually belongs to the asserted structure. This attempt derives the cone decision principle, settles functions with countable degree range, and separates strict jump growth from the much stronger successor assertion.

How determinacy supplies a cone.

Let $A\subseteq2^{\mathbb N}$ be invariant under Turing equivalence. Play the ordinary infinite binary game in which the two players alternately contribute bits to a real $Z$. Player I wins when $Z\in A$. By determinacy one player has a winning strategy $\sigma$, coded by a real. Given any real $X\ge_T\sigma$, let the other player put the successive bits of $X$ on that player's turns, while the winning player follows $\sigma$. The resulting play $Z$ computes $X$ from those turns. Conversely $X$ computes the whole play, because it computes $\sigma$ and can simulate each finite stage. Thus $Z\equiv_T X$. If I has the winning strategy then $X\in A$ for every $X\ge_T\sigma$; if II has it then $X\notin A$ throughout that cone. This proves the cone theorem in the form needed here.

Two cones with bases $A,B$ contain the cone with base $A\oplus B$. It follows that the cone-containing invariant sets form an ultrafilter: one of a set and its complement contains a cone, never both. This is a statement about invariant sets. An arbitrary set of reals, such as the reals with first bit one, need not contain or avoid a cone.

Countable degree range is eventually constant.

For this paragraph use countable choice for sets of reals, a standard consequence of $\mathsf{AD}$ recorded in [E1, Section 1.4]. No axiom of dependent choice beyond the stated setting is inserted. If $C_j$ is a sequence of cones, choose bases $A_j$ and take their countable join $A=\bigoplus_j A_j$. Then every real above $A$ is in every $C_j$. Hence the cone ultrafilter is countably complete.

Suppose that on a cone the values of $f$ have degrees among a given sequence $\deg_T(B_0),\deg_T(B_1),\ldots$. The sets \[ E_j=\{X:f(X)\equiv_T B_j\} \] are invariant. If none contained a cone, every complement would contain a cone. Their countable intersection, further intersected with the original cone, would still contain a cone, contradicting that the $E_j$ cover it. Thus some $E_j$ contains a cone, proving Part I for this class of functions.

In particular, if there is a fixed oracle $B$ with $f(X)\le_T B$ throughout a cone, then $f$ is constant in degree on a smaller cone. Only countably many reals are computable from $B$, since oracle programs are indexed by integers. The word "fixed" is essential. The condition $f(X)\le_T X$ allows the bound to vary with $X$ and does not put all output degrees below one oracle. Replacing the latter condition by the former would bypass a central part of the conjecture.

What cone decisions say about comparison.

For two invariant functions $f,g$, the set $\{X:f(X)\le_Tg(X)\}$ is invariant and so is the reversed comparison set. Deciding both on cones and intersecting gives one uniform pattern: equality of degrees, strict inequality in one direction, or incomparability at every point of a cone. Thus determinacy reduces comparison to a stable alternative but does not itself remove the incomparability alternative. Part II requires its removal for functions above the identity, as well as well-foundedness of the resulting order.

The same observation with $g(X)=X$ leaves possible eventual regression or incomparability unless one proves the eventual-constant conclusion of Part I. Stating that every invariant predicate is decided on a cone does not determine which side of that predicate must be selected. This is the first gap in a proof that invokes only the cone theorem.

Jump is well-defined and strictly raises the cone class.

If $U\le_TV$, a $V$-oracle can simulate a $U$-oracle computation, so the oracle halting problems satisfy $U'\le_TV'$. Consequently pointwise jump preserves Turing invariance and cone equivalence, and it is order-preserving for $\le_M$. For every $U$, one has $U\le_TU'$ and $U'\not\le_TU$. The first reduction uses a program which halts exactly when the queried bit of $U$ is one. For the second, a purported $U$-decision procedure for its own halting set yields a $U$-program which, on its own index, halts precisely when the procedure says it does not halt. This is the usual diagonal contradiction, valid relative to every oracle.

It follows pointwise, and therefore on every cone, that \[ f(X)<_T f(X)',\qquad [f]<_M[f']. \] Here strictness means $f\le_M f'$ but $f'\not\le_M f$; the latter is impossible on even a single input by the diagonal argument. If $f$ is above the identity, so is $f'$. These facts establish a strictly increasing operation, not that it is the immediate successor. The missing assertion is that no invariant $g$ can satisfy \[ [f]<_M[g]<_M[f']. \] Pointwise strictness does not rule out such an intermediate function, nor does it prove that arbitrary classes are comparable or that descending chains are absent.

Tests of proposed exotic examples.

For a fixed real $A$, the map $f_A(X)=X\oplus A$ looks different from the identity but agrees with it in degree on the cone above $A$. It produces no new Martin-order class. On the other hand, define $h(X)=X$ when $0\notin X$ and $h(X)=X'$ when $0\in X$. This is not Turing-invariant: toggling the first bit changes no Turing degree of the input, but switches the output between that degree and its strict jump. Therefore it is not a counterexample to the conjecture. This test guards against constructing arbitrary case distinctions on representatives rather than on degrees.

Finite iterates $X,X',X'',\ldots$ do give a strict chain of invariant functions above the identity. Enumerating those examples does not prove exhaustiveness, and assigning names to putative transfinite iterates would not prove the specified well-order and successor law.

Literature, verification, and outcome.

[S1] states the Turing-degree conjecture while studying an enumeration-degree analogue; results about that analogue do not automatically transfer. Lutz--Siskind [E1] establish Part I for the additional order-preserving class and carefully distinguish the choice assumptions of different proofs. The present arguments use only the elementary cone proof and its countable completeness, with the indicated consequence of determinacy. Verification is logical: finite computations cannot establish oracle noncomputability or quantification over all reals. The strongest partial conclusions are eventual constancy for countable degree range and strictness of the jump operation. General Part I, comparability and well-foundedness in Part II, and the immediate-successor property remain UNRESOLVED.

Sources

• S1 Antonio Nakid Cordero, Martin's Conjecture in the Enumeration Degrees $2025$, Introduction, Conjecture 1.2 and following paragraph. https://arxiv.org/html/2510.19147. Formulation source. Consulted 24 September 2026: Martin conjecture Parts I and II, cone order, and jump successors.
• E1 Patrick Lutz and Benjamin Siskind, Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions, arXiv:2305.19646, Sections 1.4 and 4.3. https://arxiv.org/html/2305.19646. Primary research source for the order-preserving subcase and the distinction between countable choice for reals (a consequence of AD) and stronger choice assumptions in other arguments. Consulted 27 September 2026; no stronger axiom is silently added here.