editors: nobody
% =====================================================================
% 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.
% =====================================================================
usetikzlibrary{arrows.meta}
hypersetup{pdftitle={Rigidity of the Turing degrees}}
# Rigidity of the Turing degrees
maketitle
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.
% =====================================================================
# Introduction
## What a Turing degree is
Fix once and for all an effective list $(Phi_e)_{einN}$ of Turing
machines (think: programs). A set $A⊆N$ is computable if
some machine decides membership in $A$: it halts with output $1$ on
inputs $nin A$ and with output $0$ on inputs $nnotin A$.
An oracle for a set $B⊆N$ is a black box that answers the
question ``is $nin B$?'' for any $n$, instantly and correctly. An
oracle machine is a Turing machine that may consult such a box at
any time. Write
[
AleT B
]
if some oracle machine with an oracle for $B$ decides membership in $A$.
Thus $AleT 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] is the standard
reference for the subject.
Mutual reducibility $AequivT B$ (both $AleT B$ and $BleT A$) is an
equivalence relation. The class $degT A$ of $A$ is its Turing
degree. The relation
[
degT AleTdegT B iff AleT B
]
is well defined and makes the set $DT$ of all degrees a partial order,
the Turing degrees. The least degree $mathbf 0$bf0$ is the degree of
the computable sets. Any two degrees have a least upper bound, the
join $mathbf abfaveemathbf b$:bfb$: it is the degree of
$A ⊕ B$, where $A ⊕ B$ interleaves the characteristic functions
of $A$ and $B$. An oracle computes $A ⊕ B$ exactly when it computes
both $A$ and $B$, so $mathbf abfaveemathbf b$bfb$ is indeed the least upper
bound. Finite joins are obtained by repeating this operation; the
result does not depend on the bracketing.
## The question
An order automorphism of $(DT,leT)$ is a bijection
$pi:DTtoDT$ with
[
mathbf abfaleTmathbf bbfb
quad⇔quad
pi(mathbf a)bfa)leTpi(mathbf b).bfb).
]
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.
[Rigidity]
Every order automorphism $pi$ of $(DT,leT)$ is the identity:
[
pi(mathbf a)=bfa)=mathbf abfa qquad(mathbf abfainDT).
]
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$,bf0$, since $mathbf 0$bf0$ 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)=bf0)=mathbf 0$bf0$ and
$pi(mathbf abfaveemathbf b)=bfb)=pi(mathbf a)bfa)veepi(mathbf b)$.bfb)$.
## 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 every input, not
merely at generic inputs cite[Theorem~6.3.1(2)]{SlamanWoodin2005}; it is
restated as Theorem~thm:representation below. This supplies the
regularity (Borelness) needed for category arguments, while keeping the
unrestricted scope of Theorem~thm:rigidity.
## 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 biinterpretability conjecture asks
whether the relation matching a tuple coding a set $X⊆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~thm:rigidity
settles it; see Corollary~cor:biinterpretability.
# Reals, degrees, and category
## 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)_{iinN}$ of $Q$, for instance
$0,1,-1,2,-2,...$, and for $xinR$ put
[
C(x)={iinN : 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.
(a) The map $C:Rto2^N$ is Borel and injective.
(b) If $kge1$, $c_0,...,c_kinQ$, and $x_1,...,x_kinR$, then
[
d(c_0+sum_{i=1}^{k}c_ix_i) leT ∨_{i=1}^{k}d(x_i).
]
(c) Every noncomputable degree equals $d(t)$ for some irrational
$tin(0,1)$.
Proof.
(a) The $i$th coordinate of $C$ is the indicator function of the open ray
$(q_i,∞)$, 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 $iin C(y)∖ 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_ile b$. Combining brackets for the $x_i$ with the rational
arithmetic of the coefficients gives rationals $a_mle zle b_m$ with
$b_m-a_mle 2^{-m}$, uniformly in $m$.
If $z$ is irrational, then for a rational query $q$ we have $qne 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⊆N$ be noncomputable and put
$t=sum_{nge0}B(n)2^{-n-1}$. Then $tne0$ and $tne1$, since $t=0$
forces $B=∅$ 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),...,B(n-1)$, form the
truncation $s_n=sum_{m<n}B(m)2^{-m-1}$; then
$t-s_nin[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 $BleT C(t)$, and
$C(t)equivT B$.
## Category
A set is nowhere dense if its closure has empty interior, and
meager if it is a countable union of nowhere dense sets;
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}.
Let $X$ be Polish, $Y$ second countable, and $f:Xto Y$ Borel. Then
there is a comeager $D⊆ X$ such that $f|D$ is continuous.
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{△}V_n⊆ M_n$ meager. Put
$D=X∖∪_nM_n$. For $xin D$,
$xin f^{-1}(U_n)$ iff $xin V_n$; that is,
$(f|D)^{-1}(U_n)=Dcap V_n$, which is open in $D$.
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~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.
[Category avoidance]
Let $A,Y⊆N$ with $YnotleT A$. Then
[
bigl{(u,v)inR^2: YleT A ⊕ C(u) ⊕ C(v)bigr}
]
is meager.
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 ⊕ C(u) ⊕ C(v)$ is the characteristic function of $Y$. Suppose
$S_e$ is dense in a nonempty open rectangle $R$ with rational corners.
We show $YleT 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 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
$ule 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_ecap 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'⊆ R$. By density of $S_e$
in $R$ there is a pair in $S_ecap 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 $YleT 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.
The index of the reduction in Lemma~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~prop:recovery and in the proof of
Theorem~thm:rigidity.
% =====================================================================
# Representing an arbitrary automorphism
The following is the sole external input. Its scope matters: it applies
to any automorphism of the full degree order and yields a single
function valid at every input.
[Slaman--Woodin]
For every $piinAut(DT,leT)$ there is an arithmetic function
$widehatwidehat F:2^F:2^Nto2^N$ with
[
degT{widehatwidehat F(A)}F(A)=pi(degT A)
qquadfor every A⊆N.
]
This is Theorem~6.3.1(2) of [cite]; see also
Theorem~4.29 of the author's version of [cite]. The
generic-input assertion in the first clause of that theorem is separate
from, and weaker than, the all-input assertion used here.
Arithmetic refers to the graph of a single total function, which is
a Borel subset of $2^Ntimes2^N$. By the Borel-graph criterion
cite[Corollary~4.15]{MarkerDST}, $widehatwidehat F$F$ is Borel; the weaker Borel
conclusion is also Corollary~4.25 in the author's version of
[cite].
For every $piinAut(DT,leT)$ there is a Borel $F:Rto2^N$ with
countable fibres such that, for all $x,yinR$,
degT{F(x)}&=pi(d(x)),
F(x+y)&leT F(x) ⊕ F(y).
Proof.
Let $F=widehatwidehat FFcirc C$, using Theorem~thm:representation and the
cut map of Lemma~lem:cuts. As a composition of Borel maps, $F$ is
Borel, and (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 (eq:addition), Lemma~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))leTpi(d(x))veepi(d(y))
=degT{F(x) ⊕ F(y)},
]
which is (eq:addition).
No injectivity of $F$ is available or needed:
(eq:representation) prescribes only the 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.
% =====================================================================
# Recovery from four values
This section isolates the constructive core of the proof from degrees
entirely. The only hypotheses are Borelness, countable fibres, and
subadditivity up to join.
[Recovery from four values]
Let $F:Rto2^N$ be Borel with countable fibres and suppose
[
F(x+y)leT F(x) ⊕ F(y)qquad(x,yinR).
]
Then for every irrational $tin(0,1)$ there is a comeager set
$G_t⊆R^2$ such that for each $(u,v)in G_t$ there is a rational
$deltain(0,1)$ with
C(t) leT
F(u) ⊕ F(u-v) ⊕
F(v-u+delta t) ⊕ F(v-u+delta(t-1)).
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$.
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 (eq:four-values), and the fixed return oracle is
the second. The first entry is the starting point.
medskip
noindentStep 1: two local addition programs.
For $(x,y)inR^2$ let $e(x,y)$ be the least index with
[
Phi_{e(x,y)}^{F(x) ⊕ 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 ⊕ 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^2toN$ is Borel.
Apply Lemma~lem:continuity to $F$ and to $e$, getting comeager sets
$D⊆R$ and $E⊆R^2$ with $F|D$ and $e|E$ continuous. Fix
the given $t$ and put
[
H=Q+Q t={p+qt : p,qinQ},
]
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
u+sin D,qquad
(u+s,,v-u+a)in E,qquad
(v+s,,u-v)in E
qquadfor all s,ain H.
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 $umapsto 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
noindentStep 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 (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_pni(u,v-u)$ and $W_qni(v,u-v)$ with
[
(x,y)in W_pcap E⇒ e(x,y)=p,qquad
(x,y)in W_qcap E⇒ 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
(eq:all-shifts) and with membership in $E$,
e(u+s,,v-u+a)&=p
&&(s,ain H, |s|,|a|<rho),
e(v+s,,u-v)&=q
&&(sin H, |s|<rho).
Thus $p$ and $q$ perform the two additions listed at the start,
uniformly in $s,a$ inside the radius $rho$.
medskip
noindentStep 3: two endpoints and a tested bit.
Choose $b_-$ with $-rho<b_-<0$ and $u+b_-in D$. The set
$Dcap(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
$ε_1,ε_2>0$ such that the bit $j$ differs from $h$
on $Hcap[b_-,b_-+ε_1]$ and equals $h$ on
$Hcap[b_+-ε_2,b_+]$. Any smaller positive number has the same
property, so a rational $delta$ with
$0<delta<min(rho,ε_1,ε_2)$ gives
F(u+s)(j)&ne h
&&(sin Hcap[b_-,b_-+delta]),
F(u+s)(j)&=h
&&(sin Hcap[b_+-delta,b_+]).
Every translate tested here lies in $D$ by (eq:all-shifts); the
endpoints themselves are not tested.
medskip
noindentStep 4: a walk that cannot escape.
Define $s_0=0$ and, for $nge0$,
r_n=1,&F(u+s_n)(j)=h, 0,&F(u+s_n)(j)ne h,
qquad
s_{n+1}=s_n+delta(t-r_n).
Then $s_nin Hcap[b_-,b_+]$ for all $n$. This is proved by induction on
$n$; the case $n=0$ holds since $b_-<0<b_+$ and $0in H$. Suppose
$s_nin Hcap[b_-,b_+]$. If $r_n=0$, then by (eq:right) the point
$s_n$ is not in $[b_+-delta,b_+]$, so $s_n<b_+-delta$; the increment
$delta tin(0,delta)$ is positive, so $s_{n+1}in(s_n,b_+)$. If
$r_n=1$, then by (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
$tin 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 (eq:p) and (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~fig:bounded-recurrence.
[tb]
centering
[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)$};
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$.
medskip
noindentStep 5: the bits are computable from the tuple.
Let $T$ denote the join on the right of (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_nin H$ and
$|s_n|,|a_n|,|s_n+a_n|<rho$. So (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(v+s_n+a_n)=F(v+s_{n+1}).
]
Since $|s_{n+1}|<rho$, (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
(eq:four-values).
medskip
noindentStep 6: recovering the parameter.
Summing (eq:recurrence) and using $s_0=0$ gives the telescoping
identity
[
s_N=delta(Nt-sum_{n<N}r_n).
]
Since $|s_N|<rho<1$, the rationals
$A_N=N^{-1}sum_{n<N}r_n$ computed from $T$ satisfy
|t-A_N|<(1)/(Ndelta)qquad(Nge1).
To decide whether $q<t$ for a rational $q$, search for $N$ with
$q<A_N-1/(Ndelta)$ or with $q>A_N+1/(Ndelta)$, and answer accordingly.
The existence of such $N$ follows from (eq:error) and $qne t$; here
irrationality of $t$ is used. So $q<t$ is decided, $C(t)leT T$, and
(eq:four-values) holds.
The rational $delta$ and the reduction in Proposition~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~lem:avoidance tolerates exactly this nonuniformity, since it
takes a union over all indices.
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.
% =====================================================================
# Rigidity and biinterpretability
Proof. [Proof of Theorem~thm:rigidity]
Fix an order automorphism $pi$ and take the Borel map $F$ of
Lemma~lem:lift. Fix an irrational $tin(0,1)$ and let $G_t$ be the
comeager set of Proposition~prop:recovery. For $(u,v)in G_t$, let
$delta$ be as in (eq:four-values) and put
[
mathbf b=d(t)bfb=d(t)vee d(u)vee d(v).
]
Each of the four arguments in (eq:four-values) is a rational affine
combination of $t,u,v$, so by Lemma~lem:cuts its degree is at most
$mathbf b$;bfb$; by (eq:representation) the degree of its $F$-value is
at most $pi(mathbf b)$.bfb)$. The same bound holds for the finite join of the
four values, hence
[
d(t)leTpi(d(t)vee d(u)vee d(v))qquad((u,v)in G_t).
]
Apply the inverse automorphism, which also preserves order and joins:
pi^{-1}(d(t))leT d(t)vee d(u)vee d(v)qquad((u,v)in G_t).
Fix one set $Y⊆N$ of degree $pi^{-1}(d(t))$. If
$YnotleT C(t)$, then Lemma~lem:avoidance, applied with
$A=C(t)$, says that
[
bigl{(u,v):YleT C(t) ⊕ C(u) ⊕ C(v)bigr}
]
is meager. But (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) ⊕ C(u) ⊕ C(v)$. A comeager set
cannot be meager, since $R^2$ is Baire and nonempty. Hence
$YleT C(t)$, that is,
[
pi^{-1}(d(t))leT d(t).
]
The set $Y$ was fixed before $(u,v)$ varied, and the reductions in
(eq:generic-bound) need not be uniform in $(u,v)$.
The irrational $tin(0,1)$ was arbitrary; by Lemma~lem:cuts(c) the
degrees $d(t)$ for such $t$ are exactly the noncomputable degrees, and
$pi^{-1}(mathbf 0)=bf0)=mathbf 0$.bf0$. Therefore
pi^{-1}(mathbf a)bfa)leTmathbf abfaqquad(mathbf abfainDT)
for every order automorphism $pi$.
Now apply (eq:one-sided) to the automorphism $pi^{-1}$, which is
also an order automorphism and also admits a representing function by
Theorem~thm:representation. This gives
$pi(mathbf a)bfa)leTmathbf a$bfa$ for all $mathbf a$.bfa$. Together with
(eq:one-sided) and antisymmetry of $leT$, we get
$pi(mathbf a)=bfa)=mathbf a$bfa$ for every degree $mathbf a$.bfa$.
The second application uses Theorem~thm:representation for the
inverse automorphism; it does not require an inverse of the function $F$,
which may have nontrivial fibres.
The Turing-degree ordering is biinterpretable without parameters with
full second-order arithmetic, in the sense of
cite[Definition~7.5.1]{SlamanWoodin2005}.
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~thm:rigidity.
% =====================================================================
{99}
bibitem{GroszekSlaman1998} M.~J. Groszek and T.~A. Slaman, A basis theorem for perfect sets, Bull. Symbolic Logic 4 (1998), no.~2, 204--209; author's version (2000) at https://math.berkeley.edu/~slaman/papers/prikry.pdf, whose numbering is used here.
bibitem{JockuschSolovay1977} C.~G. Jockusch, Jr. and R.~M. Solovay, Fixed points of jump preserving automorphisms of degrees, Israel J. Math. 26 (1977), no.~1, 91--94.
bibitem{KjosHanssen2018} B. Kjos-Hanssen, Permutations of the integers induce only the trivial automorphism of the Turing degrees, Bull. Symbolic Logic 24 (2018), no.~2, 165--174; arXiv:1603.00525, whose numbering is used here.
bibitem{KumarShelah2023} A. Kumar and S. Shelah, Large Turing independent sets, Proc. Amer. Math. Soc. 151 (2023), no.~1, 355--367.
bibitem{LutzSiskind2025} P. Lutz and B. Siskind, Part 1 of Martin's conjecture for order-preserving and measure-preserving functions, J. Amer. Math. Soc. 38 (2025), no.~2, 319--367; arXiv:2305.19646, whose numbering is used here.
bibitem{MarkerDST} D. Marker, Descriptive Set Theory, course notes, Fall 2002, https://www.math.uic.edu/~marker/math512/dst.pdf.
bibitem{NerodeShore1980} A. Nerode and R.~A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no.~1, 61--89.
bibitem{Shore2007} R.~A. Shore, Direct and local definitions of the Turing jump, J. Math. Logic 7 (2007), no.~2, 229--262.
bibitem{ShoreSlaman1999} R.~A. Shore and T.~A. Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), no.~5--6, 711--722; author's version at https://math.berkeley.edu/~slaman/papers/jump.pdf.
bibitem{SlamanGlobal} T.~A. Slaman, 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. 14, World Scientific, 2008, 83--101; author's version at https://math.berkeley.edu/~slaman/papers/IMS_slaman.pdf, whose numbering is used here.
bibitem{SlamanWoodin2005} T.~A. Slaman and W.~H. Woodin, Definability in Degree Structures, unpublished manuscript, 21 July 2005, https://math.berkeley.edu/~slaman/talks/sw.pdf.
bibitem{Soare1987} R.~I. Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer, 1987.
bibitem{Turing1939} A.~M. Turing, Systems of logic based on ordinals, Proc. London Math. Soc. (2) 45 (1939), 161--228.