% =====================================================================
% turing_degrees_rigidity_v2.txt
%
% Rigidity of the Turing degrees: a complete, self-contained proof that
% every order automorphism of the Turing degrees is the identity.
%
% This single file replaces the original collection
%   Rigidity-of-the-Turing-degrees/{main,glyph-mappings,references}.tex
%   .../sections/{introduction,preliminaries,representation,recovery,rigidity}.tex
%   .../figures/bounded-recurrence.tex
%
% Exactly one external input is used: the Slaman--Woodin representation
% theorem (Theorem 3.1 below). Everything else is proved here.
%
% Written to be read by a strong high-school student: every symbol is
% introduced before it is used, every lemma has a full proof, and the
% two ideas that make the argument work (a bounded recurrence, and
% Baire category) are explained in plain words first.
% =====================================================================
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=1.1in]{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}}
\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{}
\date{}
\begin{document}
\maketitle

\begin{abstract}
Every order automorphism of the partial order of Turing degrees is the
identity. We give a complete proof. The single external input is a
Slaman--Woodin representation theorem, which turns an arbitrary
automorphism into a Borel function on sets of integers. Everything else
is proved from scratch, and two tools do the work: a four-value recovery
lemma for Borel functions that are subadditive up to join, and a Baire
category argument that removes the auxiliary reals used in the recovery.
\end{abstract}

% =====================================================================
\section{Introduction}\label{sec:introduction}

\subsection{What a Turing degree is}

Fix once and for all an effective list $(\Phi_e)_{e\in\N}$ of Turing
machines (think: programs). A set $A\subseteq\N$ is \emph{computable} if
some machine decides membership in $A$: it halts with output $1$ on
inputs $n\in A$ and with output $0$ on inputs $n\notin A$.

An \emph{oracle} for a set $B\subseteq\N$ is a black box that answers the
question ``is $n\in B$?'' for any $n$, instantly and correctly. An
\emph{oracle machine} is a Turing machine that may consult such a box at
any time. Write
\[
A\leT B
\]
if some oracle machine with an oracle for $B$ decides membership in $A$.
Thus $A\leT B$ means ``$B$ carries at least as much information as $A$'',
or ``$A$ can be computed from $B$''. This relation is reflexive and
transitive; the underlying notion of relative computation is Turing's
\cite[Section~4]{Turing1939}, and \cite{Soare1987} is the standard
reference for the subject.

Mutual reducibility $A\equivT B$ (both $A\leT B$ and $B\leT A$) is an
equivalence relation. The class $\degT A$ of $A$ is its \emph{Turing
degree}. The relation
\[
\degT A\leT\degT B \iff A\leT B
\]
is well defined and makes the set $\DT$ of all degrees a partial order,
the \emph{Turing degrees}. The least degree $\mathbf 0$ is the degree of
the computable sets. Any two degrees have a least upper bound, the
\emph{join} $\mathbf a\vee\mathbf b$: it is the degree of
$A\oplus B$, where $A\oplus B$ interleaves the characteristic functions
of $A$ and $B$. An oracle computes $A\oplus B$ exactly when it computes
both $A$ and $B$, so $\mathbf a\vee\mathbf b$ is indeed the least upper
bound. Finite joins are obtained by repeating this operation; the
result does not depend on the bracketing.

\subsection{The question}

An \emph{order automorphism} of $(\DT,\leT)$ is a bijection
$\pi:\DT\to\DT$ with
\[
\mathbf a\leT\mathbf b
\quad\Longleftrightarrow\quad
\pi(\mathbf a)\leT\pi(\mathbf b).
\]
Such a $\pi$ is a symmetry of the information order: it may rename
degrees, but it must preserve every comparison. The rigidity conjecture
predicts that there is nothing to rename, that is, that the ordering by
itself determines each degree. We prove it.

\begin{theorem}[Rigidity]\label{thm:rigidity}
Every order automorphism $\pi$ of $(\DT,\leT)$ is the identity:
\[
\pi(\mathbf a)=\mathbf a \qquad(\mathbf a\in\DT).
\]
\end{theorem}

No definability, measurability, or continuity is assumed on $\pi$; it is
an arbitrary bijection of a set of size $2^{\aleph_0}$.

Two remarks will be used without further comment. First, an order
automorphism fixes $\mathbf 0$, since $\mathbf 0$ is the unique least
element. Second, it preserves joins, since a join is a least upper bound
and least upper bounds are described purely in terms of $\leT$. Thus
$\pi(\mathbf 0)=\mathbf 0$ and
$\pi(\mathbf a\vee\mathbf b)=\pi(\mathbf a)\vee\pi(\mathbf b)$.

\subsection{What was already known}

