Automorphisms of jump ideals of the Turing degrees: countability and the fixed cone above 0′ (Shore's Questions 3.4 and 3.6)

Shore's 2007 survey on local definability in degree structures poses two precise open questions that together ask for a local form of the Slaman–Woodin automorphism analysis of the Turing degrees $\mathcal{D}$: (Question 3.4) does every jump ideal — a substructure of $\mathcal{D}$ closed downward and under join and the Turing jump — have at most countably many automorphisms; and (Question 3.6) is every degree above $\mathbf{0}'$, or even every degree, fixed by every automorphism of $\mathcal{D}$, or even of every jump ideal? Globally, Slaman and Woodin proved that the automorphism group of $\mathcal{D}$ is countable and that every automorphism fixes every degree above $\mathbf{0}''$, and Shore extended the fixed-cone result to every jump ideal containing $\mathbf{0}^{(\omega)}$; the analogous hyperdegree structures are even rigid. No resolution of either question is known: no automorphism count is known for any proper jump ideal, no nontrivial automorphism of $\mathcal{D}$ has an accepted construction, and the existence of any nontrivial automorphism of $\mathcal{D}$ was still described in print in 2018 as a major open problem. Both questions remain open.

Background

A set $A$ is Turing-reducible to a set $B$, written $A\le_T B$, if $A$ is computable with $B$ as an oracle; the Turing degrees $\mathcal{D}$ are the equivalence classes of sets under mutual Turing reducibility, partially ordered by the induced relation $\le$, with a least degree $\mathbf{0}$ (the computable sets) and a join $\vee$ induced by pairing sets. The Turing jump $x\mapsto x'$ maps a degree to the degree of the halting problem relativized to any set of degree $x$; its iterates are written $\mathbf{0}',\mathbf{0}'',\ldots,\mathbf{0}^{(n)}$, and $\mathbf{0}^{(\omega)}=\bigoplus_n\mathbf{0}^{(n)}$ sits above them all. A central program in computability theory, going back to Kleene and Post, asks which apparently external relations on $\mathcal{D}$ are definable in the structure $(\mathcal{D},\le,\vee)$ alone. Its landmark is the definability of the Turing jump itself (Shore and Slaman 1999), built on the Slaman–Woodin coding of countable antichains of degrees by finitely many parameters and the definability of the double jump $x\mapsto x''$.

This program is inseparable from the study of automorphisms: an automorphism of $\mathcal{D}$ (or of a substructure) is a bijection of degrees that preserves the order $\le$ (equivalently, the full degree structure), and any definable relation or degree must be fixed by every automorphism. The structure is called rigid if its only automorphism is the identity. Jockusch and Solovay (1977) proved that every automorphism that preserves the jump fixes all degrees above $\mathbf{0}^{(4)}$; since the jump is now known to be definable, every automorphism of $\mathcal{D}$ automatically preserves it. Slaman and Woodin, in a long-circulating manuscript 'Definability in degree structures' announced in Slaman's 1991 ICM lecture and never published but described in Slaman's 2008 survey chapter, proved the two global facts: the automorphism group $\mathrm{Aut}(\mathcal{D})$ is countable, and every automorphism of $\mathcal{D}$ fixes every degree above $\mathbf{0}''$. Whether $\mathcal{D}$ is rigid — which by Slaman and Woodin is equivalent to $\mathcal{D}$ being biinterpretable with second-order arithmetic, i.e., admitting definable standard models of arithmetic with definable schemes matching degrees to codes for sets of those degrees — remains open; indeed no nontrivial automorphism of $\mathcal{D}$ is known, Cooper's claimed construction in Mathematical Logic Quarterly (2001) being unaccepted.

Shore's 2007 survey (full journal version: Journal of Mathematical Logic 7 (2007), 229–262) made this analysis local. A jump ideal is a subset $\mathcal{I}\subseteq\mathcal{D}$ closed downward and under join and the jump; the smallest one is the class of arithmetic degrees $\{x:x\le\mathbf{0}^{(n)}\text{ for some }n\}$, and larger examples are generated by any degree under these closure operations. Shore defined the (double) jump inside any jump ideal containing $\mathbf{0}^{(\omega)}$ by purely degree-theoretic means (Theorem 1.1) and derived (Theorem 1.2) that every automorphism of any such ideal fixes every degree above $\mathbf{0}''$, with all relations on the ideal invariant under the double jump definable there if and only if definable in second-order arithmetic. The contrast with the hyperdegrees — the degrees under hyperarithmetic reducibility, a strengthening of Turing reducibility in which computation may use the jump iterated along any computable ordinal; the corresponding jump operator is the hyperjump, and a hyperjump ideal is the analogue of a jump ideal for this reducibility — where Shore proved every hyperjump ideal is rigid (Theorem 1.3) — shows that local rigidity is specifically open for the Turing jump ideals. Two questions from §3 of the survey state exactly what is missing: the countability of automorphism groups of jump ideals (Question 3.4), and the lowering of the fixed-cone base from $\mathbf{0}''$ to $\mathbf{0}'$ or to $\mathbf{0}$, the latter being rigidity (Question 3.6).

Recent work has localized the automorphism analysis only to a different family of substructures. Slaman and Soskova (2018) proved that the degrees below $\mathbf{0}'$ — an ideal closed under join but not under the jump, hence not a jump ideal — have a finite automorphism base (a set of degrees such that every automorphism is determined by its action on it), a countable automorphism group with arithmetically definable presentations, and that rigidity for this ideal is equivalent to its biinterpretability with first-order arithmetic. Kjos-Hanssen (2018) proved that no permutation of the integers induces a nontrivial automorphism of $\mathcal{D}$. Shore (2014) established biinterpretability up to double jump below $\mathbf{0}'$. None of these touches automorphisms of jump ideals, and the two questions Shore posed remain the precise open target.

Problem Statement

Let $\mathcal{D}$ be the structure of Turing degrees with order $\le$ and join $\vee$, and let $\mathbf{0}'$ be the degree of the halting problem. A jump ideal is a subset $\mathcal{I}\subseteq\mathcal{D}$ closed downward and under join and the Turing jump; an automorphism of $\mathcal{I}$ is a bijection of $\mathcal{I}$ onto itself preserving the degree structure, and $\mathcal{I}$ is rigid if its only automorphism is the identity. The problem, posed as Questions 3.4 and 3.6 of Shore (2007), is to extend the global Slaman–Woodin automorphism analysis of $\mathcal{D}$ to jump ideals, along two axes:

1. Countability (Question 3.4): Does every jump ideal of $\mathcal{D}$ have at most countably many automorphisms? A positive answer would imply the known global theorem of Slaman and Woodin that $\mathrm{Aut}(\mathcal{D})$ is countable. Shore's Proposition 3.5 gives only a partial reduction in the converse direction: if every sufficiently large countable jump ideal (one containing some fixed degree) or sufficiently closed countable jump ideal (one closed under the $\omega$-jump $x\mapsto\bigoplus_n x^{(n)}$ or any other fixed function on $\mathcal{D}$) has at most countably many automorphisms, then $\mathrm{Aut}(\mathcal{D})$ is countable — that is, the reduction yields only the $\mathcal{I}=\mathcal{D}$ instance of Question 3.4, already known from Slaman–Woodin, and not Question 3.4 for every jump ideal.

2. Fixed cone (Question 3.6): Are all degrees above $\mathbf{0}'$ — or even all degrees — fixed by every automorphism of $\mathcal{D}$, or even of every jump ideal $\mathcal{I}$?

The two axes share one scientific objective: determine the automorphism group of every jump ideal of the Turing degrees — whether it is at most countable (axis 1) and which degrees its automorphisms fix (axis 2). They are related as a ladder: rigidity of every jump ideal, the strongest form of axis 2, settles axis 1 trivially and would by Slaman–Woodin make $\mathcal{D}$ biinterpretable with second-order arithmetic; conversely, even countability of $\mathrm{Aut}(\mathcal{D})$ itself currently rests only on an unpublished manuscript. The open target is Question 3.4 as universally quantified over all jump ideals, and Question 3.6 in the disjunctive gradations the source itself lists — all degrees above $\mathbf{0}'$ or even all degrees, fixed under all automorphisms of $\mathcal{D}$ or even of every jump ideal $\mathcal{I}$; a result answering one of the alternatives the source explicitly lists answers that part of Question 3.6 as posed. Resolving the task requires an answer to each axis — countability (Question 3.4) for every jump ideal and the fixed cone (Question 3.6) — and within Question 3.6 any one of the alternatives the source lists suffices; the strongest such alternative (rigidity of every jump ideal) settles axis 1 as a corollary, whereas an answer to axis 1 alone leaves Question 3.6 open.

References

1. Richard A. Shore, 'Local Definitions in Degree Structures: The Turing Jump, Hyperdegrees and Beyond', Bulletin of Symbolic Logic 13(2):226–239, 2007. DOI: 10.2178/bsl/1185803806. https://doi.org/10.2178/bsl/1185803806
2. Richard A. Shore, 'Direct and Local Definitions of the Turing Jump', Journal of Mathematical Logic 7 (2007), 229–262. DOI: 10.1142/S0219061307000676. https://doi.org/10.1142/S0219061307000676
3. Theodore A. Slaman and W. Hugh Woodin, 'Definability in the Turing degrees', Illinois Journal of Mathematics 30 (1986), 320–334. DOI: 10.1215/ijm/1256044641. https://doi.org/10.1215/ijm/1256044641
4. Richard A. Shore and Theodore A. Slaman, 'Defining the Turing Jump', Mathematical Research Letters 6(6) (1999), 711–722. DOI: 10.4310/MRL.1999.v6.n6.a10. https://doi.org/10.4310/MRL.1999.v6.n6.a10
5. Carl G. Jockusch, Jr. and Robert M. Solovay, 'Fixed points of jump preserving automorphisms of degrees', Israel Journal of Mathematics 26 (1977), 91–94. DOI: 10.1007/BF03007659. https://doi.org/10.1007/BF03007659
6. S. Barry Cooper, 'On a Conjecture of Kleene and Post', Mathematical Logic Quarterly 47(1) (2001), 3–33. DOI: 10.1002/1521-3870(200101)47:1<3::AID-MALQ3>3.0.CO;2-A. https://doi.org/10.1002/1521-3870(200101)47:1%3C3::AID-MALQ3%3E3.0.CO;2-A
7. Theodore A. Slaman, 'Global Properties of the Turing Degrees and the Turing Jump', in Computational Prospects of Infinity, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, World Scientific, 2008, pp. 83–101. DOI: 10.1142/9789812794055_0002. https://doi.org/10.1142/9789812794055_0002
8. Theodore A. Slaman and Mariya I. Soskova, 'The Δ^0_2 Turing degrees: Automorphisms and Definability', Transactions of the American Mathematical Society 370 (2018), 1351–1375. DOI: 10.1090/tran/7187. https://doi.org/10.1090/tran/7187
9. Bjørn Kjos-Hanssen, 'Permutations of the Integers Induce only the Trivial Automorphism of the Turing Degrees', Bulletin of Symbolic Logic 24(2) (2018), 165–174. DOI: 10.1017/bsl.2018.15. https://doi.org/10.1017/bsl.2018.15
10. Richard A. Shore, 'Biinterpretability up to double jump in the degrees below 0′', Proceedings of the American Mathematical Society 142 (2014), 351–360. DOI: 10.1090/S0002-9939-2013-11719-3. https://doi.org/10.1090/S0002-9939-2013-11719-3
11. Andrew E. M. Lewis-Pye, 'The search for natural definability in the Turing degrees', Computability 7 (2018), 189–235. DOI: 10.3233/COM-170068. https://doi.org/10.3233/COM-170068
12. Hristo Ganchev and Andrey C. Sariev, 'The automorphism group and definability of the jump operator in the ω-enumeration degrees', Archive for Mathematical Logic 60(7–8) (2021), 909–925. DOI: 10.1007/s00153-021-00766-7. https://doi.org/10.1007/s00153-021-00766-7