Bard's Question 5.1: does the locally generated family $\mathcal{J}_{\mathbf{x}}$ exhaust all uniformly Turing-invariant functions on a single Turing degree?

Bard's paper "Uniform Martin's conjecture, locally" (arXiv:1907.10766; Proc. Amer. Math. Soc. 148, 2020) proved that part I of the uniform Martin's conjecture follows from a local phenomenon on single Turing degrees — every non-constant uniformly Turing-invariant (UTI) function on one degree computes its argument, $f(x)\ge_T x$ — and closed by asking whether part II is likewise local. Its Question 5.1 defines, for a fixed Turing degree $\mathbf{x}$, the family $\mathcal{J}_{\mathbf{x}}$ generated from the constant functions, the identity, the bit-flip, and all pointclass jump operators defined on $\mathbf{x}$, by closing under pointwise finite and countable joins and under the symmetrized "Turing equivalence via" operations $(i,j)^s\odot_T$; every member of $\mathcal{J}_{\mathbf{x}}$ is UTI on $\mathbf{x}$. The question is whether $\mathcal{J}_{\mathbf{x}}$ is exactly the class of all UTI functions from $\mathbf{x}$ to $2^{\mathbb{N}}$. Bard's Question 5.1 remains open in its original form.

Background

The Turing degrees are the equivalence classes of infinite binary sequences (reals) under mutual Turing reducibility $\equiv_T$. Martin's conjecture is a proposed classification, under the Axiom of Determinacy (AD), of all "definable" functions on this structure. A function $f$ on reals is Turing invariant (TI) if $x\equiv_T y$ implies $f(x)\equiv_T f(y)$. A cone is the set of degrees above some fixed degree, and Turing Determinacy (TD, a consequence of AD) makes cones a natural notion of largeness on degree-invariant sets; one writes $f\le_M g$ when $f(x)\le_T g(x)$ on a cone. Martin's conjecture asserts: (I) every TI $f$ either satisfies $f(x)\ge_T x$ on a cone or is constant up to Turing equivalence on a cone; and (II) the TI functions at or above the identity are pre-well-ordered by $\le_M$ (a linear preorder whose equivalence classes are well-ordered, and whose proper initial segments are sets rather than proper classes), with the pointwise jump $f'(x)=f(x)'$ raising $\le_M$-rank by exactly one — so the Turing jump $x\mapsto x'$, which produces the halting problem relative to the oracle $x$, and its iterates are the only "natural" strictly increasing functions on the degrees.

The full conjecture is open, but it is a theorem for the class of uniformly Turing invariant (UTI) functions. Uniformity is formalized through indices: writing $\varphi_e^z$ for the $e$-th oracle computation with oracle $z$, one says $x\equiv_T y$ via $(i,j)$ when $y=\varphi_i^x$ and $x=\varphi_j^y$; a function $f$ is UTI when there is $u:\mathbb{N}^2\to\mathbb{N}^2$ such that $x\equiv_T y$ via $(i,j)$ implies $f(x)\equiv_T f(y)$ via $u(i,j)$ — Turing equivalences between arguments are converted to Turing equivalences between values uniformly in the witnessing indices. Steel proved part II and Slaman–Steel proved part I of the uniform Martin's conjecture for UTI functions under AD. Part II was later reproved by Becker in a structural way: every UTI function strictly above the identity in the $\le_M$ ordering is, on a cone, Turing equivalent to a pointclass jump operator $J_\Gamma(x)=$ a universal $\Gamma(x)$ subset of $\mathbb{N}$, for a reasonable lightface pointclass $\Gamma$ — a class of definable sets that relativizes to arbitrary oracles and admits universal sets; the Turing jump is the $\Sigma^0_1$ case and the hyperjump $x\mapsto O^x$ (relativized Kleene's $\mathcal{O}$, a complete $\Pi^1_1$ set) is a $\Pi^1_1$ case. Kihara–Montalbán refined this connection by proving that the uniformly invariant functions from Turing equivalence to many-one equivalence correspond, up to cone equivalence, one-to-one with the Wadge degrees (the degrees of sets of reals under continuous reductions, which rank definable complexity of sets of reals). Thus, globally and up to cone-equivalence, the UTI functions are exhausted by the constants, the identity, and the pointclass jump operators.

