The partial order of the Turing degrees

The Turing degrees $\mathcal D$ , ordered by Turing reducibility, form a partial order whose study began with Kleene and Post (1954). This course examines its global structure: which bounds exist, which partial orders appear inside it, and whether it has minimal elements above $\obf$ . This first lesson gathers the elementary properties of $\mathcal D$ and proves Spector’s exact pair theorem, which shows that the degrees are far from forming a lattice.

For a set $G$ and $k \in \nat$ , the column $G^{[k]}$ is the set $\{ y : \langle k, y \rangle \in G \}$ . For sets $A_0, A_1, \dots$ , the set $\bigoplus_n A_n$ has columns $A_n$ .

1.1 Elementary properties

Proposition 1.1.#

$\obf$ is the least degree, and every degree has at most countably many degrees below it.
Every degree has continuum many degrees above it, and no degree is maximal.
Every two degrees have a least upper bound, the degree of the join: $\mathcal D$ is an upper semilattice.
Every countable set of degrees has an upper bound.

Proof of Proposition 1.1.

Computable sets are computable from every set; lower cones are countable by Proposition 2.4 of “Turing reducibility and degrees”.
Let $A$ be a set. The sets $A \oplus X$ , $X \in \cs$ , compute $A$ , and they are continuum many. Each degree contains only countably many sets, so they fall into continuum many degrees. Since only one of them is $\deg_T(A)$ itself, $\deg_T(A)$ is not maximal; an explicit degree strictly above it is $\deg_T(A')$ (Theorem 3.2 of “The Turing jump”).
This is Proposition 2.6 of “Turing reducibility and degrees”.
Given representatives $X_n$ , the set $\bigoplus_n X_n$ computes each of them.

An upper bound of a countable set of degrees given by (4) is not a least upper bound in general. The rest of the lesson shows that a strictly increasing sequence never has one.

1.2 Exact pairs

A non-empty set $\mathcal I$ of degrees is an ideal if it is closed downward and under $\vee$ . The countable ideals are exactly the sets of the form

\mathcal I(A_0, A_1, \dots) = \{ \deg_T(X) : X \leq_T A_0 \oplus \cdots \oplus A_n \text{ for some } n \},

the ideal generated by a sequence of sets: such a set is an ideal, and a countable ideal is generated by any sequence of representatives of its elements.

Definition 1.2.#

Two degrees $\abf$ and $\bbf$ form an exact pair for an ideal $\mathcal I$ if $\mathcal I = \{ \cbf : \cbf \leq \abf \text{ and } \cbf \leq \bbf \}$ .

So $\abf$ and $\bbf$ are upper bounds of $\mathcal I$ , and every common lower bound of $\abf$ and $\bbf$ belongs to $\mathcal I$ .

Theorem 1.3 (Spector).#

Every countable ideal of Turing degrees has an exact pair.

Proof of Theorem 1.3.

Let $\mathcal I$ be generated by $A_0, A_1, \dots$ , and let $B_s = A_0 \oplus \cdots \oplus A_{s-1}$ , with $B_0 = \emptyset$ . We build $G = \bigcup_s g_s$ and $H = \bigcup_s h_s$ as limits of strings, so that the column $k$ of $G$ and of $H$ agrees with $A_k$ from some point on.

For strings $\sigma \preceq \tau$ , say that $\tau$ is an $s$ -admissible extension of $\sigma$ if $\tau(\langle k, y \rangle) = A_k(y)$ for every position $\langle k, y \rangle$ with $k < s$ and $|\sigma| \leq \langle k, y \rangle < |\tau|$ . Columns $k < s$ are locked beyond $\sigma$ : an admissible extension must copy $A_k$ there. Admissibility of $\tau$ over $\sigma$ is decidable with oracle $B_s$ , uniformly in $s$ .

Fix an enumeration $s \mapsto (i_s, j_s)$ of all pairs of indices. Start with $g_0 = h_0 = \varepsilon$ . At stage $s$ :

If there are $x$ and $s$ -admissible extensions $g'$ of $g_s$ and $h'$ of $h_s$ with $\Phi^{g'}_{i_s}(x)\converge \neq \Phi^{h'}_{j_s}(x)\converge$ , take such $g', h'$ . Otherwise let $g' = g_s$ and $h' = h_s$ .
Extend $g'$ and $h'$ by one bit to obtain $g_{s+1}$ and $h_{s+1}$ : at a position $p = \langle k, y \rangle$ , the new bit is $A_k(y)$ if $k \leq s$ , and $0$ otherwise.

So $g_{s+1}$ is an $s$ -admissible extension of $g_s$ , and $h_{s+1}$ of $h_s$ . Since $t$ -admissibility implies $s$ -admissibility for $t \geq s$ , every $G \uh m$ with $m \geq |g_s|$ is an $s$ -admissible extension of $g_s$ , and similarly for $H$ .

$\abf = \deg_T(G)$ and $\bbf = \deg_T(H)$ are upper bounds of $\mathcal I$ . Fix $k$ . At every stage $s \geq k + 1$ , the new positions of $G$ in column $k$ receive the values of $A_k$ , since all extensions made at stage $s$ are $s$ -admissible and the new bit follows $A_k$ . So $G(\langle k, y \rangle) = A_k(y)$ for all positions $\langle k, y \rangle \geq |g_{k+1}|$ . Hence $A_k$ is a finite variant of $G^{[k]}$ , and $A_k \leq_T G$ . The same holds for $H$ .

Common lower bounds belong to $\mathcal I$ . Let $Y \leq_T G$ and $Y \leq_T H$ , say $Y = \Phi^G_i = \Phi^H_j$ , and let $s$ be the stage with $(i_s, j_s) = (i, j)$ . At stage $s$ , no pair of admissible extensions with distinct convergent values was found: otherwise $G \succeq g'$ and $H \succeq h'$ would give $\Phi^G_i(x) \neq \Phi^H_j(x)$ . We compute $Y$ with oracle $B_s$ . Given $x$ , search for an $s$ -admissible extension $g'$ of $g_s$ with $\Phi^{g'}_i(x)\converge$ , and output the value $v$ .

