Proof. If X is $\Delta ^1_1$ , then $\{X\}$ is a $\Sigma ^1_1$ class, and thus $\mathbf {d}$ computes X.⊣

Proof. Note that $X = \{ (i, j) : \mathcal {M}_i \cong \mathcal {M}_j\}$ is a $\Sigma ^1_1$ -complete set (folklore; see [Reference Goncharov and Knight20]). However, if $\mathbf {d}$ is high for isomorphism with $D \in \mathbf {d}$ , then $(i,j) \in X$ if and only if $\exists e\, [\{e\}^D: \mathcal {M}_i \cong \mathcal {M}_j]$ , and the matrix of the right-hand side is $\Pi ^0_2(D)$ . Then $\Sigma ^1_1$ sets are $\Sigma ^0_3(\mathbf {d})$ , making $\mathcal {O} \in \Pi ^0_3(\mathbf {d})$ .

If, instead, $\mathbf {d}$ is uniformly high for isomorphism as witnessed by D and f, then we can strip off the opening existential quantifier from the previous argument: $(i, j) \in X$ if and only if $\{f(i,j)\}^D: \mathcal {M}_i \cong \mathcal {M}_j$ . In this case, $\Sigma ^1_1$ sets are $\Pi ^0_2(\mathbf {d})$ , making $\mathcal {O} \in \Sigma ^0_2(\mathbf {d})$ .⊣

Proof. Let

$$ \begin{align*} \mathcal{R} = \{ (X, f) \in \mathcal{Q} \times (\omega\cup \{-1\})^\omega &: \text{if}\ f(e) =\ -1, \text{then}\ \{e\}^X\ \text{is ill-founded,}\\ & \text{and if}\ f(e) = n>\ -1, \text{then}\ \{e\}^X \cong \{n\}^\emptyset\}. \end{align*} $$

Note that $\mathcal {R}$ is $\Sigma ^1_1$ . In order to show that $\mathcal {R}$ is nonempty via the Gandy Basis Theorem, we fix $X \in \mathcal {Q}$ with $\omega _1^X = \omega _1^{ck}$ . Then for every e such that $\{e\}^X$ is well founded, there is an n with $\{e\}^X \cong \{n\}^\emptyset $ , so we define $f(e) = n$ for such an n. For e such that $\{e\}^X$ is ill founded, we define $f(e) =\ -1$ . Then $(X, f) \in \mathcal {R}$ .

As $\mathcal {R}$ is a nonempty $\Sigma ^1_1$ class, there is some $(X, f) \in \mathcal {R}$ computable from $\mathcal {O}$ . Then $e \in \mathcal {O}^X$ if and only if $-1 < f(e) \in \mathcal {O}$ , and so $\mathcal {O}^X \le _T \mathcal {O}$ . Furthermore, the process for constructing the Turing reduction is uniform from an index for $\mathcal {Q}$ .⊣

Proof. Certainly g is a function with the necessary extension condition. It remains in point 1 to show the (uniform) computability of g from each $g(X)$ . For any X, we have $g(X) = f(X\oplus Y)$ , so $g(X)$ computes f by assumption. The pair $(g(X),f) = (f(X\oplus Y), f)$ computes $X\oplus Y$ and so computes Y, and $(f,Y)$ computes g. Since g computes $g(0^\infty )$ , it follows that $Y \le _T g$ . All of this is uniform if the reduction from $f(X\oplus Y)$ to f is.⊣

Proof. For a set X, we take $X^{(3)} = \{ e : \exists m\, [\lambda z.\{e\}^X(m,z) \text { is total}]\}$ .

We build an $\mathcal {O}$ -computable sequence of uniformly pointed perfect trees $f_0 \ge f_1 \ge \cdots $ where $\mathcal {O}^{f_i} \le _T \mathcal {O}$ for each i (and the sequence of indices for the reductions is computable in $\mathcal {O}$ ). We alternate between working to force the triple jump and coding the next required isomorphism.

We begin by setting $f_0$ to be the identity: $f_0(\sigma ) = \sigma $ .

Suppose we have defined $f_n$ with $n = 2\langle e,0\rangle $ . Consider the class

$$ \begin{align*} U_e = \{ g : \ &g\ \text{is a uniformly pointed perfect tree} \ \& \ g \le f_n\\ &\& \ \exists m\, [\lambda z.\{e\}^{g(X)}(m,z)\text{ is total for every}\ X \in 2^\omega]\}. \end{align*} $$

This is arithmetic relative to $f_n$ (again, this relies on compactness) and thus is a $\Sigma ^1_1(f_n)$ class. Thus $\mathcal {O}^{f_n}$ can decide whether $U_e$ is empty, and since $\mathcal {O}^{f_n} \le _T \mathcal {O}$ , so can $\mathcal {O}$ .

If $U_e$ is nonempty, there is a $g \in U_e$ with $\mathcal {O}^{g} \le _T \mathcal {O}^{f_n} \le _T \mathcal {O}$ , and indices for the relevant reductions can be obtained effectively. We thus let $f_{n+1} = g$ , and we have now forced e into the triple jump. By replacing g with $\lambda \sigma. g(0^n\widehat {\phantom {\alpha }}\sigma )$ , we may assume that $|f_{n+1}(\langle \rangle )|> n$ .

