==== TABLE OF CONTENTS ====
Rigidity-of-the-Turing-degrees//figures/bounded-recurrence.tex
Rigidity-of-the-Turing-degrees//glyph-mappings.tex
Rigidity-of-the-Turing-degrees//main.tex
Rigidity-of-the-Turing-degrees//references.tex
Rigidity-of-the-Turing-degrees//sections/introduction.tex
Rigidity-of-the-Turing-degrees//sections/preliminaries.tex
Rigidity-of-the-Turing-degrees//sections/recovery.tex
Rigidity-of-the-Turing-degrees//sections/representation.tex
Rigidity-of-the-Turing-degrees//sections/rigidity.tex
===========================

==== BEGIN Rigidity-of-the-Turing-degrees//figures/bounded-recurrence.tex ====
\begin{figure}[tb]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,>=Stealth,font=\small]
  \fill[blue!12] (0,0) rectangle (1.2,.55);
  \fill[gray!7] (1.2,0) rectangle (8.8,.55);
  \fill[orange!18] (8.8,0) rectangle (10,.55);
  \draw[thick] (0,0) -- (10,0);
  \foreach \x in {0,1.2,8.8,10} {\draw (\x,-.08) -- (\x,.62);}
  \node[below] at (0,-.09) {$b_-$};
  \node[below] at (1.2,-.09) {$b_-+\delta$};
  \node[below] at (8.8,-.09) {$b_+-\delta$};
  \node[below] at (10,-.09) {$b_+$};
  \node at (.6,.3) {$r_n=0$};
  \node at (9.4,.3) {$r_n=1$};
  \node at (5,.3) {either choice may occur};
  \draw[->,thick,blue!65!black] (.12,.9) -- (1.1,.9);
  \node[above,blue!65!black] at (.61,.97) {$+\delta t$};
  \draw[->,thick,orange!70!black] (9.88,.9) -- (8.9,.9);
  \node[above,orange!70!black] at (9.39,.97) {$-\delta(1-t)$};
\end{tikzpicture}
\caption{The bounded recurrence, schematically. The tested bit forces
an inward step in each endpoint strip; the bit need not be monotone
between them. Each step has length less than $\delta$, so no state
can leave $[b_-,b_+]$. The oracle computation produces the choices
$r_n$, not the numerical states $s_n$.}
\label{fig:bounded-recurrence}
\end{figure}
==== END Rigidity-of-the-Turing-degrees//figures/bounded-recurrence.tex ====

==== BEGIN Rigidity-of-the-Turing-degrees//glyph-mappings.tex ====
\input{glyphtounicode}
\pdfglyphtounicode{parenleftbig}{0028}
\pdfglyphtounicode{parenrightbig}{0029}
\pdfglyphtounicode{parenleftBigg}{0028}
\pdfglyphtounicode{parenrightBigg}{0029}
\pdfglyphtounicode{braceleftBigg}{007B}
\pdfglyphtounicode{summationtext}{2211}
\pdfglyphtounicode{summationdisplay}{2211}
\pdfglyphtounicode{uniontext}{22C3}
\pdfglyphtounicode{logicalordisplay}{22C1}
\pdfglyphtounicode{hatwide}{0302}
\pdfgentounicode=1
==== END Rigidity-of-the-Turing-degrees//glyph-mappings.tex ====

