turing_degrees_rigidity_v2.txt @ 5068a47

5068a47
% =====================================================================
% 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_i<x\},\qquad d(x)=\degT{C(x)}.
\]
So $C(x)$ records exactly which rationals lie strictly below $x$; by
density of $\Q$ this determines $x$. All computability assertions about
real numbers below refer to these strict cuts.

\begin{lemma}\label{lem:cuts}
(a) The map $C:\R\to2^\N$ is Borel and injective.
(b) If $k\ge1$, $c_0,\dots,c_k\in\Q$, and $x_1,\dots,x_k\in\R$, then
\[
d\Bigl(c_0+\sum_{i=1}^{k}c_ix_i\Bigr)\ \leT\ \bigvee_{i=1}^{k}d(x_i).
\]
(c) Every noncomputable degree equals $d(t)$ for some irrational
$t\in(0,1)$.
\end{lemma}

\begin{proof}
(a) The $i$th coordinate of $C$ is the indicator function of the open ray
$(q_i,\infty)$, which is Borel; a map into a countable product is Borel
as soon as all coordinates are. If $x<y$, choose a rational $q_i$ with
$x<q_i<y$; then $i\in C(y)\setminus C(x)$, so $C$ is injective.

(b) Let $z=c_0+\sum_ic_ix_i$. An oracle for all the cuts $C(x_i)$
computes rational brackets of each $x_i$ of arbitrarily small width:
search over pairs of rationals $a<b$ and check the cut bits to confirm
$a<x_i\le b$. Combining brackets for the $x_i$ with the rational
arithmetic of the coefficients gives rationals $a_m\le z\le b_m$ with
$b_m-a_m\le 2^{-m}$, uniformly in $m$.

If $z$ is irrational, then for a rational query $q$ we have $q\ne z$, so
for all large $m$ the interval $[a_m,b_m]$ misses $q$; comparing $q$ with
$a_m$ then decides whether $q<z$. This computes $C(z)$. If $z$ is
rational, then $C(z)$ is computable, because $q_i<z$ is decided by direct
comparison of rationals; a computable set is reducible to any oracle.
Hence a reduction exists in either case. It may depend on the tuple, and
we do not claim an algorithm that decides which case occurs.

(c) Let $B\subseteq\N$ be noncomputable and put
$t=\sum_{n\ge0}B(n)2^{-n-1}$. Then $t\ne0$ and $t\ne1$, since $t=0$
forces $B=\emptyset$ and $t=1$ forces $B=\N$, both computable. Also $t$ is
irrational: if $t$ were rational, every binary expansion of $t$ would be
eventually periodic, hence computable, but $B$ is one of the at most two
binary expansions of $t$; so $B$ would be computable, a contradiction.

The bits of $B$ give the partial sums of the series, hence rational
brackets for $t$; by the argument in (b) applied to the irrational $t$,
this computes $C(t)$. Conversely, given $C(t)$ we recover the digits
$B(n)$ one at a time. Having recovered $B(0),\dots,B(n-1)$, form the
truncation $s_n=\sum_{m<n}B(m)2^{-m-1}$; then
$t-s_n\in[0,2^{-n}]$, and $B(n)=1$ exactly when
$s_n+2^{-n-1}<t$, because equality would make $t$ rational. Comparing $t$
with a rational is a cut query. Hence $B\leT C(t)$, and
$C(t)\equivT B$.
\end{proof}

\subsection{Category}

A set is \emph{nowhere dense} if its closure has empty interior, and
\emph{meager} if it is a countable union of nowhere dense sets;
\emph{comeager} means that the complement is meager. We use the Baire
Category Theorem, and the fact that Borel subsets of a Polish space have
the Baire property \cite[Theorem~2.52 and Corollary~2.57]{MarkerDST}.

\begin{lemma}\label{lem:continuity}
Let $X$ be Polish, $Y$ second countable, and $f:X\to Y$ Borel. Then
there is a comeager $D\subseteq X$ such that $f|D$ is continuous.
\end{lemma}

