Proof We use a forcing notion with conditions of the form $p = (n, X_0, \dots , X_{n-1}, D)$ , where $n\in \omega $ , $X_i\in 2^{\omega }$ , and D is a finite set. We associate with every p the set $A_p = (\bigoplus _{i\in \omega } X_i)\cup D$ , where $X_i = \emptyset $ if $i\geq n$ . So $X_i$ is the i-th column of $A_p$ modulo a finite set. We will say that $q = (m, Y_0, \dots , Y_{m-1}, E)$ extends p if $m\geq n$ , for all $i<n$ we have that $X_i = Y_i$ , $D\subseteq E$ , and if $x\in E\smallsetminus D$ then $x\in \omega ^{[\geq n]}$ , i.e., $x = {\left \langle {k,z}\right \rangle }$ for some $k\geq n$ and $z\in \omega $ . We construct A as $\bigcup _{s\in \omega } A_{p_s}$ , where $\{p_{s}\}_{s\in \omega }$ is a sequence of conditions such that $p_{s+1}$ extends $p_s$ .

We denote by $P_e{\left \langle {A}\right \rangle }$ the $\Pi ^0_1{\left \langle {A}\right \rangle }$ class $2^{\omega }\smallsetminus [\Gamma _e(A)]$ , where $\{\Gamma _e\}_{e\in \omega }$ lists all enumeration operators. To ensure that A is ${\left \langle {\text {self}\kern2pt}\right \rangle }$ -PA, we satisfy the requirements:

$$\begin{align*}\mathcal{P}_e: P_e{\left\langle{A}\right\rangle}\neq \emptyset\rightarrow (\exists X\in P_e{\left\langle{A}\right\rangle}) [X\oplus\overline X\leq_e A]. \end{align*}$$

To ensure that A is not cototal, we satisfy the requirements:

$$\begin{align*}\mathcal{N}_e: A\neq \Gamma_e(\overline{K^{{\left\langle{A}\right\rangle}}}).\end{align*}$$

Start with $p_0 = (0, \emptyset )$ . At stage $s = 2e$ , we satisfy the requirement $\mathcal {P}_e$ . Fix $p_s = (n, X_0, X_1, \dots X_{n-1}, D)$ . We ask if $p_s$ has an extension $q = (n, X_0, \dots , X_{n-1}, E)$ such that $P_e{\left \langle {A_{q}}\right \rangle } = \emptyset $ and if so then let $p_{s+1} = q$ for some such q. Otherwise, it follows by compactness that $P = P_e{\left \langle {A_{p_s}\cup \omega ^{[\geq n]}}\right \rangle }$ is a nonempty $\Pi ^0_1{\left \langle {X_0\oplus \dots \oplus X_{n-1}}\right \rangle }$ class that will be a subclass of $P_e{\left \langle {A}\right \rangle }$ no matter how the construction of A continues. Let $X_n$ be some path in P and let $p_{s+1} = (n+2, X_0, \dots , X_n, \overline {X_n}, D)$ .

At stage $s= 2e+1$ , we deal with the requirement $\mathcal {N}_e$ . Let $x_e$ be the least element in $\omega ^{[n]}$ , whose membership in A is not determined by $p_s= (n, X_0, \dots , X_{n-1}, D)$ , i.e., $x_e$ is least in $\omega ^{[ n]} \smallsetminus D$ . We first ask if $p_s$ has some extension q such that q forces $x_e\in \Gamma _e(\overline {K^{{\left \langle {A}\right \rangle }}})$ : there is some axiom ${\left \langle {x_e, F}\right \rangle }\in \Gamma _e$ such that for every member ${\left \langle {u,z}\right \rangle }\in F$ and every r extending q we have that $z\notin \Gamma _u(A_r)$ . If there is some such extension q, then there is one that also forces $x_e$ out of A, because the fewer elements in A, the more elements in $\overline {K^{{\left \langle {A}\right \rangle }}}$ . The extension $q= (m, Y_0, \dots Y_{m-1}, E)$ forces $x_e$ out of A if $m>n$ and $x_e \notin A_q$ . We let $p_{s+1} = q$ for some such q.

If there is no such extension, then for every extension q of $p_s$ and every axiom ${\left \langle {x_e,F}\right \rangle }\in \Gamma _e$ there is some member ${\left \langle {u,z}\right \rangle }\in F$ and some r extending q such that $z\in \Gamma _{u}(A_r)$ . Note that if $A_r\subseteq A$ , then this axiom for $x_e$ is not valid with respect to the oracle $\overline {K^{{\left \langle {A}\right \rangle }}}$ . In this case we say that $\mathcal {N}_e$ is persistent. We then extend to $p_{s+1}= (n, X_0, \dots , X_{n-1}, E)$ where E is a finite set defined so that $x_e\in E$ and so that for every persistent $\mathcal {N}_i$ , with $i\leq e$ , we ensure that the first s many axioms for $x_i$ in $\Gamma _i$ are invalidated. (This will be the outcome at infinitely many odd stages, so if $\mathcal {N}_i$ is persistent, then $x_i$ will be in $A\smallsetminus \Gamma _i(\overline {K^{{\left \langle {A}\right \rangle }}})$ and $\mathcal {N}_i$ will be satisfied.)

Proof One direction in this theorem was already shown to be true in [Reference Ganchev, Kalimullin, Miller and Soskova11]: every continuous degree is PA bounded. Here we prove that if A is not of continuous degree, then A is not PA bounded. So fix A that is not of continuous degree, hence by Theorem 2.6, not codable. We will build a sequence of nonempty $\Pi ^0_1{\left \langle {A}\right \rangle }$ classes $\{Q_s\}_{s\in \omega }$ so that $Q_s\supseteq Q_{s+1}$ . A nested intersection of nonempty compact sets is nonempty, so $\bigcap _{s} Q_s$ will be nonempty. The construction will ensure that if $Z\in \bigcap _{s} Q_s$ then ${\left \langle {Z}\right \rangle }$ is PA relative to ${\left \langle {A}\right \rangle }$ and $A\nleq _e Z$ . It follows that A is not PA bounded.

We start with $Q_0 = (2^{\omega })^{\omega }$ . In other words, $Q_0$ is the full $\Pi ^0_1$ class, but we think of it as a sequence of countably many copies of the full class. Each $Q_s$ will be thought of as a countable sequence of $\Pi ^0_1{\left \langle {A}\right \rangle }$ classes such that all but finitely many of them are $2^{\omega }$ . We will denote by $Q_s^{[i]}$ the i-th member of this sequence and call it the i-th column of $Q_s$ . We will keep track of an index $k_s$ such that for all $i\geq k_s$ , $Q_s^{[i]} = 2^{\omega }$ . Under this arrangement $k_0 = 0$ .