If $U_e$ is empty, we let $f_{n+1} = f_n$ (again, adjusting to ensure $|f_{n+1}(\langle \rangle )|> n$ ). By our actions at steps $2\langle e,m+1\rangle $ for $m \in \omega $ , we will force e out of the triple jump.

Now suppose instead that we have defined $f_n$ with $n = 2\langle e, m+1\rangle $ . If $U_e$ was nonempty at step $2\langle e,0\rangle $ , then the triple jump is already forced at e, so we let $f_{n+1} = f_n$ .

If $U_e$ was empty at step $2\langle e,0\rangle $ , we know there are $\tau $ and z such that $\{e\}^{f_n(\sigma )}(m,z)\!\!\uparrow $ for every $\sigma \supseteq \tau $ : if this were not the case, we could define an h as follows for a contradiction.

• • Let $h(\langle \rangle ) = \sigma $ for the first string $\sigma $ discovered with $\{e\}^{f_n(\sigma )}(m,0)\!\!\downarrow $ .

• • For $\rho \in 2^{<\omega }$ and $i < 2$ , let $h(\rho \widehat {\phantom {\alpha }} i) = \sigma $ for the first string $\sigma \supseteq h(\rho )\widehat {\phantom {\alpha }} i$ discovered with $\{e\}^{f_n(\sigma )}(m,|\rho |+1)\!\!\downarrow $ .

By assumption, h is total. Now we let $g = f_n\circ h$ . Note that $h \le _T f_n$ , so $g \le _T f_n$ , and for every X, $g(X) = f(h(X))$ . Thus g is a uniformly pointed perfect tree, and $g \le f_n \le f_{2\langle e,0\rangle }$ . Also, $\lambda z.\{e\}^{g(X)}(m,z)$ is total for all X, and so $g \in U_e$ contrary to assumption. Therefore, there must be such a $\tau $ and z. The set of such pairs $(\tau , z)$ is arithmetical in $f_n$ , and so $\mathcal {O}^{f_n} \le _T \mathcal {O}$ can uniformly find such a pair.

We define $f_{n+1}(\sigma ) = f_n(\tau \widehat {\phantom {\alpha }} \sigma )$ . So $\{e\}^{f_{n+1}(X)}(m,z)\!\!\uparrow $ for every $X \in 2^\omega $ , and we have taken another step towards forcing the triple jump at e.

Suppose instead we have defined $f_n$ with $n = 2\langle k,m\rangle +1$ . We will choose $f_{n+1}$ able to compute an isomorphism between $\mathcal {M}_k$ and $\mathcal {M}_m$ if such an isomorphism exists. Consider $V_n = \{ r\in \omega ^\omega \ | \ r : \mathcal {M}_k \cong \mathcal {M}_m\}$ . This is a $\Sigma ^1_1$ class, and $\mathcal {O}$ can therefore determine whether it is empty.

If $V_n$ is empty, we define $f_{n+1} = f_n$ . If $V_n$ is nonempty, then we note that $V_n$ is also a $\Sigma ^1_1(f_n)$ class. This means that there is an $r \in V_n$ with $\mathcal {O}^{r,f_n} \le _T \mathcal {O}^{f_n} \le _T \mathcal {O}$ , and relevant indices can be obtained effectively. Let R be a set coding r in some effective fashion, and let $f_{n+1} = f_n\oplus R$ . Then $f_{n+1} \le _T (f_n, R)$ , and so $\mathcal {O}^{f_{n+1}} \le _T \mathcal {O}$ .

By construction, $|f_{n+1}(\langle \rangle )|> n$ for every $n = 2\langle e,0\rangle $ . We let

$$\begin{align*}D = \bigcup_{n = 2\langle e,0\rangle} f_{n+1}(\langle \rangle). \end{align*}$$

Then for every n, $D = f_n(X)$ for some X, so if $\mathcal {M}_k \cong \mathcal {M}_m$ , we can let $n = 2\langle k,m\rangle $ . Furthermore, for the r chosen at step n, we have

$$\begin{align*}r \equiv_T R \le_T f_n\oplus R = f_{n+1} \le_T D,\end{align*}$$

and thus D computes an isomorphism between $\mathcal {M}_k$ and $\mathcal {M}_m$ .

Furthermore, $e \in D^{(3)}$ precisely when $U_e$ is nonempty by construction. Since the construction is $\mathcal {O}$ -computable, $D^{(3)} \le _T \mathcal {O}$ . By Proposition 2.8, $\mathbf {d} = {\mathbf{deg}}(D)$ is the desired degree.⊣

Proof. If $\mathbf {d}'$ were uniformly high for isomorphism, then by Proposition 2.8, $\mathcal {O}$ would be $\Sigma ^0_2(\mathbf {d}')$ and thus $\Sigma ^0_3(\mathbf {d})$ . As $\mathbf {d}$ is high for isomorphism, $\mathcal {O}$ is $\Pi ^0_3(\mathbf {d})$ , and so $\mathcal {O}$ would be $\Delta ^0_3(\mathbf {d})$ , contradicting $\mathbf {d}^{(3)} = \mathcal {O}$ .⊣