\begin{proof}
Let $(U_n)$ be a countable basis for $Y$. By the Baire property, for each
$n$ there is an open $V_n$ with
$f^{-1}(U_n)\mathbin{\triangle}V_n\subseteq M_n$ meager. Put
$D=X\setminus\bigcup_nM_n$. For $x\in D$,
$x\in f^{-1}(U_n)$ iff $x\in V_n$; that is,
$(f|D)^{-1}(U_n)=D\cap V_n$, which is open in $D$.
\end{proof}

In particular, if the codomain of $f$ is countable and discrete (such as
$\N$), then $f|D$ is locally constant at each point of $D$: each fibre is
an open subset of $D$. We use exactly this in the recovery proof, and in
Lemma~\ref{lem:continuity} as applied to a bit-valued function.

The last lemma of the section is the relative category cone avoidance
principle attributed to Sacks in \cite[Lemma~4.1]{KumarShelah2023}. It is
the tool that will delete the two auxiliary reals from a degree bound.

\begin{lemma}[Category avoidance]\label{lem:avoidance}
Let $A,Y\subseteq\N$ with $Y\not\leT A$. Then
\[
\bigl\{(u,v)\in\R^2: Y\leT A\oplus C(u)\oplus C(v)\bigr\}
\]
is meager.
\end{lemma}

\begin{proof}
For an index $e$, let $S_e$ be the set of pairs $(u,v)$ with both
coordinates irrational such that $\Phi_e$ with oracle
$A\oplus C(u)\oplus C(v)$ is the characteristic function of $Y$. Suppose
$S_e$ is dense in a nonempty open rectangle $R$ with rational corners.
We show $Y\leT A$, uniformly in $e$ and the corners of $R$, which is the
contradiction.

Given $n$, search relative to $A$ for a finite halting computation of
$\Phi_e(n)$ together with a finite table of answers to the two variable
oracles, subject to two conditions: queries to $A$ are answered by $A$
itself, and the table is \emph{compatible} with some nonempty open
subrectangle of $R$. Compatibility for a cut means the following:
answering $1$ to a rational $q$ imposes $q<u$, answering $0$ imposes
$u\le q$. A finite table of such constraints (together with the corners
of $R$) is satisfiable throughout a nonempty open interval exactly when
the largest lower bound is smaller than the smallest upper bound; this is
decidable rational arithmetic, and the same check applies to $v$.
Repeated queries must be answered consistently.

The search terminates. There is a pair $(u,v)\in S_e\cap R$, and
$\Phi_e(n)$ halts on it. Since $u,v$ are irrational, none of the finitely
many queried rationals equals $u$ or $v$, so the finite transcript of that
computation holds throughout a small open box around $(u,v)$ inside $R$,
and that transcript is found by the search.

The search is sound. Suppose it accepts a transcript with table $W$,
compatible with a nonempty open box $R'\subseteq R$. By density of $S_e$
in $R$ there is a pair in $S_e\cap R'$; the table holds there, so on that
pair the same deterministic computation halts with the same output, which
is $Y(n)$. Hence the search always outputs $Y(n)$. Therefore $Y\leT A$,
contradiction.

So $S_e$ is not dense in any open rectangle with rational corners. Those
rectangles form a basis, so $S_e$ is nowhere dense. The pairs with a
rational coordinate form a countable union of nowhere dense lines.
Taking the countable union of all these sets over $e$ completes the
proof.
\end{proof}

The index of the reduction in Lemma~\ref{lem:avoidance} may depend on
$(u,v)$: the proof takes a union over all indices, so no uniformity
across the success set is needed. This point recurs in
Proposition~\ref{prop:recovery} and in the proof of
Theorem~\ref{thm:rigidity}.

% =====================================================================
\section{Representing an arbitrary automorphism}\label{sec:representation}