Suppose we have constructed $Q_s$ and identified $k_s$ . Consider the $\Pi ^0_1{\left \langle {A}\right \rangle }$ class Q defined so that for all $i<k_s $ we have that $Q^{[i]} = Q_s^{[i]}$ and for all $i\geq k_s$ we have $Q^{[i]} =\{\omega \}$ . In other words, Q is the subclass of $Q_s$ such that if $Y\in Q$ and $i\geq k_s$ , then $Y^{[i]} = \omega $ . Now since A is not codable, we can fix $Y\in Q$ such that $\Gamma _s(Y) \neq A$ , where $\Gamma _s$ is the s-th enumeration operator. Note that codability is defined in terms of c.e. operators, but of course, an enumeration operator is a c.e. operator. Let y be the least difference between $\Gamma _s(Y)$ and A. We have two possibilities:

Case 1. If $y\in \Gamma _s(Y)\smallsetminus A$ , let $D\subseteq Y$ be a finite set such that $y\in \Gamma _s(D)$ . We restrict $Q_s$ to the largest possible $\Pi ^0_1{\left \langle {A}\right \rangle }$ subclass R so that D is a subset of every member of R. Note that R is nonempty because it contains Y. Since D is finite the class R also has the desired form, i.e., there is some number $k\geq k_s$ such that $R^{[i]} = 2^{\omega }$ for all $i\geq k$ . Let k be the least such number. Furthermore, if Z is a member of R then $y\in \Gamma _s(Z)$ .

Case 2. If $y\in A\smallsetminus \Gamma _s(Y)$ , then we trim the first $k_s$ many columns of $Q_s$ to get a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class R so that if $Z\in R$ , then $y\notin \Gamma _s(Z)$ . In more detail, we let $R^{[0]}, \dots , R^{[k_s-1]}$ be defined so that if Z is a member of the class with columns $R^{[0]}, \dots , R^{[k_s-1]}, \{\omega \}, \{\omega \},\dots $ , then $y\notin \Gamma _s(Z)$ . We leave the remaining columns of R full: $R^{[i]} = 2^{\omega }$ for all $i\geq k_s$ . Once again, $Y\in R$ guarantees that R is nonempty. Furthermore, for all $Z\in R$ we have that if $i\geq k_s$ , then $Z^{[i]}\subseteq \omega =Y^{[i]}$ ; hence by the monotonicity of enumeration operators, $y\notin \Gamma _s(Z)$ . Let $k = k_s$ .

In each case, we have ensured that if $Z\in R$ then $\Gamma _s(Z)\neq A$ . (Note in the next paragraph that $Q_{s+1}\subseteq R$ .)

Now let $P_s{\left \langle {A}\right \rangle }$ be the s-th $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. If $P_s{\left \langle {A}\right \rangle }$ is empty, let $Q_{s+1} = R$ and $k_{s+1} = k$ . Otherwise, let $Q_{s+1}$ be defined by setting $Q_{s+1}^{[i]} = R^{[i]}$ for all $i\neq k$ and $Q_{s+1}^{[k]} = \{Z\oplus \overline Z \colon Z\in P_s{\left \langle {A}\right \rangle }\}$ . We will have that $k_{s+1} = k+1$ . In this case, we have ensured that if $Z\in Q_{s+1}$ , then the k-th column of Z codes the positive and negative information about a member of $P_s{\left \langle {A}\right \rangle }$ .

As required, if $Z\in \bigcap _{s} Q_s$ , then ${\left \langle {Z}\right \rangle }$ is PA relative to ${\left \langle {A}\right \rangle }$ but does not enumerate A. It follows that A is not PA bounded.

Proof ( $\Leftarrow $ ) This is obvious: if X has PA degree and a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class P has a nonempty $\Pi ^0_1$ subclass Q, then X computes a member of Q and hence of P.

( $\Rightarrow $ ) Let P be a nonempty $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We first claim that there is a nonempty $\Pi ^0_1$ class U and a Turing reduction $\Phi _e$ such that if $X\in U$ , then $\Phi _e^X\in P$ . Assume not. We build a sequence $U_0\supseteq U_1\supseteq U_2\supseteq \cdots $ of nonempty $\Pi ^0_1$ classes as follows. Let $U_0 = \text {DNC}_2$ . Say that $U_e$ has been defined. By assumption, there is an $X\in U_e$ such that $\Phi _e^X$ is not an element of P. This means that either $\Phi _e^X$ is partial or that $\Phi _e^X = Y$ and $Y\notin P$ . In the first case, suppose $\Phi _e^X(n)\operatorname {\mathrm {\uparrow }}$ . Let $U_{e+1} = \{Z\in U_e \colon \Phi _e^Z(n)\operatorname {\mathrm {\uparrow }}\}$ . In the second case, fix $\sigma \prec X$ such that no extension of $\Phi _e^{\sigma }$ is in P and let $U_{e+1} = \{Z\in U_e \colon \sigma \prec Z\}$ . In both cases, $U_{e+1}$ is a nonempty $\Pi ^0_1$ subclass of $U_e$ and if $Z\in U_{e+1}$ , then $\Phi _e^{Z}$ is not an element of P. Finally, take $Z \in \bigcap _{e\in \omega } U_e$ . Then Z has PA degree but does not compute any element of P, which contradicts our assumption that ${\left \langle {A}\right \rangle }$ is low for PA. This proves the claim.

So fix a nonempty $\Pi ^0_1$ class U and an e such that $X\in U$ implies that $\Phi _e^{X}\in P$ . Let $Q = \{Y \colon (\exists X\in U)\; \Phi _e^{X} = Y\}$ . Note that Q is a nonempty subclass of P. We claim that Q, which is the computable image of a $\Pi ^0_1$ class, is also a $\Pi ^0_1$ class. This is standard: Assume that $U = [T]$ , where T is a $\Pi ^0_1$ tree in $2^{<\omega }$ . Let

$$\begin{align*}S = \{\sigma\in 2^{<\omega} \colon (\exists n)(\forall \tau\in 2^n)\; \tau\notin T\text{ or }\Phi_e^{\tau}\text{ is incompatible with }\sigma\}. \end{align*}$$

Then $2^{<\omega }\smallsetminus S$ is a $\Pi ^0_1$ tree and, by compactness, $Q = [2^{<\omega }\smallsetminus S]$ . Therefore, Q is a $\Pi ^0_1$ class.

Proof For (1), assume that $A\geq _e Z\oplus \overline Z$ , where Z is not computable. Then $\{Z\}$ is a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. Take any PA degree X that does not compute Z; this exists by Jockusch and Soare [Reference Jockusch and Soare13, Theorem 2.5]. Then X does not compute any member of $\{Z\}$ , so ${\left \langle {A}\right \rangle }$ is not low for PA.

To see (2), recall that there is a single Turing functional that lets a DNC $_2$ Turing oracle compute a path in any nonempty $\Pi ^0_1$ class uniformly from its index, so if P is a nonempty $\Pi ^0_1{\left \langle {A}\right \rangle }$ class and $Q\subseteq P$ is a nonempty $\Pi ^0_1$ class then an index for Q gives a fixed functional as required in the definition.

