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 0bf0 is the degree of
the computable sets. Any two degrees have a least upper bound, the
join b:b: 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 bbfb 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
[
bbfb
⇔
pi(a)a)leTpi(b).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.
[Rigidity]
Every order automorphism pi of (DT,leT) is the identity:
[
pi(a)=a)=a (ainDT).
]
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 0,0, since 0bf0 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(0)=0)=0bf0 and
pi( b)=b)=pi(a)a)veepi(b).b).
## 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}, 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 ith 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
Fhat:2^F:2^Nto2^N with
[
degT{Fhat(A)}F(A)=pi(degT A)
for 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}, FFhat 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=FFcirchat 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)(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, (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.
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,
(u+s,,v-u+a)in E,
(v+s,,u-v)in E
for 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 u|-> u+s, and the other two are pullbacks
of E under the affine homeomorphisms
[
(u,v)|-> (u+s,,v-u+a), (u,v)|-> (v+s,,u-v),
]
with inverses (w,z)|->(w-s,,z+w-s-a) and
(w,z)|->(z+w-s,,w-s). Hence G_t is comeager.
noindentStep 2: constants that persist along the walk.
Fix (u,v)in G_t and put
[
p=e(u,v-u), 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,
(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.
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.
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,
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.
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).
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)(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
[
b=d(t)b=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
b;b; by (eq:representation) the degree of its F-value is
at most pi(b).b). The same bound holds for the finite join of the
four values, hence
[
d(t)leTpi(d(t)vee d(u)vee d(v))((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)((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}(0)=0)=0.0. Therefore
pi^{-1}(a)a)leTbfa (ainDT)
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(a)a)leTbfa for all a.a. Together with
(eq:one-sided) and antisymmetry of leT, we get
pi(a)=a)=a for every degree a.a.
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}
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 pdf/m-j-groszek-and-t-a-1998-no-2-204-209-author-s-version.pdf, whose numbering is used here.
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.
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.
A. Kumar and S. Shelah, Large Turing independent sets, Proc. Amer. Math. Soc. 151 (2023), no.~1, 355--367.
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.
D. Marker, Descriptive Set Theory, course notes, Fall 2002, pdf/d-marker-descriptive-set-theory-course-2002.pdf.
A. Nerode and R.~A. Shore, Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18 (1980), no.~1, 61--89.
R.~A. Shore, Direct and local definitions of the Turing jump, J. Math. Logic 7 (2007), no.~2, 229--262.
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 pdf/r-a-shore-and-t-a-1999-no-5-6-711-722-author-s.pdf.
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 pdf/t-a-slaman-global-properties-of-2008-83-101-author-s-version-at.pdf, whose numbering is used here.
T.~A. Slaman and W.~H. Woodin, Definability in Degree Structures, unpublished manuscript, 21 July 2005, pdf/t-a-slaman-and-w-h-2005.pdf.
R.~I. Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer, 1987.
A.~M. Turing, Systems of logic based on ordinals, Proc. London Math. Soc. (2) 45 (1939), 161--228.