The Posner–Robinson theorem

Genericity is usually a tool for building sets with few computational abilities. Combined with coding, it also produces sets with prescribed strength. The idea is to build a 1-generic set $G$ that carries a given set $Z$ in its bits, in such a way that the coding can be read back with the help of an arbitrary non-computable set $A$. The resulting theorem, due in this form to Jockusch and Shore, has two classical consequences: the Posner–Robinson theorem, which says that every non-computable set joins with some set to compute the jump of the latter, and Friedberg’s jump inversion theorem, admitted in the course on Turing degrees, which says that every degree above $\obf'$ is a jump.

Theorem 4.1 (Jockusch–Shore).#

Let $A$ and $Z$ be sets, with $A$ not computable. There is a 1-generic set $G$ such that $Z \leq_T A \oplus G$, $Z \leq_T G \oplus \emptyset'$, and $G \leq_T A \oplus Z \oplus \emptyset'$.

4.1 The construction

We may assume that $A$ is not c.e. Indeed, if $A$ is c.e., then its complement is not c.e., since $A$ is not computable; and the complement is Turing equivalent to $A$, so it can replace $A$ in the statement. Fix an enumeration $(W_e)$ of the c.e. sets of strings.

We build strings $\sigma_0 \preceq \sigma_1 \preceq \cdots$, starting with $\sigma_0 = \varepsilon$, and let $G$ be their limit. At step $e$, given $\sigma_e$, write $i = Z(e)$ and consider the set

$$D_e = \{ m : \text{some extension of } \sigma_e\, i\, 0^m\, 1 \text{ belongs to } W_e \}.$$

It is c.e. Since $A$ is not c.e., $A \neq D_e$; so there is $m$ with either $m \in D_e \setminus A$ or $m \in A \setminus D_e$. Let $m$ be the least such number.

• If $m \in D_e \setminus A$, let $\sigma_{e+1}$ be the first extension of $\sigma_e\, i\, 0^m\, 1$ enumerated into $W_e$. Then $G$ meets $W_e$.
• If $m \in A \setminus D_e$, let $\sigma_{e+1} = \sigma_e\, i\, 0^m\, 1$. Then no extension of $\sigma_{e+1}$ belongs to $W_e$: $\sigma_{e+1}$ avoids $W_e$.

Proof of Theorem 4.1.

$G$ is 1-generic. At each step $e$, $G$ meets $W_e$ or has a prefix avoiding it, so $G$ meets $W_e \cup W_e^\perp$.

$G \leq_T A \oplus Z \oplus \emptyset'$. The bit $Z(e)$ is read from $Z$. The membership $m \in D_e$ is a c.e. question, answered by $\emptyset'$, and $m \in A$ is answered by $A$; so the least $m$ is found. In the first case, the first extension enumerated into $W_e$ is found by a computable search. So the sequence $(\sigma_e)$ is computable in $A \oplus Z \oplus \emptyset'$.

$Z \leq_T A \oplus G$. We compute the sequence $(\sigma_e)$ from $A \oplus G$, by induction. Suppose $\sigma_e$ is known. The bit of $G$ following $\sigma_e$ is $Z(e)$. Then read the number $m$ of zeros that follow, up to the next $1$; by construction it is the number chosen at step $e$. If $m \in A$, step $e$ was in the second case, and $\sigma_{e+1} = \sigma_e\, Z(e)\, 0^m\, 1$. If $m \notin A$, step $e$ was in the first case, so $m \in D_e$, and $\sigma_{e+1}$ is the first extension of $\sigma_e\, Z(e)\, 0^m\, 1$ enumerated into $W_e$, found by a computable search, which terminates. Hence $A \oplus G$ computes every bit $Z(e)$.

$Z \leq_T G \oplus \emptyset'$. The same decoding works with $\emptyset'$ in place of $A$: given $\sigma_e$, $Z(e)$ and $m$ are read from $G$ as above, and $\emptyset'$ decides whether $m \in D_e$, a c.e. question about $(e, \sigma_e, Z(e), m)$. If $m \in D_e$, step $e$ was in the first case, since in the second case $m \notin D_e$; otherwise it was in the second case. In both cases $\sigma_{e+1}$ is then obtained as before.

The decoding from $A \oplus G$ uses $A$ for a single question at each step: is $m$ in $A$? The construction chose $m$ precisely so that the answer distinguishes the two cases, which is possible because $A$ is not c.e. A c.e. set $A$ could coincide with $D_e$, leaving no such $m$.

4.2 Consequences

Corollary 4.2 (Posner–Robinson).#