The \emph{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 every degree above $\mathbf 0^{(4)}$, the fourth
jump of $\mathbf 0$ \cite{JockuschSolovay1977}. Shore and Slaman proved
that the jump is definable from the ordering alone
\cite{ShoreSlaman1999}, so every order automorphism preserves the jump;
Shore later gave direct degree-theoretic definitions \cite{Shore2007}.

A \emph{cone} is the set 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]{SlamanGlobal}. Slaman and Woodin improved this to a
cone fixed by \emph{all} automorphisms at once, namely the cone above
$\mathbf 0''$. They also showed that each automorphism is induced on
degrees by an arithmetic function on sets of integers, and that the
automorphism group is countable
\cite{SlamanWoodin2005,SlamanGlobal}.

So the ordering does determine a great deal. What was missing was any
control on degrees below $\mathbf 0''$, where an automorphism could in
principle permute freely.

\subsection{The plan}

The proof has four steps, one per section.

\begin{enumerate}
\item \emph{Code reals by degrees} (Section~\ref{sec:preliminaries}).
Associate to a real number $x$ the set $C(x)$ of rationals below $x$, and
let $d(x)$ be its degree. Rational affine combinations then have degrees
below the join of the ingredients (Lemma~\ref{lem:cuts}). Two category
lemmas are also proved here.
\item \emph{Pass to a nice function} (Section~\ref{sec:representation}).
By Slaman--Woodin, an arbitrary $\pi$ is induced by an arithmetic, hence
Borel, function $\widehat F$ on sets. Composing with $C$ gives a Borel
$F:\R\to2^\N$ with $\degT{F(x)}=\pi(d(x))$ and, because $\pi$ preserves
joins, $F(x+y)\leT F(x)\oplus F(y)$.
\item \emph{Recover a parameter from four values}
(Section~\ref{sec:recovery}). For such an $F$, and any irrational
$t\in(0,1)$, the cut $C(t)$ is computable from four values of $F$ at
explicit affine arguments, for a comeager set of auxiliary pairs $(u,v)$.
The engine is a bounded recurrence, explained in plain words below.
\item \emph{Remove the auxiliaries} (Section~\ref{sec:rigidity}). A bound
that holds for comeager many $(u,v)$ and mentions $u,v$ can be freed of
them by Sacks' category cone avoidance. Applied to $\pi$ and to
$\pi^{-1}$, this forces $\pi$ to be the identity.
\end{enumerate}

The bounded recurrence, in plain words. Pick a rational step length
$\delta>0$. Start a walker at $0$. At stage $n$ the walker is at
$s_n$; we look at one bit of $F(u+s_n)$ and use it to choose one of two
steps, $+\delta t$ or $-\delta(1-t)$. The bit is rigged so that
near the right end of an interval $[b_-,b_+]$ the walker is pushed left,
and near the left end pushed right. Since each step is shorter than
$\delta$, the walker never leaves $[b_-,b_+]$. Summing the steps shows
that a state $s_N$ is $\delta(Nt-\#\{\text{left steps}\})$, so the
long-run frequency of left steps is $t$ with an explicit error bound.
The point is that the walker's \emph{states} need never be computed by
the reduction: only the \emph{bits}, which are bits of the four known
values of $F$. That is what makes the recovery effective.

\subsection{The one external input}

Step 2 is the only place where we appeal to deep prior work: the
all-input form of the Slaman--Woodin representation theorem, which
assigns to every automorphism of the full degree order a single
arithmetic function on sets that induces it at \emph{every} input, not
merely at generic inputs \cite[Theorem~6.3.1(2)]{SlamanWoodin2005}; it is
restated as Theorem~\ref{thm:representation} below. This supplies the
regularity (Borelness) needed for category arguments, while keeping the
unrestricted scope of Theorem~\ref{thm:rigidity}.

\subsection{A consequence for definability}

Full second-order arithmetic is the two-sorted structure of natural
numbers together with all subsets of $\N$, with arithmetic operations and
membership. Slaman and Woodin interpret this structure inside finite
tuples of Turing degrees. Their \emph{biinterpretability} conjecture asks
whether the relation matching a tuple coding a set $X\subseteq\N$ with
the 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}, so Theorem~\ref{thm:rigidity}
settles it; see Corollary~\ref{cor:biinterpretability}.

\subsection{Organization}

Section~\ref{sec:preliminaries} sets up the coding of reals by degrees and
proves the three lemmas on cuts, continuity, and category avoidance.
Section~\ref{sec:representation} states the Slaman--Woodin theorem and
extracts the Borel function $F$ on $\R$.
Section~\ref{sec:recovery} proves four-value recovery.
Section~\ref{sec:rigidity} proves rigidity and the corollary.

% =====================================================================
\section{Reals, degrees, and category}\label{sec:preliminaries}

\subsection{Coding a real number by a degree}

