Problem #17
Non-trivial automorphisms of the Turing degrees
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 is an automorphism of the Turing degrees which preserves the Turing jump (i.e. for all , ) then is equal to the identity on the cone above .
- 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 [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 there is an arithmetic function such that for all , .
- Slaman and Woodin also showed that any automorphism of the Turing degrees is fully determined by what is does on any -generic real. In particular, the set of degrees below 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]
Loading comments…