Bard showed that part I of the uniform Martin's conjecture is not merely a global statement: it follows from a local dichotomy on single degrees. For a single degree $\mathbf{x}$, viewed as the set of all reals in that $\equiv_T$-class, and a function $f:\mathbf{x}\to 2^{\mathbb{N}}$ that is UTI on $\mathbf{x}$ (the same index-uniformity condition, now required only for pairs of reals inside the one degree — since all elements of a degree are mutually Turing equivalent, this says that the Turing equivalences among the values of $f$ are certified by indices computed uniformly from the indices certifying the equivalences among the arguments), either $f(x)\ge_T x$ or $f$ is constant. This local dichotomy is proved without any determinacy assumption; TD is used only to lift it to the global statement, and over ZF+DC part I of the uniform Martin's conjecture is in fact equivalent to TD (Bard's Corollary 2.4). Bard's paper closes by asking whether part II of the uniform Martin's conjecture likewise reflects a local phenomenon, and proposes a concrete family of locally generated UTI functions as the candidate local counterpart of Becker's global classification. The generators are the basic UTI building blocks (constants, the identity, the bit-flip $\bar{x}:i\mapsto 1-x(i)$, and all pointclass jump operators defined on the degree); the closure operations are the pointwise join $(f_0\oplus f_1)(x)=f_0(x)\oplus f_1(x)$, the pointwise countable join, and post-composition with the symmetrized "Turing equivalence via" operator $(i,j)^s\odot_T$, which sends a real $y$ to $\varphi_i^y$ whenever that is total and $\varphi_j^{\varphi_i^y}=y$ (exactly when $\varphi_i^y\equiv_T y$ via $(i,j)$). Every function so generated is UTI; the question is whether these families exhaust the locally UTI functions.

Problem Statement

Fix a Turing degree $\mathbf{x}$, i.e., the set of all reals in one $\equiv_T$-class. Let $\mathcal{J}_{\mathbf{x}}$ be the smallest family of functions $f:\mathbf{x}\to 2^{\mathbb{N}}$ that:

• contains all constant functions from $\mathbf{x}$ to $2^{\mathbb{N}}$;
• contains the identity $\mathrm{id}_{\mathbf{x}}$ and the bit-flip $x\mapsto\bar{x}$, where $\bar{x}(i)=1-x(i)$;
• contains all pointclass jump operators defined on $\mathbf{x}$ (each $J_\Gamma(x)$ being a universal $\Gamma(x)$ subset of $\mathbb{N}$ for a reasonable lightface pointclass $\Gamma$ — e.g., the Turing jump $x\mapsto x'$ as a $\Sigma^0_1$-jump, and the hyperjump $x\mapsto O^x$ as a $\Pi^1_1$-jump);
• and is closed under the pointwise operations: if $f_0,f_1,\dots\in\mathcal{J}_{\mathbf{x}}$ then $f_0\oplus f_1\in\mathcal{J}_{\mathbf{x}}$ and $\bigoplus_n f_n\in\mathcal{J}_{\mathbf{x}}$ (joins taken pointwise, $(f_0\oplus f_1)(x)=f_0(x)\oplus f_1(x)$), and for every $(i,j)\in\mathbb{N}^2$ such that $(i,j)^s\odot_T f_0(x)$ is defined for each $x\in\mathbf{x}$, the function $x\mapsto(i,j)^s\odot_T f_0(x)$ is in $\mathcal{J}_{\mathbf{x}}$.

Every function in $\mathcal{J}_{\mathbf{x}}$ is UTI on $\mathbf{x}$. Bard's Question 5.1 asks: is $\mathcal{J}_{\mathbf{x}}$ the set of all UTI functions from $\mathbf{x}$ to $2^{\mathbb{N}}$, for every Turing degree $\mathbf{x}$? Equivalently: can every uniformly Turing-invariant function on a single degree be generated from the constants, the identity, the bit-flip, and the pointclass jumps by the pointwise joins and index-actions above, or does there exist a Turing degree $\mathbf{x}$ and a UTI function on $\mathbf{x}$ that lies outside the generated family $\mathcal{J}_{\mathbf{x}}$? A positive answer would give the local analogue of Becker's global characterization of UTI maps by pointclass jump operators and would show that part II of the uniform Martin's conjecture, like part I, is the global manifestation of a local phenomenon on single degrees; a negative answer would exhibit locally defined UTI functions invisible to the global cone-level classification.

References

1. Vittorio Bard, "Uniform Martin's conjecture, locally", Proceedings of the American Mathematical Society 148(12) (2020) 5369–5380. DOI: 10.1090/proc/15159; arXiv:1907.10766. https://doi.org/10.1090/proc/15159
2. John R. Steel, "A classification of jump operators", Journal of Symbolic Logic 47(2) (1982) 347–358. DOI: 10.2307/2273146. https://doi.org/10.2307/2273146
3. Theodore A. Slaman and John R. Steel, "Definable functions on degrees", in Cabal Seminar 81–85, Lecture Notes in Mathematics 1333, Springer, Berlin/Heidelberg (1988) 37–55. DOI: 10.1007/bfb0084969. https://doi.org/10.1007/bfb0084969
4. Howard Becker, "A characterization of jump operators", Journal of Symbolic Logic 53(3) (1988) 708–728. DOI: 10.2307/2274567. https://doi.org/10.2307/2274567
5. Takayuki Kihara and Antonio Montalbán, "The uniform Martin's conjecture for many-one degrees", Transactions of the American Mathematical Society 370(12) (2018) 9025–9044. DOI: 10.1090/tran/7519; arXiv:1608.05065. https://doi.org/10.1090/tran/7519
6. Uri Andrews, Daniel F. Belin and Luca San Mauro, "On the structure of computable reducibility on equivalence relations of natural numbers", The Journal of Symbolic Logic 88(3) (2023) 1038–1063. DOI: 10.1017/jsl.2022.28; arXiv:2105.12534. https://doi.org/10.1017/jsl.2022.28
7. John D. Clemens, Samuel Coskey and Gianni Krakoff, "Computable reducibility of equivalence relations and an effective jump operator", The Journal of Symbolic Logic 88(2) (2023) 540–561. DOI: 10.1017/jsl.2022.45; arXiv:2005.13777. https://doi.org/10.1017/jsl.2022.45
8. Antonio Nakid Cordero, "Martin's Conjecture in the Enumeration Degrees", arXiv:2510.19147 (2025). https://arxiv.org/abs/2510.19147
9. Patrick Lutz and Benjamin Siskind, "Part 1 of Martin's Conjecture for order-preserving and measure-preserving functions", Journal of the American Mathematical Society 38(2) (2025) 319–367. DOI: 10.1090/jams/1046; arXiv:2305.19646. https://doi.org/10.1090/jams/1046
10. Patrick Lutz, "Martin's conjecture for regressive functions on the hyperarithmetic degrees", Journal of Mathematical Logic 25(2), Article 2450015 (2025). DOI: 10.1142/S0219061324500156; arXiv:2306.05746. https://doi.org/10.1142/s0219061324500156
11. Adam Day and Andrew Marks, "On a question of Slaman and Steel", Transactions of the American Mathematical Society, Series B 13(11) (2026) 379–402. DOI: 10.1090/btran/253; arXiv:2004.00174. https://doi.org/10.1090/btran/253