Proof Assume that A is enumeration $1$ -generic and let $P{\left \langle {A}\right \rangle }$ be a nonempty $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. Recall that a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class is defined in terms of an enumeration operator that is applied to the oracle ${\left \langle {A}\right \rangle }$ . We can hence view P as an operator that maps any oracle ${\left \langle {X}\right \rangle }$ to a $\Pi ^0_1{\left \langle {X}\right \rangle }$ class. We claim that there is a prefix $\sigma \prec A$ such that $P{\left \langle {\sigma 1^\omega }\right \rangle }$ is nonempty. If so, then $Q = P{\left \langle {\sigma 1^\omega }\right \rangle }$ is a nonempty $\Pi ^0_1$ class and $Q\subseteq P{\left \langle {A}\right \rangle }$ ; as observed in Theorem 3.8, this means that ${\left \langle {A}\right \rangle }$ is low for PA. So let us prove the claim. Consider the c.e. set of finite sets $W = \{D \colon P{\left \langle {D}\right \rangle }=\emptyset \}$ . Because $P{\left \langle {A}\right \rangle }$ is nonempty, there is no subset of A in W. By enumeration $1$ -genericity, we can fix $F\subseteq \overline A$ such that F intersects every member of W. Let $\sigma $ be the initial segment of A of length $\max (F)+1$ . Then $Q = P{\left \langle {\sigma 1^\omega }\right \rangle }$ is nonempty because no member of W is a subset of the set with characteristic function $\sigma 1^{\omega }$ .

Proof Fix a set B and a c.e. set W such that A and B are a nontrivial $\mathcal {K}$ -pair as witnessed by W. So we have $A\times B\subseteq W$ and $\overline {A}\times \overline {B}\subseteq \overline {W}$ . Let $P{\left \langle {A}\right \rangle }$ be a nonempty $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. Consider the c.e. set

$$\begin{align*}V = \{b \colon (\exists F\subseteq\omega)\;F\text{ is finite, }F\times\{b\}\subseteq W\text{, and }P{\left\langle{F}\right\rangle}=\emptyset\}. \end{align*}$$

Say that $b\in V$ as witnessed by F. Since $P{\left \langle {F}\right \rangle }=\emptyset $ , we know that $F\nsubseteq A$ . Fix $c\in F\smallsetminus A$ . Since $(c,b)\in W$ , it must be the case that $b\in B$ . So we have that $V\subseteq B$ . But we assumed that A and B form a nontrivial $\mathcal {K}$ -pair; hence B is not c.e. Therefore, we can fix a $d\in B\smallsetminus V$ .

Now consider the c.e. set $U = \{a \colon {\left \langle {a,d}\right \rangle }\in W\}$ . Since $d\in B$ and $A\times B\subseteq W$ , we have $A\subseteq U$ . Therefore, $Q = P{\left \langle {U}\right \rangle }$ is a $\Pi ^0_1$ subclass of $P{\left \langle {A}\right \rangle }$ . All that remains is to prove that Q is nonempty. But if Q were empty, there would be some finite $F\subseteq U$ such that $P{\left \langle {F}\right \rangle }=\emptyset $ . By the definition of U, we would also have $F\times \{d\}\subseteq W$ . But then it would be the case that $d\in V$ , contradicting our choice of d.

Proof Fix an effective bijection between $\omega $ and $2^{<\omega }$ . For example, associate $\sigma _n\in 2^{<\omega }$ with $n\in \omega $ if $1\sigma _n$ is the binary expansion of $n+1$ . Now define a $\Pi ^0_1{\left \langle {B}\right \rangle }$ class $P{\left \langle {B}\right \rangle }$ as follows: remove the neighborhood generated by $\sigma _n$ from $P{\left \langle {B}\right \rangle }$ if both $2n$ and $2n+1$ are in B.

Let Q be the $\Pi ^0_1$ class $\{B \colon P{\left \langle {B}\right \rangle }\neq \emptyset \}$ . We calculate the measure of Q by finding the probability that $P{\left \langle {B}\right \rangle }$ is nonempty, assuming that B is chosen at random. Let $p_k$ be the probability that the tree generating $P{\left \langle {B}\right \rangle }$ (i.e., the tree that avoids $\sigma _n$ if both $2n$ and $2n+1$ are in B) has a path of length at least k. Then and —the probability that the root is not removed and that at least one of its children has a path of length at least k. It is not hard to see that $\{p_k\}_{k\in \omega }$ is a decreasing sequence with limit $2/3$ , which is the only positive root of . Therefore, the measure of Q is .

Since A is Martin-Löf random and Q is a $\Pi ^0_1$ class of positive measure, a result of Kučera tells us that some tail of A is in Q [Reference Kučera, Ebbinghaus, Müller and Sacks18, Proof of Lemma 3]. Call such a tail B, so $P{\left \langle {B}\right \rangle }$ is a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class.Footnote ³

Note that B is Martin-Löf random. By the randomness preservation basis theorem [Reference Downey, Hirschfeldt, Miller and Nies9, Reference Reimann and Slaman26], there is an X of PA degree such that B is Martin-Löf random relative to X. Assume, for a contradiction, that ${\left \langle {A}\right \rangle }$ is low for PA. So there must be a $Y\in P{\left \langle {B}\right \rangle }$ such that $Y\leq _T X$ . Since B is Martin-Löf random relative to X, it must be Martin-Löf random relative to Y. But this is clearly not the case; if $\sigma _n\prec Y$ , then we know that either $2n\notin B$ or $2n+1\notin B$ . So in fact, B is not even Kurtz random relative to Y: B is contained in a measure zero $\Pi ^0_1(Y)$ class. Therefore, ${\left \langle {A}\right \rangle }$ is not low for PA.

Proof Fix X with the reduction property. Let A consist of all ${\left \langle {e,\sigma }\right \rangle }$ such that $\sigma 0$ is not extendible in the e-th $\Pi ^0_1{\left \langle {X}\right \rangle }$ class $P_e$ . Let B be defined similarly but for $\sigma 1$ , not $\sigma 0$ . Note that $A,B \leq _e X$ by compactness. As defined,

$$\begin{align*}P_e = 2^\omega \smallsetminus \left[\{\sigma0 \colon {\left\langle{e,\sigma}\right\rangle}\in A\}\cup \{\sigma1 \colon {\left\langle{e,\sigma}\right\rangle}\in B\}\right]. \end{align*}$$

Note that if $\sigma $ is extendible in $P_e$ , then ${\left \langle {e,\sigma }\right \rangle }\notin A\cap B$ . So a “separator” for A and B would let us choose either $\sigma 0$ or $\sigma 1$ still extendible in $P_e$ . But of course, A and B are not disjoint. Apply the reduction property: let $A_0\subseteq A$ and $B_0\subseteq B$ be such that $A_0,B_0 \leq _e X$ , $A_0\cap B_0 = \emptyset $ , and $A_0 \cup B_0 = A \cup B$ . Let U be the separating class for $A_0$ and $B_0$ , which is a nonempty $\Pi ^0_1{\left \langle {X}\right \rangle }$ class.