Proof. We will construct, effectively in $\mathcal {O}$ , two degrees $\mathbf {d}_1$ and $\mathbf {d}_2$ , each of which enumerates $\omega - \mathcal {O}$ , and such that $\mathbf {d}_1 \oplus \mathbf {d}_2 \equiv _T \mathcal {O}$ . By Theorem 5.2, these degrees will be uniformly high for isomorphism.

Let $\langle \cdot , \cdot \rangle $ be a bijection of $\omega ^2$ with $\omega - \{2^k : k \in \omega \}$ . We first define an operator R on $2^{<\omega }$ by setting $R(\sigma )$ to be the set of n such that there is k with $\sigma (\langle k,n \rangle ) = 1$ , and we set $\delta _{1,0}=\delta _{2,0} = \emptyset $ . We will maintain that $R(\delta _{1,s}), R(\delta _{2,s}) \subset \omega - \mathcal {O}$ , and we will arrange that $\bigcup _s R(\delta _{1,s}) = \bigcup _s R(\delta _{2,s}) = \omega - \mathcal {O}$ .

At stage $5s$ , we search, using oracle $\mathcal {O}$ , for some $\sigma \in 2^{<\omega }$ extending $\delta _{1,5s}$ such that $\varphi _s^\sigma (s)\!\!\downarrow $ and $R(\sigma ) \cap \mathcal {O} = \emptyset $ . If such a $\sigma $ exists (a $\Sigma _1^1$ condition), we set $\delta _{1,5s+1} = \sigma $ and $\delta _{2,5s+1} = \delta _{2,5s} \cup \{(2^{k_{5s}},1)\}$ for the least $k_{5s}>\left |\delta _{2,5s}\right |$ . Otherwise, we set $\delta _{1,5s+1} = \delta _{1,5s}$ and $\delta _{2,5s+1} = \delta _{2,5s} \cup \{(2^{k_{5s}},0)\}$ . At stage $5s+1$ , we act similarly, exchanging the roles of $\delta _1$ and $\delta _2$ .

At stage $5s+2$ , we let $n_{5s+1}$ be the least such that

$$\begin{align*}n_{5s+1} \in (\omega - \mathcal{O}) \cap \left(\omega - R\left( \delta_{1,5s+2} \right)\right)\end{align*}$$

and find the least $k_{5s+2}$ such that $\langle k_{5s+2},n_{5s+1} \rangle> \left |\delta _{1,5s+2}\right |$ . We set

$$\begin{align*}\delta_{1,5s+3} = \delta_{1,5s+2} \cup \left\{(\langle k_{5s+1},n_{5s+1} \rangle, 1)\right\}\end{align*}$$

and $\delta _{2,5s+3} = \delta _{2,5s+2}$ . At stage $5s+3$ , we act similarly, again exchanging the roles of $\delta _1$ and $\delta _2$ .

At stage $5s+4$ , we let $s = \langle e_1, e_2\rangle $ . Fix the least $k_1> |\delta _{1, 5s+4}|$ and $k_2> |\delta _{2, 5s+4}|$ . We search, using oracle $\mathcal {O}$ , for some $\sigma _1$ extending $\delta _{1, 5s+4}$ and $\sigma _2$ extending $\delta _{2, 5s+4}$ with $\sigma _1(2^{k_1}) = \sigma _2(2^{k_2}) = 1$ and $R(\sigma _1) \cap \mathcal {O} = R(\sigma _2)\cap \mathcal {O} = \emptyset $ and some m with $\Phi _{e_1}^{\sigma _1}(m)\!\!\downarrow \neq \Phi _{e_2}^{\sigma _2}(m)\!\!\downarrow $ . If such $\sigma _1$ and $\sigma _2$ exist (a $\Sigma ^1_1$ condition), we set $\delta _{1,5s+5} = \sigma _1$ and $\delta _{2, 5s+5} = \sigma _2$ .

If no such pair exists, we instead search for a split above just $\delta _{1,5s+4}$ . If there are strings $\tau _1, \tau _2$ both extending $\delta _{1, 5s+4}$ with $\tau _1(2^{k_1}) = \tau _2(2^{k_1}) = 1$ and $R(\tau _1)\cap \mathcal {O} = R(\tau _2)\cap \mathcal {O} = \emptyset $ and some m with $\Phi _{e_1}^{\tau _1}(m)\!\!\downarrow \neq \Phi _{e_1}^{\tau _2}(m)\!\!\downarrow $ , then we let

$$\begin{align*}\delta_{1,5s+5} = \delta_{1, 5s+4} \cup \{(2^{k_1}, 0)\}\end{align*}$$

and

$$\begin{align*}\delta_{2, 5s+5} = \delta_{2, 5s+4} \cup \{2^{k_2}, 1)\}.\end{align*}$$

Otherwise, we let $\delta _{1,5s+5} = \delta _{1, 5s+4} \cup \{(2^{k_1}, 1)\}$ and $\delta _{2, 5s+5} = \delta _{2, 5s+4} \cup \{(2^{k_2}, 0)\}$ .

We now let $D_i = \bigcup \limits _{s \in \omega } \delta _{i,s}$ for each i. We note that, by construction, each $D_i$ enumerates $(\omega - \mathcal {O})$ and is computable from $\mathcal {O}$ ; indeed, $\mathcal {O}$ can compute $D_i'$ , since when we find at stage $5s$ that there is no $\sigma $ which both forces convergence and maintains disjointness from $\mathcal {O}$ , we commit to never allowing $\varphi _s^{D_i}(s)$ to converge. By a standard argument, $D_1\oplus D_2$ can compute the sequence $(\delta _{1, s}, \delta _{2, s})_{s \in \omega }$ . Thus the join can compute $\mathcal {O}$ , as $n \in \mathcal {O}$ if and only if $n \not \in R(\delta _{1, 5(n+1)})$ .