The following is the sole external input. Its scope matters: it applies
to \emph{any} automorphism of the full degree order and yields a single
function valid at \emph{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$ with
\[
\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 of the author's version of \cite{SlamanGlobal}. The
generic-input assertion in the first clause of that theorem is separate
from, and weaker than, the all-input assertion used here.

\emph{Arithmetic} refers to the graph of a single total function, which is
a Borel subset of $2^\N\times2^\N$. By the Borel-graph criterion
\cite[Corollary~4.15]{MarkerDST}, $\widehat F$ is Borel; the weaker Borel
conclusion is also Corollary~4.25 in the author's version of
\cite{SlamanGlobal}.

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

\begin{proof}
Let $F=\widehat F\circ C$, using Theorem~\ref{thm:representation} and the
cut map of Lemma~\ref{lem:cuts}. As a composition of Borel maps, $F$ is
Borel, and \eqref{eq:representation} holds by construction.

If $F(x)=F(y)$, then $\pi(d(x))=\pi(d(y))$, and injectivity of $\pi$ gives
$d(x)=d(y)$. So each fibre of $F$ is carried by $C$ into a single Turing
degree. Every degree is countable: its members are exactly the sets
computed by the countably many oracle programs from any one
representative. Hence every fibre of $F$ is countable.

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

No injectivity of $F$ is available or needed:
\eqref{eq:representation} prescribes only the \emph{degree} of the output
set, and $F$ may take the same value at two reals of the same degree. The
countable-fibre property is all that the recovery argument uses.

% =====================================================================
\section{Recovery from four values}\label{sec:recovery}

This section isolates the constructive core of the proof from degrees
entirely. The only hypotheses are Borelness, countable fibres, and
subadditivity up to join.

\begin{proposition}[Recovery from four values]\label{prop:recovery}
Let $F:\R\to2^\N$ be Borel with countable fibres and suppose
\[
F(x+y)\leT F(x)\oplus F(y)\qquad(x,y\in\R).
\]
Then for every irrational $t\in(0,1)$ there is a comeager set
$G_t\subseteq\R^2$ such that for each $(u,v)\in G_t$ there is a rational
$\delta\in(0,1)$ with
\begin{equation}\label{eq:four-values}
C(t)\ \leT\
F(u)\oplus F(u-v)\oplus
F(v-u+\delta t)\oplus F(v-u+\delta(t-1)).
\end{equation}
\end{proposition}

The four arguments are $u$, $u-v$, $v-u+\delta t$, and
$v-u+\delta(t-1)$; the third and fourth are the two possible positions of
a walker that started at $v-u$ and took the step $\delta(t-r)$ with
$r=0$ or $r=1$.

\begin{proof}
The two auxiliary reals $u,v$ let us move from $u+s$ to $u+s+a$ by two
additions, each of which changes only one summand:
\[
(u+s)+(v-u+a)=v+s+a,\qquad (v+s+a)+(u-v)=u+s+a.
\]
If the programs witnessing these two additions can be held fixed while
$s$ and $a$ vary, then the oracles $F(v-u+a)$ and $F(u-v)$ turn an oracle
for $F(u+s)$ into one for $F(u+s+a)$. Only the increments $\delta t$ and
$\delta(t-1)$ occur, so the fixed increment oracles are the third and
fourth entries of \eqref{eq:four-values}, and the fixed return oracle is
the second. The first entry is the starting point.

\medskip
\noindent\emph{Step 1: two local addition programs.}
For $(x,y)\in\R^2$ let $e(x,y)$ be the least index with
\[
\Phi_{e(x,y)}^{F(x)\oplus F(y)}=F(x+y).
\]
Such an index exists by hypothesis. For a fixed $e$, the set of triples
$(X,Y,Z)$ with $\Phi_e^{X\oplus Y}=Z$ is Borel: for each output bit the
condition is that the machine halts and prints correctly, which is a
Borel condition in the oracle. Hence $\{e=e_0\}$ is Borel for each $e_0$,
being a finite Boolean combination of such conditions, and
$e:\R^2\to\N$ is Borel.

Apply Lemma~\ref{lem:continuity} to $F$ and to $e$, getting comeager sets
$D\subseteq\R$ and $E\subseteq\R^2$ with $F|D$ and $e|E$ continuous. Fix
the given $t$ and put
\[
H=\Q+\Q t=\{p+qt : p,q\in\Q\},
\]
a countable subgroup of $\R$ containing $t$, $0$ and $1$, hence containing
every state and every increment that can occur. Let $G_t$ be the set of
pairs $(u,v)$ such that
\begin{equation}\label{eq:all-shifts}
u+s\in D,\qquad
(u+s,\,v-u+a)\in E,\qquad
(v+s,\,u-v)\in E
\qquad\text{for all }s,a\in H.
\end{equation}
Since $H$ is countable, $G_t$ is an intersection of countably many sets.
For fixed $s,a$, the first condition is the pullback of the comeager set
$D$ under the translation $u\mapsto u+s$, and the other two are pullbacks
of $E$ under the affine homeomorphisms
\[
(u,v)\mapsto (u+s,\,v-u+a),\qquad (u,v)\mapsto (v+s,\,u-v),
\]
with inverses $(w,z)\mapsto(w-s,\,z+w-s-a)$ and
$(w,z)\mapsto(z+w-s,\,w-s)$. Hence $G_t$ is comeager.

\medskip
\noindent\emph{Step 2: constants that persist along the walk.}
Fix $(u,v)\in G_t$ and put
\[
p=e(u,v-u),\qquad q=e(v,u-v).
\]
The points $(u,v-u)$ and $(v,u-v)$ lie in $E$ by \eqref{eq:all-shifts}.
Since $e|E$ is continuous into a discrete space, it is locally constant
at each point of $E$: there are open neighbourhoods
$W_p\ni(u,v-u)$ and $W_q\ni(v,u-v)$ with
\[
(x,y)\in W_p\cap E\Rightarrow e(x,y)=p,\qquad
(x,y)\in W_q\cap E\Rightarrow e(x,y)=q.
\]
Choose $0<\rho<1$ so that $W_p$ contains every $(u+s,v-u+a)$ and $W_q$
contains every $(v+s,u-v)$ with $|s|,|a|<\rho$. Combining with
\eqref{eq:all-shifts} and with membership in $E$,
\begin{align}
e(u+s,\,v-u+a)&=p
&&(s,a\in H,\ |s|,|a|<\rho),\label{eq:p}\\
e(v+s,\,u-v)&=q
&&(s\in H,\ |s|<\rho).\label{eq:q}
\end{align}
Thus $p$ and $q$ perform the two additions listed at the start,
uniformly in $s,a$ inside the radius $\rho$.

\medskip
\noindent\emph{Step 3: two endpoints and a tested bit.}
Choose $b_-$ with $-\rho<b_-<0$ and $u+b_-\in D$. The set
$D\cap(u,u+\rho)$ is comeager in the interval $(u,u+\rho)$, hence
uncountable; the fibre of $F(u+b_-)$ is countable; so there is
$b_+\in(0,\rho)$ with $u+b_+\in D$ and $F(u+b_-)\ne F(u+b_+)$. Fix a bit
$j$ on which those two sets differ and put $h=F(u+b_+)(j)$.

By continuity of $F|D$ at $b_-$ and at $b_+$, there are
$\varepsilon_1,\varepsilon_2>0$ 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_-<0<b_+$ and $0\in H$. Suppose
$s_n\in H\cap[b_-,b_+]$. If $r_n=0$, then by \eqref{eq:right} the point
$s_n$ is not in $[b_+-\delta,b_+]$, so $s_n<b_+-\delta$; the increment
$\delta t\in(0,\delta)$ is positive, so $s_{n+1}\in(s_n,b_+)$. If
$r_n=1$, then by \eqref{eq:left} the point $s_n$ is not in
$[b_-,b_-+\delta]$, so $s_n>b_-+\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_{n<N}r_n\Bigr).
\]
Since $|s_N|<\rho<1$, the rationals
$A_N=N^{-1}\sum_{n<N}r_n$ computed from $T$ satisfy
\begin{equation}\label{eq:error}
|t-A_N|<\frac{1}{N\delta}\qquad(N\ge1).
\end{equation}
To decide whether $q<t$ for a rational $q$, search for $N$ with
$q<A_N-1/(N\delta)$ or with $q>A_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<t$ is decided, $C(t)\leT T$, and
\eqref{eq:four-values} holds.
\end{proof}