We claim that there is a uniform procedure to compute a path in the e-th $\Pi ^0_1{\left \langle {X}\right \rangle }$ class $P_e$ , assuming that it is nonempty, given a separator Z for $A_0$ and $B_0$ . If $\sigma $ is extendible in $P_e$ , check if ${\left \langle {e,\sigma }\right \rangle }$ lies in Z. If it does, we claim that $\sigma 1$ is extendible in $P_e$ . Otherwise, ${\left \langle {e,\sigma }\right \rangle } \in B \subseteq A_0 \cup B_0$ . Since ${\left \langle {e,\sigma }\right \rangle } \in Z$ and $Z \cap B_0 = \emptyset $ , it follows that ${\left \langle {e,\sigma }\right \rangle } \in A_0 \subseteq A$ . So ${\left \langle {e,\sigma }\right \rangle }\in A\cap B$ , which means that both $\sigma 0$ and $\sigma 1$ are not extendible in $P_e$ . This contradicts our assumption that $\sigma $ is extendible in $P_e$ . Similarly, if ${\left \langle {e,\sigma }\right \rangle }$ does not lie in Z, then $\sigma 0$ is extendible in $P_e$ .

Proof This is immediate from our definitions. For the second part, if X is ${\left \langle {\text {self}\kern2pt}\right \rangle }$ -PA then every nonempty $\Pi ^0_1{\left \langle {X}\right \rangle }$ class, and hence every $\operatorname {\mathrm {Sep}}{\left \langle {X}\right \rangle }$ class, contains a path Y such that $Y\oplus \overline Y\leq _e X$ .

Proof To see that $(1)\Rightarrow (2)$ , we note that if $\psi $ is a partial computable extension of a $\{0,1\}$ -valued function $\varphi $ then the partial computable function

$$\begin{align*}\psi^*(x) = \begin{cases} 0, & \mbox{if } \psi(x)\operatorname{\mathrm{\downarrow}} = 0,\\ 1, & \mbox{if } \psi(x)\operatorname{\mathrm{\downarrow}} \neq 0 \end{cases}\end{align*}$$

is $\{0,1\}$ -valued and extends $\varphi $ .

For $(2) \Rightarrow (1)$ , we use a proof from [Reference Kalimullin and Puzarenko15]. Suppose that $G_{\varphi }\leq _e X$ is the graph of a partial function. Consider the function $\varphi ^*({\left \langle {x,y}\right \rangle }) = 1$ if $\varphi (x) = y$ and $\varphi ^*({\left \langle {x,y}\right \rangle }) = 0$ if there is some $z\neq y$ such that $\varphi (x) = z$ . This is a $\{0,1\}$ -valued function whose graph is reducible to X, with the additional property that if $\varphi (x) = y$ then $\varphi ^*({\left \langle {x,z}\right \rangle })\operatorname {\mathrm {\downarrow }}$ for all z. If $\psi ^*$ is a partial computable extension of $\varphi ^*$ , then the function $\psi $ defined by $\psi (x) = \mu y\;[\psi ^*({\left \langle {x,y}\right \rangle }) = 1]$ is a partial computable extension of $\varphi $ .

$(2)\Rightarrow (3)$ : Suppose that Y has PA degree. Consider a nonempty $\operatorname {\mathrm {Sep}}{\left \langle {X}\right \rangle }$ class $Q(A,B)$ of all separators for $A,B\leq _e X$ . Since A and B are disjoint, $A\times \{1\}\cup B\times \{0\}\leq _e X$ is the graph of a partial function. By (2), let $\psi $ be a partial computable $\{0,1\}$ -valued extension. The class of all total $\{0,1\}$ -valued extensions of $\psi $ is a nonempty $\Pi ^0_1$ class; hence a set Y of PA degree computes a member f of that set. The set C with characteristic function f is a separator for A and B.

$(3)\Rightarrow (4)$ follows from the proof of Theorem 3.8. Fix a separating class $Q(A, B)$ relative to ${\left \langle {X}\right \rangle }$ . Since every PA degree computes a member of $Q(A,B)$ , there is a nonempty $\Pi ^0_1$ class U and a Turing reduction $\Phi _e$ such that if $X\in U$ , then $\Phi _e^{X}\in Q(A,B)$ . Then $Q = \{Y \colon (\exists X\in U)\; \Phi _e^{X} = Y\}$ is a nonempty $\Pi ^0_1$ class that is contained in $Q(A,B)$ .

For $(4)\Rightarrow (2)$ , suppose that $G_{\varphi }\leq _e X$ for some $\{0,1\}$ -valued partial function $\varphi $ . Let $A = \{x \colon \varphi (x) = 1\}$ and $B = \{x \colon \varphi (x) = 0\}$ . Let $Q(A,B)$ be the class of all sets separating A and B. By (4), let $P\subseteq Q(A,B)$ be a nonempty $\Pi ^0_1$ class. We define the $\{0,1\}$ -valued function $\psi $ by $\psi (x) = i$ if $Y(x) = i$ for all $Y\in P$ . By compactness, $\psi $ is a partial computable extension of $\varphi $ .

$(5)$ is clearly a rewording of $(6)$ . In one direction, given a $\operatorname {\mathrm {Sep}}{\left \langle {X}\right \rangle }$ class $Q(A,B)$ , the sets A and B must be disjoint and reducible to X. If C and D are disjoint c.e. sets such that $A \subseteq C$ and $B \subseteq D$ , then the $\Pi ^0_1$ class of all separators of C and D is a subset of $Q(A,B)$ . Conversely, given disjoint sets $A,B \leq _e X$ , the class of all separators of A and B form a $\operatorname {\mathrm {Sep}}{\left \langle {X}\right \rangle }$ class $Q(A,B)$ . If $P(C,D) \subseteq Q(A,B)$ is a $\Pi ^0_1$ separating subclass, then C and D are disjoint c.e. sets such that $A \subseteq C$ and $B \subseteq D$ .

$(2)\Rightarrow (6)$ : If A and B are reducible to X and disjoint, then $A\times \{1\}\cup B\times \{0\}$ is the graph of a partial $\{0,1\}$ -valued function $\varphi $ . If $\psi $ is a partial computable extension of $\varphi $ , then $C = \{x \colon \psi (x) = 1\} \supseteq A$ and $D = \{x \colon \psi (x) = 0\} \supseteq B$ are disjoint c.e. sets.

Finally, $(5)$ clearly implies $(4)$ .

Proof The implication $(1)\Rightarrow (2)$ is easy: if $\Gamma $ is an enumeration operator such that $\Gamma (X)$ is the graph of a universal function for X, then define

$$\begin{align*}\Lambda = \{{\left\langle{{\left\langle{x,0}\right\rangle},D}\right\rangle} \colon {\left\langle{{\left\langle{x,0}\right\rangle},D}\right\rangle}\in \Gamma\}\cup \{{\left\langle{{\left\langle{x,1}\right\rangle},D}\right\rangle} \colon (\exists n>0)[{\left\langle{{\left\langle{x,n}\right\rangle},D}\right\rangle}\in \Gamma]\}. \end{align*}$$

One can check that $\Lambda (X)$ is the graph of a universal function for the $\{0,1\}$ -valued partial functions whose graphs are enumeration reducible to X.

