Problem #17

Non-trivial automorphisms of the Turing degrees

Open!!High impact — resolution would likely be publishable in a top journal (Advances-level or above)

Is there a non-trivial automorphism of the Turing degrees?

Definitions

By an automorphism of the Turing degrees, we mean an automorphism of the Turing degrees considered as a partial order.

Known Partial Results

  • Jockusch and Solovay [JS77] showed that if ff is an automorphism of the Turing degrees which preserves the Turing jump (i.e. for all xx, f(x)=f(x)f(x') = f(x)') then ff is equal to the identity on the cone above 0(4)0^{(4)}.
  • Nerode and Shore [NS80] proved that every automorphism is equal to the identity on some cone. Slaman and Woodin later showed that every automorphism is equal to the identity on the cone above 0(2)0^{(2)} [SW05].
  • Slaman and Woodin showed that there are only countably many automorphisms [SW05]. Furthermore, they showed that every automorphism can be represented by an arithmetic function—i.e. for any automorphism ff there is an arithmetic function g ⁣:2N2Ng\colon 2^\mathbb{N} \to 2^\mathbb{N} such that for all xx, [g(x)]T=f([x]T)[g(x)]_T = f([x]_T).
  • Slaman and Woodin also showed that any automorphism of the Turing degrees is fully determined by what is does on any 55-generic real. In particular, the set of degrees below 0(5)0^{(5)} is an automorphism base for the Turing degrees [SW05].
  • Kjos-Hanssen [Kjo18] showed that no permutation of the natural numbers induces a non-trivial automorphism of the Turing degrees.

Notes

The question has been open since at least the 1970s. In the 1990s, Cooper claimed to have constructed a non-trivial automorphsim. However, his claims were not widely accepted.

Reference for the problem statement

[Kjo18]Bjørn Kjos-Hanssen, Permutations of the integers induce only the trivial automorphism of the Turing degrees, Bulletin of Symbolic Logic, 2018 [link] [doi]

Additional References

[SW05]Theodore A. Slaman and W. Hugh Woodin, Definability in degree structures, 2005 [link]

[JS77]Carl G.Jockusch Jr. and Robert M. Solovay, Fixed points of jump preserving automorphisms of degrees, Israel Journal of Mathematics, 1977 [doi]

[NS80]Anil Nerode and Richard A. Shore, Reducibility orderings: theories, definability and automorphisms, Annals of Mathematical Logic, 1980 [doi]

Comments

Loading comments…