A degree is attached to a set of integers, but addition lives on the real
line. The bridge is the rational cut. Identify a subset of $\N$ with its
characteristic function, so that $2^\N$ is the set of all subsets of $\N$,
topologized as a product of discrete two-point spaces (Cantor space). Fix
an effective listing $(q_i)_{i\in\N}$ of $\Q$, for instance
$0,1,-1,2,-2,\dots$, and for $x\in\R$ put
\[
C(x)=\{i\in\N : q_i0$ such that the bit $j$ differs from $h$
on $H\cap[b_-,b_-+\varepsilon_1]$ and equals $h$ on
$H\cap[b_+-\varepsilon_2,b_+]$. Any smaller positive number has the same
property, so a rational $\delta$ with
$0<\delta<\min(\rho,\varepsilon_1,\varepsilon_2)$ gives
\begin{align}
F(u+s)(j)&\ne h
&&\bigl(s\in H\cap[b_-,b_-+\delta]\bigr),\label{eq:left}\\
F(u+s)(j)&=h
&&\bigl(s\in H\cap[b_+-\delta,b_+]\bigr).\label{eq:right}
\end{align}
Every translate tested here lies in $D$ by \eqref{eq:all-shifts}; the
endpoints themselves are not tested.

\medskip
\noindent\emph{Step 4: a walk that cannot escape.}
Define $s_0=0$ and, for $n\ge0$,
\begin{equation}\label{eq:recurrence}
r_n=\begin{cases}1,&F(u+s_n)(j)=h,\\ 0,&F(u+s_n)(j)\ne h,\end{cases}
\qquad
s_{n+1}=s_n+\delta(t-r_n).
\end{equation}
Then $s_n\in H\cap[b_-,b_+]$ for all $n$. This is proved by induction on
$n$; the case $n=0$ holds since $b_-<0b_-+\delta$; the increment $\delta(t-1)$ has
size $\delta(1-t)<\delta$, so $s_{n+1}\in(b_-,s_n)$. In both cases
$s_{n+1}\in[b_-,b_+]$, and rationality of $\delta$ together with
$t\in H$ gives $s_{n+1}\in H$.

In particular every $s_n$ and every increment $\delta(t-r_n)$ has absolute
value less than $\rho$, so \eqref{eq:p} and \eqref{eq:q} apply at every
stage. No monotonicity or regularity of the tested bit between the two
endpoints is required; the only feature used is that near either end the
bit points the next step inward. See Figure~\ref{fig:bounded-recurrence}.

\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. In the left strip the tested bit forces
the step $+\delta t$; in the right strip it forces $-\delta(1-t)$. Each
step is shorter than $\delta$, so the walk never leaves $[b_-,b_+]$. The
bit may behave arbitrarily in between. The reduction computes the choices
$r_n$, not the states $s_n$.}
\label{fig:bounded-recurrence}
\end{figure}

\medskip
\noindent\emph{Step 5: the bits are computable from the tuple.}
Let $T$ denote the join on the right of \eqref{eq:four-values}. We
maintain, relative to $T$, an index $P_n$ with
\[
\Phi_{P_n}^{T}=F(u+s_n).
\]
Initially take $P_0$ to be the projection onto the first component
$F(u)$. Given $P_n$, read $\Phi_{P_n}^{T}(j)$, compare with the fixed bit
$h$, and obtain $r_n$. Then select the third component of $T$ if $r_n=0$
and the fourth if $r_n=1$; that component is
$F(v-u+\delta(t-r_n))$.

Put $a_n=\delta(t-r_n)$. By Step 4, $s_n,a_n\in H$ and
$|s_n|,|a_n|,|s_n+a_n|<\rho$. So \eqref{eq:p} applies to the pair
$(s_n,a_n)$: program $p$, run with the two oracle components simulated by
$\Phi_{P_n}^{T}$ and by the selected component, computes
\[
F\bigl(v+s_n+a_n\bigr)=F(v+s_{n+1}).
\]
Since $|s_{n+1}|<\rho$, \eqref{eq:q} applies to $s_{n+1}$: program $q$,
run with this output and with the fixed component $F(u-v)$, computes
$F(u+s_{n+1})$. Substituting oracle programs into one another effectively
produces the next index $P_{n+1}$.

This is a genuine computation relative to the fixed tuple. The indices are
built using the bits already computed; inductively each substituted
program is total on its actual oracle and each outer program is a correct
reduction at the argument pair where it is used; nesting depth is finite
and every bit computation halts. No bound on running time is needed. To
compute $r_n$, carry out the finite construction through stage $n$.

The program uses only the integers $p,q,j,h$, the rational $\delta$, and
the four components of $T$. It does not compute the states $s_n$, and it
does not use $t,u,v,\rho,b_-,b_+$ as oracles. The constants may depend on
$t$ and on $(u,v)$, which is exactly the nonuniformity allowed in
\eqref{eq:four-values}.

\medskip
\noindent\emph{Step 6: recovering the parameter.}
Summing \eqref{eq:recurrence} and using $s_0=0$ gives the telescoping
identity
\[
s_N=\delta\Bigl(Nt-\sum_{nA_N+1/(N\delta)$, and answer accordingly.
The existence of such $N$ follows from \eqref{eq:error} and $q\ne t$; here
irrationality of $t$ is used. So $q