For $(2)\Rightarrow (1)$ , we use a familiar trick: Every function $\varphi \colon \omega \rightarrow \omega $ can be represented by a $\{0,1\}$ -valued function $\psi \colon \omega ^2\rightarrow \{0,1\}$ defined by $\psi (x,y) = 1$ if $\varphi (x) = y$ and $\psi (x, y) = 0$ if $\varphi (x)\operatorname {\mathrm {\downarrow }}\neq y$ . If U is universal for the $\{0,1\}$ -valued functions, define the function $\widehat {U}$ by $\widehat {U}(e,x) = y$ if and only if $U(e, {\left \langle {x,y}\right \rangle }) = 1$ and for all $z < y$ , $U(e,{\left \langle {x,z}\right \rangle }) = 0$ . Then $\widehat {U}$ is universal and $G_{\widehat {U}} \leq _e G_U$ .

For $(2)\Rightarrow (3)$ , suppose that U is a universal $\{0,1\}$ -valued function for X and $G_U\leq _e X$ . For every $\{0,1\}$ -valued $\varphi $ with $G_{\varphi }\leq _e X$ , the set of all total $\{0,1\}$ -valued extensions of $\varphi $ is a nonempty $\Pi ^0_1{\left \langle {X}\right \rangle }$ class. Using U we can interweave all such classes into one class P. Formally, define P to be the $\Pi ^0_1{\left \langle {X}\right \rangle }$ separating class for the disjoint sets $\{{\left \langle {e,x}\right \rangle } \colon U(e,x) = 1\}$ and $\{{\left \langle {e,x}\right \rangle } \colon U(e,x) = 0\}$ . Now if $Q(B,C)$ is a $\Pi ^0_1{\left \langle {X}\right \rangle }$ separating class, then $B\times \{1\}\cup C\times \{0\}$ is the graph of a $\{0,1\}$ -valued function whose graph is e-reducible to X. Fix some e such that this function is $\lambda x. U(e,x)$ . Then for any $Y\in P$ , the column $Y^{[e]}$ is an extension of $\lambda x. U(e,x)$ , and hence a separator for B and C. Note that once we have e, the reduction is uniform.

The implication $(3) \Rightarrow (4)$ is immediate.

Finally, to see that $(4)\Rightarrow (2)$ is true, let $\Gamma $ be an enumeration operator such that $P = 2^{\omega }\smallsetminus [\Gamma (X)]$ is a $\Pi ^0_1{\left \langle {X}\right \rangle }$ class that is universal for $\operatorname {\mathrm {Sep}}{\left \langle {X}\right \rangle }$ classes. We define a universal $\{0,1\}$ -valued function U as follows: for every pair ${\left \langle {e,i}\right \rangle }$ , we set $U({\left \langle {e,i}\right \rangle }, x) = y$ if

1. (1) $y\leq 1$ ,

2. (2) ${\left \langle {x,y}\right \rangle }\in \Gamma _e(X)$ , and

3. (3) there is a finite set $D\subseteq \Gamma (X)$ and an n such that if $\sigma \in 2^n\smallsetminus [D]$ , then $\Phi _i^{\sigma }(x)\operatorname {\mathrm {\downarrow }} = y$ .

Here, $\Gamma _e$ is the e-th enumeration operator, and $\Phi _i$ is the i-th Turing functional. Clearly, U is a $\{0,1\}$ -valued function with graph that is e-reducible to X. It is also universal, because if $\varphi $ is a $\{0,1\}$ -valued function such that $G_{\varphi } = \Gamma _e(X)$ , we may consider the $\operatorname {\mathrm {Sep}}{\left \langle {X}\right \rangle }$ class of all sets which separate the disjoint sets $B =\{n \colon \varphi (n) = 1\}$ and $C =\{n \colon \varphi (n) = 0\}$ . Let i be the index of the Turing functional via which every member of P computes a separator for B and C. Then $\lambda x.U( {\left \langle {e,i}\right \rangle },x) = \varphi $ . Indeed, the second condition ensures that if $U({\left \langle {e,i}\right \rangle },x) = y$ , then $\varphi (x) = y$ . Conversely, if $\varphi (x) = y$ , then compactness and our choice of i implies that the third condition holds, so $U({\left \langle {e,i}\right \rangle },x) = y$ .

Proof We shall verify that $A_G$ satisfies (6) in Theorem 4.6. Let ${\left \langle {T, \varepsilon }\right \rangle }$ be an arbitrary condition. Consider a pair of enumeration operators $\Gamma _0$ and $\Gamma _1$ . If there is a condition ${\left \langle {S, \delta }\right \rangle }$ extending ${\left \langle {T, \varepsilon }\right \rangle }$ such that $\Gamma _0(A_S)$ and $\Gamma _1(A_S)$ intersect, then we make that extension. This ensures that $\Gamma _0(A_G)$ and $\Gamma _1(A_G)$ are not disjoint.

Now assume that we cannot force $\Gamma _0(A_G)$ and $\Gamma _1(A_G)$ to intersect. We want to extend ${\left \langle {T, \varepsilon }\right \rangle }$ to ensure that $\Gamma _0(A_G)$ and $\Gamma _1(A_G)$ are separated by disjoint c.e. sets. We claim that ${\left \langle {T, \varepsilon /2}\right \rangle }$ is such an extension. For $i=0,1$ , define $C_i$ to be the set of all n for which there is some condition ${\left \langle {S, \delta }\right \rangle }$ extending ${\left \langle {T, \varepsilon /2}\right \rangle }$ such that $n \in \Gamma _i(A_S)$ . It is straightforward to see that $C_i$ is c.e. and contains $\Gamma _i(A_G)$ .

Furthermore, we claim that $C_0$ and $C_1$ are disjoint. If not, fix $n \in \omega $ and conditions ${\left \langle {S_0, \delta _0}\right \rangle }$ and ${\left \langle {S_1, \delta _1}\right \rangle }$ extending ${\left \langle {T, \varepsilon /2}\right \rangle }$ that witness that $n \in C_0$ and $n \in C_1$ , respectively. Without loss of generality, we may assume that $|S_0| = |S_1|$ . Consider the condition ${\left \langle {S_0 \cap S_1, \varepsilon }\right \rangle }$ .

It is straightforward to see that ${\left \langle {S_0 \cap S_1, \varepsilon }\right \rangle }$ extends ${\left \langle {T, \varepsilon }\right \rangle }$ . In fact, for every $\sigma \in S_0 \cap S_1$ with $|T| \leq |\sigma | < |S_0|$ ( $=|S_1|$ ), at least $\left \lceil (1-\varepsilon /2) \cdot 2^{|\sigma |} \right \rceil $ of its immediate successors lie in $S_0$ and at least $\left \lceil (1-\varepsilon /2) \cdot 2^{|\sigma |} \right \rceil $ of its immediate successors lie in $S_1$ . Therefore at least $\left \lceil (1-\varepsilon ) \cdot 2^{|\sigma |} \right \rceil $ of its immediate successors lie in $S_0 \cap S_1$ .