==== BEGIN Rigidity-of-the-Turing-degrees//main.tex ====
\newcommand{\DoNotLoadEpstopdf}{}
\documentclass[11pt]{article}
\ifdefined\pdfinfoomitdate\pdfinfoomitdate=1\fi
\ifdefined\pdftrailerid\pdftrailerid{}\fi
\ifdefined\pdfsuppressptexinfo\pdfsuppressptexinfo=15\fi
\input{glyph-mappings}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=1.08in]{geometry}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\hypersetup{pdftitle={Rigidity of the Turing degrees},pdfauthor={OpenAI}}
\setlength{\emergencystretch}{1.5em}
\setlist[enumerate]{leftmargin=*,itemsep=3pt,topsep=4pt}
\setlist[itemize]{leftmargin=*,itemsep=3pt,topsep=4pt}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\N}{\mathbb N}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\DT}{\mathcal D_T}
\newcommand{\leT}{\le_T}
\newcommand{\equivT}{\equiv_T}
\newcommand{\degT}[1]{[#1]_T}
\DeclareMathOperator{\Aut}{Aut}
\title{Rigidity of the Turing degrees}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that every order automorphism of the full partial order of
Turing degrees is the identity, resolving the rigidity conjecture for
the Turing degrees positively.
\end{abstract}
\input{sections/introduction}
\input{sections/preliminaries}
\input{sections/representation}
\input{sections/recovery}
\input{sections/rigidity}
\input{references}
\end{document}
==== END Rigidity-of-the-Turing-degrees//main.tex ====

==== BEGIN Rigidity-of-the-Turing-degrees//references.tex ====
\begingroup
\small
\begin{thebibliography}{99}

\bibitem{GroszekSlaman1998}
M.~J.~Groszek and T.~A.~Slaman,
A basis theorem for perfect sets,
\emph{Bulletin of Symbolic Logic} \textbf{4} (1998), no.~2,
204--209.
\href{https://doi.org/10.2307/421023}{DOI}.
\href{https://math.berkeley.edu/~slaman/papers/prikry.pdf}{Author's version},
dated 17 November 2000, whose lemma numbering is used here.

\bibitem{JockuschSolovay1977}
C.~G.~Jockusch, Jr., and R.~M.~Solovay,
Fixed points of jump preserving automorphisms of degrees,
\emph{Israel Journal of Mathematics} \textbf{26} (1977), no.~1,
91--94.
\href{https://doi.org/10.1007/BF03007659}{DOI}.

\bibitem{KjosHanssen2018}
B.~Kjos-Hanssen,
Permutations of the integers induce only the trivial automorphism
of the Turing degrees,
\emph{Bulletin of Symbolic Logic} \textbf{24} (2018), no.~2,
165--174.
\href{https://doi.org/10.1017/bsl.2018.15}{DOI}.
\href{https://arxiv.org/abs/1603.00525v1}{arXiv:1603.00525v1}.

\bibitem{KumarShelah2023}
A.~Kumar and S.~Shelah,
Large Turing independent sets,
\emph{Proceedings of the American Mathematical Society}
\textbf{151} (2023), no.~1, 355--367.
\href{https://doi.org/10.1090/proc/16081}{DOI}.

\bibitem{LutzSiskind2025}
P.~Lutz and B.~Siskind,
Part 1 of Martin's conjecture for order-preserving and
measure-preserving functions,
\emph{Journal of the American Mathematical Society}
\textbf{38} (2025), no.~2, 319--367.
\href{https://doi.org/10.1090/jams/1046}{DOI}.
\href{https://arxiv.org/abs/2305.19646v3}{arXiv:2305.19646v3},
whose theorem numbering is used here.

\bibitem{MarkerDST}
D.~Marker,
\href{https://www.math.uic.edu/~marker/math512/dst.pdf}{\emph{Descriptive Set Theory}},
course notes, Fall 2002.

\bibitem{NerodeShore1980}
A.~Nerode and R.~A.~Shore,
Reducibility orderings: theories, definability and automorphisms,
\emph{Annals of Mathematical Logic} \textbf{18} (1980), no.~1,
61--89.
\href{https://doi.org/10.1016/0003-4843(80)90004-2}{DOI}.

\bibitem{Shore2007}
R.~A.~Shore,
Direct and local definitions of the Turing jump,
\emph{Journal of Mathematical Logic} \textbf{7} (2007), no.~2,
229--262.

\bibitem{ShoreSlaman1999}
R.~A.~Shore and T.~A.~Slaman,
Defining the Turing jump,
\emph{Mathematical Research Letters} \textbf{6} (1999), no.~5--6,
711--722.
\href{https://math.berkeley.edu/~slaman/papers/jump.pdf}{Author's version}.

\bibitem{SlamanGlobal}
T.~A.~Slaman,
Global properties of the Turing degrees and the Turing jump,
in \emph{Computational Prospects of Infinity, Part I: Tutorials},
C.~Chong, Q.~Feng, T.~A.~Slaman, W.~H.~Woodin,
and Y.~Yang (eds.),
Lecture Notes Series, Institute for Mathematical Sciences,
National University of Singapore, vol.~14,
World Scientific, Hackensack, NJ, 2008, pp.~83--101.
\href{https://doi.org/10.1142/9789812794055_0002}{DOI}.
\href{https://math.berkeley.edu/~slaman/papers/IMS_slaman.pdf}{Author's version},
whose theorem numbering is used here.

\bibitem{SlamanWoodin2005}
T.~A.~Slaman and W.~H.~Woodin,
\href{https://math.berkeley.edu/~slaman/talks/sw.pdf}{\emph{Definability in Degree Structures}},
unpublished manuscript, 21 July 2005.

\bibitem{Soare1987}
R.~I.~Soare,
\href{https://link.springer.com/book/9783540666813}{\emph{Recursively Enumerable Sets and Degrees:
A Study of Computable Functions and Computably Generated Sets}},
Perspectives in Mathematical Logic,
Springer-Verlag, Berlin, 1987.

\bibitem{Turing1939}
A.~M.~Turing,
Systems of logic based on ordinals,
\emph{Proceedings of the London Mathematical Society}
(2) \textbf{45} (1939), 161--228.
\href{https://doi.org/10.1112/plms/s2-45.1.161}{DOI}.

\end{thebibliography}
\endgroup
==== END Rigidity-of-the-Turing-degrees//references.tex ====

==== BEGIN Rigidity-of-the-Turing-degrees//sections/introduction.tex ====
\section{Introduction}\label{sec:introduction}

Turing reducibility compares the information available from sets of
integers: $A\leT B$ means that an oracle Turing machine with oracle $B$
computes the characteristic function of $A$. Mutual reducibility
defines Turing equivalence, and its equivalence classes form the
partial order $(\DT,\leT)$ of Turing degrees. The underlying notion
of relative computation goes back to Turing's oracle machines
\cite[Section~4]{Turing1939}; see \cite{Soare1987} for standard
degree-theoretic background. The automorphism problem asks how much
of this information the abstract ordering retains.

The rigidity conjecture for the Turing degrees asks whether every
automorphism of this ordering fixes every degree.
An automorphism here is any bijection
$\pi:\DT\to\DT$ satisfying
\[
\mathbf a\leT\mathbf b
\quad\Longleftrightarrow\quad
\pi(\mathbf a)\leT\pi(\mathbf b).
\]
We work in ZFC and impose no definability or regularity hypothesis
on $\pi$.

\begin{theorem}\label{thm:rigidity}
Every order automorphism of the full Turing-degree structure is
the identity:
\[
\forall\pi\in\Aut(\DT,\leT)\ \forall\mathbf a\in\DT
\qquad \pi(\mathbf a)=\mathbf a.
\]
\end{theorem}

\paragraph{Prior work and the remaining problem.}
The Turing jump sends a degree $\mathbf a$ to the degree
$\mathbf a'$ of the halting problem relative to an oracle of
degree $\mathbf a$. Jockusch and Solovay proved that every
jump-preserving order automorphism fixes all degrees above
$\mathbf0^{(4)}$, the fourth jump of the computable degree
\cite{JockuschSolovay1977}. Using Slaman and Woodin's definability
of the double jump, Shore and Slaman proved that the jump is
definable from the ordering
\cite{ShoreSlaman1999}, so every order automorphism preserves it.
Shore later gave direct degree-theoretic definitions of the jump
\cite{Shore2007}.

A cone consists of all degrees above a fixed degree. Nerode and
Shore proved that every automorphism fixes some cone, whose base
may depend on the automorphism \cite{NerodeShore1980}; see also
\cite[Theorem~3.2, author's version]{SlamanGlobal}.
Slaman and Woodin obtained a fixed cone common to all
automorphisms: every automorphism fixes all degrees above
$\mathbf0''$, the second jump of the computable degree.
Their analysis also shows that the automorphism group is
countable and that each automorphism has an arithmetic
representation on sets of integers
\cite{SlamanWoodin2005,SlamanGlobal}.
These results show that the order determines substantial
computability-theoretic structure. They leave the rigidity
problem at degrees outside the known fixed cone.

The representation theorem is the external input to our proof.
In its all-input form, it assigns to every arbitrary degree
automorphism a single arithmetic, hence Borel, function on sets of
integers that induces that automorphism on degrees
\cite[Theorem~6.3.1(2)]{SlamanWoodin2005}. The cited source is the
2005 unpublished manuscript; the result also appears in Slaman's
account \cite{SlamanGlobal}. This theorem supplies the regularity
needed for a category argument while retaining the unrestricted
scope of Theorem~\ref{thm:rigidity}.

\paragraph{A consequence for definability.}
Theorem~\ref{thm:rigidity} also settles the biinterpretability
conjecture of Slaman and Woodin. Full second-order arithmetic is
the two-sorted structure of natural numbers and all subsets of
natural numbers, with arithmetic and membership. Slaman and Woodin
interpret this structure using finite tuples of Turing degrees.
In their formulation, biinterpretability asks whether the relation
matching such a code for a set $X\subseteq\N$ with its degree
$\degT X$ is first-order definable in the degree ordering without
parameters \cite[Definition~7.5.1]{SlamanWoodin2005}.
They prove that this is equivalent to rigidity
\cite[Theorem~7.5.3]{SlamanWoodin2005}; thus our theorem gives a
positive answer. We state the resulting corollary in
Section~\ref{sec:rigidity}.

\paragraph{Recovery and removal of parameters.}
Our main construction is the recovery theorem of
Proposition~\ref{prop:recovery}. We identify $2^\N$ with the sets of
integers; recovering a real means computing which rational numbers
lie below it. Write $\oplus$ for the oracle join,
which combines the information in finitely many sets of integers.
For a Borel map $F:\R\to2^\N$ with countable fibers satisfying
\[
F(x+y)\leT F(x)\oplus F(y),
\]
we recover any prescribed irrational $t\in(0,1)$ from four values
of $F$ at rational affine combinations of $t$ and two auxiliary
reals $u,v$. Recovery holds for a comeager set of pairs $(u,v)$:
the exceptional pairs form a countable union of nowhere-dense
sets. The statement applies beyond functions representing degree
automorphisms.

The numerical mechanism is an averaging identity. For a fixed
positive rational $\delta$, start with a real state $s_0=0$
and repeatedly choose the increment $\delta t$ or
$\delta(t-1)$, recording the choice as $r_n=0$ or $r_n=1$,
respectively. Summing these increments gives
\[
s_N=\delta\left(Nt-\sum_{nb_-+\delta$; its negative increment has magnitude
$\delta(1-t)<\delta$, with the same conclusion.
Rationality of $\delta$ ensures $s_{n+1}\in H$.
This proves \eqref{eq:invariant}, and in particular
$|s_n|<\rho$.
Figure~\ref{fig:bounded-recurrence} isolates the only feature of the
tested bit needed for this confinement: it points the next step
inward near either endpoint. No restriction on its intervening
behavior is needed.
\input{figures/bounded-recurrence}

\medskip
\noindent\emph{Computing the binary choices.}
Let $T$ denote the finite join on the right of
\eqref{eq:four-values}. We show that $(r_n)_{n\ge0}$ is
computable from $T$ by maintaining, relative to $T$, an
oracle-program index $P_n$ satisfying
\[
\Phi_{P_n}^{T}=F(u+s_n).
\]
Initially $P_0$ projects to the first component $F(u)$.
Given $P_n$, read $\Phi_{P_n}^{T}(j)$ and compare it with
the fixed bit $h$ to obtain $r_n$. Select the third component
of $T$ if $r_n=0$ and the fourth if $r_n=1$, namely
\[
F(v-u+\delta(t-r_n)).
\]

Set $a_n=\delta(t-r_n)$. By \eqref{eq:invariant},
$s_n,a_n\in H$ and $|s_n|,|a_n|<\rho$. Equation~\eqref{eq:p}
therefore shows that program $p$, with its two oracle
components simulated by $\Phi_{P_n}^{T}$ and the selected
tuple component, computes
\[
F(v+s_n+a_n)=F(v+s_{n+1}).
\]
Since $|s_{n+1}|<\rho$, Equation~\eqref{eq:q} then shows
that program $q$, with this output and the fixed component
$F(u-v)$ as its two oracles, computes $F(u+s_{n+1})$.
Effective substitution of oracle subroutines produces
the next index $P_{n+1}$.

This is an actual computation relative to the fixed tuple.
The indices are constructed using the already computed
branch bits. Inductively each substituted subroutine is
total on its actual oracle, and both outer programs are
valid reductions at the indicated argument pairs. Every
bit computation has finite nesting depth through earlier
indices and terminates. No bound on its running time is
needed. To compute $r_n$, perform the finite construction
through stage $n$.

The program uses only the fixed integers $p,q,j,h$, the
rational $\delta$, and the four tuple components. It does
not compute the numerical states $s_n$, or use
$t,u,v,\rho,b_-,b_+$ as additional real oracles. The finite
program constants may depend on $t,u,v$, as allowed in the
pointwise reduction \eqref{eq:four-values}.

\medskip
\noindent\emph{Recovering the parameter.}
Summing \eqref{eq:recurrence} gives
\[
s_N=\delta\left(Nt-\sum_{nA_N+1/(N\delta)$, and return
the corresponding cut bit. Irrationality of $t$ guarantees
termination. The rational $\delta$ makes the error bound
effective, so this computes $C(t)$ from $T$ and proves
\eqref{eq:four-values}.
\end{proof}

\begin{remark}\label{rem:nonuniform}
The parameter $\delta$ and the reduction program in
Proposition~\ref{prop:recovery} need not be selected
effectively from $(u,v)$. The conclusion is that the
reduction exists for every pair in a comeager set.
The category avoidance argument allows precisely this
form of nonuniformity.
\end{remark}
==== END Rigidity-of-the-Turing-degrees//sections/recovery.tex ====

==== BEGIN Rigidity-of-the-Turing-degrees//sections/representation.tex ====
\section{Representing an arbitrary automorphism}
\label{sec:representation}

We invoke the following established result. Its
scope is essential: it applies to any automorphism of the full
degree order and supplies a single function valid at every input.

\begin{theorem}[Slaman--Woodin]\label{thm:representation}
For every $\pi\in\Aut(\DT,\leT)$ there is an arithmetic function
$\widehat F:2^\N\to2^\N$ such that
\[
\degT{\widehat F(A)}=\pi(\degT A)
\qquad\text{for every }A\subseteq\N.
\]
\end{theorem}

This is Theorem~6.3.1(2) of \cite{SlamanWoodin2005};
see also Theorem~4.29 in the author version of
\cite{SlamanGlobal}. The generic-input assertion in the first
clause of the cited Theorem~6.3.1 is separate from the all-input assertion
used here.

Arithmetic here describes the graph of a single total function.
That graph is Borel. By the Borel-graph
criterion for functions between Polish spaces
\cite[Corollary~4.15]{MarkerDST}, $\widehat F$ is Borel.
The weaker Borel conclusion also appears directly as
Corollary~4.25 in the author version of \cite{SlamanGlobal}.

\begin{lemma}\label{lem:lift}
For an arbitrary $\pi\in\Aut(\DT,\leT)$ there is a Borel
function $F:\R\to2^\N$ with countable fibers such that
\begin{align}
\degT{F(x)}&=\pi(d(x))\qquad(x\in\R),\label{eq:representation}\\
F(x+y)&\leT F(x)\oplus F(y)\qquad(x,y\in\R).
\label{eq:addition}
\end{align}
\end{lemma}

\begin{proof}
Take $F=\widehat F\circ C$ from
Theorem~\ref{thm:representation} and Lemma~\ref{lem:cuts}.
If $F(x)=F(y)$, then $\pi(d(x))=\pi(d(y))$, hence $d(x)=d(y)$.
Each fiber of $F$ therefore injects, by $C$, into a single
Turing degree. Such a degree is countable: its members are
among the outputs of countably many oracle programs with
any fixed representative as oracle.

By Lemma~\ref{lem:cuts}, $d(x+y)\leT d(x)\vee d(y)$.
Since $\pi$ preserves order and joins,
\[
\degT{F(x+y)}
\leT \pi(d(x))\vee\pi(d(y))
=\degT{F(x)\oplus F(y)}.
\]
This is exactly \eqref{eq:addition}.
\end{proof}

The representing function is not required to be injective,
or to give the same output set on equivalent input sets.
Equation~\eqref{eq:representation} prescribes only its output
degree. The countable-fiber property is the consequence of
injectivity of the automorphism that will enter the argument.
==== END Rigidity-of-the-Turing-degrees//sections/representation.tex ====

==== BEGIN Rigidity-of-the-Turing-degrees//sections/rigidity.tex ====
\section{Rigidity and biinterpretability}
\label{sec:rigidity}

We now apply the recovery construction to the full degree
structure.

\begin{proof}[Proof of Theorem~\ref{thm:rigidity}]
Fix an arbitrary order automorphism $\pi$ and take the
Borel map $F$ given by Lemma~\ref{lem:lift}. Fix an
irrational $t\in(0,1)$. Proposition~\ref{prop:recovery}
gives a comeager set $G_t$ of pairs $(u,v)$ for which
\eqref{eq:four-values} holds with a suitable rational
$\delta\in(0,1)$.

For such a pair, put
$\mathbf b=d(t)\vee d(u)\vee d(v)$.
Each argument in the four values on the right of
\eqref{eq:four-values} is a rational linear combination
of $t,u,v,1$. Lemma~\ref{lem:cuts} bounds its degree by
$\mathbf b$, and Equation~\eqref{eq:representation}
bounds the degree of its $F$-value by $\pi(\mathbf b)$.
The same upper bound holds for the finite join of the
four values. Thus
\[
d(t)\leT \pi\bigl(d(t)\vee d(u)\vee d(v)\bigr)
\qquad((u,v)\in G_t).
\]
Applying the inverse order automorphism yields
\begin{equation}\label{eq:generic-bound}
\pi^{-1}(d(t))\leT d(t)\vee d(u)\vee d(v)
\qquad((u,v)\in G_t).
\end{equation}

Choose one fixed set $Y$ representing $\pi^{-1}(d(t))$.
If $Y\not\leT C(t)$, Lemma~\ref{lem:avoidance} says that
\[
\{(u,v):Y\leT C(t)\oplus C(u)\oplus C(v)\}
\]
is meager. But \eqref{eq:generic-bound} puts the
comeager set $G_t$ inside this set, contradicting the
Baire Category Theorem for $\R^2$. Consequently
\[
\pi^{-1}(d(t))\leT d(t).
\]
The set $Y$ is fixed before the pair varies. No common
index for the reductions in \eqref{eq:generic-bound}
is required.

The irrational $t$ was arbitrary. By Lemma~\ref{lem:cuts},
its degrees cover every noncomputable degree, and the
least degree is fixed. We have therefore proved
\begin{equation}\label{eq:one-sided}
\pi^{-1}(\mathbf a)\leT\mathbf a
\qquad(\mathbf a\in\DT)
\end{equation}
for every order automorphism $\pi$.
Apply this result to the automorphism $\pi^{-1}$ to
obtain $\pi(\mathbf a)\leT\mathbf a$. Applying $\pi$
to \eqref{eq:one-sided} gives
$\mathbf a\leT\pi(\mathbf a)$. Antisymmetry now gives
$\pi(\mathbf a)=\mathbf a$ for every degree.
\end{proof}

The second application uses Theorem~\ref{thm:representation}
for the inverse degree automorphism. It does not require
an inverse of $F$, which may have nontrivial fibers.

\begin{corollary}\label{cor:biinterpretability}
The Turing-degree ordering is biinterpretable without parameters
with full second-order arithmetic, in the sense of
\cite[Definition~7.5.1]{SlamanWoodin2005}.
\end{corollary}

\begin{proof}
Slaman and Woodin prove that this property is equivalent to
rigidity \cite[Theorem~7.5.3]{SlamanWoodin2005}.
Apply Theorem~\ref{thm:rigidity}.
\end{proof}
==== END Rigidity-of-the-Turing-degrees//sections/rigidity.tex ====