Finally, we argue that if $X \le _T D_1, D_2$ , then X is hyperarithmetic. Fix $s = \langle e_1, e_2\rangle $ with $X = \Phi _{e_1}^{D_1} = \Phi _{e_2}^{D_2}$ . Then we must not have found the desired strings $\sigma _1, \sigma _2$ at stage $5s+4$ . Suppose we found the subsequent strings $\tau _1, \tau _2$ and the corresponding m instead. Then $D_2(2^{k_2}) = 1$ and $\Phi _{e_2}^{D_2}(m)\!\!\downarrow $ , so there is some initial segment of $D_2$ witnessing this convergence and extending $\delta _{2, 5s+4}$ . There is some j such that $\Phi _{e_1}^{\tau _j}(m) \neq \Phi _{e_2}^{D_2}(m)$ , which gives us a pair $\sigma _1, \sigma _2$ , contrary to the above.

So we did not find $\tau _1$ and $\tau _2$ , meaning that $D_1(2^{k_1}) = 1$ . Thus, for any m and any $\tau $ extending $\delta _{1, 5s+4}$ with $\tau (2^{k_1}) = 1$ and $R(\tau )\cap \mathcal {O} = \emptyset $ , we have

$$\begin{align*}\Phi_{e_1}^{\tau}(m)\!\!\downarrow \Rightarrow \Phi_{e_1}^{\tau}(m) = \Phi_{e_1}^{D_1}(m) = X(m).\end{align*}$$

Thus $X(m) = 1$ if and only if there is such a $\tau $ with $\Phi _{e_1}^{\tau }(m) = 1$ , and $X(m) = 0$ if and only if there is such a $\tau $ with $\Phi _{e_1}={\tau }(m) = 0$ . These are both $\Sigma ^1_1$ conditions, so X is $\Delta ^1_1$ .⊣

Proof. A sequence $((\sigma _0^i, \sigma _1^i))_{i \in \omega }$ is a path through $S\star T$ if and only if $(\sigma _0^i)_{i \in \omega }$ is a path through S and $(\sigma _1^i)_{i \in \omega }$ is a path through T.⊣

Proof of Theorem 2.18. The backwards direction is immediate. For the other direction, we will show that (uniform) highness for isomorphism for Harrison orders implies (uniform) highness for paths. Specifically, given a computable tree T generating a $\Pi ^0_1$ class, we will uniformly exhibit a pair of computable linear orders such that if $[T]$ is nonempty, then the linear orders are both of order type $\omega _1^{ck}(1+\mathbb {Q})$ , and we will give a uniform process to compute an element of $[T]$ from an isomorphism between the orders. This will suffice to establish the result.

First, we fix a Harrison order $\mathcal {H}$ , i.e., a computable linear order of order type $\omega _1^{ck}(1+\mathbb {Q})$ with no descending hyperarithmetic sequence. Let $\mathcal {L} = \mathcal {H}(1+\mathbb {Q})$ . Note that $\mathcal {L} \cong \mathcal {H}$ : it is easy to see that $(1+\mathbb {Q})(1+\mathbb {Q})$ has a least element and is otherwise a countable dense linear order without endpoints, whence $(1+\mathbb {Q})(1+\mathbb {Q}) \cong 1+\mathbb {Q}$ ; and multiplication of linear orders is associative. Furthermore, there is a computable embedding $\iota :\mathbb {Q} \hookrightarrow \mathcal {L}$ : fix some $h \in \mathcal {H}$ , and define $\iota (q) = (h, q)$ . Let S be the tree of finite descending sequences in $\mathcal {H}$ .

Now fix a computable tree T.

Note that S has the property that if $\sigma \in S$ is extendible to an infinite path, then $\sigma $ has infinitely many immediate children in S. It follows that $S \star T$ has the same property.

Let $\mathcal {K}$ be the order made from $KB(S\star T)$ by removing the root $\langle \rangle $ . Then $\mathcal {L}$ and $\mathcal {K}$ are our two orders of order type $\omega _1^{ck}(1+\mathbb {Q})$ . Observe that if $\tau \in S\star T$ , then $\{ \rho \in S\star T: \rho \supset \tau \}$ is a computable, convex set in $\mathcal {K}$ .

Suppose now that $f: \mathcal {L} \cong \mathcal {K}$ . We recursively construct a sequence $(\tau _n)_{n \in \omega }$ of elements of $S\star T$ with $\tau _{n} \subset \tau _{n+1}$ and maintain the inductive assumption that $f\circ \iota $ maps a nontrivial interval of $\mathbb {Q}$ into $\{ \rho \in S \star T : \rho \supset \tau _n\}$ (and thus that this interval of K is ill founded, and so $\tau _n$ is extendible to a path through $S\star T$ ). We begin with $\tau _0 = \langle \rangle $ .