The argument above also implies that $|S_0 \cap S_1| = |S_0| = |S_1|$ . So $A_{S_0 \cap S_1}$ contains $A_{S_0}$ , meaning that $n\in \Gamma _0(A_{S_0 \cap S_1})$ . Similarly, $n\in \Gamma _1(A_{S_0 \cap S_1})$ . This contradicts our assumption that there is no condition ${\left \langle {S, \delta }\right \rangle }$ extending ${\left \langle {T, \varepsilon }\right \rangle }$ such that $\Gamma _0(A_S)$ and $\Gamma _1(A_S)$ intersect. Therefore, $C_0$ and $C_1$ are disjoint c.e. sets covering $\Gamma _0(A_G)$ and $\Gamma _1(A_G)$ , respectively.

Proof To show that ${\left \langle {A_G}\right \rangle }$ is not low for PA, note that $[G]$ is a nonempty $\Pi ^0_1{\left \langle {A_G}\right \rangle }$ class, where $[G]\subseteq f^\omega $ is the set of infinite paths through G. We show that it has no nonempty $\Pi ^0_1$ subclass. Indeed, let $P \subseteq f^{\omega }$ be a nonempty $\Pi ^0_1$ class and let ${\left \langle {T, \varepsilon }\right \rangle }\in \mathbb {P}$ be an arbitrary condition. Since P is nonempty, there must be some $\sigma \in f^{<\omega }$ of length $n>\max \{|T|, -\log _2(\varepsilon )+1\}$ such that $\sigma $ has an extension in P. For such a $\sigma $ , we can extend ${\left \langle {T, \varepsilon }\right \rangle }$ to ${\left \langle {S, \varepsilon }\right \rangle }$ , where S has height n and does not contain $\sigma $ . Then ${\left \langle {S, \varepsilon }\right \rangle }$ ensures that P is not a subclass of $[G]$ , and we have shown that such conditions are dense.

Proof We pointed out after Theorem 4.6 that every low for PA oracle has the computable extension property. Strictness follows from Lemmas 5.2 and 5.3.

Proof Consider an oracle $\Pi ^0_1{\left \langle {A_G}\right \rangle }$ class $P{\left \langle {A_G}\right \rangle }$ . We want to show that $P{\left \langle {A_G}\right \rangle }$ is not a universal $\Pi ^0_1{\left \langle {A_G}\right \rangle }$ class. Let ${\left \langle {T, \varepsilon }\right \rangle }$ be an arbitrary condition. The easy win, of course, is if there is an extension ${\left \langle {S,\delta }\right \rangle }$ of ${\left \langle {T, \varepsilon }\right \rangle }$ such that $P{\left \langle {A_S}\right \rangle }$ is empty. Since $P{\left \langle {A_G}\right \rangle }\subseteq P{\left \langle {A_S}\right \rangle }$ , this would force $P{\left \langle {A_G}\right \rangle }$ to be empty. So let us assume that this is not true. In other words, we are assuming that

$$\begin{align*}{\left\langle{T, \varepsilon}\right\rangle}\Vdash P{\left\langle{A_G}\right\rangle}\text{ is nonempty}. \end{align*}$$

In this case, we will have to meet infinitely many dense sets to ensure that $P{\left \langle {A_G}\right \rangle }$ is not universal.

First, let ${\left \langle {S,\delta }\right \rangle }$ be an extension of ${\left \langle {T, \varepsilon }\right \rangle }$ such that $|S|> -\log _2(\varepsilon )+1$ , and there is a $\tau \in S$ of length $|S|-1$ such that every immediate successor of $\tau $ is in S. Obviously, such extensions are dense. Let $\sigma $ be an immediate successor of $\tau $ . Note that we have set things up so that $S\smallsetminus \{\sigma \}$ is an $\varepsilon $ -extension of T. Furthermore, if R is any $\delta $ -extension of S, then $R\smallsetminus [\sigma ]^\prec $ is an $\varepsilon $ -extension of T. Here, $[\sigma ]^\prec \subseteq f^{<\omega }$ is the set of all finite strings extending $\sigma $ . (Not to be confused with $[\sigma ]\subseteq f^{\omega }$ .)

This implies that

$$\begin{align*}{\left\langle{S,\delta}\right\rangle}\Vdash P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty}. \end{align*}$$

Also note that ${\left \langle {S,\delta }\right \rangle }$ forces that $[G]\cap [\sigma ]$ is a nonempty $\Pi ^0_1{\left \langle {A_G}\right \rangle }$ class because every leaf of S must have a full-height extension in every $\delta $ -extension of S. Our goal is to prove that

$$\begin{align*}{\left\langle{S,\delta}\right\rangle}\Vdash \left(\exists X\in P{\left\langle{A_G}\right\rangle}\right)\; X \text{ computes no member of }[G]\cap[\sigma]. \end{align*}$$

The witness X will actually be in $P{\left \langle {A_{G\smallsetminus [\sigma ]^\prec }}\right \rangle }$ , which is a subset of $P{\left \langle {A_G}\right \rangle }$ . This is the key to the argument: any choice that we make when building G above $\sigma $ —i.e., any choice that affects $[G]\cap [\sigma ]$ —has no effect on $P{\left \langle {A_{G\smallsetminus [\sigma ]^\prec }}\right \rangle }$ .

Now let ${\left \langle {R,\gamma }\right \rangle }$ be an extension of ${\left \langle {S,\delta }\right \rangle }$ and let $Q\subseteq f^\omega $ be a $\Pi ^0_1$ class such that

$$\begin{align*}{\left\langle{R,\gamma}\right\rangle}\Vdash Q\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty}. \end{align*}$$

Furthermore, let $\Phi $ be a Turing functional. We will find an extension ${\left \langle {R',\gamma '}\right \rangle }$ of ${\left \langle {R,\gamma }\right \rangle }$ and a $\Pi ^0_1$ subclass $Q'\subseteq Q$ such that

(5.1) $$ \begin{align} \begin{split} {\left\langle{R',\gamma'}\right\rangle}\Vdash &\ Q'\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty and}\\ & \left(\forall X\in Q'\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\right)\; \Phi^X\notin [G]\cap[\sigma]. \end{split} \end{align} $$

Fix $n>\max \{|R|,-\log _2(\gamma )+1\}$ . Let

$$\begin{align*}Q^* = \{X\in Q \colon \Phi^X\operatorname{\mathrm{\upharpoonright}} n\text{ is partial or does not extend }\sigma\}. \end{align*}$$

If

$$\begin{align*}{\left\langle{R,\gamma}\right\rangle}\Vdash Q^*\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty}, \end{align*}$$

then let ${\left \langle {R',\gamma '}\right \rangle } = {\left \langle {R,\gamma }\right \rangle }$ and $Q' = Q^*$ ; this satisfies (5.1).