\begin{remark}\label{rem:nonuniform}
The rational $\delta$ and the reduction in Proposition~\ref{prop:recovery}
need not be found effectively from $(u,v)$. The content of the
proposition is that a reduction exists for every pair in a comeager set.
Lemma~\ref{lem:avoidance} tolerates exactly this nonuniformity, since it
takes a union over all indices.
\end{remark}

\begin{remark}\label{rem:related}
Recovery of a real from finitely many values of a perfect-set coding is a
known theme. Groszek and Slaman recover a real from two branches of a
perfect tree plus a sequence supplying a dense set
\cite[Lemma~2.2]{GroszekSlaman1998}; Lutz and Siskind recover any real
from four elements of a perfect set plus one fixed real that computes a
countable dense subset \cite[Theorem~4.3]{LutzSiskind2025}. Here the
hypotheses are different: one Borel function satisfying a join
subadditivity law, four prescribed affine arguments, and a bounded
recurrence that removes the need for any additional real oracle. The
closest methodological relative is Kjos-Hanssen's proof of rigidity for
automorphisms induced by permutations of $\N$
\cite[Theorem~20]{KjosHanssen2018}, which recovers a Bernoulli parameter
and uses a measure cone theorem instead of category.
\end{remark}

% =====================================================================
\section{Rigidity and biinterpretability}\label{sec:rigidity}