For every non-computable set $A$, there is a 1-generic set $G$ with $A \oplus G \equiv_T G' \equiv_T G \oplus \emptyset'$.

Proof of Corollary 4.2.

Apply Theorem 4.1 with $Z = A \oplus \emptyset'$: $G$ is 1-generic, $A \oplus \emptyset' \leq_T A \oplus G$, and $A \oplus \emptyset' \leq_T G \oplus \emptyset'$. Since $G$ is 1-generic, $G' \equiv_T G \oplus \emptyset'$ (Theorem 6.3 of “Low and high sets”, with $G \oplus \emptyset' \leq_T G'$ for every set). From $\emptyset' \leq_T A \oplus G$ we get $G \oplus \emptyset' \leq_T A \oplus G$. From $A \leq_T G \oplus \emptyset'$ we get $A \oplus G \leq_T G \oplus \emptyset'$. Hence $A \oplus G \equiv_T G \oplus \emptyset' \equiv_T G'$.

So every non-computable set, however weak, bridges the gap between some set and its jump. For a low non-computable $A$, this gives a set $G$ with $A \oplus G \equiv_T G' \geq_T \emptyset'$ while $A$ alone is far from $\emptyset'$.

Corollary 4.3 (Friedberg’s jump inversion theorem).#

For every set $Z \geq_T \emptyset'$, there is a 1-generic set $G$ with $G' \equiv_T Z$, and moreover $G \oplus \emptyset' \equiv_T Z$.

Proof of Corollary 4.3.

Apply Theorem 4.1 with $A = \emptyset'$, which is not computable: $G$ is 1-generic, $Z \leq_T \emptyset' \oplus G$ and $G \leq_T \emptyset' \oplus Z \oplus \emptyset' \equiv_T Z$. Hence $G \oplus \emptyset' \equiv_T Z$, and $G' \leq_T G \oplus \emptyset'$ since $G$ is 1-generic (Theorem 6.3 of “Low and high sets”). The converse $G \oplus \emptyset' \leq_T G'$ holds for every set, so $G' \equiv_T Z$.

Corollary 4.4.#

There is a high set that computes no DNC function; in particular, a high set that is not Turing complete.

Proof of Corollary 4.4.

By Corollary 4.3 with $Z = \emptyset''$, there is a 1-generic $G$ with $G' \equiv_T \emptyset''$, so $G$ is high. By Theorem 3.4, $G$ computes no DNC function; since $\emptyset'$ computes one, $G$ does not compute $\emptyset'$.

This gives a second construction of high incomplete sets, after Corollary 6.7 of “Low and high sets”; the set obtained here is moreover 1-generic and computable in $\emptyset''$.

4.3 Exercises

Exercise 4.5 ★.

Show that every set $Z \geq_T \emptyset'$ is the join of $\emptyset'$ with a set $G$ such that $G \not\geq_T \emptyset'$.

Solution

Take $G$ as in Corollary 4.3: $Z \equiv_T G \oplus \emptyset'$, and $G$ is 1-generic, so it computes no DNC function, hence not $\emptyset'$.

Exercise 4.6 ★.

Let $A \leq_T \emptyset'$ be non-computable. Show that there is a low 1-generic set $G$ with $A \oplus G \equiv_T \emptyset'$.

Solution

Apply Theorem 4.1 with $Z = \emptyset'$. Then $G$ is 1-generic, $\emptyset' \leq_T A \oplus G$, and $G \leq_T A \oplus \emptyset' \equiv_T \emptyset'$. Hence $A \oplus G \leq_T \emptyset'$, so $A \oplus G \equiv_T \emptyset'$. Since $G$ is 1-generic and $\Delta^0_2$, $G' \leq_T G \oplus \emptyset' \equiv_T \emptyset'$ by Theorem 6.3 of “Low and high sets”, so $G$ is low.

4.4 Notes and references

Posner and Robinson proved their join theorem in 1981, answering a question on the degrees below $\obf'$. The general form with an arbitrary coded set $Z$ and the use of 1-generic sets is due to Jockusch and Shore (1984). Friedberg’s jump inversion theorem dates from 1957.

• D. B. Posner and R. W. Robinson, Degrees joining to 0′, Journal of Symbolic Logic 46 (1981), 714–722.
• C. G. Jockusch and R. A. Shore, Pseudo-jump operators II: transfinite iterations, hierarchies and minimal covers, Journal of Symbolic Logic 49 (1984), 1205–1236.
• R. M. Friedberg, A criterion for completeness of degrees of unsolvability, Journal of Symbolic Logic 22 (1957), 159–160.