Otherwise, let $R^*$ be a $\gamma $ -extension of R such that $Q^*\cap P{\left \langle {A_{R^*\smallsetminus [\sigma ]^\prec }}\right \rangle }$ is empty. In other words, for every $X\in Q\cap P{\left \langle {A_{R^*\smallsetminus [\sigma ]^\prec }}\right \rangle }$ , we know that $\Phi ^X\operatorname {\mathrm {\upharpoonright }} n$ is total and extends $\sigma $ . Note that we may assume that $R^*$ contains all extensions of $\sigma $ up to length $|R^*|$ . It will also be convenient to assume that $|R^*|\geq n$ .

For each $\tau \in f^n$ extending $\sigma $ , let $Q_\tau = \{X\in Q\cap P{\left \langle {A_{R^*\smallsetminus [\sigma ]^\prec }}\right \rangle } \colon \Phi ^X\operatorname {\mathrm {\upharpoonright }} n = \tau \}$ . Note that $Q_\tau $ is a $\Pi ^0_1$ class by our choice of $R^*$ . Let $\gamma ' = \gamma /2^n$ . We claim that for some $\tau \in f^n$ that extends $\sigma $ we have

(5.2) $$ \begin{align} {\left\langle{R^*,\gamma'}\right\rangle}\Vdash Q_\tau\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty}. \end{align} $$

If this were not the case, then following the proof of Lemma 5.2, we intersect the $2^{n-|\sigma |}$ same height $\gamma '$ -extensions of $R^*$ that are chosen to force the emptiness of $Q_\tau \cap P{\left \langle {A_{G\smallsetminus [\sigma ]^\prec }}\right \rangle }$ for each $\tau \in f^n$ extending $\sigma $ . This gives us a $\gamma $ -extension of $R^*$ that witnesses the emptiness of $Q\cap P{\left \langle {A_{G\smallsetminus [\sigma ]^\prec }}\right \rangle }$ , which is a contradiction.

So fix a $\tau \in f^n$ that extends $\sigma $ such that (5.2) holds. Let $R' = R^*\smallsetminus [\tau ]^\prec $ and note that ${\left \langle {R',\gamma '}\right \rangle }$ extends ${\left \langle {R,\gamma }\right \rangle }$ , because of the choice of n, and that

$$\begin{align*}{\left\langle{R',\gamma'}\right\rangle}\Vdash Q_\tau\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty}. \end{align*}$$

This latter fact holds because, as we mentioned above, nothing we do to G above $\sigma $ has any effect on $P{\left \langle {A_{G\smallsetminus [\sigma ]^\prec }}\right \rangle }$ . Finally, having removed $\tau $ from $R'$ , we have

$$\begin{align*}{\left\langle{R',\gamma'}\right\rangle}\Vdash \left(\forall X\in Q_\tau\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\right)\; \Phi^X \notin [G]\cap[\sigma]. \end{align*}$$

Therefore, letting $Q'=Q_\tau $ , we have satisfied (5.1).

We are now ready to wrap up the proof that

$$\begin{align*}{\left\langle{S,\delta}\right\rangle}\Vdash \left(\exists X\in P{\left\langle{A_G}\right\rangle}\right)\; X \text{ computes no member of }[G]\cap[\sigma]. \end{align*}$$

Let $\mathcal {F}\subseteq \mathbb {P}$ be a sufficiently generic filter containing ${\left \langle {S,\delta }\right \rangle }$ . Then by the argument above, there is a sequence of conditions ${\left \langle {S,\delta }\right \rangle } = {\left \langle {R_0,\gamma _0}\right \rangle } \geq {\left \langle {R_1,\gamma _1}\right \rangle } \geq {\left \langle {R_2,\gamma _2}\right \rangle } \geq \cdots $ , all of which are in $\mathcal {F}$ , and a sequence of $\Pi ^0_1$ classes $f^\omega = Q_0\supseteq Q_1\supseteq Q_2\supseteq \cdots $ such that, for each i,

$$\begin{align*}{\left\langle{R_i,\gamma_i}\right\rangle}\Vdash Q_i\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\text{ is nonempty}, \end{align*}$$

and for each $i>0$ ,

$$\begin{align*}{\left\langle{R_i,\gamma_i}\right\rangle}\Vdash \left(\forall X\in Q_i\cap P{\left\langle{A_{G\smallsetminus[\sigma]^\prec}}\right\rangle}\right)\; \Phi_{i-1}^X\notin [G]\cap[\sigma]. \end{align*}$$

Here, as you would expect, $\{\Phi _i\}_{i\in \omega }$ is an enumeration of the Turing functionals. So take any X in $\bigcap _{i\in \omega } Q_i\cap P{\left \langle {A_{G\smallsetminus [\sigma ]^\prec }}\right \rangle }$ , which must be nonempty by compactness. Then X computes no member of $[G]\cap [\sigma ]$ , as desired.

We have shown that for every oracle $\Pi ^0_1{\left \langle {A}\right \rangle }$ class $P{\left \langle {A}\right \rangle }$ , and every condition ${\left \langle {T, \varepsilon }\right \rangle }$ , there is an extension of ${\left \langle {T, \varepsilon }\right \rangle }$ that forces $P{\left \langle {A_G}\right \rangle }$ not to be a universal $\Pi ^0_1{\left \langle {A_G}\right \rangle }$ class (possibly by making it empty). Therefore, as long as G is sufficiently generic, there is no universal $\Pi ^0_1{\left \langle {A_G}\right \rangle }$ class.

Proof We use a forcing notion that combines $\mathbb {P}$ and (a minor variant of) the forcing notion used in the proof of Theorem 2.11. Our conditions have the form

$$\begin{align*}p = ({\left\langle{T, \varepsilon}\right\rangle}, n, X_1, \dots X_{n-1}, D), \end{align*}$$

where

1. 1. ${\left \langle {T, \varepsilon }\right \rangle }\in \mathbb {P}$ , i.e., T is a finite tree in $f^{<\omega }$ and $\varepsilon \in (0,1)$ is rational.

2. 2. $(n, X_1, \dots X_{n-1}, D)$ are almost as in Theorem 2.11: $n\in \omega $ , $X_1, \dots , X_{n-1}\in 2^{\omega }$ and D is a finite subset of $\omega ^{[>0]}$ .

We associate with a condition p the set

$$\begin{align*}A_p =\bigg( \bigoplus_{i\in\omega} Y_i\bigg) \cup D, \end{align*}$$

where $Y_0 = f^{\leq |T|}\smallsetminus T$ , $Y_{i } = X_{i}$ for $0< i <n$ and $Y_{i} = \emptyset $ for $i>n$ . A condition $q = ({\left \langle {S, \delta }\right \rangle }, m, Y_1, \dots , Y_{m-1}, E)$ extends p if:

• • ${\left \langle {S,\delta }\right \rangle }$ extends ${\left \langle {T,\varepsilon }\right \rangle }$ (in the sense of $\mathbb {P}$ );

• • $m\geq n$ and $X_1 = Y_1$ , …, $X_{n-1} = Y_{n-1}$ ;

• • $D\subseteq E$ and $E\smallsetminus D\subseteq \omega ^{[\geq n]}$ .

We shall build a monotone sequence $\{p_s\}_{s\in \omega }$ and let $A = \bigcup _{s}A_{p_s}$ . To ensure that A has the separation property we satisfy requirements:

$$\begin{align*}\mathcal{S}_{i,j}: \Gamma_i(A)\cap \Gamma_j(A) = \emptyset \rightarrow (\exists C)[\Gamma_i(A)\subseteq C\ \& \ \Gamma_j(A)\subseteq \overline C\ \ \&\ C\oplus \overline C\leq_e A ]. \end{align*}$$

To ensure that A is not ${\left \langle {\text {self}\kern2pt}\right \rangle }$ -PA we satisfy requirements:

$$\begin{align*}\mathcal{N}_e\colon \bigcup \Gamma_e(A) \text{ is not a path through } [f^{<\omega }\smallsetminus A^{[0]}]. \end{align*}$$

(See Remark 5.1 for a discussion of paths through subclasses of $f^\omega $ .) Note that $[f^{<\omega }\smallsetminus A^{[0]}]$ is a nonempty $\Pi ^0_1{\left \langle {A}\right \rangle }$ class just as in the forcing notion $\mathbb {P}$ that we introduced earlier in this section.

We start with $p_0 = ( {\left \langle {\emptyset , \frac {1}{2}}\right \rangle }, 0, \emptyset )$ . Suppose we have constructed

$$\begin{align*}p_s =({\left\langle{T, \varepsilon}\right\rangle}, n, X_1, \dots, X_{n-1}, D)\end{align*}$$

and $s = 2{\left \langle {i,j}\right \rangle }$ . To satisfy $\mathcal {S}_{i,j}$ , we ask if $p_s$ has an extension of the form

$$\begin{align*}q = ({\left\langle{S, \varepsilon}\right\rangle}, n, X_1, \dots, X_{n-1}, E) \end{align*}$$

such that $\Gamma _i(A_q)\cap \Gamma _j(A_q)\neq \emptyset $ . If so, then let $p_{s+1}$ be such an extension. In this case, we can argue that $\mathcal {S}_{i,j}$ is vacuously satisfied.

If there is no such extension, we define $p_{s+1}$ as follows. For $k = i,j$ , let $W_k$ be the set of all numbers x such that there is some

$$\begin{align*}q = ({\left\langle{S, \varepsilon/2}\right\rangle}, n, X_1, \dots, X_{n-1}, E) \end{align*}$$

extending $({\left \langle {T, \varepsilon /2}\right \rangle }, n, X_1, \dots ,X_{n-1}, D)$ such that $x\in \Gamma _{k}(A_q)$ . We claim that $W_i$ and $W_j$ are disjoint. If not, fix $x \in W_i \cap W_j$ and conditions

$$ \begin{align*} &({\left\langle{S_i,\varepsilon/2}\right\rangle}, n,X_1,\dots,X_{n-1},E_i) \\ \text{and} \quad &({\left\langle{S_j,\varepsilon/2}\right\rangle}, n,X_1,\dots,X_{n-1},E_j) \end{align*} $$

witnessing that x lies in $W_i$ and $W_j$ , respectively. Without loss of generality, we may assume that $|S_i| = |S_j|$ . Following the proof of Lemma 5.2, the condition

$$\begin{align*}q = ({\left\langle{S_i \cap S_j,\varepsilon}\right\rangle},n,X_1,\dots,X_{n-1},E_i \cup E_j) \end{align*}$$

extends $p_s$ and satisfies $x \in \Gamma _i(A_q) \cap \Gamma _j(A_q)$ , which is a contradiction. This proves that $W_i$ and $W_j$ are disjoint.

Let C be an arbitrary separator for $W_i$ and $W_j$ and let

$$\begin{align*}p_{s+1} = ({\left\langle{T, \varepsilon/2}\right\rangle}, n+2, X_1 \dots, X_{n-1}, C, \overline{C}, D). \end{align*}$$

We claim that for $k = i,j$ , we have $\Gamma _k(A) \subseteq W_k$ . If $x \in \Gamma _k(A)$ , there is some condition $q = ({\left \langle {S,\delta }\right \rangle },m,X_1,\dots ,X_{m-1},E)$ extending $p_{s+1}$ such that $x \in \Gamma _k(A_q)$ . Fix a finite set $F \subseteq A_q$ such that $x \in \Gamma _k(F)$ . Define $E' = D \cup (F \cap \omega ^{[\geq n]})$ . Then $q' = ({\left \langle {S,\varepsilon /2}\right \rangle },n,X_1,\dots ,X_{n-1},E')$ extends $({\left \langle {T,\varepsilon /2}\right \rangle },n,X_1,\dots ,X_{n-1},D)$ and $x \in \Gamma _k(A_{q'})$ . This shows that $x \in W_k$ , proving the claim.