\begin{proof}[Proof of Theorem~\ref{thm:rigidity}]
Fix an order automorphism $\pi$ and take the Borel map $F$ of
Lemma~\ref{lem:lift}. Fix an irrational $t\in(0,1)$ and let $G_t$ be the
comeager set of Proposition~\ref{prop:recovery}. For $(u,v)\in G_t$, let
$\delta$ be as in \eqref{eq:four-values} and put
\[
\mathbf b=d(t)\vee d(u)\vee d(v).
\]
Each of the four arguments in \eqref{eq:four-values} is a rational affine
combination of $t,u,v$, so by Lemma~\ref{lem:cuts} its degree is at most
$\mathbf b$; by \eqref{eq:representation} the degree of its $F$-value is
at most $\pi(\mathbf b)$. The same bound holds for the finite join of the
four values, hence
\[
d(t)\leT\pi\bigl(d(t)\vee d(u)\vee d(v)\bigr)\qquad((u,v)\in G_t).
\]
Apply the inverse automorphism, which also preserves order and joins:
\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}

Fix one set $Y\subseteq\N$ of degree $\pi^{-1}(d(t))$. If
$Y\not\leT C(t)$, then Lemma~\ref{lem:avoidance}, applied with
$A=C(t)$, says that
\[
\bigl\{(u,v):Y\leT C(t)\oplus C(u)\oplus C(v)\bigr\}
\]
is meager. But \eqref{eq:generic-bound} places the comeager set $G_t$
inside it, since $\pi^{-1}(d(t))\leT d(t)\vee d(u)\vee d(v)$ means that
$Y$ is computable from $C(t)\oplus C(u)\oplus C(v)$. A comeager set
cannot be meager, since $\R^2$ is Baire and nonempty. Hence
$Y\leT C(t)$, that is,
\[
\pi^{-1}(d(t))\leT d(t).
\]
The set $Y$ was fixed before $(u,v)$ varied, and the reductions in
\eqref{eq:generic-bound} need not be uniform in $(u,v)$.

The irrational $t\in(0,1)$ was arbitrary; by Lemma~\ref{lem:cuts}(c) the
degrees $d(t)$ for such $t$ are exactly the noncomputable degrees, and
$\pi^{-1}(\mathbf 0)=\mathbf 0$. Therefore
\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$.

