A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 1 · Rigidity of the Turing degrees
Rigidity of the Turing degrees
expertly designed by an internal OpenAI model · released 2026-09-24
· original PDF
IntroductionTuring reducibility compares the information available from sets of integers: \(A\le_TB\) means that an oracle Turing machine with oracle \(B\) computes the characteristic function of \(A\). Mutual reducibility defines Turing equivalence, and its equivalence classes form the partial order \((\mathcal D_T,\le_T)\) of Turing degrees. The underlying notion of relative computation goes back to Turing’s oracle machines [13]; see [12] for standard degree-theoretic background. The automorphism problem asks how much of this information the abstract ordering retains. The rigidity conjecture for the Turing degrees asks whether every automorphism of this ordering fixes every degree. An automorphism here is any bijection \(\pi:\mathcal D_T\to\mathcal D_T\) satisfying \[\mathbf a\le_T\mathbf b \quad\Longleftrightarrow\quad \pi(\mathbf a)\le_T\pi(\mathbf b).\] We work in ZFC and impose no definability or regularity hypothesis on \(\pi\). Theorem 1. Every order automorphism of the full Turing-degree structure is the identity: \[\forall\pi\in\mathop{\mathrm{Aut}}(\mathcal D_T,\le_T)\ \forall\mathbf a\in\mathcal D_T \qquad \pi(\mathbf a)=\mathbf a.\] Prior work and the remaining problem.The Turing jump sends a degree \(\mathbf a\) to the degree \(\mathbf a'\) of the halting problem relative to an oracle of degree \(\mathbf a\). Jockusch and Solovay proved that every jump-preserving order automorphism fixes all degrees above \(\mathbf0^{(4)}\), the fourth jump of the computable degree [2]. Using Slaman and Woodin’s definability of the double jump, Shore and Slaman proved that the jump is definable from the ordering [9], so every order automorphism preserves it. Shore later gave direct degree-theoretic definitions of the jump [8]. A cone consists of all degrees above a fixed degree. Nerode and Shore proved that every automorphism fixes some cone, whose base may depend on the automorphism [7]; see also [10]. Slaman and Woodin obtained a fixed cone common to all automorphisms: every automorphism fixes all degrees above \(\mathbf0''\), the second jump of the computable degree. Their analysis also shows that the automorphism group is countable and that each automorphism has an arithmetic representation on sets of integers [11, 10]. These results show that the order determines substantial computability-theoretic structure. They leave the rigidity problem at degrees outside the known fixed cone. The representation theorem is the external input to our proof. In its all-input form, it assigns to every arbitrary degree automorphism a single arithmetic, hence Borel, function on sets of integers that induces that automorphism on degrees [11]. The cited source is the 2005 unpublished manuscript; the result also appears in Slaman’s account [10]. This theorem supplies the regularity needed for a category argument while retaining the unrestricted scope of Theorem 1. A consequence for definability.Theorem 1 also settles the biinterpretability conjecture of Slaman and Woodin. Full second-order arithmetic is the two-sorted structure of natural numbers and all subsets of natural numbers, with arithmetic and membership. Slaman and Woodin interpret this structure using finite tuples of Turing degrees. In their formulation, biinterpretability asks whether the relation matching such a code for a set \(X\subseteq\mathbb N\) with its degree \([X]_T\) is first-order definable in the degree ordering without parameters [11]. They prove that this is equivalent to rigidity [11]; thus our theorem gives a positive answer. We state the resulting corollary in Section 5. Recovery and removal of parameters.Our main construction is the recovery theorem of Proposition 7. We identify \(2^\mathbb N\) with the sets of integers; recovering a real means computing which rational numbers lie below it. Write \(\oplus\) for the oracle join, which combines the information in finitely many sets of integers. For a Borel map \(F:\mathbb R\to2^\mathbb N\) with countable fibers satisfying \[F(x+y)\le_TF(x)\oplus F(y),\] we recover any prescribed irrational \(t\in(0,1)\) from four values of \(F\) at rational affine combinations of \(t\) and two auxiliary reals \(u,v\). Recovery holds for a comeager set of pairs \((u,v)\): the exceptional pairs form a countable union of nowhere-dense sets. The statement applies beyond functions representing degree automorphisms. The numerical mechanism is an averaging identity. For a fixed positive rational \(\delta\), start with a real state \(s_0=0\) and repeatedly choose the increment \(\delta t\) or \(\delta(t-1)\), recording the choice as \(r_n=0\) or \(r_n=1\), respectively. Summing these increments gives \[s_N=\delta\left(Nt-\sum_{n<N}r_n\right).\] If the states remain in \((-1,1)\), the proportion of choices with \(r_n=1\) approximates \(t\) with error less than \(1/(N\delta)\). Thus computing the binary choices suffices to recover the irrational parameter \(t\) with an effective error bound. The function \(F\) supplies both a rule for choosing the increments and a way to compute those choices. Countable fibers ensure that \(F\) takes distinct values on opposite sides of \(u\). Continuity on a comeager restriction then makes one output bit take opposite values near two such points. At state \(s_n\), we test this bit of \(F(u+s_n)\), choosing an upward step near the lower endpoint and a downward step near the upper endpoint. This keeps the states bounded, regardless of the bit’s behavior between the two endpoint regions. The addition reductions need not be uniform in their inputs. For each auxiliary pair in a comeager set, Borel regularity provides two programs that remain fixed along the recurrence. The first adds the selected increment while moving from a neighborhood of \(u\) to a neighborhood of \(v\); the second returns to the neighborhood of \(u\) at the new offset. The computation uses a fixed function value for each of the two possible increments, a fixed return value, and the initial value \(F(u)\). These four values are its only real oracles. The program indices and rational constants may depend on \(t\) and the chosen pair \((u,v)\). Finite-oracle recovery also appears in perfect-set coding. Groszek and Slaman recover a real from two branches of a perfect tree together with a sequence supplying a suitable dense set [1]. Lutz and Siskind’s refinement recovers any real from four elements of a perfect set together with a fixed real that computes each member of a countable dense subset, without requiring an enumeration computable from that fixed real [5]. Our recovery statement has different hypotheses: it uses the addition relation for one Borel function and prescribes affine arguments for its four values. Its bounded recurrence supplies the decoding procedure without an additional real oracle. To conclude rigidity, represent an arbitrary automorphism by a map \(F\) as above. The degrees of the four arguments are bounded by the join of the degrees of \(t,u,v\). Applying the inverse automorphism to the recovery bound therefore bounds the preimage degree of \(t\) by this same join. Sacks’s relative category cone-avoidance principle says that, over a fixed oracle, auxiliary reals compute a fixed set not already computable from that oracle only on a meager set of choices [4]. Since recovery holds on a comeager set, Lemma 4 removes the auxiliary degrees and yields \(\pi^{-1}(\mathbf a)\le_T\mathbf a\) for every degree \(\mathbf a\). Applying \(\pi\) to this inequality and repeating the argument for \(\pi^{-1}\) gives the opposite inequalities between \(\pi(\mathbf a)\) and \(\mathbf a\). A related method appears in Kjos-Hanssen’s proof of rigidity for automorphisms induced by permutations of the natural numbers [3]. That argument recovers a Bernoulli parameter (the probability of a \(1\)), uses a measure cone theorem, and applies the inverse automorphism. Here the parameter is recovered from the addition relation for a Borel function, and category removes the auxiliary degrees. The representing function need not arise from a permutation. Organization.Section 2 fixes the real and oracle codings and proves the category lemmas. Section 3 states the exact Slaman–Woodin input and constructs the Borel map on the real line. Section 4 proves four-value recovery, and Section 5 removes the auxiliary degrees, completes the proof, and derives the biinterpretability corollary. Computability and categoryWe first encode ordinary real arithmetic by Turing degrees. The category lemma at the end of the section will remove the auxiliary real parameters introduced by the recovery construction. We identify \(2^\mathbb N\) with the sets of natural numbers, equipped with the usual Cantor topology. Fix an effective enumeration \((\Phi_e)_{e\in\mathbb N}\) of oracle Turing machines. For sets \(A,B\), their join \(A\oplus B\) interleaves their characteristic functions. Finite joins use a fixed effective coding. The degree join \(\mathbf a\vee\mathbf b\) is the least upper bound of \(\mathbf a,\mathbf b\): an oracle computes \(A\oplus B\) exactly when it computes both \(A\) and \(B\). Every order automorphism therefore preserves finite joins. It also fixes the least degree \(\mathbf0\). To distinguish ordinary real numbers from oracle sets, fix an effective listing \((q_i)_{i\in\mathbb N}\) of \(\mathbb Q\) and put \[C(x)=\{i:q_i<x\},\qquad d(x)=[C(x)]_T \quad(x\in\mathbb R).\] Thus all computability assertions about real numbers below refer to these strict rational cuts. Lemma 2. The cut map \(C:\mathbb R\to2^\mathbb N\) is Borel and injective. If \(c_0,\ldots,c_k\in\mathbb Q\) and \(x_1,\ldots,x_k\in\mathbb R\), with \(k\ge1\), then \[d\left(c_0+\sum_{i=1}^k c_ix_i\right) \le_T\bigvee_{i=1}^k d(x_i).\] Every noncomputable degree equals \(d(t)\) for some irrational \(t\in(0,1)\). Proof. The \(i\)th coordinate of \(C\) is the indicator of the open ray \((q_i,\infty)\), so \(C\) is Borel. Density of \(\mathbb Q\) gives injectivity. An oracle for \(C(x)\) computes rational brackets \(a<x\le b\) of arbitrarily small width: search over rational pairs and check their cut bits. The input cuts consequently compute rational approximations, with prescribed error, to any fixed rational linear combination \(z\). If \(z\) is irrational, comparison with each rational query eventually separates and computes \(C(z)\). If \(z\) is rational, its cut is computable. This proves the degree inequality. It asserts existence of a reduction for each fixed tuple, and does not require an algorithm deciding whether the combination is rational. Given a noncomputable set \(B\), let \(t=\sum_{n\ge0}B(n)2^{-n-1}\). Then \(0<t<1\) and \(t\) is irrational: the endpoint expansions and all binary expansions of rational numbers are computable. The bits of \(B\) give effective approximations to \(t\), hence compute \(C(t)\) by irrationality. Conversely, successive dyadic comparisons with the cut recover the unique binary expansion of \(t\). Thus \(C(t)\equiv_TB\). ◻ Recall that a set is meager if it is a countable union of nowhere-dense sets, and comeager if its complement is meager. We use the Baire Category Theorem and the fact that Borel sets in Polish spaces have the Baire property [6]. Lemma 3. If \(X\) is Polish, \(Y\) is second countable, and \(f:X\to Y\) is Borel, there is a comeager set \(D\subseteq X\) such that \(f|D\) is continuous. Proof. Let \((U_n)\) be a countable basis for \(Y\). By the Baire property, write \(f^{-1}(U_n)\mathbin{\triangle}V_n\subseteq M_n\), where \(V_n\) is open and \(M_n\) is meager. On \(D=X\setminus\bigcup_nM_n\) one has \((f|D)^{-1}(U_n)=D\cap V_n\), which is relatively open. ◻ Only continuity on the indicated restriction is asserted. For a discrete-valued function, Lemma 3 makes its value constant on the intersection of that restriction with a suitable neighborhood of each of its points. Lemma 4 will remove auxiliary real parameters from a degree bound that holds on a comeager set of pairs. It is the relative category cone-avoidance principle attributed to Sacks in [4]. We include the version for rational-cut oracles that our proof requires. Lemma 4 (Category avoidance). Let \(A,Y\subseteq\mathbb N\) with \(Y\not\le_TA\). Then \[\{(u,v)\in\mathbb R^2:Y\le_TA\oplus C(u)\oplus C(v)\}\] is meager. Proof. For a fixed index \(e\), let \(S_e\) be the set of pairs with both coordinates irrational for which \(\Phi_e^{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 endpoints. We show that \(Y\le_TA\), with \(e\) and the endpoints of \(R\) as finite program constants. On input \(n\), search for a finite halting computation of \(\Phi_e(n)\) whose answers about \(A\) are correct and whose finitely many proposed cut answers hold throughout a nonempty open subrectangle of \(R\). This is an effective search relative to \(A\). Dovetail simulations with finite time bounds and finite tables of proposed answers to the two variable oracles. For a cut \(C(u)\), answer \(1\) to a rational \(q\) imposes \(q<u\), whereas answer \(0\) imposes \(u\le q\). Such a finite table is compatible throughout a nonempty open interval inside the corresponding side of \(R\) exactly when the maximum of its lower bounds is smaller than the minimum of its upper bounds, after including the corresponding endpoints of \(R\) among these bounds. This is decidable rational arithmetic, and the same check applies to \(v\). Repeated queries must have consistent answers. The search terminates. A pair in \(S_e\cap R\) has a halting computation on \(n\). Since its coordinates are irrational, none of the finitely many queried rationals equals the relevant coordinate. Its finite transcript therefore holds on an open neighborhood inside \(R\), and appears in the search. Every transcript accepted by the search is sound: its open subrectangle intersects the dense set \(S_e\), where the same deterministic computation returns \(Y(n)\). The search thus computes \(Y(n)\) with oracle \(A\), a contradiction. It follows that \(S_e\) is not dense in any nonempty rational open rectangle. Since these rectangles form a basis, \(S_e\) is nowhere dense. The pairs with a rational coordinate form a countable union of nowhere-dense lines. Adding these pairs and taking the countable union over \(e\) completes the proof. ◻ The reduction index in Lemma 4 may depend on \((u,v)\). Its proof takes the union over all indices, so no uniformity across the success set is required. Representing an arbitrary automorphismWe invoke the following established result. Its scope is essential: it applies to any automorphism of the full degree order and supplies a single function valid at every input. Theorem 5 (Slaman–Woodin). For every \(\pi\in\mathop{\mathrm{Aut}}(\mathcal D_T,\le_T)\) there is an arithmetic function \(\widehat F:2^\mathbb N\to2^\mathbb N\) such that \[[\widehat F(A)]_T=\pi([A]_T) \qquad\text{for every }A\subseteq\mathbb N.\] This is Theorem 6.3.1(2) of [11]; see also Theorem 4.29 in the author version of [10]. The generic-input assertion in the first clause of the cited Theorem 6.3.1 is separate from the all-input assertion used here. Arithmetic here describes the graph of a single total function. That graph is Borel. By the Borel-graph criterion for functions between Polish spaces [6], \(\widehat F\) is Borel. The weaker Borel conclusion also appears directly as Corollary 4.25 in the author version of [10]. Lemma 6. For an arbitrary \(\pi\in\mathop{\mathrm{Aut}}(\mathcal D_T,\le_T)\) there is a Borel function \(F:\mathbb R\to2^\mathbb N\) with countable fibers such that \[\begin{align*} [F(x)]_T&=\pi(d(x))\qquad(x\in\mathbb R),\tag{1}\\ F(x+y)&\le_TF(x)\oplus F(y)\qquad(x,y\in\mathbb R). \tag{2}\end{align*}\] Proof. Take \(F=\widehat F\circ C\) from Theorem 5 and Lemma 2. If \(F(x)=F(y)\), then \(\pi(d(x))=\pi(d(y))\), hence \(d(x)=d(y)\). Each fiber of \(F\) therefore injects, by \(C\), into a single Turing degree. Such a degree is countable: its members are among the outputs of countably many oracle programs with any fixed representative as oracle. By Lemma 2, \(d(x+y)\le_Td(x)\vee d(y)\). Since \(\pi\) preserves order and joins, \[[F(x+y)]_T \le_T\pi(d(x))\vee\pi(d(y)) =[F(x)\oplus F(y)]_T.\] This is exactly (2). ◻ The representing function is not required to be injective, or to give the same output set on equivalent input sets. Equation (1) prescribes only its output degree. The countable-fiber property is the consequence of injectivity of the automorphism that will enter the argument. Recovery from four valuesThe following result separates the local construction from the degree automorphism to which it will be applied. Proposition 7 (Recovery from four values). Let \(F:\mathbb R\to2^\mathbb N\) be Borel with countable fibers, and suppose \[F(x+y)\le_TF(x)\oplus F(y)\qquad(x,y\in\mathbb R).\] For every irrational \(t\in(0,1)\) there is a comeager set \(G_t\subseteq\mathbb R^2\) such that for each \((u,v)\in G_t\) there is a rational \(\delta\in(0,1)\) for which \[ C(t)\le_T F(u)\oplus F(u-v)\oplus F(v-u+\delta t)\oplus F(v-u+\delta(t-1)). \tag{3}\] Proof. The two auxiliary reals allow us to advance from \(u+s\) to \(u+s+a\) through two additions: \[(u+s)+(v-u+a)=v+s+a,\qquad (v+s+a)+(u-v)=u+s+a.\] If the programs witnessing these additions can be kept fixed, 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)\). We will use only the two increments \(\delta t\) and \(\delta(t-1)\). The initial oracle \(F(u)\), the fixed return oracle \(F(u-v)\), and the two increment oracles are exactly the four values in (3). For each pair \((u,v)\) in a comeager set, we first arrange two programs that remain fixed along the recurrence. A bit of \(F(u+s)\) will then select the increment so that successive states stay bounded; the frequencies of the choices will recover \(t\). Two local addition programs. For each \((x,y)\), let \(e(x,y)\) be the least index satisfying \[\Phi_{e(x,y)}^{F(x)\oplus F(y)}=F(x+y).\] Such an index exists by hypothesis. For a fixed index, the condition that every output bit is computed correctly is arithmetical in the three oracle sets and is therefore Borel in \((x,y)\). The set on which this is the least successful index is Borel as well. Thus \(e:\mathbb R^2\to\mathbb N\) is Borel. By Lemma 3, choose comeager sets \(D\subseteq\mathbb R\) and \(E\subseteq\mathbb R^2\) such that \(F|D\) and \(e|E\) are continuous; the codomain of \(e\) is discrete. Fix the given \(t\) and put \(H=\mathbb Q+\mathbb Qt\). Let \(G_t\) consist of the pairs \((u,v)\) satisfying \[ u+s\in D,\qquad (u+s,v-u+a)\in E,\qquad (v+s,u-v)\in E \quad\text{for all }s,a\in H. \tag{4}\] The group \(H\) is countable. For each fixed pair of shifts, the last two maps of \((u,v)\) in (4) are affine homeomorphisms of \(\mathbb R^2\). The first condition is a pullback under a translated coordinate projection; the inverse image of a meager exceptional set is meager. Consequently \(G_t\) is comeager. Fix any \((u,v)\in G_t\), and set \[p=e(u,v-u),\qquad q=e(v,u-v).\] Both centers belong to \(E\). Relative continuity of \(e|E\) gives a number \(0<\rho<1\) such that \[\begin{align*} e(u+s,v-u+a)&=p && (s,a\in H,\ |s|,|a|<\rho),\tag{5}\\ e(v+s,u-v)&=q && (s\in H,\ |s|<\rho). \tag{6}\end{align*}\] The membership in \(E\) required for these equalities is supplied by (4). Thus \(p\) and \(q\) carry out the two additions above whenever \(s,a\in H\) and \(|s|,|a|,|s+a|<\rho\). The last bound is needed because the second addition starts at the new offset \(s+a\). We now choose the two increments and a rule for selecting between them so that the old and new offsets always stay in this range. A bounded recurrence. Choose \(-\rho<b_-<0\) with \(u+b_-\in D\). The interval \((0,\rho)\) contains uncountably many \(b\) with \(u+b\in D\), and the fiber of \(F(u+b_-)\) is countable. We may therefore choose \(0<b_+<\rho\) with \(u+b_+\in D\) and \(F(u+b_-)\ne F(u+b_+)\). Fix a bit \(j\) where these two sets differ, and put \(h=F(u+b_+)(j)\). Continuity of \(F|D\) makes this bit constant on sufficiently small relative neighborhoods of the two endpoint translates. Choose a positive rational \(\delta<\rho\) small enough that \[\begin{align*} F(u+s)(j)&\ne h &&\bigl(s\in H\cap[b_-,b_-+\delta]\bigr),\tag{7}\\ F(u+s)(j)&=h &&\bigl(s\in H\cap[b_+-\delta,b_+]\bigr). \tag{8}\end{align*}\] We may also require \(3\delta<b_+-b_-\). Every tested translate belongs to \(D\) by (4); the endpoints themselves need not lie in \(H\). Define \(s_0=0\) and, recursively, \[ 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). \tag{9}\] We claim that \[ s_n\in H\cap[b_-,b_+]\qquad(n\ge0). \tag{10}\] The initial state has this property. If \(r_n=0\), then (8) forces \(s_n<b_+-\delta\); the increment \(\delta t\) lies in \((0,\delta)\), so \(s_{n+1}\) remains in the interval. If \(r_n=1\), then (7) forces \(s_n>b_-+\delta\); its negative increment has magnitude \(\delta(1-t)<\delta\), with the same conclusion. Rationality of \(\delta\) ensures \(s_{n+1}\in H\). This proves (10), and in particular \(|s_n|<\rho\). Figure 1 isolates the only feature of the tested bit needed for this confinement: it points the next step inward near either endpoint. No restriction on its intervening behavior is needed. Computing the binary choices. Let \(T\) denote the finite join on the right of (3). We show that \((r_n)_{n\ge0}\) is computable from \(T\) by maintaining, relative to \(T\), an oracle-program index \(P_n\) satisfying \[\Phi_{P_n}^{T}=F(u+s_n).\] Initially \(P_0\) projects to the first component \(F(u)\). Given \(P_n\), read \(\Phi_{P_n}^{T}(j)\) and compare it with the fixed bit \(h\) to obtain \(r_n\). Select the third component of \(T\) if \(r_n=0\) and the fourth if \(r_n=1\), namely \[F(v-u+\delta(t-r_n)).\] Set \(a_n=\delta(t-r_n)\). By (10), \(s_n,a_n\in H\) and \(|s_n|,|a_n|<\rho\). Equation (5) therefore shows that program \(p\), with its two oracle components simulated by \(\Phi_{P_n}^{T}\) and the selected tuple component, computes \[F(v+s_n+a_n)=F(v+s_{n+1}).\] Since \(|s_{n+1}|<\rho\), Equation (6) then shows that program \(q\), with this output and the fixed component \(F(u-v)\) as its two oracles, computes \(F(u+s_{n+1})\). Effective substitution of oracle subroutines produces the next index \(P_{n+1}\). This is an actual computation relative to the fixed tuple. The indices are constructed using the already computed branch bits. Inductively each substituted subroutine is total on its actual oracle, and both outer programs are valid reductions at the indicated argument pairs. Every bit computation has finite nesting depth through earlier indices and terminates. No bound on its running time is needed. To compute \(r_n\), perform the finite construction through stage \(n\). The program uses only the fixed integers \(p,q,j,h\), the rational \(\delta\), and the four tuple components. It does not compute the numerical states \(s_n\), or use \(t,u,v,\rho,b_-,b_+\) as additional real oracles. The finite program constants may depend on \(t,u,v\), as allowed in the pointwise reduction (3). Recovering the parameter. Summing (9) gives \[s_N=\delta\left(Nt-\sum_{n<N}r_n\right).\] Because \(|s_N|<\rho<1\), the \(T\)-computable rational numbers \(A_N=N^{-1}\sum_{n<N}r_n\) satisfy \[ |t-A_N|<\frac{1}{N\delta}\qquad(N\ge1). \tag{11}\] For a rational query \(a\), search for an \(N\) such that \(a<A_N-1/(N\delta)\) or \(a>A_N+1/(N\delta)\), and return the corresponding cut bit. Irrationality of \(t\) guarantees termination. The rational \(\delta\) makes the error bound effective, so this computes \(C(t)\) from \(T\) and proves (3). ◻ Remark 8. The parameter \(\delta\) and the reduction program in Proposition 7 need not be selected effectively from \((u,v)\). The conclusion is that the reduction exists for every pair in a comeager set. The category avoidance argument allows precisely this form of nonuniformity. Rigidity and biinterpretabilityWe now apply the recovery construction to the full degree structure. Proof of Theorem 1. Fix an arbitrary order automorphism \(\pi\) and take the Borel map \(F\) given by Lemma 6. Fix an irrational \(t\in(0,1)\). Proposition 7 gives a comeager set \(G_t\) of pairs \((u,v)\) for which (3) holds with a suitable rational \(\delta\in(0,1)\). For such a pair, put \(\mathbf b=d(t)\vee d(u)\vee d(v)\). Each argument in the four values on the right of (3) is a rational linear combination of \(t,u,v,1\). Lemma 2 bounds its degree by \(\mathbf b\), and Equation (1) bounds the degree of its \(F\)-value by \(\pi(\mathbf b)\). The same upper bound holds for the finite join of the four values. Thus \[d(t)\le_T\pi\bigl(d(t)\vee d(u)\vee d(v)\bigr) \qquad((u,v)\in G_t).\] Applying the inverse order automorphism yields \[ \pi^{-1}(d(t))\le_Td(t)\vee d(u)\vee d(v) \qquad((u,v)\in G_t). \tag{12}\] Choose one fixed set \(Y\) representing \(\pi^{-1}(d(t))\). If \(Y\not\le_TC(t)\), Lemma 4 says that \[\{(u,v):Y\le_TC(t)\oplus C(u)\oplus C(v)\}\] is meager. But (12) puts the comeager set \(G_t\) inside this set, contradicting the Baire Category Theorem for \(\mathbb R^2\). Consequently \[\pi^{-1}(d(t))\le_Td(t).\] The set \(Y\) is fixed before the pair varies. No common index for the reductions in (12) is required. The irrational \(t\) was arbitrary. By Lemma 2, its degrees cover every noncomputable degree, and the least degree is fixed. We have therefore proved \[ \pi^{-1}(\mathbf a)\le_T\mathbf a \qquad(\mathbf a\in\mathcal D_T) \tag{13}\] for every order automorphism \(\pi\). Apply this result to the automorphism \(\pi^{-1}\) to obtain \(\pi(\mathbf a)\le_T\mathbf a\). Applying \(\pi\) to (13) gives \(\mathbf a\le_T\pi(\mathbf a)\). Antisymmetry now gives \(\pi(\mathbf a)=\mathbf a\) for every degree. ◻ The second application uses Theorem 5 for the inverse degree automorphism. It does not require an inverse of \(F\), which may have nontrivial fibers. Corollary 9. The Turing-degree ordering is biinterpretable without parameters with full second-order arithmetic, in the sense of [11]. Proof. Slaman and Woodin prove that this property is equivalent to rigidity [11]. Apply Theorem 1. ◻
|
| ||||||||
|