Math Conjectures

Automorphism Conjecture for the Turing Degrees

OPENLandmarkConjectureProposed c. 1980 · Full conjecture

Canonical statement

Let DT=P(N)/≡T\mathcal D_T=\mathcal P(\mathbb N)/{\equiv_T} be the set of Turing degrees, ordered by [A]≤T[B][A]\le_T[B] exactly when A≤TBA\le_T B. Every order automorphism Φ:DT→DT\Phi:\mathcal D_T\to\mathcal D_T is the identity.
View source LaTeX
Let \(\mathcal D_T=\mathcal P(\mathbb N)/{\equiv_T}\) be the set of Turing degrees, ordered by \([A]\le_T[B]\) exactly when \(A\le_T B\). Every order automorphism \(\Phi:\mathcal D_T\to\mathcal D_T\) is the identity.
LOG-COMP-010:[SlamanWoodin1986Definability][ShoreSlaman1999TuringJump][KjosHanssen2018Permutations]
Logic and foundationsTheoretical computer science

Notes

The Turing degrees form the quotient DT=P(N)/≡T\mathcal D_T=\mathcal P(\mathbb N)/{\equiv_T}, ordered by relative computability. The automorphism conjecture says that this order already distinguishes every degree intrinsically: an order-preserving bijection of DT\mathcal D_T cannot move any element.

Definability results sharply constrain a possible counterexample. Slaman and Woodin developed coding and definability in the degree structure and established rigidity on the cone above 0′′\mathbf 0'' [SlamanWoodin1986Definability]. Shore and Slaman proved that the Turing jump is definable from the ordering alone [ShoreSlaman1999TuringJump], while Kjos-Hanssen showed that permutations of the integers can induce only the trivial automorphism [KjosHanssen2018Permutations].

What remains is the lower part of the degree structure: no theorem forces every degree below the known rigid cone to be fixed, and no nontrivial automorphism has been constructed. The card concerns all Turing degrees, not merely the computably enumerable degrees, and results for truth-table or other reducibility structures do not settle it.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.