Now apply \eqref{eq:one-sided} to the automorphism $\pi^{-1}$, which is
also an order automorphism and also admits a representing function by
Theorem~\ref{thm:representation}. This gives
$\pi(\mathbf a)\leT\mathbf a$ for all $\mathbf a$. Together with
\eqref{eq:one-sided} and antisymmetry of $\leT$, we get
$\pi(\mathbf a)=\mathbf a$ for every degree $\mathbf a$.
\end{proof}

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

\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 biinterpretability without parameters is
equivalent to rigidity of the degree ordering
\cite[Theorem~7.5.3]{SlamanWoodin2005}. Apply
Theorem~\ref{thm:rigidity}.
\end{proof}

% =====================================================================
\begin{thebibliography}{99}
\bibitem{GroszekSlaman1998} M.~J. Groszek and T.~A. Slaman, \emph{A basis theorem for perfect sets}, Bull. Symbolic Logic \textbf{4} (1998), no.~2, 204--209; author's version (2000) at \url{https://math.berkeley.edu/~slaman/papers/prikry.pdf}, whose numbering is used here.
\bibitem{JockuschSolovay1977} C.~G. Jockusch, Jr. and R.~M. Solovay, \emph{Fixed points of jump preserving automorphisms of degrees}, Israel J. Math. \textbf{26} (1977), no.~1, 91--94.
\bibitem{KjosHanssen2018} B. Kjos-Hanssen, \emph{Permutations of the integers induce only the trivial automorphism of the Turing degrees}, Bull. Symbolic Logic \textbf{24} (2018), no.~2, 165--174; arXiv:1603.00525, whose numbering is used here.
\bibitem{KumarShelah2023} A. Kumar and S. Shelah, \emph{Large Turing independent sets}, Proc. Amer. Math. Soc. \textbf{151} (2023), no.~1, 355--367.
\bibitem{LutzSiskind2025} P. Lutz and B. Siskind, \emph{Part 1 of Martin's conjecture for order-preserving and measure-preserving functions}, J. Amer. Math. Soc. \textbf{38} (2025), no.~2, 319--367; arXiv:2305.19646, whose numbering is used here.
\bibitem{MarkerDST} D. Marker, \emph{Descriptive Set Theory}, course notes, Fall 2002, \url{https://www.math.uic.edu/~marker/math512/dst.pdf}.
\bibitem{NerodeShore1980} A. Nerode and R.~A. Shore, \emph{Reducibility orderings: theories, definability and automorphisms}, Ann. Math. Logic \textbf{18} (1980), no.~1, 61--89.
\bibitem{Shore2007} R.~A. Shore, \emph{Direct and local definitions of the Turing jump}, J. Math. Logic \textbf{7} (2007), no.~2, 229--262.
\bibitem{ShoreSlaman1999} R.~A. Shore and T.~A. Slaman, \emph{Defining the Turing jump}, Math. Res. Lett. \textbf{6} (1999), no.~5--6, 711--722; author's version at \url{https://math.berkeley.edu/~slaman/papers/jump.pdf}.
\bibitem{SlamanGlobal} T.~A. Slaman, \emph{Global properties of the Turing degrees and the Turing jump}, in Computational Prospects of Infinity, Part I, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. \textbf{14}, World Scientific, 2008, 83--101; author's version at \url{https://math.berkeley.edu/~slaman/papers/IMS_slaman.pdf}, whose numbering is used here.
\bibitem{SlamanWoodin2005} T.~A. Slaman and W.~H. Woodin, \emph{Definability in Degree Structures}, unpublished manuscript, 21 July 2005, \url{https://math.berkeley.edu/~slaman/talks/sw.pdf}.
\bibitem{Soare1987} R.~I. Soare, \emph{Recursively Enumerable Sets and Degrees}, Perspectives in Mathematical Logic, Springer, 1987.
\bibitem{Turing1939} A.~M. Turing, \emph{Systems of logic based on ordinals}, Proc. London Math. Soc. (2) \textbf{45} (1939), 161--228.
\end{thebibliography}
\end{document}