Suppose we have defined $\tau _n$ . Then we let $(\alpha _m)_{m \in \omega }$ enumerate the immediate children of $\tau _n$ . Observe that $\bigsqcup _m \{ \rho \in S\star T : \rho \supseteq \alpha _m\}$ partitions $\{ \rho \in S \star T : \rho \supset \tau _n\}$ , each component of the partition is convex in the ordering of K, and the components are arranged with order type $\omega $ (in the ordering of K). So there must be rationals $q_0 < q_1$ and an m with $f(\iota (q_0)), f(\iota (q_1)) \in \{ \rho \in S \star T : \rho \supseteq \alpha _m\}$ . We search for such an m and define $\tau _{n+1} = \alpha _m$ . Now, we can observe that $\{\rho \in S\star T : \rho \supset \tau _{n+1}\}$ contains the open interval from $f(\iota (q_0))$ to $f(\iota (q_1))$ , and so the inductive assumption is maintained.

Thus f uniformly computes $(\tau _n)_{n \in \omega }$ , which is a path through $S\star T$ , and therefore it gives a path through T. This completes the proof.⊣

Proof. Let $\{\mathcal {L}_e : e \in \omega \}$ be a listing of the computable ill-founded linear orders without arithmetic tight descending sequences. This cannot be an effective listing, but its true complexity will not be relevant. We will construct a degree above $\emptyset ^{(m)}$ for every $m \in \omega $ , and thus so long as it also computes a tight descending sequence in each $\mathcal {L}_e$ , it will be high for tight descending sequences.

We construct our degree via forcing. Here, a condition is a pair $(\sigma _0, \sigma _1)$ satisfying the following:

• • $\sigma _0: \omega ^2 \to \omega $ and $\sigma _1: \omega \to \omega \times \{0,1\}$ are finite partial functions; and

• • If $\sigma _1(n) = (e,0)$ , then $\tau = \lambda x.\sigma _0(n,x)$ is a finite descending sequence in $\mathcal {L}_e$ that is extendible to an infinite descending sequence.

A condition $\overline {\sigma }' = (\sigma _0', \sigma _1')$ extends $\overline {\sigma } = (\sigma _0, \sigma _1)$ if the following hold:

• • $\sigma _0'$ extends $\sigma _0$ and $\sigma _1'$ extends $\sigma _1$ ;

• • If $\sigma _1(n) = (m,1)$ , then for $\tau = \lambda x.\sigma _0(n, x)$ and $\tau ' = \lambda x.\sigma _0'(n,x)$ , we have $\tau '(x) = \emptyset ^{(m)}(x)$ for all $x \in \text {dom}(\tau ')\setminus \text {dom}(\tau )$ .

Given a filter F for this notion of forcing, we let $f = \bigcup \limits _{(\sigma _0, \sigma _1) \in F} \sigma _0$ . If F is sufficiently generic, then for every m there is an n and a $(\sigma _0, \sigma _1) \in F$ with $\sigma _1(n) = (m,1)$ , and for this n, $\lambda x.f(n, x) =^* \emptyset ^{(m)}$ . Thus, f will bound every arithmetic set. Furthermore, if F is sufficiently generic, then for every e there is an n and a $(\sigma _0, \sigma _1) \in F$ with $\sigma _1(n) = (e, 0)$ . For this n, $\lambda x.f(n,x)$ will be a tight descending sequence through $\mathcal {L}_e$ . It follows that f is high for descending sequences.