It follows that A can enumerate a separator (and its complement) for $\Gamma _i(A)$ and $\Gamma _j(A)$ , by enumerating $A^{[n]}\oplus A^{[n+1]}$ (modulo some possible finite error).

If $s = 2e+1$ , we ensure that $\mathcal {N}_e$ is satisfied. We ask if there is a condition

$$\begin{align*}q = ({\left\langle{S, \varepsilon/2}\right\rangle}, n, X_1, \dots ,X_{n-1}, E)\end{align*}$$

that extends $({\left \langle {T, \varepsilon /2}\right \rangle }, n, X_1, \dots ,X_{n-1}, D)$ (i.e., $p_s$ but with $\varepsilon $ replaced by $\varepsilon /2$ ) and puts some $\sigma $ into $\Gamma _e(A_q)$ , where $|\sigma |>\max \{|T| ,\log _2(\frac {2}{\varepsilon })+1\}$ .

If there is such a condition q and such a string $\sigma $ , we may assume that $|S| \geq |\sigma |$ . Then let

$$\begin{align*}p_{s+1} = ({\left\langle{S\smallsetminus\{\tau \colon \tau\succeq\sigma\}, \varepsilon/2}\right\rangle}, n, X_1, \dots ,X_{n-1}, E). \end{align*}$$

Since ${\left \langle {S,\varepsilon /2}\right \rangle }$ extends ${\left \langle {T,\varepsilon /2}\right \rangle }$ and $|S| \geq |\sigma | \geq \max \{|T| ,\log _2(\frac {2}{\varepsilon })+1\}$ , this is a valid extension of $p_s$ . Furthermore, it satisfies $\mathcal {N}_e$ : we have $\sigma \in \Gamma _e(A_{p_{s+1}})$ as $A_{p_{s+1}}\supseteq A_q$ , yet no path in $ [f^{<\omega }\smallsetminus A^{[0]}]$ extends $\sigma $ because $\sigma \in A^{[0]}$ .

If there is no such q and $\sigma $ , then we let

$$\begin{align*}p_{s+1} = ({\left\langle{T, \varepsilon/2}\right\rangle}, n, X_1, \dots ,X_{n-1}, D). \end{align*}$$

In this case we can argue that $\mathcal {N}_e$ is vacuously satisfied, as $\Gamma _e(A)$ does not contain any string of length larger than $\max \{|T| ,\log _2(\frac {2}{\varepsilon })+1\}$ .