The search terminates: $G \uh m$ is an $s$ -admissible extension of $g_s$ for every $m \geq |g_s|$ , and $\Phi^{G \uh m}_i(x)\converge$ for large $m$ .
The output is $Y(x)$ : similarly, $H \uh m$ is an $s$ -admissible extension of $h_s$ with $\Phi^{H \uh m}_j(x)\converge = Y(x)$ for large $m$ . Since no admissible pair gives distinct values, $v = Y(x)$ .

So $Y \leq_T B_s$ , and $\deg_T(Y) \in \mathcal I$ .

Each requirement is handled once, at a single stage: either it is satisfied by a disagreement, or the absence of any disagreement among admissible extensions gives a procedure computing the common value from the locked columns alone. The locking of columns makes $G$ and $H$ upper bounds; it also limits the freedom of later extensions, which is why the procedure needs the oracle $B_s$ .

1.3 Consequences

Corollary 1.4 (Kleene, Post; Spector).#

A strictly increasing sequence $\dbf_0 < \dbf_1 < \cdots$ of degrees has no least upper bound.
$\mathcal D$ is not a lattice: there are two degrees without a greatest lower bound.

Proof of Corollary 1.4.

Let $D_n \in \dbf_n$ , and let $\abf, \bbf$ be an exact pair for the ideal generated by $(D_n)$ . Since the sequence increases, $D_0 \oplus \cdots \oplus D_n \equiv_T D_n$ , so this ideal is the set of degrees $\cbf$ such that $\cbf \leq \dbf_n$ for some $n$ .

Suppose $\mathbf l$ is a least upper bound of the sequence. The degrees $\abf$ and $\bbf$ are upper bounds of the sequence, so $\mathbf l \leq \abf$ and $\mathbf l \leq \bbf$ . Hence $\mathbf l$ is in the ideal: $\mathbf l \leq \dbf_n$ for some $n$ . But $\dbf_{n+1} \leq \mathbf l$ , so $\dbf_{n+1} \leq \dbf_n$ , a contradiction.
Every common lower bound $\cbf$ of $\abf$ and $\bbf$ is below some $\dbf_n$ , hence strictly below $\dbf_{n+1}$ , which is another common lower bound. So no common lower bound is the greatest.

For instance, the arithmetic degrees, those below some $\obf^{(n)}$ , are exactly the common lower bounds of some pair of degrees, although they have no least upper bound. Exact pairs are a basic tool for coding countable structures into $\mathcal D$ , used in the proof that the first-order theory of $\mathcal D$ is as complex as true second-order arithmetic (Simpson, 1977).

1.4 Exercises

Exercise 1.5 ★.

Show that the arithmetic degrees, the degrees below $\obf^{(n)}$ for some $n$ , have no least upper bound, and that there are two degrees whose common lower bounds are exactly the arithmetic degrees.

Solution

The sequence $\obf^{(n)}$ is strictly increasing (Theorem 3.2 of “The Turing jump”), so Corollary 1.4 (1) applies. The arithmetic degrees form the ideal generated by $(\emptyset^{(n)})_n$ , since $\emptyset^{(0)} \oplus \cdots \oplus \emptyset^{(n)} \equiv_T \emptyset^{(n)}$ . Apply Theorem 1.3.

Exercise 1.6 ★★.

Show that in Theorem 1.3, the sets $G$ and $H$ can be chosen computable in $\big(\bigoplus_n A_n\big)'$ .

Solution

Let $B = \bigoplus_n A_n$ ; it computes each $B_s$ uniformly in $s$ . The question asked at stage $s$ , whether there exist $x$ and $s$ -admissible extensions with distinct convergent values, is $\Sigma^0_1$ relative to $B_s$ , uniformly in $s$ , $g_s$ and $h_s$ , hence decided by $B'$ . When the answer is positive, the witnesses are found by a $B$ -computable search. The extension by one bit uses $A_k(y)$ for $k \leq s$ , computable in $B$ . So the sequences $(g_s)$ and $(h_s)$ are computable in $B'$ .

1.5 Notes and references

Kleene and Post (1954) proved that the degrees form an upper semilattice that is not a lattice, and that increasing sequences have no least upper bound. Spector (1956) proved the exact pair theorem in the same paper as the existence of minimal degrees. Lerman’s monograph is the standard reference on the global structure of $\mathcal D$ .

S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics 59 (1954), 379–407.
C. Spector, On degrees of recursive unsolvability, Annals of Mathematics 64 (1956), 581–592.
M. Lerman, Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer, 1983.
S. G. Simpson, First-order theory of the degrees of recursive unsolvability, Annals of Mathematics 105 (1977), 121–139.