Suppose we have a condition $\overline {\sigma }$ and a Turing functional $\Phi $ . We wish to argue that $\overline {\sigma }$ can be extended to force $\Phi ^f \neq X$ . Let $m = \max \big \{ m' : \exists n \in \text {dom}(\sigma _1)\ \big [\sigma _1(n) = (m', 1)\big]\big\}$ . Let $E = \left \{ e : \exists n \in \text {dom}(\sigma _1)\ \left [\sigma _1(n) = (e,0)\right ]\right \}$ . Then any $\overline {\tau }$ extending $\overline {\sigma }$ is committed to writing sets $=^* \emptyset ^{(m')}$ for some $m' \le m$ on some finitely many columns of $\tau _0$ and to writing descending sequences through $\mathcal {L}_e$ for $e \in E$ on other columns of $\tau _0$ , but is unconstrained on the remaining columns of $\tau _0$ .

Let $n = |E|$ . By Lemma 4.10, we may first extend the descending sequences coded in $\sigma _1$ such that none of them can be extended to $\Delta ^0_{n+m+1}$ descending sequences. Now, working relative to $\emptyset ^{(m)}$ , the main argument in the proof of Theorem 4.5 shows that we can extend to such a $\overline {\tau }$ (we are in the “no such k” case in the proof of that theorem).

Thus for a sufficiently generic filter, $\Phi ^f \neq X$ , and the degree of f is our desired degree.⊣

Proof. Suppose $\mathbf {d}$ is uniformly high for descending sequences. We construct f as follows. On input n, for each $m \in \omega $ , we let $T_m$ be a computable tree having a path if and only if $m \in U_n$ . We take $\mathcal {L}_m$ to be the Kleene–Brouwer ordering of $T_m$ , so $U_n$ is nonempty if and only if $\mathcal {L} = \mathcal {L}_0 + \mathcal {L}_1 + \cdots $ is ill founded. We ask $\mathbf {d}$ to provide us with a descending sequence in $\mathcal {L}$ as in the definition of uniformly high for descending sequences. If $\mathbf {d}$ produces an output, we define $f(n) = m$ , where m is such that the first element of the putative descending sequence occurs in $\mathcal {L}_m$ .

If $U_n$ is truly nonempty, then $\mathbf {d}$ will produce output, and the first element of this output will bound a descending sequence, and so some $\mathcal {L}_{m'}$ with $m' \le m$ will be ill founded and thus $m' \in U_n$ .

Now suppose $\mathbf {d}$ computes such an f. Given an ill-founded linear order $\mathcal {L}$ , we construct a descending sequence as follows. First, we fix $n_0$ such that $U_{n_0} = \mathcal {L}\setminus W(\mathcal {L})$ . This is nonempty by assumption, and so $f(n_0)\!\!\downarrow $ with $\{0, \dots , f(n_0)\} \cap U_{n_0} \neq \emptyset $ . Let $a_0$ be the $\mathcal {L}$ -rightmost element of $\{0, \dots , f(n_0)\}$ ; this gives us $a_0 \in U_{n_0}$ .

Given $a_i \in U_{n_0}$ , we fix $n_{i+1}$ such that $U_{n_{i+1}} = \{x \in U_{n_0} : x <_{\mathcal {L}} a_i\}$ . This is nonempty by assumption, so $f(n_{i+1})\!\!\downarrow $ with $\{0, \dots , f(n_{i+1})\} \cap U_{n_{i+1}} \neq \emptyset $ . Let $a_{i+1}$ be the $\mathcal {L}$ -rightmost element amongst those $\{0, \dots , f(n_{i+1})\}$ which are to the left of $a_i$ ; this gives us $a_{i+1} \in U_{n_{i+1}}$ .

Now the sequence $(a_i)_{i \in \omega }$ is a descending sequence in $\mathcal {L}$ and is uniformly computable from f and an index for $\mathcal {L}$ .⊣

Proof. Fix a computable ill-founded tree T. We show how to uniformly prune T to a $\mathbf {d}$ -computable, finitely branching tree (with a $\mathbf {d}$ -computable bound on the branches). Then, as $\mathbf {b}$ is PA over $\mathbf {d}$ , it will uniformly compute a path through said tree.

We fix f as in Lemma 4.14 and proceed recursively. First, we define $n_0$ such that $U_{n_0} = \{ m \in \omega : \langle m\rangle $ is extendible in T}. Given $n_0, \dots , n_{k-1}$ , we then define

$$\begin{align*}T_k = \{\sigma \in 2^{k}: (\forall i < k)\, \sigma(i) \le f(n_i)\}\end{align*}$$

and, then, $n_k$ such that

$$\begin{align*}U_{n_k} = \{ m \in \omega : (\exists \sigma \in T_k)\, \sigma\widehat{\phantom{\alpha}} m\ \text{is extendible in}\ T\}.\end{align*}$$

Inductively, using the properties of f, each $T_k$ contains a string extendible in T. Then the tree $\{ \sigma \in T : (\forall i < |\sigma |)\, \sigma (i) \le f(n_i)\}$ is our pruned tree.⊣

Proof. Fix $X \in \Delta ^1_1$ , and suppose $\mathbf {d}$ does not compute X for a contradiction. By the cone avoidance basis theorem [Reference Gandy, Kreisel and Tait17], there is a $\mathbf {b}$ that is PA over $\mathbf {d}$ which does not compute X. But then $\mathbf {b}$ is uniformly high for isomorphism, contradicting Proposition 2.7.⊣

Proof. Given a Harrison order $\mathcal {H}$ , the set of jump hierarchies on $\mathcal {H}$ is a $\Sigma ^1_1$ class. A degree that is uniformly high for isomorphism can compute an element of such a class as long as it is nonempty.⊣

Proof. By Proposition 3.3, there is a degree that is Scott complete and low for $\omega _1^{ck}$ . On the other hand, Harrington (unpublished; see [Reference Le Goh18]) showed that the set of computable linear orders admitting jump hierarchies is $\Sigma ^1_1$ -complete, and so the same argument as in Proposition 2.8(2) shows that if $\mathbf {d}$ is jump complete, then $\mathbf {d}'' \ge _T \mathcal {O}$ .⊣

Notation 4.25. If T is a Laver tree with stem $\tau $ and $\sigma \supseteq \tau $ is on T, then

$$\begin{align*}T^\sigma = \{ \rho \in T: \rho \supseteq \sigma\} \cup \{ \rho : \rho \subseteq \sigma \}. \end{align*}$$

Proof. We construct an increasing sequence of partial functions $(r_{\alpha })_{\alpha < \omega _1}$ . We begin by defining $r_0(\sigma ) = 0$ for $\sigma \in A$ and $r_0(\sigma )\!\!\uparrow $ for $\sigma \not \in A$ .

Having defined $r_\beta $ for $\beta < \alpha $ , we let $r_{<\alpha } = \bigcup _{\beta < \alpha }r_\beta $ . If $r_{<\alpha }(\sigma )\!\!\downarrow $ , then we define $r_\alpha (\sigma ) = r_{<\alpha }(\sigma )$ . If $r_{<\alpha }(\sigma )\!\!\uparrow $ but there are infinitely many n such that $\sigma \widehat {\phantom {\alpha }} n \in T$ and $r_{<\alpha }(\sigma \widehat {\phantom {\alpha }} n)\!\!\downarrow $ , then we define $r_\alpha (\sigma ) = \alpha $ . Otherwise, we leave $r_\alpha (\sigma )$ undefined.

By cardinality considerations, there is $\lambda <\omega _1$ such that $r_\lambda = r_{\lambda +1}$ . We define $r(\sigma ) = r_\lambda (\sigma )$ for $\sigma \in \text {dom}(r_\lambda )$ and $r(\sigma ) = \infty $ for $\sigma \not \in \text {dom}(r_\lambda )$ .

Clearly r is as required.⊣

Proof. Suppose $\dot {r}_{A,T}(\tau ) = \infty $ . By induction on $|\sigma |$ , if $\tau \subseteq \sigma \in T_A$ , then $\dot {r}_{A,T}(\sigma ) = \infty $ . As $T_A \cap A = \emptyset $ , all $\sigma \supseteq \tau $ on $T_A$ have $\dot {r}_{A, T_A}(\sigma ) = \infty $ .

Now suppose $\dot {r}_{A,T}(\tau ) < \infty $ . Then for any $g \in [T_A]$ , $\dot {r}_{A,T}$ is decreasing along g after $\tau $ until it reaches $0$ . For $\sigma \in T_A$ with $\sigma \supseteq \tau $ , by induction on $\dot {r}_{A, T}(\sigma )$ , $\dot {r}_{A, T}(\sigma ) = \dot {r}_{A, T_A}(\sigma )$ .⊣

Proof. Fix $\beta \le \alpha $ and $\sigma $ with $\dot {r}_{A,T}(\sigma ) = \alpha $ . We must show that there is a $\tau $ with $\dot {r}_{A,T}(\tau ) = \beta $ . We construct a sequence $\sigma = \sigma _0 \subset \sigma _1 \subset \cdots $ with $\beta \le \dot {r}_{A,T}(\sigma _{i+1}) < \dot {r}_{A,T}(\sigma _i)$ .

Suppose we have defined $\sigma _i$ . If $\dot {r}_{A,T}(\sigma _i) = \beta $ , we are done. Otherwise, there is an n with $\beta \le \dot {r}_{A,T}(\sigma _i\widehat {\phantom {\alpha }} n) < \dot {r}_{A,T}(\sigma _i)$ . Define $\sigma _{i+1} = \sigma _i\widehat {\phantom {\alpha }} n$ for such an n.

By the well-foundedness of the ordinals, this sequence must terminate in a $\sigma _i$ with $\dot {r}_{A,T}(\sigma _i) = \beta $ .⊣

Proof. This follows by induction on $\dot {r}_{A, T}(\sigma )$ .⊣

Proof. This follows by induction on $\dot {r}_{A, T_0}(\sigma )$ .⊣

Notation 4.33. For a linear order $\mathcal {L}$ with least and greatest elements $0$ and $\infty $ , respectively, let $W(\mathcal {L})$ be the maximal well-founded initial segment of $\mathcal {L}\setminus \{\infty \}$ . We identify $W(\mathcal {L})$ with an initial segment of the ordinals in the standard fashion (such identification being unique), writing, for example, $r(\sigma ) = \alpha $ when $r(\sigma ) \in W(\mathcal {L})$ and $[0, r(\sigma ))_{\mathcal {L}}$ has order type $\alpha $ .

Proof. Suppose not. We construct a sequence of strings $\sigma = \sigma _0 \subset \sigma _1 \subset \cdots $ with $r(\sigma _{i+1}) < r(\sigma _i)$ for a contradiction, maintaining the inductive assumption that $r(\sigma _i) < \dot {r}_{A,T}(\sigma _i)$ . Clearly this holds for $i = 0$ .

Suppose we have defined $\sigma _i$ . As $\dot {r}_{A,T}(\sigma _i)> r(\sigma _i)$ , it is clear that $\dot {r}_{A,T}(\sigma _i) \neq 0$ , and thus $\sigma _i \not \in A$ . As $r(\sigma _i) < \infty $ , there are infinitely many n such that $r(\sigma _i\widehat {\phantom {\alpha }} n) < r(\sigma _i)$ , whereas for almost every n, $\dot {r}_{A,T}(\sigma _i\widehat {\phantom {\alpha }} n) \ge r(\sigma _i)$ . We can therefore define $\sigma _{i+1} = \sigma _i\widehat {\phantom {\alpha }} n$ for an n satisfying both of these.⊣

Proof. We show by induction on $\dot {r}_{A,T}(\sigma )$ that $r(\sigma ) \in W(\mathcal {L})$ with $r(\sigma ) \le \dot {r}_{A,T}(\sigma )$ . For $\dot {r}_{A,T}(\sigma ) = 0$ , this is immediate.

For $0 < \dot {r}_{A,T}(\sigma ) < \infty $ , there are infinitely many n with $\dot {r}_{A,T}(\sigma \widehat {\phantom {\alpha }} n) < \dot {r}_{A,T}(\sigma )$ . By the inductive hypothesis, $r(\sigma \widehat {\phantom {\alpha }} n) \in W(\mathcal {L})$ with $r(\sigma \widehat {\phantom {\alpha }} n) = \dot {r}_{A,T}(\sigma \widehat {\phantom {\alpha }} n) < \dot {r}_{A,T}(\sigma )$ . By the definition of rankings, $r(\sigma ) < \infty $ . Thus these $\sigma \widehat {\phantom {\alpha }} n$ witness that $r(\sigma ) \in W(\mathcal {L})$ with $r(\sigma ) \le \dot {r}_{A,T}(\sigma )$ .

The result then follows by Lemma 4.34.⊣

Proof. Suppose not. We know that for some countable $\lambda $ , $\dot {r}_{A,T}$ is an $(A, \lambda \cup \{\infty \}, T)$ Laver ranking with $\dot {r}_{A,T}(\sigma ) \ge \omega _1^{ck}$ . By Lemma 4.35, for any $(A, \mathcal {L},T)$ Laver ranking r, we have that $r(\sigma ) \in W(\mathcal {L})$ . Thus a computable linear order $\mathcal {K}$ is well founded if and only if there exists a countable linear order $\mathcal {L}$ , an $(A,\mathcal {L},T)$ Laver ranking r, and an embedding $\mathcal {K} \hookrightarrow [0, r(\sigma ))_{\mathcal {L}}$ . However, this is a $\Sigma ^1_1$ definition of well-foundedness.⊣

Proof. We can identify $W(\mathcal {H})$ with $\omega _1^{ck}$ and see that $\dot {r}_{A,T}$ is an $(A, \mathcal {H},T)$ Laver ranking.⊣

Proof of Lemma 4.23. Without loss of generality, we define $h(n) = n+1$ . (We are working in Baire space and thus can compress via pairing without affecting the compactness of the closure.) Fix $(\tau _n)_{n \in \omega }$ an effective listing of $\omega ^{<\omega }$ such that $\tau _i \subset \tau _j$ implies $i < j$ , and thus $\tau _0$ is the empty string $\langle \rangle $ . Assume this listing has the property that for all $\tau $ and b, $\tau \widehat {\phantom {\alpha }} b$ occurs earlier in the listing than $\tau \widehat {\phantom {\alpha }} (b+1)$ .

We perform a construction of length $\omega _1^{ck}$ , enumerating partial functions $k: \omega ^{<\omega } \to \omega ^{<\omega }$ and $\ell _m: (m+1) \to \omega ^m$ for $m \in \omega $ . We will also define hyperarithmetic trees $T_{n, m}$ for some $n \le m$ . We adopt the notation $A_\rho = \{\sigma : \rho \subseteq \Phi ^\sigma \}$ , and for $n> 0$ , $\tau ^-_n$ is the parent of $\tau _n$ .

We will ensure the following properties hold:

• • k is injective, order preserving, and length preserving, and its domain is downwards closed. Furthermore, for any $\tau $ such that $k(\tau )$ is defined, $k(\tau )$ majorizes $\tau $ .

• • If $\tau _n$ majorizes f, then $k(\tau _n)$ is defined, as are $\ell _m(n)$ for all $m \ge n$ .

• • For $n \le m$ , $\ell _m(n)\!\!\downarrow $ if and only if $T_{n,m}$ is defined.

• • For $n \le m$ , if $\ell _m(n)\!\!\downarrow $ , then $\dot {r}_{A,T}(k(\tau _n)) < \infty $ for $T = T_{n,m}$ and $A = A_{\ell _m(n)}$ .

• • For every $n \le m$ such that $T_{n,m}$ is defined, $T_{n, m}$ is a Laver tree with stem $k(\tau _n)$ .

• • If $T_{n, m}$ is defined for $n < m$ , then $T_{n,m-1}$ is defined and $T_{n, m} = (T_{n,m-1})_A$ for $A = A_{\ell _m(n)}$ .

• • For any $n> 0$ , suppose that $\tau _j = \tau _n^-$ . If $k(\tau _n)\!\!\downarrow $ , then $T_{j, n-1}$ is defined and $k(\tau _n) \in T_{j, n-1}$ . If $T_{n,n}$ is defined, then $T_{n,n} = \left (T_{j, n-1}^{k(\tau _n)}\right )_A$ for $A = A_{\ell _n(n)}$ .

This essentially describes the construction. We begin with $k(\langle \rangle ) = \langle \rangle $ , $\ell _0(0) = \langle \rangle $ , and $T_{0, 0} = \omega ^{<\omega }$ .

For $n> 0$ , let $\tau _j = \tau _n^-$ . We wait to see if $k(\tau _j)$ and $T_{j, n-1}$ are ever defined. If this happens, we then define $k(\tau _n)$ to be the nth child of $k(\tau _j)$ on $T_{j, n-1}$ .

For $n \le m$ with $m> 0$ , if $m = n$ , we then let $\tau _j = \tau _n^-$ and let $T = T_{j, n-1}^{k(\tau _n)}$ ; if $m> n$ , we let $T = T_{n, m-1}$ (including when $n = 0$ ). We wait until T is defined and then search for $\rho \in \omega ^m$ such that $\dot {r}_{A, T}(k(\tau _n)) < \infty $ for $A = A_\rho $ ; if we see such a $\rho $ , we define $\ell _m(n) = \rho $ and $T_{n, m} = T_A$ for $A = A_\rho $ .

Most of the stated properties of the construction are immediate.