A $ \prod _{2}^{0}$ SINGLETON OF MINIMAL ARITHMETIC DEGREE

Abstract

In the study of the arithmetic degrees the $\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. However, much less is known about the arithmetic degrees and the role of the $\omega \text {-REA}$ sets in that structure than about the Turing degrees. Indeed, even basic questions such as the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree are open. This paper makes progress on this question by demonstrating that some promising approaches inspired by the analogy with the r.e. sets fail to show that no $\omega \text {-REA}$ set is arithmetically minimal. Finally, it constructs a $\prod ^0_{2}$ singleton of minimal arithmetic degree. Not only is this a result of considerable interest in its own right, constructions of $\prod ^0_{2}$ singletons often pave the way for constructions of $\omega \text {-REA}$ sets with similar properties. Along the way, a number of interesting results relating arithmetic reducibility and rates of growth are established.

1 Introduction

In the study of the arithmetic degrees (the degree structure induced by relative arithmetic definability, $\leq _{\mathbf {a}}$ ) the $\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. This analogy holds both as a matter of structure (e.g., the arithmetic jump is an $\omega \text {-REA}$ operation and the jump is an r.e. operation) and as a way to approach constructions. For instance, just as the r.e. sets allow us to characterize the range of the Turing jump on $\mathscr {D}({\mathbf {0}}')$ (the Turing degrees less than or equal to ${\mathbf {0}}'$ ) via the Shoenfield jump inversion [13] the $\omega \text {-REA}$ sets allow us to similarly identify the range of the arithmetic jump on $\mathscr {D}_{\mathbf {a}}({{\mathbf {0}}_{\mathbf {a}}}')$ with the degrees of the sets $\omega \text {-REA}$ in ${{\mathbf {0}}_{\mathbf {a}}}'$ [14].

However, while the Turing degrees generally and the degrees of the r.e. sets specifically have been extensively studied much less is known about the arithmetic degrees and even less about the role of the $\omega \text {-REA}$ sets in that structure. Even seemingly basic questions remain open. For instance, whether or not there are any $\omega \text {-REA}$ sets of minimal arithmetic degree remains an open question. The analogy between the r.e. sets and the Turing degrees and the $\omega \text {-REA}$ sets suggests that $\omega \text {-REA}$ sets of minimal arithmetic degree shouldn’t exist. However, it is already known that the analogy is imperfect as there is a minimal pair (in the arithmetic degrees) of $\omega \text {-REA}$ sets which join to ${{\mathbf {0}}_{\mathbf {a}}}'$ [14] in contrast to the non-diamond theorem in the r.e. degrees [8].

While we don’t settle the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree in this paper we make what we believe is an important step in that direction by proving the following result (and thereby presenting an alternate solution to Question 62 in [2] by providing a $\prod ^0_{2}$ singleton not arithmetically equivalent to any ${\mathbf {0}}^{(\alpha )}$ ).

Corollary 4.3. There is a $\prod ^0_{2}$ singleton of minimal arithmetic degree.

While the degrees of $\omega \text {-REA}$ sets are properly contained in the degrees of singletons, results about $\prod ^0_{2}$ singletons have often paved the way for corresponding results about $\omega \text {-REA}$ sets, e.g., Harrington’s construction of an arithmetically low $\prod ^0_{2}$ singleton [5] or arithmetically incomparable $\prod ^0_{2}$ singletons [4] both ¹ foreshadowed related constructions of $ \omega \text {-REA}$ sets with those properties [14]. As the approach taken in this paper draws heavily on the ideas in [5] we hypothesize, contra the analogy with r.e. sets, that there is an arithmetically minimal $\omega \text {-REA}$ set and hope the construction here points to a way to build such a set.

2 Background

There is a fair amount of notation required for the results in this paper; however, almost all of it is standard. Readers familiar with standard notation may wish to skip most of the subsections below and return to them only as needed for reference. However, Section 2.5 is worth looking at for all readers as it contains some slightly less common definitions and results.

2.1 Computations, strings, and degrees

We largely adopt standard notation from [9] which we briefly review. Set difference is denoted by $X \setminus Y$ , powerset by $\mathcal {P}\left (X\right )$ , the e-th set r.e. in X is $W^{X}_{e}$ , and the e-th computable functional applied to X by $\Phi _{i}\left (X\right )$ . We denote convergence and divergence by $\Phi _{i}\left (X;y\right )\downarrow $ and $\Phi _{i}\left (X;y\right )\uparrow $ respectively. Convergence in s-steps is denoted by $\Phi _{i}\left (X;y\right )\downarrow _s \iff \Phi _{i,s}\left (X;y\right )\downarrow $ and its negation by .

We write elements of $2^{<\omega }$ and $\omega ^{<\omega }$ (referred to as strings) like $\langle {x_0, x_1, \ldots , x_{n-1}}\rangle $ with ${\langle \rangle }$ denoting the empty string. For elements in $2^{<\omega }, \omega ^{<\omega }, \omega ^{\omega }, 2^{\omega }$ (identifying sets with their characteristic functions) we denote that $\sigma $ is (non-strictly) extended by $\tau $ by $\sigma \prec \tau $ , incompatibility by $\mid $ , compatibility by ${\,\not |\,}$ and use $<_L$ to denote the lexicographic ordering. For elements of $2^{<\omega }, \omega ^{<\omega }$ we denote the length of $\sigma $ by $\lvert \sigma \rvert $ and write $\sigma ^{-}$ to indicate the immediate predecessor of $\sigma $ under $\prec $ and write $\alpha \widehat {\phantom {x}} \beta $ to denote $\alpha $ concatenated with $\beta $ and write ${\langle i\rangle }^n$ to denote $\langle i\rangle $ concatenated with itself $n \leq \omega $ times. We let $\Phi _{e}\left (\sigma \right )$ denote the longest string $\tau , \lvert \tau \rvert \leq \lvert \sigma \rvert $ such that $\tau (n) = \Phi _{e,\lvert \sigma \rvert }\left (\sigma ;n\right )\downarrow $ and relativize to define $\Phi _{e}\left (\sigma \oplus X\right )$ in the obvious manner.

We let $\left \ulcorner \alpha \right \urcorner $ denote the canonical bijection of $\omega ^{< \omega }$ with $\omega $ where $\alpha \prec \beta \implies \left \ulcorner \alpha \right \urcorner < \left \ulcorner \beta \right \urcorner $ , $i < j \implies \left \ulcorner \alpha \widehat {\phantom {x}}\langle i\rangle \right \urcorner < \left \ulcorner \alpha \widehat {\phantom {x}}\langle j\rangle \right \urcorner $ , and $\left \ulcorner {\langle \rangle }\right \urcorner = 0$ . We regularly gloss over the distinction between strings and their codes as that between sets and their characteristic functions. We let $\langle x,y\rangle = \frac {1}{2}(x+y)(x+y+1)+y$ (this is a bijection of $\omega ^2$ with $\omega $ ) and we let ${\left ({\langle a,b\rangle }\right )_{0}} = a$ and ${\left ({\langle a,b\rangle }\right )_{1}} = b$ . We define $A \oplus B$ , $\oplus _{n \in S} X_n$ , $ {X}^{\left [n\right ]}$ , and ${X}^{\left [< n\right ]}$ standardly and extend these operations to strings in the obvious fashion (preserving the identification of $2^{\omega }$ with ${\mathcal {P}}\left (\omega \right )$ ).

A set X is arithmetic in Y (written $X \leq _{\mathbf {a}} Y$ ) just if there is a formula in the language of arithmetic (with a designated set constant) $\psi _e$ such that $Y \models \psi _e(z) \iff z \in X$ (see [9] for details). In this case we write $\psi _e(Y) = X$ . Recall that an equivalent characterization of arithmetic reducibility is given by $X \leq _{\mathbf {a}} Y \iff \left (\exists n \right )\!\left (X \leq _{\mathbf {T}} {{Y}^{(n)}} \right )$ . We denote the arithmetic degree of $\emptyset $ by ${\mathbf {0}}_{\mathbf {a}}$ and, as the arithmetic jump of X is defined to be $X^{\omega }$ , that of ${\mathbf {0}}^{(\omega )}$ by ${{\mathbf {0}}_{\mathbf {a}}}'$ . An arithmetic degree is minimal just if it has exactly one predecessor under $\leq _{\mathbf {a}}$ .

2.2 Trees and forcing

A tree T is a $\prec $ closed set of strings and $[T]$ is the set of paths through T. We define ${T^{\langle \infty \rangle }} = {\left \{{\sigma \in T}\mid {\left (\exists f \in [T] \right )\!\left (\sigma \prec f \right )}\right \}}$ and call a tree pruned if $T = {T^{\langle \infty \rangle }}$ . A node $\sigma \in T$ is terminal if $\sigma $ has no extensions in T, branching if it has more than one immediate extension, $\omega $ -branching if it has infinitely many immediate extensions and the root of T if it is the unique $\prec $ least branching node in T. A tree is $\omega $ -branching if every branching node is $\omega $ -branching. A subtree of T is a tree $\hat {T} \subset T$ .

We abuse notation and write $T{{\restriction _{l}}}$ for ${\left \{{\sigma \in T}\mid {\lvert \sigma \rvert \leq l}\right \}}$ . We write $\sigma {\mathbin {\ast }} T$ for ${\left \{{\sigma \widehat {\phantom {x}}\tau }\mid {\tau \in T}\right \}}$ , for $ {\left \{{\tau }\mid {\sigma \widehat {\phantom {x}}\tau \in T}\right \}}$ (with the unique element of ) and called the subtree of T above $\sigma $ . We recall that the standard topology on $\omega ^{\omega }$ is induced by basic open sets $[\sigma ] = {\left \{f\mid f \succ \sigma \right \}}$ for $\sigma \in \omega ^{<\omega }$ and likewise for $2^{\omega }$ . A set is perfect if it contains no isolated points and we call a tree T perfect if $[T]$ is perfect.

When working with unpruned trees in $\omega ^{<\omega }$ we can’t identify trees ( $\prec $ closed sets) with $\prec $ respecting functions on strings as we’ll do over ² $2^{<\omega }$ . We use the term f-tree for a $\prec , <_L$ respecting partial function $T{\mathop {:}{\omega ^{<\omega }}\mapsto {\omega ^{<\omega }}}$ with a $\prec $ closed domain that preserves longest common initial segments, i.e., $T(\sigma \widehat {\phantom {x}}\langle n\rangle )(\left \lvert T(\sigma )\right \rvert )$ is strictly monotonic in n (on its domain). A f-tree $\hat {T}$ is a subtree of an f-tree T if $\mathrm {rng} \hat {T} \subset \mathrm {rng} T$ . An f-tree T is branching if every non-terminal element in $\mathrm {dom} T$ has multiple immediate successors, (weakly) $ \omega $ -branching if every non-terminal element in $\mathrm {dom} T$ has infinitely many immediate successors, and $\omega $ -branching if whenever $\sigma \in \mathrm {dom} T$ is non-terminal than $\sigma \widehat {\phantom {x}}\langle n\rangle \in \mathrm {dom} T$ for all n. Unless otherwise stated, we assume every f-tree is a branching f-tree and generalize the notions of being pruned, ${T^{\langle \infty \rangle }}$ , , $\sigma {\mathbin {\ast }} T$ , and $T^{\left \langle \tau \right \rangle }$ to f-trees in the obvious way.

We write $\sigma \Vdash \psi $ to denote forcing over $2^{<\omega }$ or $\omega ^{<\omega }$ and $\sigma \Vdash _T \psi $ to denote local forcing on the (pruned) tree T (see [9] for details). A set/function is $\kappa $ -generic iff it forces either $\psi $ or $\lnot \psi $ for every $\Sigma ^1_\lambda $ sentence with $\lambda < 1 + \kappa $ and weakly $\kappa $ -generic (note the application at limit ordinals) iff it meets every dense $\Sigma ^1_\lambda $ set of strings. Recall that a set of strings W is dense if every string is extended by an element of W.

2.3 $ \prod ^0_{n}$ classes and $\omega $ -REA sets

A $\prod ^0_{n}$ set class is the set of elements in ${\mathcal {P}}\left (\omega \right )$ (identified with $2^{\omega }$ ) that satisfy some $\prod ^0_{n}$ formula with a free set variable. A $\prod ^0_{n}$ function class is defined likewise for elements in $\omega ^{\omega }$ . We will use the term $\prod ^0_{n}$ class without further specification to refer to a $\prod ^0_{n}$ set class. We note that if $n> 0$ then ${\mathscr {F} \subset \omega ^{\omega }}$ is a $\prod ^0_{n}$ function class iff there is a computable relation R and a quantifier block $\forall x \ldots Qy$ containing n alternations such that $f \in \mathscr {F}$ iff $\forall x \ldots Qy R(f{{\restriction _{y}}}, x, \ldots , y)$ (and likewise for a $\prod ^0_{n}$ set class).

An immediate consequence of this fact is that $\prod ^0_{1}$ classes can be identified with the set of paths through a computable tree. Interestingly, up to degree, $\prod ^0_{2}$ classes and $\prod ^0_{1}$ function classes are equivalent in the following sense.

Lemma 2.1. Every $\prod ^0_{1}$ function class is homeomorphic with a $\prod ^0_{2}$ class via a computable (hence degree preserving) homeomorphism and vice versa. This holds with all possible uniformity.

Proof For the first claim, it is enough to note that there is a computable homeomorphism of $\omega ^{\omega }$ with $2^{\omega } \setminus {\left \{{\sigma \widehat {\phantom {x}}\langle 1\rangle ^\omega }\mid {\sigma \in 2^{<\omega }}\right \}}$ given by setting $\Gamma (\langle \rangle ) = \langle \rangle $ and $\Gamma (\sigma \widehat {\phantom {x}}\langle i\rangle ) = \Gamma (\sigma )\widehat {\phantom {x}}\langle 1\rangle ^i\widehat {\phantom {x}}\langle 0\rangle $ .

The other direction is slightly more tricky. Given a $\prod ^0_{2}$ class $\mathscr {C}$ such that $X \in \mathscr {C} \iff \left (\forall z\right )\!\left (\exists y\right )\!R(X{{\restriction _{y}}}, z, y)$ define $\Gamma (X)(2z)$ to be the least y such that $ R(X{{\restriction _{y}}}, z, y)$ and $\Gamma (X)(2z+1) = X(z)$ . We now define a computable tree $T \subset \omega ^{<\omega }$ with $\mathscr {F} = [T]$ . Given $\sigma \in \omega ^{<\omega }$ with $\lvert \sigma \rvert \equiv 0 \ \ \pmod {2}$ let $\sigma = \tau \oplus \epsilon $ and place $\sigma \in T$ iff $\left (\forall l < \lvert \tau \rvert \right )\!R(\epsilon {{\restriction _{l}}}, \tau (l), l)$ . If $\lvert \sigma \rvert \equiv 1 \ \ \pmod {2}$ then place $\sigma \in T$ iff either $\sigma \widehat {\phantom {x}}\langle 0\rangle \in T$ or $ \sigma \widehat {\phantom {x}}\langle 1\rangle \in T$ . Clearly, T is a computable tree and $\Gamma $ is a computable continuous bijection of $\mathscr {C}$ with $[T]$ with a continuous inverse on $[T]$ .

As the name would suggest, a $\prod ^0_{n}$ singleton is a set/function that’s the only element in a $\prod ^0_{n}$ class. Recall that every $\omega \text {-REA}$ set is a $\prod ^0_{2}$ singleton but not vice-versa. For the interested reader unfamiliar with the $\omega \text {-REA}$ sets we refer them to [6] but as these sets will primarily play a motivating role in this paper it’s enough for the reader to understand that they are the result of effectively iterating the operation $X \mapsto X \oplus W^(X)_{i}$ $\omega $ many times (so the ( $n +1$ )-st component must be uniformly r.e. in the first n components).

2.4 Ordinal notations

We will generalize our main theorem past $\omega $ to arbitrary ordinal notations. The reader interested in only claims about arithmetic reductions (such as the headline corollary) can assume that notations only range over $\omega \cup {\left \{\omega \right \}}$ as the lemmas required for larger ordinal notations have been exiled to Appendix B. However, some notational conventions, inspired by [12], are still necessary in either case.

Kleene’s set of ordinal notations is $\mathcal {O}$ with ordering $<_{\mathcal {O}}$ . The height of $\kappa $ is $\left \lVert \kappa \right \rVert _{\mathcal {O}}$ . $\overrightarrow {\mathcal {O}}$ is the set of limit notations, ${}^{+}{\mathcal {O}}$ the set of successor notations. For $ \lambda $ a limit notation we denote the n-th element of the effectively given increasing sequence defining $\lambda $ by ${\left \{ \lambda \right \}}^{\mathcal {O}}(n)$ . We elide the differences between finite notations and elements of $ \omega $ as well as that between $\omega $ and some canonical notation for it.

2.5 Rates of growth

We say that $g \in \omega ^{\omega }$ is C-escaping if g isn’t dominated by any $f \in C$ , X-escaping for $X \subset \omega $ if it escapes from ${\left \{{f}\mid {f \equiv _{\mathbf {T}} X}\right \}}$ and arithmetically escaping if it escapes from the set of arithmetic functions. Recall that f majorizes (dominates) g iff $f(x) \geq g(x)$ for all x (all but finitely many x). Following [9] we draw on the fact that a Turing degree is hyperimmune just if it contains a $\mathbf {0}$ -escaping function and say that an arithmetic degree is arithmetically hyperimmune just if it contains an arithmetically escaping function. As there is no notion of a set being arithmetically hyperimmune to cause confusion, we call X arithmetically hyperimmune just if it is of arithmetically hyperimmune degree.

It’s a well-known fact that if A is an r.e. set then A is uniformly computable in any g majorizing $m_A(x) = \min {\left \{{s}\mid {A{{\restriction _{x}}} = A_s{{\restriction _{x}}}}\right \}}$ . Thus, the degree of an r.e. set can be characterized in terms of the rate of growth of a function computable in that degree. However, it’s slightly less well-known that this isn’t just true of r.e. sets but of all $\prod ^0_{2}$ singletons.

Lemma 2.2. If f is a $\prod ^0_{1}$ function singleton then every g majorizing f uniformly computes f. If X is a $\prod ^0_{2}$ singleton then there is some $f \equiv _{\mathbf {T}} X$ such that every g majorizing f uniformly computes X. Moreover, if X isn’t arithmetic then it is arithmetically hyperimmune.

Proof By Lemma 2.1 the second and third claims follow from the first. Now suppose that f is the unique path through $[T]$ and that f is majorized by some arithmetic function g. Now let $ \hat {T}$ consist of all $\sigma \in T$ majorized by g (on $\mathrm {dom} \sigma $ ). To compute $f{{\restriction _{l}}}$ from g, search for some $\sigma , k$ such that $\lvert \sigma \rvert = l$ and $\left (\forall \tau \in \hat {T}\right )\!\left (\lvert \tau \rvert = k \implies \tau \succ \sigma \right )$ . As $\hat {T}$ is finitely branching and $[\hat {T}] = {\left \{{f}\right \}}$ König’s lemma guarantees that such a k exists.

3 Fast growing functions and minimality

Before we prove Corollary 4.3 we first consider a seemingly promising, but ultimately futile, approach to proving that no $\omega \text {-REA}$ set can be of minimal arithmetic degree. This failure provides an interesting result about the arithmetic degrees in its own right and illustrates both some of the similarities and differences between the role of the r.e. sets in the Turing degrees and the $\omega \text {-REA}$ sets in the arithmetic degrees. As an added bonus it will preview some issues that will arise later and remind readers of the standard construction of a minimal arithmetic degree [11].

3.1 Motivation

One of the most powerful methods to prove results about r.e. sets is to threaten to code one set into another (see, e.g., Sack’s proof of the Density theorem [10]). However, translating this approach to the $\omega \text {-REA}$ sets under $\leq _{\mathbf {a}}$ faces two serious barriers. First, the fact we can only place elements into the ( $n + 1$ )-th component of an $\omega \text {-REA}$ set if they are enumerated in an r.e. fashion from the n-th component. This makes it very difficult to threaten to code X into Y without following through. Second, the coding would somehow have to control/react to facts about arbitrarily many jumps of Y.

One potential way to avoid these difficulties with coding is to ignore the details about what elements enter a set and just focus on rate of growth/domination. Every non-arithmetic $\prod ^0_{2}$ singleton (and hence $ \omega \text {-REA}$ set) computes an arithmetically escaping function and we know that non-domination strength is often a good way to build sets of smaller degree, e.g., Kurtz’s proof that every hyperimmune degree computes a weak $1$ -generic [7].

Also, [1] showed that every ${\mathbf {0}}'$ -escaping function computes a weak $2$ -generic (and is thus not of minimal Turing degree). While further non-domination strength won’t ensure we can compute a weak $3$ -generic an examination of the proof of this claim [1] suggests that this is more about the ease of avoiding genericity not necessarily a limitation on the computational power of non-domination strength. This leaves open the possibility that arithmetically escaping functions compute $\omega $ -generics under some local forcing ³ or other forcing notion. Besides, it simply seems intuitively unlikely that a minimal arithmetic degree, a degree which should have the very least amount of computational power, could include an arithmetically escaping function.

This possibility is rendered more plausible by the fact that the standard construction of a minimal arithmetic degree [11] naturally produces a set which doesn’t compute any arithmetically escaping functions.

Proposition 3.1. Suppose that for every n there is an arithmetic tree $T_n \subset 2^{<\omega }$ such that $X \in [T_n]$ and every path through $T_n$ is n-generic with respect to $\Vdash _{T_n}$ then X is arithmetically hyperimmune-free.

Proof Suppose $f \in \omega ^{\omega }$ and $X \models \psi (x,y) \iff f(x) = y$ for some $\Sigma ^1_n$ sentence $\psi $ . We now construct an arithmetic g majorizing f as follows.

Let $m = n + 2$ and consider the sentence that asserts $\psi (x,y)$ defines a total function

$$\begin{align*}\varphi \overset{{\rm def}}{=} \left(\forall x\right)\!\left(\exists y\right)\!\left(\psi(x,y)\right) \land \left(\forall x\right)\!\left(\forall y\right)\!\left(\forall y'\right)\!\left(\psi(x,y) \land \psi(x,y') \implies y = y'\right). \end{align*}$$

By assumption, $X \models \varphi $ and therefore there is some $\sigma \prec X, \sigma \in T_m$ with $\sigma \Vdash _{T_m} \varphi $ . Let $\hat {T}$ be the strings in $T_m$ compatible with $\sigma $ .

We compute $g(x)$ by searching for a finite set of pairs $y_i, \tau _i$ with $\tau _i \Vdash _{T_m} \psi (x,y_i)$ such that every path through $[\hat {T}]$ extends some $\tau _i$ . Since all $Y \in [\hat {T}]$ are m locally generic every such $Y \models \varphi $ . Thus, for all $Y \in [\hat {T}]$ there are $x, y$ such that $Y \Vdash _{T_m} \psi (x,y)$ . Thus, there is an set of pairs $y_i, \tau _i$ as described and the $ \tau _i$ may be taken to be incompatible. As $T_m$ is finitely branching by König’s lemma, there can only be finitely many elements in $\hat {T}$ extending no $\tau _i$ ensuring that we can always find a finite collection of such pairs. Now let $g(x)$ be larger than all the $y_i$ in our set of pairs.

If $Y \in [\hat {T}]$ then g majorizes the function $f_Y$ where $f_Y(x) = y \iff Y \models \psi (x,y)$ and as $X \in [\hat {T}]$ it follows that g majorizes f. As $T_m \geq _{\mathbf {T}} \hat {T}$ is arithmetic it follows that g is an arithmetic function majorizing f.

The trees $T_n$ in the above proposition track the trees used in the construction of a minimal arithmetic degree. Thus, the usual construction of a minimal arithmetic degree produces an arithmetically hyperimmune-free degree.

3.2 An arithmetically hyperimmune minimal degree

Unfortunately, despite the reasons to conjecture that arithmetically hyperimmune functions couldn’t be of minimal arithmetic degree, it turns out not to be the case. Indeed, it turns out that any amount of non-domination strength is compatible with being of minimal arithmetic degree. This contrasts with the situation in the Turing degrees where no ${\mathbf {0}}'$ escaping function can be of minimal Turing degree.

Theorem 3.2. There is a pruned perfect $\omega $ -branching f-tree $T \leq _{\mathbf {T}} {\mathbf {0}}^{(\omega )}$ such that every $f \in [T]$ is of minimal arithmetic degree.

We will break the proof of this theorem up into a sequence of lemmas. However, before we do that let’s first verify that the theorem actually provides the desired (arguably undesired) arithmetically minimal, arithmetically hyperimmune degree.

Corollary 3.3. There is an arithmetically minimal degree $\mathbf {a}$ that is of arithmetically hyperimmune degree. Indeed, for any countable $C \subset \omega ^{\omega }$ there is a minimal arithmetic degree $\mathbf {a}$ containing a C escaping member.

Proof The first claim follows from the second by taking C to be the collection of arithmetic $f \in \omega ^{\omega }$ . For the second claim, fix a function h dominating every element of C and then build a path f through the tree in Theorem 3.2 by always extending $\sigma $ to $\sigma \widehat {\phantom {x}}\langle m\rangle $ such that $T(\sigma \widehat {\phantom {x}}\langle m\rangle )\downarrow $ and escapes h one more time.

Recall from the construction of a minimal Turing degree that

Definition 3.4. The strings $\tau _0, \tau _1$ e-split if $\Phi _{e}\left (\tau _0\right ) \mid \Phi _{e}\left (\tau _1\right )$

and that in that construction we built a sequence of computable trees $T_e \subset 2^{<\omega }$ with $T_{e+1}$ a subtree of $T_e$ such that one of the following obtains (here we identify pruned, perfect binary trees and the corresponding f-trees).

1. 1. (Partiality) $\left (\forall f \in [T_e]\right )\!\left (\Phi _{e}\left (f\right )\uparrow \right ).$

2. 2. (Non e-splitting) For all $\tau , \tau ' \in T_e$ , $\tau , \tau '$ don’t e-split.

3. 3. (e-splitting) For all $\sigma \in T_e$ , $T_e(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ and $T_e(\sigma \widehat {\phantom {x}}\langle 1\rangle )$ e-split.

We then build $f \in \bigcap_{e \in \omega } [T_e]$ ensuring that either $\Phi _{e}\left (f\right )$ is partial (1), computable (2), or computes f (3). We adopt the same general approach, but, to handle arithmetic reductions rather than Turing reductions we’ll replace the notion of e-splitting with an analogue based on local forcing (as in the construction of a minimal arithmetic degree from [11]). We’ll then adjust this construction to allow us to build $\omega $ -branching trees. First, however, we introduce notation to represent an analogue of partial application of a functional for forcing.

Definition 3.5. Given a notion of forcing $\Vdash $ a condition $\sigma $ and a sentence $\psi $ with a single free (number) variable let ${\psi ^{\Vdash }\left (\sigma \right )}$ denote the longest string $\tau \in 2^{<\omega }$ such that $n \in \mathrm {dom} \tau $ implies $\sigma \Vdash \psi (n) \land \tau (n) = 1$ or $\sigma \Vdash \lnot \psi (n) \land \tau (n) = 0$ . We extend this in the obvious way to infinite paths.

In other words, $\psi ^{\Vdash }(\sigma )$ represents the initial segment of $\psi (A)$ whose values have been determined for $A \succ \sigma $ (assuming A is sufficiently generic).

Definition 3.6. If $\psi _e$ is a $\Sigma ^1_n$ or $\prod ^0_{n}$ formula with a single free variable then:

1. 1. A pair of strings $\tau , \tau '$ e-fsplits on T just if ${\psi _{e}^{\Vdash _{T}}\left (\tau \right )} \mid {\psi _{e}^{\Vdash _{T}}\left (\tau \right )}$ .

2. 2. A pruned f-tree T is totally non-e-fsplitting if there are no $\tau , \tau '$ in the image of T that e-fsplit.

3. 3. A pruned f-tree is totally e-fsplitting if whenever $\sigma \in \omega ^{<\omega }, n \neq n'$ then $T(\sigma \widehat {\phantom {x}}\langle n\rangle )$ , $T(\sigma \widehat {\phantom {x}}\langle n'\rangle )$ e-fsplits whenever both are defined.

4. 4. A pruned f-tree T is e-deciding if it is either totally non-e-fsplitting or totally e-fsplitting and every path through T is n generic with respect to $\Vdash _T$ .

Lemma 3.7. If $T:\omega ^{<\omega } \mapsto \omega ^{<\omega }$ is a pruned e-deciding f-tree, $f \in [T]$ , and ${X = \psi _e(f)}$ then X is either arithmetic in T or f is arithmetic in $X \oplus T$ .

Proof As every path through T is n-generic with respect to $\Vdash _{T}$ if $f \Vdash _{T} \psi _e(x)$ then $x \in \psi _e(f)$ . Hence, if T is totally non-e-fsplitting then (the characteristic function for) X is the union of ${\psi _{e}^{\Vdash _{T}}\left (\tau \right )}$ for $\tau $ in the image of T. If T is totally e-fsplitting and $X = \psi _e(f)$ then f is the union of $\tau $ in the image of T with $ {\psi _{e}^{\Vdash _{T}}\left (\tau \right )}$ compatible with X. As forcing for arithmetic sentences is arithmetic the conclusion follows.

We now prove the key lemma we’ll use to establish Theorem 3.2.

Lemma 3.8. Given e and a pruned $\omega $ -branching perfect f-tree $T\!: \omega ^{<\omega } \mapsto \omega ^{<\omega }$ there is a pruned $\omega $ -branching perfect e-deciding subtree $\hat {T}$ uniformly arithmetic in T.

Proof We first observe that given a pruned perfect f-tree T there is a pruned perfect subtree $\tilde {T}$ where every path through $\tilde {T}$ is n-generic with respect to $\Vdash _{T}$ . Moreover, we note that since $\sigma \Vdash _{T} \psi \implies \sigma \Vdash _{\tilde {T}} \psi $ every path is also n-generic with respect to $\tilde {T}$ and if T was either totally non-e-fsplitting or totally e-fsplitting and $\psi _e \in \Sigma ^1_n \cup \prod ^0_{n}$ than $\tilde {T}$ is e-deciding. As we can take $\tilde {T}$ to be arithmetic in T, it is enough to demonstrate that there is pruned $\omega $ -branching perfect subtree of $ T$ , $\hat {T}$ arithmetic in T that is either totally non-e-fsplitting or totally e-fsplitting.

We consider two cases.

Case 1: Suppose some $\sigma \in \mathrm {rng} T$ isn’t extended by any e-fsplit $\tau _0, \tau _1 \in \mathrm {rng} T$ . Let $\hat {T} = T^{\left \langle \sigma \right \rangle }$ , the subtree of T above $\sigma $ . Clearly, $\hat {T}$ is totally non-e-fsplitting.

Case 2: Suppose Case 1 doesn’t hold. We now seek to build a perfect pruned $\omega $ -branching totally e-fsplitting subtree $\hat {T}$ of T. Absent the need to be $ \omega $ branching we could simply search for an e-fsplitting pair extending $\hat {T}(\sigma )$ on T to define $\hat {T}(\sigma \widehat {\phantom {x}}\langle 0\rangle ), \hat {T}(\sigma \widehat {\phantom {x}}\langle 1\rangle )$ . However, if we then later tried to define $ \hat {T}(\sigma \widehat {\phantom {x}}\langle i\rangle )$ we might be unable to choose a value for $\hat {T}(\sigma \widehat {\phantom {x}}\langle i\rangle )$ which e-fsplits with $\hat {T}(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ . We could further extend $T(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ to find a splitting but we risk having to do this infinitely often. Instead, we make sure that when we pick a value for $\hat {T}(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ it e-fsplits with extensions of infinitely many other strings of the form $ \hat {T}(\sigma )\widehat {\phantom {x}}\langle i\rangle $ .

To define $\hat {T}(\sigma \widehat {\phantom {x}}\langle 1\rangle )$ we essentially repeat the above process and choose one of the infinitely many extensions which e-fsplits with $\hat {T}(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ that can be extended to e-fsplit with (extensions of) an infinite subset of those allowed extensions. The seemingly daunting details spelled out below are just the bookkeeping needed to allow us to repeatedly select a value for $\hat {T}(\sigma \widehat {\phantom {x}}\langle i\rangle )$ and ensure that we have an infinite set of options that e-fsplit with $\hat {T}(\sigma \widehat {\phantom {x}}\langle i'\rangle ), i' \leq i$ to use for $\hat {T}(\sigma \widehat {\phantom {x}}\langle i'\rangle ), i'> i$ (and to do this for every $\sigma $ ).

We build an f-tree $V\!: \omega ^{<\omega } \mapsto \omega ^{<\omega }$ and define $\hat {T} = T \mathbin {\circ } V$ . Our construction of V will proceed in stages. At stage s we will define $V(\sigma )$ where $s = \left \ulcorner \sigma \right \urcorner $ (remember, that $\sigma \prec \tau \implies \left \ulcorner \sigma \right \urcorner < \left \ulcorner \tau \right \urcorner $ ). At stage $0 = \left \ulcorner \langle \rangle \right \urcorner $ we begin by defining $V(\langle \rangle ) = \langle \rangle $ . Note that, since $i < j \implies \left \ulcorner \sigma \widehat {\phantom {x}}\langle i\rangle \right \urcorner < \left \ulcorner \sigma \widehat {\phantom {x}}\langle j\rangle \right \urcorner $ if $\left \ulcorner \sigma \widehat {\phantom {x}}\langle n\rangle \right \urcorner = s$ then we’ve already defined $V(\sigma \widehat {\phantom {x}}\langle m\rangle ), m < n$ .

Once we’ve defined $V(\sigma )$ we maintain a set $S^{\sigma }_s$ of extensions of $\sigma $ representing possible initial segments of $V(\sigma \widehat {\phantom {x}}\langle i\rangle )$ for $V(\sigma \widehat {\phantom {x}}\langle i\rangle )$ not yet defined at s. To ensure that $\hat {T}$ remains $\omega $ -branching we ensure that all elements in $S^{\sigma }_s$ extend incompatible immediate extensions of $\sigma $ . Unless otherwise specified, $S^{\sigma }_{s+1} = S^{\sigma }_s$ .

Suppose that at stage s we are working to define $V(\sigma \widehat {\phantom {x}}\langle n\rangle )$ , i.e., $\left \ulcorner \sigma \widehat {\phantom {x}}\langle n\rangle \right \urcorner = s$ . Let $\tau $ be the lexicographically least element of $S^{\sigma }_s$ and $U = S^{\sigma }_s \setminus {\left \{\tau \right \}}$ . Let $\tau _0, \tau _1 \succ \tau $ be such that $T(\tau _0), T(\tau _1)$ e-fsplit. Such strings must exist or Case 1 would have obtained. Let $U_i, i \in {\left \{0,1\right \}}$ be the set of $\prec $ minimal $\upsilon $ extending some element in U such that $T(\upsilon )$ and $T(\tau _i)$ e-fsplit. Let $i \in {\left \{0,1\right \}}$ by the least such that $U_i$ is infinite. Since the ‘images’ of $T(\tau _0)$ and $T(\tau _1)$ under $\psi _e$ disagree such an i must exist.

Set $V(\sigma \widehat {\phantom {x}}\langle n\rangle ) = \tau _i$ and $S^{\sigma }_{s+1} = U_i$ , initialize $S^{\sigma \widehat {\phantom {x}}\langle n\rangle }$ to ${\left \{{\tau _i\widehat {\phantom {x}}\langle m\rangle }\mid {m \in \omega }\right \}}$ , and proceed to stage $s + 1$ . This completes our definition of V and clearly defines a pruned f-tree $\hat {T} = T \circ V$ arithmetically in T.

We claim that $\hat {T}$ is a totally e-fsplitting perfect $\omega $ -branching subtree of T. Our definition of $S^{\sigma }_s$ ensures that $\hat {T}$ is $\omega $ -branching and that $\hat {T}$ is perfect. Since whenever we define $V(\sigma \widehat {\phantom {x}}\langle n\rangle )$ we limit $T(V(\sigma \widehat {\phantom {x}}\langle n'\rangle )), n'> n$ to extensions of strings which e-fsplit with $T(V(\sigma \widehat {\phantom {x}}\langle n\rangle ))$ it follows that $\hat {T}$ is totally e-fsplitting.

As these cases are exhaustive, this suffices to complete the proof.

We can now complete the proof of the theorem.

Theorem 3.2. There is a pruned perfect $\omega $ -branching f-tree $T \leq _{\mathbf {T}} {\mathbf {0}}^{(\omega )}$ such that every $f \in [T]$ is of minimal arithmetic degree.

Proof Iteratively applying Lemma 3.8 would immediately suffice to produce a minimal arithmetic degree. However, we wish to end up with an $\omega $ -branching tree of such degrees. To that end, we set $ T_{0}$ to be the identity function on $\omega ^{<\omega }$ and inductively define $T_{n+1}{{\restriction _{n}}} = T_n{{\restriction _{n}}}$ (i.e., equal when applied to strings of length at most n) and if $\lvert \sigma \rvert = n$ and $T^{\sigma }_{n+1}$ is the n -deciding subtree of $T_n^{\left \langle T_n(\sigma ) \right \rangle }$ produced by Lemma 3.8 then $T_{n+1}(\sigma \widehat {\phantom {x}}\tau ) = T_n(\sigma ) {\mathbin {\ast }} T^{\sigma }_{n+1}$ .

Now let T be the limit of this process, i.e., $T(\sigma ) = T_{\lvert \sigma \rvert }(\sigma )$ . T is a perfect pruned $\omega $ -branching f-tree. Since we defined $T_{n+1}$ in a uniform arithmetic fashion from $T_n$ we have $T \leq _{\mathbf {T}} {\mathbf {0}}^{(\omega )}$ . Finally, if $f \in [T]$ and $X = \psi _e(f)$ and $\sigma = f{{\restriction _{e+1}}}$ then and thus, as $T^{\sigma }_{e+1}$ is arithmetic, by Lemma 3.7 either X is arithmetic or is arithmetic in X.

3.3 Fast growth and definability

In retrospect, perhaps we shouldn’t be too surprised by the result in the last section. After all, there are minimal Turing degrees of hyperimmune degree (e.g., any minimal degree below ${\mathbf {0}}'$ ). And maybe we don’t have to completely give up the idea of using non-domination strength to show that no $\omega \text {-REA}$ set can be of minimal arithmetic degree. While, surprisingly, unlike a true $1$ -generic, a weak $1$ -generic can be of minimal Turing degree (a minimal degree below ${\mathbf {0}}'$ can’t be hyperimmune-free and thus computes a weak $1$ -generic which, by virtue of being non-computable, must be of that very minimal degree), we were still able to use non-domination strength to demonstrate the non-existence of minimal r.e. degrees by identifying a property (weak $1$ -genericity) that enough non-domination strength would let us satisfy (compute) but which couldn’t hold of any set of r.e. degree. Perhaps we could similarly show that every arithmetically escaping function computes a non-arithmetic set with a property that guarantees it’s not of $\omega \text {-REA}$ degree.

What might play the role of this property in the arithmetic degrees? The result in [1] tells us that it can’t be $\omega $ -genericity but the following lemma suggests a different way of generalizing the idea that more non-domination strength should somehow allow us to compute less definable sets.

Lemma 3.9. If $X \subset \omega $ is n-generic with respect to local forcing on some perfect tree (or weakly n-generic) then X isn’t a $\prod ^0_{n}$ singleton. Similarly, no n-generic $f \in \omega ^{\omega }$ is a $\prod ^0_{n}$ function singleton.

Proof Suppose that X is the unique set such that $X \models \psi $ for some $\prod ^0_{n}$ formula (with a set constant) $\psi $ . By n-genericity we must have $X{{\restriction _{l}}} \Vdash _{T} \psi $ for some l. As T is perfect there is some n-generic path $Y \succ X{{\restriction _{l}}}, Y \neq X$ through T. But, by n-genericity $Y \models \psi $ contradicting the fact that X was the unique solution.

To show the claim holds for weakly n-generic sets suppose that $\psi = \left (\forall x\right )\! \Psi (x)$ . Now let $S = {\left \{{\sigma }\mid {\left (\exists x\right )\!\left ( \sigma \Vdash \lnot \Psi (x) \right )}\right \}}$ . S is a $\Sigma ^1_n$ set and if no element in S extended $\tau $ then $\tau \Vdash ^{w} \psi $ and, as above, would contradict the uniqueness of X. Hence, S is a $\Sigma ^1_n$ dense set of strings and, as every weak n generic is ( $n - 1$ )-generic and $\lnot \Psi \in \prod ^0_{n - 1}$ , if X is a weak n-generic meeting S then $X \models \lnot \psi $ .

The argument for function singletons proceeds identically.

In this light, we can think of the results from [1] as showing us that any $\mathbf {0}$ -escaping function computes a set that’s not a $\prod ^0_{1}$ singleton and any ${\mathbf {0}}'$ -escaping function computes a set that’s not a $\prod ^0_{2}$ singleton. ⁴ We leave it as an exercise to demonstrate that the techniques in [1] show that sufficient non-domination strength allows us to compute a set that’s not a $\prod ^0_{3}$ singleton. Thus, a plausible conjecture is that an arithmetically escaping function computes a set that’s not an arithmetic singleton (i.e., not a $\prod ^0_{n}$ singleton for any n). If true, this would prove that no $\omega \text {-REA}$ set is on minimal arithmetic degree.

Proposition 3.10. If every arithmetically escaping function f can arithmetically define a set that’s not an arithmetic singleton then no $\prod ^0_{2}$ singleton, and hence no $\omega \text {-REA}$ set, is of minimal arithmetic degree.

Proof Suppose, for contradiction, X is a $\prod ^0_{2}$ singleton of minimal arithmetic degree. By Lemma 2.2 X computes an arithmetically escaping f. Let $Y \leq _{\mathbf {a}} f$ such that Y isn’t an arithmetic singleton as per the proposition. If Y were arithmetic then Y would be a $\Sigma ^1_n$ set for some n and thus an arithmetic singleton. Therefore, we must have $Y \equiv _{\mathbf {a}} X$ . Thus, for some arithmetic formulas $\psi , \Psi $ we have $\psi (X) = Y \land \Psi (Y) = X$ and thus Y is the unique solution of the arithmetic formula which asserts that $\Psi (Y)$ satisfies the $\prod ^0_{2}$ formula defining X and that $\psi (\Psi (Y)) = Y$ . Contradiction.

4 An arithmetically minimal $ \prod ^0_{2}$ singleton

We will now prove that our seemingly plausible conjectures (once again) fail and that there is a $\prod ^0_{2}$ singleton of minimal arithmetic degree. Our approach to proving this borrows substantially from Harrington’s proof of McLaughlin’s conjecture [5]. As it’s easier to work with computable trees than $\prod ^0_{2}$ classes we’ll work in $\omega ^{<\omega }$ . By Lemma 2.1 it will be enough to build a computable tree $T \subset \omega ^{<\omega }$ with a single path f of minimal arithmetic degree. However, doing this in a single step would be dauntingly difficult, so we instead break up our construction into steps.

Specifically, the primary task will be to prove the following proposition.

Proposition 4.1. Given a (potentially partial) tree $S \subset \omega ^{<\omega }$ computable in ${X}^{\prime \prime }$ there is a (total) computable tree $T \subset \omega ^{<\omega }$ and an ${X}^{\prime \prime }$ computable partial f-tree $\hat {T}$ such that:

1. 1. $\mathrm {rng} \hat {T} \subset T$ and $[\hat {T}] = [T]$ .

2. 2. $\hat {T}(\cdot )$ is a homeomorphism of $[S]$ with $[T]$ .

3. 3. If $f \in [T]$ then $f \nleq _{\mathbf {T}} X$ .

4. 4. If $g \in [S]$ then $g \oplus {X}^{\prime \prime } \equiv _{\mathbf {T}} {\left (\hat {T}(g) \oplus X\right )}^{\prime \prime } \equiv _{\mathbf {T}} \hat {T}(g) \oplus {X}^{\prime \prime }$ .

5. 5. If $f \in [T]$ and $Y \leq _{\mathbf {T}} f \oplus X$ then either $Y \leq _{\mathbf {T}} X$ or $f \leq _{\mathbf {T}} Y \oplus {X}^{\prime \prime }$ .

6. 6. For all $\sigma \in 2^{<\omega }$ , $\left \lvert \hat {T}(\sigma )\right \rvert \geq \lvert \sigma \rvert $ (when defined).

Moreover, this holds with all possible uniformity. In particular, given a computable functional $\Upsilon _2$ we can effectively produce functionals $\Upsilon , \hat {\Upsilon }$ so that whenever ${\Upsilon _2({X}^{\prime \prime }) =S}$ then $\Upsilon (X)=T$ and $\hat {\Upsilon }({X}^{\prime \prime }) = \hat {T}$ with the properties described above.

We will then leverage this proposition to prove the main theorem below by using it repeatedly to pull down a tree $T_\alpha \leq _{\mathbf {T}} {\mathbf {0}}^{(\alpha )}$ to a homeomorphic image $T \leq _{\mathbf {T}} \mathbf {0}$ .

Theorem 4.2. Given a limit ordinal $\alpha < {\omega ^{\text {CK}}_1}$ and a tree $T_{\alpha } \subset \omega ^{<\omega }, T_\alpha \leq _{\mathbf {T}} {\mathbf {0}}^{(\alpha )}$ there is a computable tree T and an f-tree $\Gamma \leq _{\mathbf {T}} {\mathbf {0}}^{(\alpha )}$ such that $\Gamma $ is a homeomorphism of $[T_\alpha ]$ with $[T]$ satisfying the following for all $f \in [T]$ and ordinals $\beta < \alpha $ :

• • ${{f}^{({\beta })}} \equiv _{\mathbf {T}} f \oplus {\mathbf {0}}^{(\beta )}$ and, indeed, ${{f}^{(\alpha )}} \equiv _{\mathbf {T}} f \oplus {\mathbf {0}}^{(\alpha )}$ .

• • $f \nleq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ .

• • If $Y \leq _{\mathbf {T}} {{f}^{({\beta })}}$ then either $Y \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ or $f \leq _{\mathbf {T}} Y \oplus {\mathbf {0}}^{(\beta +2)}$ .

Moreover, this holds with all possibility uniformity.

Note that the final point above immediately entails that if there is some $\beta < \alpha $ such that $Y \leq _{\mathbf {T}} {{f}^{({\beta })}}$ then there is some $\gamma < \alpha $ such that either $Y \leq _{\mathbf {T}} {\mathbf {0}}^{(\gamma )}$ or $f \leq _{\mathbf {T}} {{Y}^{(\gamma )}}$ . We now catalogue a number of interesting corollaries, such as the existence of a $\prod ^0_{2}$ singleton of minimal arithmetic degree.

Corollary 4.3. There is a $\prod ^0_{2}$ singleton of minimal arithmetic degree.

Proof Taking $T_\omega = {\left \{{\langle {0^n}\rangle }\mid {n \in \omega }\right \}}$ immediately produces a $\prod ^0_{1}$ function singleton of minimal arithmetic degree and applying Lemma 2.1 transforms this into a $\prod ^0_{2}$ singleton of minimal arithmetic degree.

Our work from the previous section isn’t wasted as it allows us to prove the following interesting corollary.

Corollary 4.4. There is an arithmetically escaping function $f \leq _{\mathbf {T}} {\mathbf {0}}^{(\omega )}$ such that every $X \leq _{\mathbf {a}} f$ is an arithmetic singleton.

Proof By Corollary 4.3 and Lemma 2.1 let f be a $\prod ^0_{1}$ singleton of minimal arithmetic degree. By Lemma 2.2 f must be arithmetically escaping and by Proposition 3.10 every $Y \leq _{\mathbf {a}} f$ is an arithmetic singleton.

We can also derive some interesting consequences about perfect sets of minimal arithmetic degree.

Corollary 4.5. There is a perfect $\prod ^0_{2}$ class $\mathscr {C}$ all of whose members are of minimal arithmetic degree and which contains elements of arbitrarily large non-domination strength.

By containing elements of arbitrarily large non-domination strength, we mean that for any countable $C \subset \omega ^{\omega }$ there is an $X \in \mathscr {C}$ and $f \in \omega ^{\omega }$ such that $X \equiv _{\mathbf {T}} f$ and f isn’t dominated by any $g \in C$ .

Proof Take $T_\omega = \omega ^{<\omega }$ . Since $\Gamma $ is an f-tree and a homeomorphism at each $\sigma \in T_\omega $ we can pick i large which ensures that $\Gamma (\sigma \widehat {\phantom {x}}\langle i\rangle )$ is large at $n = \left \lvert \Gamma ^{\omega }_0(\sigma )\right \rvert $ . Thus, we can apply the same approach as in Corollary 3.3 to show that there is an element of $[T]$ that avoids domination by any element in C. By applying Lemma 2.1 we get a $\prod ^0_{2}$ class whose members are Turing equivalent to the elements in $[T]$ .

Before we move on to providing proofs of Theorem 4.2 and Proposition 4.1, we end this section by asking a few questions. While the existence of a $\prod ^0_{2}$ singleton of minimal arithmetic degree is suggestive, it isn’t quite enough to demonstrate that the project of using the properties of fast growing functions to show $\omega \text {-REA}$ sets can’t be of minimal degree fails. This gives rise to the following question.

Question 4.6. If f is arithmetically escaping, must there be some $X \leq _{\mathbf {a}} f$ where X isn’t of $\omega \text {-REA}$ arithmetic degree.

At first glance, one might think that this question stands or falls with the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree. After all, the question must have a negative answer if there is such an $ \omega \text {-REA}$ set and if the question has a positive answer then no such set can exist. However, there is still the possibility that the question has a negative answer and no $\omega \text {-REA}$ set is of minimal arithmetic degree. This would require that there is some non-arithmetic $\omega \text {-REA}$ set A such that every $B \leq _{\mathbf {a}} A$ is arithmetically equivalent to an $\omega \text {-REA}$ set, but that doesn’t seem beyond the realm of possibility.

Next, inspired by the methods in [5], we ask if this approach offers any utility if extended up through all ordinals below $\omega ^{\mathrm {CK}}_1$ .

Question 4.7. Do results that create a unique path through $\mathcal {O}$ via ‘non-standard’ notations offer a means to extend Theorem 4.2 to prove interesting results about hyperdegrees?

Such a generalization isn’t as simple as merely applying the construction used in Theorem 4.2 to some non-standard notation. That can’t work as we could then build a $\prod ^0_{1}$ function singleton that isn’t of hyperarithmetic degree which contradicts the fact that if f is the unique path through a computable tree $[T]$ then $f \in \mathrm {HYP}$ . However, the methods in [5] might allow the definition of a perfect $\prod ^0_{1}$ class of elements all of which satisfy the conclusion of Theorem 4.2 with respect to all $\alpha $ in some linearly ordered path through $\mathcal {O}$ .

Question 4.8. Is there a perfect $\prod ^0_{1}$ function class all of whose elements are both arithmetically minimal and arithmetically escaping?

The difficulty here is that modifying $T_\omega $ also results in modification to T.

Question 4.9. What kind of ability do we have to control the join of pairs of minimal degrees? Are there $\prod ^0_{2}$ singletons $A, B$ of minimal arithmetic degree such that $A \oplus B \equiv _{\mathbf {a}} {\mathbf {0}}^{(\omega )}$ (or even $\equiv _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ for arbitrary $\beta \in \mathcal {O}$ ). Could we combine this with the idea in Question 4.7 to create a perfect $\prod ^0_{2}$ class whose elements join to compute $\mathcal {O}$ ?

5 Towers of trees

Before we get into the weeds of proving Proposition 4.1 we first show that it suffices to establish the main theorem. As not all readers may wish to delve into the details involved in manipulating ordinal notations we segregate the results needed to prove the claim for $\alpha $ above $\omega $ into an appendix. If you are only interested in the case $\alpha = \omega $ you may simply take ${\beta }^{\Diamond } = \omega $ and $l^{\Diamond }(n) = n$ for all $n \in \omega $ and ${\left \{\omega \right \}}^{\mathcal {O}}(n) = 2n$ and replace the following definition of an even notation with that of an even number.

Definition 5.1. The ordinal notation $\beta $ is an even notation if $\beta = \lambda + 2k$ where $\lambda $ is either $0$ or a limit notation and $k \in \omega $ .

We break our proof of Theorem 4.2 into a construction of a uniform sequence of trees $T_\beta $ and a verification that this uniform sequence of trees has the desired properties.

Proposition 5.2. Given a limit notation $\alpha $ and a tree $T_{\alpha }$ computable in ${\mathbf {0}}^{(\alpha )}$ the following hold:

1. 1. For each even notation $\beta <_{\mathcal {O}} \alpha $ there is a tree $T_\beta $ uniformly computable in ${\mathbf {0}}^{(\beta )}$ .

2. 2. For all $\gamma <_{\mathcal {O}} \beta \leq _{\mathcal {O}} \alpha $ , there is a uniformly given f-tree $\Gamma ^{\beta }_\gamma \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ that’s a homeomorphism of $[T_\beta ]$ with $[T_\gamma ]$ .

3. 3. For each even notation $\beta <_{\mathcal {O}} \alpha $ there is some $l^{\Diamond }(\beta ) \in \omega $ such that if $\sigma \in T_\beta , \lvert \sigma \rvert = l^{\Diamond }(\beta )$ then applying Proposition 4.1 with and $X = {\mathbf {0}}^{(\beta )}$ produces and $\hat {T}$ where $\sigma \widehat {\phantom {x}} \hat {T}(\tau ) = \Gamma ^{\beta +2}_{\beta }(\sigma \widehat {\phantom {x}}\tau )$ for all $\tau $ .

For 2 we understand the uniformity claim to mean that $\Gamma ^{\beta }_\gamma (\tau )$ is given by $\Gamma (\beta , \gamma , {\mathbf {0}}^{(\beta )}, \tau )$ for a single computable functional $\Gamma $ . Similarly, for 1 we understand the uniformity claim to mean that there is a single computable functional such that $\Upsilon (\beta , {\mathbf {0}}^{(\beta )}, \cdot )$ gives the characteristic function for $T_\beta $ for all even notations $\beta \leq _{\mathcal {O}} \alpha $ , Moreover, that indexes for both functionals are given by a computable function of $\alpha $ and an index for $T_\alpha $ .

5.1 Verifying the main theorem

We now prove a utility lemma which will let us show that Theorem 4.2 follows from the claim above.

Lemma 5.3. Given $\alpha , T_\beta , \Gamma $ as in Proposition 5.2 and $f \in [T_0]$ for all even notations $\beta \leq _{\mathcal {O}} \alpha $ :

1. 1. There is a unique $g_\beta \in [T_\beta ]$ such that $\Gamma ^{\beta }_{0}(g_\beta ) = f$ .

2. 2. $g_\beta $ is uniformly computable from $f \oplus {\mathbf {0}}^{(\beta )}$ .

3. 3. ${{f}^{({\beta })}} \equiv _{\mathbf {T}} f \oplus {\mathbf {0}}^{(\beta )} \equiv _{\mathbf {T}} g_\beta \oplus {\mathbf {0}}^{(\beta )}$ . Moreover, this equivalence holds uniformly in $\beta $ .

4. 4. $\beta <_{\mathcal {O}} \alpha $ implies $g_\beta \nleq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ .

5. 5. If $\beta <_{\mathcal {O}} \alpha $ and $Y \leq _{\mathbf {T}} g_\beta \oplus {\mathbf {0}}^{(\beta )}$ then either $Y \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ or $g_\beta \leq _{\mathbf {T}} Y \oplus {\mathbf {0}}^{(\beta +2)}$ .

Proof By point 2 of Proposition 5.2 there is a unique $g_{\beta }$ whose image under $\Gamma ^{\beta }_0$ is f. We can compute $g_\beta $ in ${\mathbf {0}}^{(\beta )} \oplus f$ as $ \Gamma ^{\beta }_0 \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ and as it’s an f-tree it sends incompatible elements in the domain to incompatible elements in the range. This verifies points 1 and 2.

For point 4 let $\sigma = g_\beta {{\restriction _{{l^{\Diamond }(\beta )}}}}$ and note that by 3 of Proposition 5.2 for $\beta <_{\mathcal {O}} \alpha $ the tree is the result of Proposition 4.1 applied to and by 3 of Proposition 4.1 we know that $ g_{\beta } \nleq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ . By part 5 of Proposition 4.1 we have that 5 holds. This leaves us only 3 to verify.

Suppose that 3 holds for all notations $\gamma <_{\mathcal {O}} \beta $ (where we regard the claim as trivially true for odd notations). We prove the claim holds for $\beta $ . First, suppose that $\beta = \gamma + 2$ .

Now let $\sigma = g_\gamma {{\restriction _{l^{\Diamond }(\gamma )}}}$ . By 3 of Proposition 5.2 the tree is the result of Proposition 4.1 applied to . Thus, by point 4 of Proposition 4.1 we have ${\left (g_\gamma \oplus {\mathbf {0}}^{(\gamma )}\right )}^{\prime \prime } \equiv _{\mathbf {T}} g_\gamma \oplus {\mathbf {0}}^{(\gamma +2)} \equiv _{\mathbf {T}} g_{\gamma +2} \oplus {\mathbf {0}}^{(\gamma +2)}$ . The inductive assumption transforms this equivalence into the one asserted in 3.

Now, suppose that $\beta $ is a limit notation. Note that as Proposition 5.2 guarantees that $T_\gamma $ is uniformly computable from ${\mathbf {0}}^{(\gamma )}$ (for $\gamma $ an even notation) and Proposition 4.1 holds uniformly therefore claim 3 holds uniformly below $\beta $ . But ${\mathbf {0}}^{(\beta )}$ can uniformly compute ${\mathbf {0}}^{(\gamma )}$ and thus $f \oplus {\mathbf {0}}^{(\beta )}$ can compute ${{f}^{(\gamma )}}$ for notations $\gamma <_{\mathcal {O}} \beta $ . Hence $f \oplus {\mathbf {0}}^{(\beta )}$ can compute ${{f}^{({\beta })}}$ which is automatically an equivalence. Using $\Gamma ^{\beta }_0 \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ to translate between $g_\beta $ and f we see $f \oplus {\mathbf {0}}^{(\beta )} \equiv _{\mathbf {T}} g \oplus {\mathbf {0}}^{(\beta )}$ completing the verification.

We can now show that Theorem 4.2 follows from Proposition 5.2.

Proof Take $\alpha '$ to be a notation for the desired ordinal in Theorem 4.2 and apply Proposition 5.2 to get the notation $\alpha $ , the sequence $T_\beta $ and $\Gamma $ . We now apply Lemma 5.3. The equivalence ${{f}^{({\beta })}} \equiv _{\mathbf {T}} f \oplus {\mathbf {0}}^{(\beta )} \equiv _{\mathbf {T}} g_\beta \oplus {\mathbf {0}}^{(\beta )}$ from part 3 of Lemma 5.3 gives the first claim in Theorem 4.2 on its own. Applying it to part 5 of Lemma 5.3 is enough to give the final claim in Theorem 4.2. Finally, if $f \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ then that equivalence implies that $g_\beta \oplus {\mathbf {0}}^{(\beta )} \leq _{\mathbf {T}} {\mathbf {0}}^{(\beta )}$ contradicting part 4 of Lemma 5.3.

5.2 Constructing the tower

We now prove Proposition 5.2 follows from Proposition 4.1. To deal with notations for ordinals above $\omega $ we use some results proved in Appendices A and B. We start by defining $ l^{\Diamond }(\beta ), {\beta }^{\Diamond }$ via Definition B.3. As mentioned above, readers only interested in the case $\alpha = \omega $ can skip the material on ordinal notations in Appendices A and B. They will, however, still need to know that we can replace $T_\omega $ with a tree $T^{\prime }_\omega $ with $[T^{\prime }_\omega ] = [T_\omega ]$ in which the membership of $\sigma \in T^{\prime }_\omega $ for $\lvert \sigma \rvert = 2n$ can be computed uniformly in ${\mathbf {0}}^{(2n)}$ (a special case of the general result proved in Lemma B.6).

We construct a computable functional $\Upsilon $ such that for all even notations $\beta $ with $\beta \leq _{\mathcal {O}} \alpha $ , $\Upsilon (\beta , {\mathbf {0}}^{(\beta )}, \cdot )$ gives the characteristic function for $T_\beta $ . Regarding functionals as r.e-sets of axioms we can define a functional $\Upsilon $ assuming that we already have access to some partial functional $\hat {\Upsilon }$ and then use the recursion theorem to yield a single functional satisfying $\Upsilon = \tilde {\Upsilon }$ . Formally speaking, $\Upsilon $ and $\tilde {\Upsilon }$ are defined to be sets of axioms; however, we will only specify those sets implicitly by instead defining the trees $T_\beta $ in terms of the trees $\tilde {T}_\beta $ where we understand that $\tilde {T}_\beta $ represents the set defined by $\tilde {\Upsilon }(\beta , X, \cdot )$ on the guess that $X = {\mathbf {0}}^{(\beta )}$ .

Specifically, we define $T_\alpha $ to be $T_\alpha $ . That is, regardless of the behaviour of $\tilde {\Upsilon }$ , $\Upsilon (\alpha , X, \cdot )$ gives the computation that yields the characteristic function for $ T_\alpha $ when $X = {\mathbf {0}}^{(\alpha )}$ . Given $\beta $ an even notation with $\beta <_{\mathcal {O}} \alpha $ we define the tree $T_\beta $ as follows (once $\Upsilon $ has verified the $\Sigma ^1_1$ fact that $\beta <_{\mathcal {O}} \alpha $ is an even notation).

Let $\lambda = {\beta }^{\Diamond }$ . If $\lvert \sigma \rvert \leq l^{\Diamond }(\beta )$ then $\sigma \in T_\beta $ iff $\sigma \in \tilde {T}^{\prime }_\lambda $ where if $\lambda $ is a limit notation, $\tilde {T}^{\prime }_\lambda $ is the result of applying Lemma B.6 to $\tilde {T}_\lambda $ so that $\tilde {T}^{\prime }_\lambda {{\restriction _{l^{\Diamond }(\beta )}}}$ has membership uniformly computable in ${\mathbf {0}}^{(\beta )}$ and $[\tilde {T}^{\prime }_\lambda ]$ = $ [\tilde {T}_\lambda ]$ . If $\lambda $ is a successor notation then $\tilde {T}^{\prime }_\lambda = \tilde {T}_\lambda $ .

For $\sigma '$ with $\left \lvert \sigma '\right \rvert> l^{\Diamond }(\beta )$ let $\sigma ' = \sigma \widehat {\phantom {x}} \tau $ where $\lvert \sigma \rvert = l^{\Diamond }(\beta )$ . Set $\sigma ' \notin T_\beta $ if $\sigma \notin \tilde {T}^{\prime }_\lambda $ . If $\sigma \in \tilde {T}^{\prime }_\lambda $ then apply Proposition 4.1 to to yield some $T^{\sigma }_\beta $ and place $\sigma ' \in T_\beta $ just if $\tau \in T^{\sigma }_\beta $ . Note that, we can enforce the fact that $\tilde {T}^{\sigma }_{\beta +2}$ is always a tree by only allowing strings into this set when all their predecessors have been seen to be in the set.

We now define $\Upsilon $ to be the fixed point rendering $\tilde {\Upsilon } = \Upsilon $ . Thus, for an even notation $\beta \leq _{\mathcal {O}} \alpha $ we define $T_\beta = \Upsilon (\beta , {\mathbf {0}}^{(\beta )})$ . Note that, by part 3 of Proposition B.5 we can be sure that our fixed point will satisfy $T_\beta {{\restriction _{l^{\Diamond }(\beta )}}} \subset T_{\beta +2}{{\restriction _{{l^{\Diamond }(\beta )}}}}$ so that $ \tilde {T}^{\sigma }_{\beta +2}$ will be defined for $\sigma \in T_{\beta }, \lvert \sigma \rvert = l^{\Diamond }(\beta )$ .

We define the functional $\Gamma $ in a similar fashion assuming we have some $\tilde {\Gamma }$ and applying the recursion theorem. Note that, the argument above produces two indexes i and $q(i)$ for the functional $\Upsilon $ where q is the computable functional implicitly defined by the construction above and i is the index given by the recursion theorem applied to q. While i and $q(i)$ result in the same set of axioms, we can’t guarantee that the application of Proposition 4.1 produces the same $T, \hat {T}$ for different indexes for the same tree S. To handle this issue, we use $\tilde {T}_{\beta + 2}$ to indicate the definition in terms of i and apply Proposition 4.1 to not to ensure we get the f-tree $\hat {T}$ associated with the construction of .

With this in mind, we define $\Gamma ^{\beta +2}_\beta $ for $\beta \leq _{\mathcal {O}} \alpha $ an even notation as follows. If ${\lvert \sigma \rvert \leq l^{\Diamond }(\beta )}$ then $\Gamma ^{\beta +2}_\beta (\sigma ) = \sigma $ if $\sigma \in \tilde {T}_{\beta + 2}$ and undefined otherwise. If $\left \lvert \sigma '\right \rvert> l^{\Diamond }(\beta )$ then let $\sigma = \sigma '{{\restriction _{{l^{\Diamond }(\beta )}}}}$ and if $\sigma \notin \tilde {T}_{\beta + 2}$ then $\Gamma ^{\beta +2}_\beta (\sigma ')\uparrow $ . Otherwise, we define $\Gamma ^{\beta +2}_\beta (\sigma ') = \sigma \widehat {\phantom {x}} \hat {T}(\tau )$ where, $\sigma ' = \sigma \widehat {\phantom {x}} \tau $ and $\hat {T}$ is the f-tree produced by Proposition 4.1 as applied to . For $\beta ' <_{\mathcal {O}} \beta $ we define $ \Gamma ^{\beta +2}_{\beta '}$ to be $\Gamma ^{\beta +2}_{\beta } \circ \tilde {\Gamma }^{\beta }_{\beta '}$ .

Finally, for $\lambda $ a limit and $\beta <_{\mathcal {O}} \lambda \leq _{\mathcal {O}} \alpha $ , $\beta $ an even notation we define $\Gamma ^{\lambda }_{\beta }(\sigma )$ as follows. Let $\beta _n$ be the sequence of notations given by part 4 of Proposition B.5. Let m be the least with $\lvert \sigma \rvert \leq m$ and $\beta \leq _{\mathcal {O}} \beta _m$ and define $\Gamma ^{\lambda }_{\beta }(\sigma )$ to be equal to $ \tilde {\Gamma }^{\beta _m}_{\beta }(\sigma )$ . Finally, we define $\Gamma $ via the recursion theorem so that $\Gamma = \tilde {\Gamma }$ .

To verify this construction produces the desired result, we suppose that $\beta , \gamma $ is the lexicographically least pair of even notations $\gamma <_{\mathcal {O}} \beta \leq _{\mathcal {O}} \alpha $ such that $\Gamma ^{\beta }_\gamma $ isn’t an f-tree that’s a homeomorphism of $[T_\beta ]$ with $[T_\gamma ]$ and then observe that if $\beta = \beta ' + 2$ then since $\Gamma ^{\beta '+2}_{\beta '}$ is a homeomorphism we get a contradiction. Similarly, if $ \lambda = \beta $ is a limit then by Proposition B.5, 6 of Proposition 4.1, and the inductive assumption regarding $\Gamma ^{\beta _n}_\beta $ we can derive that $\Gamma ^{\lambda }_\beta $ is an f-tree that’s a homeomorphism of $[T_\lambda ]$ with its image contained in $[T_\beta ]$ . Now suppose that some $f \in [T_\beta ]$ isn’t equal to $\Gamma ^{\lambda }_\beta (g)$ for any $g \in [T_\lambda ]$ . Then, for some n we have that $f \succ \Gamma ^{\beta _n}_\beta (\sigma )$ for no $\sigma \in T^{\prime }_\lambda $ with $\lvert \sigma \rvert = l^{\Diamond }(\beta _n)$ and thus by the inductive assumption $f \notin [T_\beta ]$ . Thus, the claim holds for $\Gamma ^{\lambda }_\beta $ as well. This suffices to prove Proposition 5.2.

6 Minimality and double jump inversion

In this section, we finally present the proof of Proposition 4.1. However, before we do this we answer an obvious question raised by our construction. Why do we use double jump inversion and not single jump inversion as Harrington did in [5]? The answer is that it’s not possible. We can’t satisfy the minimality style requirements while also using $\omega $ -branching to encode the copy of $ T_{\beta + 1}$ . Specifically, we now show that no ${\mathbf {0}}'$ $\omega $ -branching tree T lets us achieve the kind of minimality required by part 5 of Proposition 4.1.

Proposition 6.1. Given a perfect weakly $\omega $ -branching pruned f-tree $T \leq _{\mathbf {T}} {\mathbf {0}}'$ one can uniformly construct a computable functional $\Phi $ such that e-splitting pairs in T occur above every node in T and for every $\tau \in \mathrm {rng} T$ there are paths $f \neq g$ extending $\tau $ through T with $\Phi _{e}\left (f\right ) = \Phi _{e}\left (g\right )$ .

Indeed, the result is actually slightly stronger in that we show that even if T is unpruned we can start building such $f, g$ above every node in T and always extend to preserve agreement under $\Phi _{e}$ until we hit a terminal node. Even without this improvement, this rules out the possibility of building $\hat {T}$ to be computable in ${X}^{\prime }$ . While we aren’t guaranteed that $\hat {T}$ itself is pruned it will be pruned whenever S is pruned. Thus, the above result rules out the possibility of performing the construction using only single jump inversion. Since the proof of this proposition takes some work and would interrupt the flow of the paper we relegate it to Appendix A.

6.1 Machinery

The construction will build T via a stagewise approximation $T_s$ with $T_{s+1} \supset T_s$ and $\sigma \in T$ iff $\sigma \in T_{\left \ulcorner \sigma \right \urcorner }$ . We will also maintain a stagewise approximation $\hat {T}_{s}$ to $\hat {T}$ . We will organize the construction of by drawing on ideas from $\prod ^0_{2}$ constructions in the r.e. sets. In particularly, we will arrange modules on a priority tree, denoted $ \mathbb {T} \subset \omega ^{<\omega }$ , but the differences between constructing a set and a tree require we make some modifications.

Usually, in a $\prod ^0_{2}$ tree construction we assign modules to elements of $\omega ^{<\omega }$ , denoting an arbitrary module assigned to $\alpha $ by ${\mathcal {M}}_{\alpha }$ (for a module of type R, ${\mathcal {R}}_{\alpha }$ ) and use only the outcome of that module at stage s to determine where next to visit at stage s. However, rather than working on meeting a requirement globally for the entire tree T we will assign modules to work on meeting a requirement for the path extending $\hat {T}(\sigma )$ for some $\sigma $ . Thus, rather than working on $\mathbb {T} \subset \omega ^{<\omega }$ we work on $\mathbb {T} \subset \omega ^{<\omega } \times \omega ^{<\omega }$ . More specifically, we identify modules in our construction with pairs $(\alpha , \sigma )$ where $\alpha $ is the string built up out of the outcomes of prior modules and $\sigma $ indicates the element in $\mathrm {dom} \hat {T}$ we are working to define. The idea is that at certain points in our construction, rather than following a single outcome of a module, we will simultaneously work both above (our approximation to) $\hat {T}(\sigma \widehat {\phantom {x}}\langle m\rangle )$ and above/to define $ \hat {T}(\sigma \widehat {\phantom {x}}\langle m'\rangle )$ .

When we specify a module ${\mathcal {M}}_{\xi }$ we also specify a set $\mathfrak {O}(\xi )$ of pairs of potential successors $(o, \delta )$ where o is a potential outcome of the module (identified with elements in $\omega $ but written more suggestively) and $\delta \in \omega ^{<\omega }$ . As usual, at each stage any module we visit will have a single outcome o but as there may be multiple pairs $(o, \delta ) \in \mathfrak {O}(\xi )$ there may be multiple immediate successors of this module which both get visited at this stage. In our construction most modules will only allow $\delta = \langle \rangle $ but some modules will have successors both of the form $(o, \langle \rangle )$ and $(o, \langle n\rangle )$ (for some particular value n). Thus, we will only work on finitely many modules at any stage. With this in mind, we define our priority tree $\mathbb {T}$ inductively as follows. In what follows, keep in mind that ${\left ({\langle a,b\rangle }\right )_{0}} = a$ and ${\left ({\langle a,b\rangle }\right )_{1}} = b$ .

Definition 6.2. $\mathbb {T}$ is the smallest set of pairs $\langle \alpha ,\sigma \rangle $ closed under the following conditions:

• • $\langle \langle \rangle ,\langle \rangle \rangle \in \mathbb {T}$ .

• • If $\xi = \langle \alpha ,\sigma \rangle \in \mathbb {T} \land (o, \delta ) \in \mathfrak {O}(\xi )$ then $\nu = \langle \alpha \widehat {\phantom {x}}\langle o\rangle , \sigma \widehat {\phantom {x}} \delta \rangle \in \mathbb {T}$ . In this case we write $\nu ^{-} = \xi $ and call $\xi $ the predecessor of $\nu $ .

We define $\left \lvert \xi \right \rvert \in \mathbb {T} = \left \lvert {\left ({\xi }\right )_{{0}}} \right \rvert $ and say $\xi \prec \xi '$ if $\prec $ holds on both components (i.e., ${\left ({\xi }\right )_{i}} \prec {\left ({\xi '}\right )_{i}}, i \in {\left \{{0,1}\right \}}$ ). Finally, $\xi ^{-}$ is defined to be the unique $\prec $ maximal element in $\mathbb {T}$ with $\xi ^{-} \prec \xi $ .

The careful reader might note the possibility that $\xi ^{-}$ could fail to be unique if we aren’t careful. To avoid this, we assume that the outcomes of $\xi = \langle \alpha ,\sigma \rangle $ are modified to be of the form $ \langle o,\sigma \rangle $ . This ensures that $\xi ^{-}$ is uniquely defined and $\prec $ is always a linear order when restricted to the predecessors of $\xi $ on $\mathbb {T}$ . As it won’t cause any confusion, we will assume this happens in the background and will present our outcomes untransformed.

We now define what it means for a node on this tree to be to the left of another node (we retain the terminology ‘left of’ even though its not longer visually accurate) and extend this to a set of nodes as follows.

Definition 6.3. We define $\xi <_L \xi '$ on $\mathbb {T}$ just if there are $\nu \prec \xi , \nu ' \prec \xi $ with ${\nu ^{-} = {\nu '}^{-}}$ , ${\left (\nu \right )_{0}} = \alpha \widehat {\phantom {x}}\langle o\rangle , {\left ({\nu '}\right )_{0}} = \alpha \widehat {\phantom {x}}\langle o'\rangle $ and $o < o'$ . We extend this relation to sets by setting $Q <_L \xi $ (read left of) for $Q \subset \mathbb {T}, \xi \in \mathbb {T}$ just if Q contains an element $\nu <_L \xi $ .

Our truepath, and its approximations, will no longer be single paths but sets of nodes. Informally speaking, we define to be the set of nodes visited at stage s following the rules described above but not visiting any extensions of a node $\xi $ being visited for the first time at stage s. Formally speaking, we give the following definition.

Definition 6.4. We define as the largest set satisfying the following closure conditions:

• • .

• • If , $s_\xi> 0$ and at stage s, o is the outcome of $\xi $ at stage s and $\nu \in \mathbb {T}, \nu ^{-} = \xi $ with ${\left (\nu \right )_{0}} = {\left (\xi \right )_{0}}\widehat {\phantom {x}}\langle o\rangle $ then $\nu \in \mathbb {T}$ .

Where $s_\xi $ is defined to be .

We define iff .

Note that our priority construction will never reinitialize any nodes. That is, our construction will satisfy the following condition.

Condition 1. If $s'> s$ and then for all $t \geq s'$ .

With the action of the priority tree defined we need to specify how the modules are able to control the construction. As described above, modules will directly enumerate elements into $T = \bigcup _{s \in \omega } T_s$ with a deadline of stage $s = \left \ulcorner \sigma \right \urcorner $ to place $\sigma $ into T. We use a bit more machinery to specify our approximation to $\hat {T}$ . Each module ${\mathcal {M}}_{\xi }$ receives a string $\delta ^{\xi }$ and specifies a string $\delta ^{\nu }$ for each successor to $\xi $ . If $\xi = \langle \alpha ,\sigma \rangle $ then we understand the module $\xi $ to be executing on the guess that $\delta ^{\xi } \prec \hat {T}(\sigma )$ .

This is sufficient for modules that only need to manipulate a single path but some modules will need to manipulate the collection of potential branches of $\hat {T}(\sigma )$ . To this end, some modules will also define an infinite set $\Theta ^{\xi }$ of branches with the n-th element (ordered lexicographically) indicated by ${\theta ^{\xi }_{n}}$ . In our construction, we will ensure that our definition of $\delta ^{\xi }$ and $\Theta ^{\xi }$ satisfy the following condition.

Condition 2. For each $\xi \in \mathbb {T}$ :

1. 1. If then ${\mathcal {M}}_{\xi ^{-}}$ must set $\delta ^{\xi }$ during stage s and ensure $\delta ^{\xi } \in T_{s+1}$ .

2. 2. $\nu \succeq \xi \implies \delta ^{\xi } \succeq \delta ^{\nu }$ .

If $\xi \in \mathbb {T}$ and ${\mathcal {M}}_{\xi ^{-}}$ defines $\Theta ^{\xi }$ then:

1. 1. ${\theta ^{\xi }_{n}}$ enumerates $\Theta ^{\xi }$ with ${\theta ^{\xi }_{n}} \succ \delta ^{\xi }\widehat {\phantom {x}}\langle k_n\rangle $ with $n \mapsto k_n$ monotonic, injective function of n.

2. 2. If then ${\mathcal {M}}_{\xi ^{-}}$ must set ${\theta ^{\xi }_{n}}$ by the end of stage s and ensure ${\theta ^{\xi }_{n}} \in T_{s+1}$ .

These are mostly straightforward demands that what the module at $\xi $ does is compatible with what $\xi ^{-}$ does and defines its output promptly. However, a few points deserve mentioning. The requirement that $ \delta ^{\xi } \in T_{s+1}$ will ensure that $\mathrm {rng} \hat {T} \subset T$ . The final condition will enable multiple modules who all want to ensure the leftmost branch extending $\hat {T}(\sigma )$ has some property to cooperate. Without this condition, a module that only ensured ${\theta ^{\xi }_{0}}$ has some property might find their work erased by the next module leaving all extensions of ${\theta ^{\xi }_{0}}$ out of the set of branches it specifies.

We also impose the following condition on the construction to (help) ensure that if then the modules above $\xi $ get to control whether $\delta ^{\xi }$ extends to a path through T.

Condition 3. If $\delta ^{\xi } = \tau $ and the module ${\mathcal {M}}_{\xi }$ enumerates $\sigma $ into T then $\sigma \succ \tau $ .

6.2 Requirements

With an understanding of how our $\mathbb {T}$ operates we are now in a position to present the requirements our construction will meet and arrange the modules we will use to meet them on the tree. Recall that we seek to prove the following result.

Proposition 4.1. Given a (potentially partial) tree $S \subset \omega ^{<\omega }$ computable in ${X}^{\prime \prime }$ there is a (total) computable tree $T \subset \omega ^{<\omega }$ and an ${X}^{\prime \prime }$ computable partial f-tree $\hat {T}$ such that:

1. 1. $\mathrm {rng} \hat {T} \subset T$ and $[\hat {T}] = [T]$ .

2. 2. $\hat {T}(\cdot )$ is a homeomorphism of $[S]$ with $[T]$ .

3. 3. If $f \in [T]$ then $f \nleq _{\mathbf {T}} X$ .

4. 4. If $g \in [S]$ then $g \oplus {X}^{\prime \prime } \equiv _{\mathbf {T}} {\left (\hat {T}(g) \oplus X\right )}^{\prime \prime } \equiv _{\mathbf {T}} \hat {T}(g) \oplus {X}^{\prime \prime }$ .

5. 5. If $f \in [T]$ and $Y \leq _{\mathbf {T}} f \oplus X$ then either $Y \leq _{\mathbf {T}} X$ or $f \leq _{\mathbf {T}} Y \oplus {X}^{\prime \prime }$ .

6. 6. For all $\sigma \in 2^{<\omega }$ , $\left \lvert \hat {T}(\sigma )\right \rvert \geq \lvert \sigma \rvert $ (when defined).

Moreover, this holds with all possible uniformity. In particular, given a computable functional $\Upsilon _2$ we can effectively produce functionals $\Upsilon , \hat {\Upsilon }$ so that whenever ${\Upsilon _2({X}^{\prime \prime }) =S}$ then $\Upsilon (X)=T$ and $\hat {\Upsilon }({X}^{\prime \prime }) = \hat {T}$ with the properties described above.

We work to meet the following requirements during the construction. We state the requirements in unrelativized form. Unlike requirements in the construction of a single set, we work to ensure that the requirement of the form ${\mathscr {R}}_{e}$ is satisfied for all e and all $\sigma \in {S^{\langle \infty \rangle }}$ with $\lvert \sigma \rvert = e$ . For the purposes of stating the requirements, we use $\hat {T}^-(\sigma )$ to denote an extension of $ \hat {T}(\sigma ^{-})$ that would be extended by $\hat {T}(\sigma )$ if the later were defined. We won’t actually define this function but just use it in the requirements to stand in for some string to be defined later. ⁵

$$ \begin{align*} {\mathscr{P}}_{e}:\quad &\hat{T}(\sigma) \mid \Phi_{e}\left(X\right) \lor \Phi_{e}\left(X\right)\uparrow\\ {\mathscr{L}}_{e}:\quad & \left(\forall {f \kern1.3pt{\in}\kern1.3pt [T], f \kern1.2pt{\succ}\kern1.2pt \hat{T}(\sigma)}\right)\!\left(\Phi_{e}\left(f \kern1.2pt{\oplus}\kern1.2pt X\right)\uparrow\right) \kern1.2pt{\lor}\kern1.2pt \left(\forall {f \kern1.2pt{\in}\kern1.2pt [T], f \kern1.3pt{\succ}\kern1.3pt \hat{T}(\sigma)}\right)\!\left(\Phi_{e}\left(f \kern1.3pt{\oplus}\kern1.3pt X\right)\kern-1pt\downarrow\right)\\{\mathscr{H}}_{\sigma}:\quad& S(\sigma)\downarrow = 0 \implies \hat{T}(\sigma)\downarrow \land \left(\forall m\right)\!\left(\hat{T}(\sigma)\widehat{\phantom{x}}\langle m\rangle \notin T \right) \\ &S(\sigma)\downarrow = 1 \implies \hat{T}(\sigma)\downarrow \in {T^{\langle \infty\rangle}} \iff \sigma \in {S^{\langle\infty\rangle}} \\ &\qquad S(\sigma)\uparrow \implies \hat{T}(\sigma)\uparrow \land \hat{T}^-(\sigma) \notin {T^{\langle\infty\rangle}}\\{\mathscr{S}}^n_{e}:\quad& T^{\left\langle \hat{T}(\sigma\widehat{\phantom{x}}\langle n\rangle) \right\rangle} \text{ is totally non-}e\text{-splitting } \lor m> n \implies \\ &\qquad\qquad\!\!\hat{T}^-(\sigma\widehat{\phantom{x}}\langle n\rangle) \text{ and } \hat{T}^-(\sigma\widehat{\phantom{x}}\langle m\rangle) e-\text{split} \end{align*} $$

Note that $\Phi _{e}\left (f\right )\downarrow $ means $\left (\forall n\right )\!\left (\Phi _{e}\left (f;n\right )\downarrow \!\right )$ (and similarly for $\Phi _{e}\left (f\right )\uparrow $ ) and that, when we speak of e-splittings we mean the notion relativized to X. The statement of ${\mathscr {H}}_{\sigma }$ is a bit odd in the case where $\sigma \in S$ since in that we do nothing except don’t try to stop $\hat {T}(\sigma )$ from potentially extending to a full path should $\sigma $ extend to a full path through S.

Each requirement gets its own module to assist in meeting it; however, some modules get helper modules. For instance, we break up meeting the requirement ${\mathscr {H}}_{\sigma }$ into a module ${\mathcal {H}}^+_{\sigma ^{-}}$ responsible for creating an $\omega $ -branching above $\hat {T}(\sigma ^{-})$ and a module ${\mathcal {H}}_{\sigma }$ responsible for ensuring $\hat {T}(\sigma )$ doesn’t extend to a path through T if $\sigma \notin S$ . Similarly, we supplement ${\mathcal {L}}_{e}$ with submodules ${\mathcal {L}}^n_{e}$ responsible for checking if we can extend $\Phi _{e}\left (f\right )$ to converge on $\Phi _{e}\left (f;n\right )$ . Finally, we use the module $ {\mathcal {S}}^n_{-1}$ as a helper to split off those modules who will work above $\hat {T}(\sigma \widehat {\phantom {x}}\langle n\rangle )$ from those modules working to define $\hat {T}(\sigma \widehat {\phantom {x}}\langle m\rangle ), m> n$ .

Definition 6.5. Modules are be assigned to nodes on $\mathbb {T}$ as follows:

1. 1. If $\xi = (\langle \rangle , \langle \rangle )$ then $\xi $ implements ${\mathcal {H}}^+_{\langle \rangle }$ . Also, if $\xi ^{-}$ implements some module ${\mathcal {H}}_{\sigma }$ and has an outcome guessing $\sigma \in S$ then $\xi $ implements ${\mathcal {H}}^+_{\sigma }$ .

2. 2. If $\xi ^{-}$ implements ${\mathcal {H}}^+_{\sigma }$ with $\lvert \sigma \rvert = e$ then $\xi $ implements ${\mathcal {S}}^0_{e}$ .

3. 3. If $\xi ^{-}$ implements ${\mathcal {S}}^n_{e}$ with $e \geq 0$ then $\xi $ implements ${\mathcal {S}}^n_{e - 1}$ .

4. 4. If $\xi ^{-}$ implements ${\mathcal {S}}^n_{-1}$ and ${\left (\xi \right )_{1}} = {\left ({\xi ^{-}}\right )_{1}} = \sigma $ then $\xi $ implements ${\mathcal {S}}^{n+1}_{e}$ where $\lvert \sigma \rvert = e$ .

5. 5. If $\xi ^{-}$ implements ${\mathcal {S}}^n_{-1}$ and ${\left (\xi \right )_{1}} \neq {\left ({\xi ^{-}}\right )_{1}}$ then $\xi $ implements ${\mathcal {P}}_{e}$ for the least e such that no module of this form is assigned to any .

6. 6. If $\xi ^{-}$ implements ${\mathcal {P}}_{i}$ then $\xi $ implements ${\mathcal {L}}_{e}$ for the least e such that no implements ${\mathcal {L}}_{e}$ .

7. 7. If $\xi ^{-}$ implements a module of the form ${\mathcal {L}}_{e}$ or ${\mathcal {L}}^n_{e}$ then let $i < e$ (if it exists) be the largest value such that $\xi $ extends the outcome $\left \ulcorner \downarrow \right \urcorner $ of $ {\mathcal {L}}_{i}$ and m be the least such that no predecessor of $\xi $ implements ${\mathcal {L}}^m_{i}$ then $\xi $ implements ${\mathcal {L}}^m_{i}$ .

8. 8. If $\xi ^{-}$ implements a module of the form ${\mathcal {L}}_{e}$ or ${\mathcal {L}}^n_{e}$ and either $e = 0$ or for all $i < e$ $\xi ^{-}$ doesn’t extend the $\left \ulcorner \downarrow \right \urcorner $ outcome of ${\mathcal {L}}_{i}$ and $\sigma = {\left ({\xi }\right )_{1}}$ then $\xi $ implements the module ${\mathcal {H}}_{\sigma }$

Before we get into any further details, we give a high-level overview of how this is all supposed to work. If we suppose that we’ve just defined $\hat {T}(\sigma )$ and wish to define $\hat {T}(\sigma \widehat {\phantom {x}}\langle m\rangle )$ we start with the module ${\mathcal {H}}^+_{\sigma }$ which will specify a bunch of immediate extensions of $\hat {T}(\sigma )$ (placing them in T). We start by executing ${\mathcal {S}}^0_{e}, \lvert \sigma \rvert = e$ then ${\mathcal {S}}^0_{e -1 }$ and so forth all of which work to ensure the leftmost potential extension of $\hat {T}(\sigma )$ e-split or $e -1$ split or so on with all the remaining potential extensions. When we finally get to the module $ {\mathcal {S}}^0_{-1}$ it specifies that $\hat {T}(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ extends the leftmost branch as extended by all the modules ${\mathcal {S}}^0_{e'}, e' \leq e$ and the construction now splits into one part which works on the next module ${\mathcal {P}}_{e}$ along that path specified as an initial segment of $\hat {T}(\sigma \widehat {\phantom {x}}\langle 0\rangle )$ and another part where ${\mathcal {S}}^1_e$ starts working to define the node which will be extended by $ \hat {T}(\sigma \widehat {\phantom {x}}\langle 1\rangle )$ . After the module of the form ${\mathcal {P}}_{e}$ we work on the next module of the form ${\mathcal {L}}_{e}$ and then, if we are above the total outcome any ${\mathcal {L}}_{e'}, e' \leq e$ we implement the next helper module of the form ${\mathcal {L}}^m_{e'}$ . Finally, after those modules, comes the module ${\mathcal {H}}_{\sigma \widehat {\phantom {x}}\langle m\rangle }$ (assuming we took the path working on $\hat {T}(\sigma \widehat {\phantom {x}}\langle m\rangle )$ ) which guesses whether or not $\sigma \widehat {\phantom {x}}\langle m\rangle \in S$ . If it determines $\sigma \widehat {\phantom {x}}\langle m\rangle $ is in S then we go on to ${\mathcal {H}}^+_{\sigma \widehat {\phantom {x}}\langle m\rangle }$ . If it determines that $\sigma \widehat {\phantom {x}}\langle m\rangle $ is not in S then no module is assigned above that outcome preventing any path from being constructed.

With this in mind, we can now give a formal definition of $\hat {T}$ and its stagewise approximation.

Definition 6.6. We define $\hat {T}_{s}(\sigma ) = \delta ^{\xi }$ where and $\xi ^{-}$ implements the module ${\mathcal {H}}_{\sigma }$ . If no such then it is undefined. We define $ \hat {T}(\sigma )$ ) in a similar manner except we require that .

6.3 Modules

We now describe the operation of the modules. For this subsection, we describe the operation of the module assuming it is located at the node $\xi \in \mathbb {T}, \xi = (\alpha , \sigma )$ and executing at stage s. As we only define the outcome of the module at $\xi $ when $s_\xi> 0$ we understand the previous outcome of the module to be undefined when $s_\xi \leq 1$ .

6.3.1 Module ${ \mathcal {P}}_{e}$ .

The module ${\mathcal {P}}_{e}$ has outcomes $\left \ulcorner \neq \right \urcorner <_L \left \ulcorner \uparrow \right \urcorner $ and $(o, \delta ) \in \mathfrak {O}(\xi )$ iff $\delta = \langle \rangle $ and o is one of the above two outcomes.

If the previous outcome was $\left \ulcorner \neq \right \urcorner $ we retain that outcome. Otherwise, the module acts as follows.

Check if there is any $\tau \in T_s, \tau \succ \delta ^{\xi }$ with $\Phi _{e,s}\left (X\right ) \mid \tau $ . If found set the outcome to $\left \ulcorner \neq \right \urcorner $ and $\delta ^{\langle \alpha \widehat {\phantom {x}}\langle \left \ulcorner \neq \right \urcorner \rangle , \sigma \rangle }$ to be a $\prec $ maximal extension of $\tau $ in $T_s$ . Otherwise, set the outcome to $\left \ulcorner \uparrow \right \urcorner $ and, if this is the first stage at which that outcome is visited, set $ \delta ^{\langle \alpha \widehat {\phantom {x}}\langle \left \ulcorner \uparrow \right \urcorner \rangle , \sigma \rangle } = \delta ^{\xi }$ .

6.3.2 Module ${ \mathcal {L}}_{e}$ .

The module ${\mathcal {L}}_{e}$ has outcomes $\left \ulcorner \downarrow \right \urcorner = 0$ and $\left \ulcorner \nu \right \urcorner $ where $\nu \succ \xi $ and some module of the form ${\mathcal {L}}^n_{e}$ is assigned to $\nu $ (hence $\left \ulcorner \nu \right \urcorner> 0$ ). $ \mathfrak {O}(\xi )$ consists of all pairs $(o, \delta )$ where o is one of the allowed outcomes and $\delta = \langle \rangle $ . The outcome $\left \ulcorner \downarrow \right \urcorner $ corresponds to the state where $\Phi _{e}\left (X \oplus f\right )$ is total for all paths $f \in [T], f \succ \delta ^{\xi }$ and the outcome $\left \ulcorner \nu \right \urcorner $ where $\nu $ implements ${\mathcal {L}}^n_{e}$ corresponds to the state where all $f \in [T], f \succ \delta ^{\langle \alpha \widehat {\phantom {x}}\langle \left \ulcorner \nu \right \urcorner \rangle , \sigma \rangle }$ satisfy $\Phi _{e}\left (X \oplus f;n\right )\uparrow $ .

Intuitively, we can think of the operation of ${\mathcal {L}}^n_{e}$ as creating something of a link with ${\mathcal {L}}_{e}$ as in a ${\mathbf {0}}^{\prime \prime \prime }$ construction. When we visit ${\mathcal {L}}^n_{e}$ we effectively pause the operation of all the intervening modules between ${\mathcal {L}}_{e}$ and ${\mathcal {L}}^n_{e}$ and start meeting the modules extending ${\mathcal {L}}_{e}$ again until we find an extension which causes the e-th functional to converge on argument n at which point we return to ${\mathcal {L}}_{e}$ . Luckily, however, we don’t need the full machinery of links and can achieve this effect merely by letting the module $ {\mathcal {L}}^n_{e}$ manipulate the internal state of the unique visiting module ${\mathcal {L}}_{e}$ as defined here.

If $s_\xi = 0$ we initialize $\upsilon = \uparrow , \delta = \uparrow $ . If $s_\xi> 0$ and $\upsilon \uparrow $ then we visit the outcome $\left \ulcorner \downarrow \right \urcorner $ with $ \delta ^{\langle \alpha \widehat {\phantom {x}}\langle \left \ulcorner \downarrow \right \urcorner \rangle , \sigma \rangle } = \delta ^{\xi }$ . We leave it to the submodules of the form ${\mathcal {L}}^n_{e}$ to define $\upsilon , \eta $ when necessary.

If $s_\xi> 0$ and $\upsilon \downarrow $ with ${\mathcal {L}}^n_{e}$ assigned to $\upsilon $ then we check if there is a (maximal) extension $\tau \succ \delta , \tau \in T_s$ such that $\Phi _{e}\left (\tau ;n\right )\downarrow $ . If there is, then set $\delta ^{\upsilon ^{+}} = \tau $ where $\upsilon ^{+}$ is the unique successor of $\upsilon $ on $\mathbb {T}$ , set $\upsilon , \delta $ to be undefined, and visit the outcome $\left \ulcorner \downarrow \right \urcorner $ as above. Otherwise, visit the outcome $\left \ulcorner \upsilon \right \urcorner $ with $\delta ^{\langle \alpha \widehat {\phantom {x}}\langle \left \ulcorner \upsilon \right \urcorner \rangle ,\sigma \rangle } = \delta $ .

6.3.3 Module ${ \mathcal {L}}^n_{e}$ .

This node only has a single outcome $0$ and $\mathfrak {O}(\xi ) = {\left \{(0, \langle \rangle )\right \}}$ .

Let $\nu \prec \xi $ be the unique ancestor node implementing ${\mathcal {L}}_{e}$ . If $s_\xi = 0$ then set the variables $\upsilon , \delta $ for the module at node $\nu $ to be equal to $\xi $ and $\delta ^{\xi }$ respectively. If we are ever visited again, we visit our single outcome and rely on the node implementing ${\mathcal {L}}_{e}$ to have set $\delta ^{\langle \alpha \widehat {\phantom {x}}\langle 0\rangle ,\sigma \rangle }$ .

6.3.4 Module ${ \mathcal {H}}^+_{\sigma }$ .

This node only has a single outcome $0$ and $\mathfrak {O}(\xi ) = {\left \{(0, \langle \rangle )\right \}}$ . Let $\nu = (\alpha \widehat {\phantom {x}}\langle 0\rangle , \sigma )$ and if $s_\xi = 1$ then set $\delta ^{\nu }$ to be a maximal element in $T_s$ extending $ \delta ^{\xi }$ . If $s_\xi = n + 1$ (hence $s_\nu = n$ ) then let k be large and $\tau = \delta ^{\nu }\widehat {\phantom {x}}\langle k\rangle $ (in particular, large enough that if $\left \ulcorner \tau \right \urcorner> s$ ). Enumerate $\tau $ into $T_{s+1}$ and set ${\theta ^{\nu }_{n}} = \tau $ .

6.3.5 Module ${ \mathcal {S}}^n_{-1}$ .

This node only has a single outcome $0$ , but $\mathfrak {O}(\xi ) = {\left \{{(0, {\langle n\rangle }), (0, \langle \rangle )}\right \}}$ . This module doesn’t take any actions, merely split up input it gets between the two successor nodes as follows. Specifically, it sets $\delta ^{\langle \alpha \widehat {\phantom {x}}\langle 0\rangle , \sigma \widehat {\phantom {x}}\langle n\rangle \rangle } = {\theta ^{\xi }_{0}}$ , $\delta ^{\langle \alpha \widehat {\phantom {x}}\langle 0\rangle ,\sigma \rangle } = \delta ^{\xi }$ , and ${\theta ^{{\langle \alpha \widehat {\phantom {x}}\langle 0\rangle ,\sigma \rangle }}_{n}} = {\theta ^{\xi }_{n+1}}$ .

6.3.6 Module ${ \mathcal {S}}^n_{e}$ .

This node has outcomes $\left \ulcorner {\,\not |\,}\right \urcorner = 0$ , $\left \ulcorner \mid _0\right \urcorner = 1$ , $\left \ulcorner (\mid _1, n)\right \urcorner = 2 + \langle n, 0\rangle $ , and $\left \ulcorner (\uparrow ,n,m)\right \urcorner = \langle n, m+1\rangle $ . $\mathfrak {O}(\xi )$ consists of all pairs $ (o, \delta )$ where o is one of the allowed outcomes and $\delta = \langle \rangle $ . Remember that in what follows e-splitting refers to the notion relativized to X.

The outcome $\left \ulcorner {\,\not |\,}\right \urcorner $ corresponds to the case where ${\theta ^{\xi }_{0}}$ isn’t extended by an e-splitting in T (as ${\,\not |\,}$ indicates the strings are compatible). The other outcomes presume we do find some e-splitting $\tau _0, \tau _1$ extending ${\theta ^{\xi }_{0}}$ . The outcome $o = \left \ulcorner \mid _0\right \urcorner $ corresponds to the case where we find infinitely many elements in $\Theta ^{\xi }$ that extend to an e-splitting with $\tau _0$ . Outcomes of the form $\left \ulcorner (\mid _1, n)\right \urcorner $ correspond to the case where we only find n elements in $\Theta ^{\xi }$ that extend to an e-splitting with $\tau _0$ but infinitely many which extend to an e-splitting with $\tau _1$ . Finally, the outcomes of the form $\left \ulcorner (\uparrow ,n,m)\right \urcorner $ correspond to the case where we find n elements in $\Theta ^{\xi }$ extending to e-splittings with $\tau _0$ after which we find another m elements extending to an e-splitting with $\tau _1$ but infinitely many elements don’t extend to an e-splitting with either.

Let $\nu = \langle \alpha \widehat {\phantom {x}}\langle o\rangle , \sigma \rangle $ for whatever value we specify for the outcome o. We’ll ensure that ${\theta ^{\nu }_{0}}$ e-splits with ${\theta ^{\nu }_{n+1}}, n \in \omega $ in all cases except when $o = \left \ulcorner {\,\not |\,}\right \urcorner $ or $o = \left \ulcorner (\uparrow ,n,m)\right \urcorner $ . In the latter case, we’ll ensure that neither $\tau _0$ or $\tau _1$ e-split with any extension of ${\theta ^{{\nu }}_{n+1}}, n \in \omega $ (ensuring that if $f \succ {\theta ^{\nu }_{n+1}}$ then $\Phi _{e}\left (f \oplus X\right )\uparrow $ ). Since we don’t want to accidentally extend ${\theta ^{{\langle \alpha \widehat {\phantom {x}}\langle o'\rangle , \sigma \rangle }}_{0}}$ to an infinite path if $o'$ isn’t the true outcome we’ll ensure that every outcome except $\left \ulcorner {\,\not |\,}\right \urcorner $ corresponds to an incompatible value for ${\theta ^{{\langle \alpha \widehat {\phantom {x}}\langle o'\rangle , \sigma \rangle }}_{0}}$ of length at most $1 + \max \left \lvert \tau _0\right \rvert , \left \lvert \tau _1\right \rvert $ while always ensuring that ${\theta ^{{\nu }}_{0}} \succ {\theta ^{\xi }_{0}}$ .

We define $\delta ^{\nu } = \delta ^{\xi }$ for all potential outcomes o. When $s_\xi = 0$ we start by setting $\tau _0, \tau _1$ to be undefined and $\hat {n} = \hat {m} = 0$ . For $s_\xi> 0$ we consider the following cases.

• Case $\tau _0\uparrow :$ Check if there are $\tau _0, \tau _1 \in T_s$ with $\tau _0, \tau _1$ e-splitting extensions of ${\theta ^{\xi }_{0}}$ . If no such values are found, then visit outcome $o = \left \ulcorner {\,\not |\,}\right \urcorner $ and define $\Theta ^{\nu } = \Theta ^{\xi }$ . If such values are found, let $\tau _0, \tau _1$ be $\prec $ maximal extensions in $T_s$ of these e-splitting extensions of ${\theta ^{\xi }_{0}}$ , let $\hat {m} = \hat {n} = n$ and visit outcome $o = \left \ulcorner \mid _0\right \urcorner $ setting ${\theta ^{\nu }_{0}} = \tau _0$ .

• Case $\tau _0\downarrow : $ We break this up into a number of subcases. We search for some $n \leq s_\xi $ and $\tau ' \succ {\theta ^{\xi }_{n}}, \tau ' \in T_s$ that satisfy the following (picking the first case satisfied):

  • Case $\tau ', \tau _0 $ e-split with $\hat {n} < n \leq s_\xi $ : In this case, we let $o = \left \ulcorner \mid _0\right \urcorner $ and set ${\theta ^{\nu }_{s_\nu }}$ to be a $\prec $ maximal extension of $\tau '$ in $ T_s$ . Finally, we set $\hat {n} = \hat {m} = n$ .

  • Case $\tau ', \tau _1 $ e-split with $\hat {m} < n \leq s_\xi $ : In this case, we let $o = \left \ulcorner (\mid _1, \hat {n})\right \urcorner $ and set $\hat {m} = n$ and ${\theta ^{\nu }_{s_\nu +1}}$ be a $\prec $ maximal extension of $\tau '$ in $T_s$ .

    If this is the first time we’ve visited this outcome $s_\nu = 0$ . We pick k to be larger than any number mentioned so far in this construction, and set ${\theta ^{\nu }_{0}} =\tau _1\widehat {\phantom {x}}\langle k\rangle $ placing $ {\theta ^{\nu }_{0}}$ into $T_{s+1}$ .

  • Case Otherwise: In this case, we visit outcome $o = \left \ulcorner (\uparrow ,\hat {n},\hat {m})\right \urcorner $ . If this is the first time we’ve visited this outcome, set ${\theta ^{\nu }_{0}} =\tau _1\widehat {\phantom {x}}\langle k\rangle $ . Let $\tau '$ be a $ \prec $ maximal element of $T_s$ extending ${\theta ^{\xi }_{\hat {m} + s_\nu + 1}}$ and set ${\theta ^{\nu }_{s_\nu +1}} = \tau '$ .

6.3.7 Module ${ \mathcal {H}}_{\sigma }$ .

We note that we can assume (see Lemma B.7) we have a uniformly given total computable binary valued function (indeed functional) $\rho (\sigma , s_1, s_0)$ such that $\rho _1(\sigma , s_1) = \lim _{s_0 \to \infty } \rho (\sigma , s_1, s_0)$ is total, $S(\sigma ) = \lim _{s_1 \to \infty } \rho _1(\sigma , s_1)$ (both diverging if either does).

Morally speaking, this module has the outcomes $\left \ulcorner (i, \hat {n})\right \urcorner $ ordered lexicographically where $i \in {\left \{0,1\right \}}$ indicates whether the module guesses that $\sigma \notin S$ or $\sigma \in S$ and $\hat {n}$ indicates the value at which $\rho _1$ achieves its limit. However, to ensure that we never reinitialize any node as required by Condition 1 we also record a value m giving the number of times an outcome to the left of $(i, \hat {n})$ has been visited. Thus, the actual outcomes will be of the form $\left \ulcorner (i, \hat {n}, m)\right \urcorner = 2\langle \hat {n}, m\rangle +i$ . As our pairing function is strictly monotonic in both arguments this functions just as if we’d used outcomes of the form $\left \ulcorner (i, \hat {n})\right \urcorner $ and reinitialized outcomes after passing to their left. $\mathfrak {O}(\xi )$ consists of all pairs $(o, \delta )$ where o is one of the allowed outcomes and $\delta = \langle \rangle $ .

If $s_\xi = 0$ set $\tau $ to be a $\prec $ maximal extension of $\delta ^{\xi }$ in $T_s$ . If $s_\xi> 0$ we define k to be the number of times before stage s at which an outcome of the form $ \left \ulcorner (i, \hat {n}, m)\right \urcorner $ has been visited. Choose the lexicographically least pair $(i, \hat {n})$ such that for all $n \in [\hat {n}, \hat {n} + k]$ there are $k + 1$ distinct values $x^{n}_j \leq s, j < k +1$ such that $i = \rho (\sigma , n, x^{n}_j)$ . Note that, such a pair is always found since for large enough $\hat {n}$ we have $k = 0$ and $\rho (\sigma , \hat {n}, 0) \in {\left \{0,1\right \}}$ . We now visit the outcome $o = \left \ulcorner (i, \hat {n}, m)\right \urcorner $ where m is the number of times that we’ve visited an outcome of the form $\left \ulcorner (i', n, m)\right \urcorner $ with $(i',n)$ lexicographically before $(i, \hat {n})$ before stage s.

If this is the first time we’ve visited outcome o then pick c to be large, enumerate $\tau \widehat {\phantom {x}}\langle c\rangle $ into $T_{s+1}$ , and set $\delta ^{\langle \alpha \widehat {\phantom {x}}\langle o\rangle , \sigma \rangle } = \tau \widehat {\phantom {x}}\langle c\rangle $ .

6.4 Verification

Before we verify the individual requirements, we verify that the construction controls the paths through T in the manner desired.

Lemma 6.7. Suppose that implements a module of the form ${\mathcal {P}}_{e}, {\mathcal {L}}_{e}, {\mathcal {L}}^n_{e}, {\mathcal {H}}_{\sigma }$ and that for some $\nu $ with $\nu ^{-} = \xi $ we have $\lvert \tau \rvert = \left \lvert {\delta ^{\nu }}\right \rvert $ but $\tau \nsucc \delta ^{\hat {\xi }}$ for , $\hat {\xi }^{-} = \xi $ . Then there are only finitely many stages at which any module at $\hat {\nu } \succ \xi $ enumerates an element $\tau ' \succ \tau $ into T.

Note that this covers the case where ${\mathcal {H}}_{\sigma }$ doesn’t have any extension $\nu $ in the truepath because S doesn’t converge on $\sigma $ .

Proof By Condition 3 and Condition 2 (and the fact that no single module ever adds a full path) it is enough to show that there are only finitely many stages at which we visit a node $ \hat {\nu }$ with $\hat {\nu } \succneqq \xi $ and $\delta ^{\hat {\nu }}$ compatible with $\tau $ .

For the module ${\mathcal {L}}^n_{e}$ this is trivial as this module only has a single outcome. For the module ${\mathcal {H}}_{\sigma }$ we note that each time visit to an outcome $\left \ulcorner i, \hat {n}, m\right \urcorner $ ensures that all outcomes to the right visit strings that have never been visited before. As ${\mathcal {P}}_{e}$ can act at most once this case is also straightforward.

This leaves only the case ${\mathcal {L}}_{e}$ . If this module takes any of the finite outcomes the claim is evident and if this module takes the outcome $\left \ulcorner \downarrow \right \urcorner $ then the claim follows because $\delta ^{\nu } \succ \delta ^{\hat {\xi }}$ for all $\nu $ with $\nu ^{-} = \xi $ when $\hat {\xi }$ corresponds to the infinitary outcome.

Lemma 6.8. Suppose that and $\xi ^{-}$ implements a module of the form ${\mathcal {H}}^+_{\sigma }$ or ${\mathcal {S}}^n_{e}, e \geq 0$ then for each k there is some l such that if $\tau \succ \delta ^{\xi }\widehat {\phantom {x}}\langle k\rangle , \lvert \tau \rvert \geq l$ but $\tau \nsucc {\theta ^{\xi }_{n}}$ for any n then there are only finitely many stages at which some $\nu \succ \xi ^{-}$ enumerates an extension of $\tau $ .

Proof This is trivial if $\xi ^{-}$ implements a module of the form ${\mathcal {H}}^+_{\sigma }$ . Also, if there is no ${\theta ^{\xi }_{n}} \succ \delta ^{\xi }\widehat {\phantom {x}}\langle k\rangle $ then there is some last stage at which we visit any $\nu $ with $\nu ^{-} = \xi ^{-}$ with $\Theta ^{\nu }$ containing an extension of $\delta ^{\xi }\widehat {\phantom {x}}\langle k\rangle $ . So suppose that ${\theta ^{\xi }_{n}} \succ \delta ^{\xi }\widehat {\phantom {x}}\langle k\rangle $ . If $n> 0$ then, once we set ${\theta ^{\xi }_{n}}$ we never visit any $\nu \neq \xi $ with $\nu ^{-} = \xi ^{-}$ with ${\theta ^{\xi }_{m}} \succ \delta ^{\xi }\widehat {\phantom {x}}\langle k\rangle $ .

This leaves only the case where ${\theta ^{\xi }_{0}} \succ \delta ^{\xi }\widehat {\phantom {x}}\langle k\rangle $ . If $\xi $ corresponds to an outcome $\left \ulcorner (\uparrow ,n,m)\right \urcorner $ or $\left \ulcorner {\,\not |\,}\right \urcorner $ then we never again visit another extension of $ \xi ^{-}$ after visiting $\xi $ so the bound can be deduced by looking at the finitely many stages before that happens. Thus, we can assume $\xi $ corresponds either to $\left \ulcorner \mid _0\right \urcorner $ or $ \left \ulcorner (\mid _1, n)\right \urcorner $ . In this case, we can take $l = 1 + \max \left \lvert \tau _0\right \rvert , \left \lvert \tau _1\right \rvert $ by the remark in Section 6.3.6.

Lemma 6.9. For all $f \in \omega ^{\omega }$ , $f \in [T]$ iff $\left (\exists g \in \omega ^{\omega }\right )\!\left (\hat {T}(g) = f \right )$ .

Proof For the if direction suppose that $\hat {T}(g) = f$ . Since any module ${\mathcal {M}}_{\xi ^{-}}$ which sets $\delta ^{\xi } = \sigma $ guarantees that $\sigma \in T$ (and we always have $\sigma ^{-} \in T$ ) and we have that $ \hat {T}(g) \in T$ . For the other direction, suppose $f \neq \hat {T}(g)$ for any g. Let $\xi $ be a $\prec $ minimal element such that $\delta ^{\xi ^{-}} \prec f$ and, if $\Theta ^{\xi ^{-}}$ defined, with f extending some element in $\Theta ^{\xi ^{-}}$ but one of those conditions failing for $\xi $ . We then argue using Lemmas 6.7 and 6.8 that there is some $\tau \prec f$ such that only finitely many extensions of $\tau $ are enumerated into T.

The only other real difficulty occurs with nodes of the form ${\mathcal {L}}_{e}$ since those are the only modules that might be assigned to some where the above lemmas (or, for ${\mathcal {L}}_{e}$ , fact that we only visit incorrect outcomes finitely many times) don’t directly exclude the possibility that some module extending an outcome to the right of the true outcome of $\nu $ could contribute infinitely many elements compatible with f. Unless the outcome of $\nu $ is $\left \ulcorner \downarrow \right \urcorner $ this clearly can’t happen as in those cases we settle on the true outcome after finitely many stages. However, there will only be finitely many stages at which $\nu $ visits an outcome of the form $\left \ulcorner \eta \right \urcorner $ where $\delta ^{\eta } \prec f$ ensuring that the false outcomes of $\nu $ don’t cause a problem.

Note that, all modules excepting those of the form ${\mathcal {H}}_{\sigma }$ clearly have a well-defined leftmost outcome that’s visited infinitely often and by Lemma 6.7, in the case where $\xi $ implements ${\mathcal {H}}_{\sigma }$ and $\xi $ has no successor along the truepath is also a case where $\delta ^{\xi }$ can’t be extended to any path through T.

With this result in hand, we can now verify the properties claimed in Proposition 4.1.

Lemma 6.10. $\mathrm {rng} \hat {T} \subset T$ and $[\hat {T}] = [T]$ , that is, claim 1 of Proposition 4.1 holds.

Proof By Condition 2 anytime a module sets $\delta ^{\xi } = \tau $ ; it ensures that $\tau \in T$ . This ensures the first part of the claim holds. The second half of the claim is just Lemma 6.9.

Lemma 6.11. If and $\xi $ implements ${\mathcal {H}}_{\sigma }$ then $\xi $ has a well-defined outcome iff $S(\sigma )\downarrow $ and that outcome is always correct about the membership of $\sigma $ in S.

By well-defined outcome we mean a leftmost outcome that is visited infinitely often.

Proof Suppose that the module at $\xi $ has the true outcome $\left \ulcorner (i, \hat {n}, m)\right \urcorner $ . If $S(\sigma ) \neq i$ (including divergence) then, since $\rho _1(\sigma , s_1)$ (first limit), can be taken to be always defined, then for some $n> \hat {n}$ we have $\rho _1(\sigma , n) = 1 -i$ . Thus, for some k we have $\rho (\sigma , n, k') = 1 - i$ for all $k' \geq k$ contradicting the assumption that we visit this outcome more than $ n + k + 1$ times. Thus, ${\mathcal {H}}_{\sigma }$ is never incorrect and thus must not have an outcome whenever $S(\sigma )\uparrow $ .

Now suppose that $S(\sigma )\downarrow = i$ . For some minimal $\hat {n}$ we have $\rho _1(\sigma , s_1) = i$ for all $s_1 \geq \hat {n}$ . By minimality, there is some last stage at which any outcome of the form $\left \ulcorner (i, n, m)\right \urcorner $ with $n < \hat {n}$ is visited and as $\rho _1(\sigma , \hat {n}) = i$ there is some last stage at which any outcome of the form $\left \ulcorner (1 - i, \hat {n}, m)\right \urcorner $ is visited. Thus, after some point we never visit an outcome of the form $\left \ulcorner (i', n, m)\right \urcorner $ with $(i', n)$ lexicographically before $(i, \hat {n})$ and thus there is some m for which $\left \ulcorner (i, \hat {n}, m)\right \urcorner $ is the true outcome.

Lemma 6.12. For all $g \in \omega ^{\omega }$ , $\hat {T}(g)$ is total iff $g \in [S]$ iff $\hat {T}(g) \in [T]$ . Moreover, $\hat {T}(\sigma )\downarrow $ iff $S(\sigma )\downarrow $ and all are in S.

Proof We first verify the moreover claim. Note that, for any module besides ${\mathcal {H}}_{\sigma }$ there is always a well-defined true outcome. Thus, by an examination of the construction, we can see that the only way for $ \hat {T}(\sigma )$ to be undefined is either if for some the module of the form ${\mathcal {H}}_{\sigma '}$ on the truepath doesn’t have a true outcome guessing $\sigma ' \in S$ or if the module $ {\mathcal {H}}_{\sigma }$ on the truepath doesn’t have any true outcome. Clearly, if either of those cases obtain then we actually do have $\hat {T}(\sigma )\uparrow $ , so this result follows from Lemma 6.11.

The main claim follows trivially since $g \in [S]$ iff all $\sigma \prec g$ are elements in S.

Lemma 6.13. $\hat {T}$ is an f-tree.

Proof As $\hat {T}$ is clearly $\prec $ respecting it is enough to show that whenever $\hat {T}(\sigma )$ isn’t terminal then $i < j$ implies that $\hat {T}(\sigma \widehat {\phantom {x}}\langle i\rangle )$ and $\hat {T}(\sigma \widehat {\phantom {x}}\langle j\rangle )$ extend incompatible immediate extensions of $\hat {T}(\sigma )$ and $\hat {T}(\sigma \widehat {\phantom {x}}\langle i\rangle )$ is lexicographically below $\hat {T}(\sigma \widehat {\phantom {x}}\langle j\rangle )$ . However, this is immediate from the operation of ${\mathcal {H}}^+_{\sigma }$ and the fact that nodes of the form ${\mathcal {S}}^n_{e}$ maintain these properties.

We can use this to prove the homeomorphism claim from Proposition 4.1.

Lemma 6.14. $\hat {T}$ is a homeomorphism of $[S]$ with $[T]$ . That is claim 2 of Proposition 4.1 holds.

Proof By Lemma 6.12 we know that $[T]$ is the image of $[S]$ under $\hat {T}$ . Evidently, both $\hat {T}$ and its inverse are continuous, so it remains only to show that $\hat {T}$ is injective. However, this follows from Lemma 6.13.

Lemma 6.15. If $\Upsilon _2$ is a computable functional then we can uniformly find computable functionals $\Upsilon , \hat {\Upsilon }$ such that if $\Upsilon _2({X}^{\prime \prime }) = S$ then $\Upsilon (X) = T$ and $\hat {\Upsilon }({X}^{\prime \prime }) = \hat {T}$ where $T, \hat {T}$ are as constructed above.

Proof To compute $\hat {T}(\sigma )$ from ${X}^{\prime \prime }$ we simply (iteratively) identify the leftmost outcome of nodes on $\mathbb {T}$ to identify elements in and search for a node and $\xi ^{-}$ implementing ${\mathcal {H}}_{\sigma }$ and return $\delta ^{\xi }$ . It’s possible that when working to compute $\hat {T}(\sigma )$ we next discover such a node $\xi $ . However, this can only happen when S fails to converge on some $\sigma ' \prec \sigma $ in which case $\hat {T}(\sigma )$ is properly undefined anyway. The uniformity can be read off the construction (note the only use of S is via Lemma B.7 which is fully uniform).

Lemma 6.16. If $f \in [T]$ then $f \nleq _{\mathbf {T}} X$ . That is claim 3 of Proposition 4.1 holds.

Proof Suppose the claim fails and for some $f \in [T], f = \Phi _{e}\left (X\right )$ for some total $\Phi _{e}\left (X \right )$ . By Lemma 6.9 we have $f = \hat {T}(g)$ . Thus, for some with $\xi ^{-}$ implementing ${\mathcal {P}}_{e}$ we have $f \succ \delta ^{\xi }$ . As $f = \hat {T}(g)$ we know that extends to a node implementing some ${\mathcal {H}}^+_{\sigma }$ and thus T contains incompatible $\tau _0, \tau _1 \succ \delta ^{\xi ^{-}}$ . Thus, by the operation of ${\mathcal {P}}_{e}$ we know that $\delta ^{\xi } \mid \Phi _{e}\left (X\right )$ contradicting the supposition.

Lemma 6.17. Suppose and $\xi ^{-}$ implements ${\mathcal {L}}_{e}$ then $\Phi _{e}\left (f \oplus X\right )$ is total iff the true outcome of $\xi ^{-}$ is $\left \ulcorner \downarrow \right \urcorner $ .

Proof Suppose $\xi ^{-}$ has true outcome $\left \ulcorner \downarrow \right \urcorner $ but that $\Phi _{e}\left (f \oplus X;n\right )\uparrow $ . For some with $\nu ^{-} \succ \xi $ implementing ${\mathcal {L}}^n_{e}$ we have $f \succ \tau $ and by operation of ${\mathcal {L}}_{e}$ and ${\mathcal {L}}^n_{e}$ we can only have true outcome $\left \ulcorner \downarrow \right \urcorner $ if $\Phi _{e}\left (\tau \oplus X;n\right )\downarrow $ . This contradicts our assumption.

On the other hand, if $\xi ^{-}$ has true outcome $\left \ulcorner \nu \right \urcorner $ then $\nu \succ \xi ^{-}$ implements some ${\mathcal {L}}^n_{e}$ . The operation of ${\mathcal {L}}_{e}$ guarantees that if we ever saw some $\tau \succ \delta ^{\xi }, \tau \in T$ with $\Phi _{e}\left (\tau \oplus X;n\right )\downarrow $ then we wouldn’t have true outcome $\left \ulcorner \nu \right \urcorner $ . Hence, we must have $\Phi _{e}\left (f \oplus X;n\right )\uparrow $ . As the operation of ${\mathcal {L}}_{e}$ ensures that one of our outcomes is true, this establishes the claim.

Lemma 6.18. If $g \in [S]$ then $g \oplus {X}^{\prime \prime } \equiv _{\mathbf {T}} {\left (\hat {T}(g) \oplus X\right )}^{\prime \prime } \equiv _{\mathbf {T}} \hat {T}(g) \oplus {X}^{\prime \prime }$ . That is claim 4 of Proposition 4.1 holds.

Note that, as $[T]$ is the image of $[S]$ under $\hat {T}$ every $f \in [T]$ has this property relative to some g.

Proof Let $g \in [S]$ . By Lemma 6.14, $\hat {T}(g) = f$ for some total f. Since whenever $\hat {T}(\sigma )\downarrow $ by Lemma 6.15 we can find $\hat {T}(\sigma )$ computably in ${X}^{\prime \prime }$ it follows that $f \leq _{\mathbf {T}} g \oplus {X}^{\prime \prime }$ . To see that $g \leq _{\mathbf {T}} f \oplus {X}^{\prime \prime }$ note that, by Lemmas 6.15 and 6.13 we can inductively recover the unique path g with $\hat {T}(g) = f$ computably in $f \oplus {X}^{\prime \prime }$ .

Clearly ${\left (f \oplus X\right )}^{\prime \prime } \geq _{\mathbf {T}} f \oplus {X}^{\prime \prime }$ . Thus, to complete the proof, it is sufficient to show that ${\left (f \oplus X\right )}^{\prime \prime } \leq _{\mathbf {T}} g \oplus {X}^{\prime \prime }$ . By a well-known result, it is enough to show that $g \oplus {X}^{\prime \prime }$ can computably decide whether e is an index for a total computable function in $f \oplus X$ . However, by Lemma 6.17 we can decide this question by searching for with $\xi $ implementing ${\mathcal {L}}_{e}$ and $\xi = \langle \alpha ,\sigma \rangle $ with $\sigma \prec g$ and determining the outcome of $\xi $ . By Lemma 6.15 this can be done computably in $g \oplus {X}^{\prime \prime }$ .

Lemma 6.19. If $f \in [T], Y = \Phi _{e}\left (f \oplus X\right )$ and there is some $\tau \prec f$ with no e-splitting $\tau _0, \tau _1 \succ \tau $ with $\tau _0, \tau _1 \in T$ then $Y \leq _{\mathbf {T}} X$ .

As remarked above, we mean e-splitting relativized to X.

Proof We can compute $Y{{\restriction _{n}}}$ from X by returning $\Phi _{e}\left (\tau ' \oplus X\right ){{\restriction _{n}}}$ for the first $\tau ' \succ \tau $ in T we can find for which this is a string of length n. As $Y = \Phi _{e}\left (f \oplus X\right )$ and $f \succ \tau , f \in [T]$ there must be some such $\tau '$ and by the lack of e-splitting extensions there is no possibility of an incompatible value.

Lemma 6.20. If $f \in [T]$ and $Y \leq _{\mathbf {T}} f \oplus X$ then either $Y \leq _{\mathbf {T}} X$ or $f \leq _{\mathbf {T}} Y \oplus {X}^{\prime \prime }$ . That is claim 5 of Proposition 4.1 holds.

Proof Suppose that $Y = \Phi _{e}\left (f \oplus X\right )$ and, by Lemma 6.14, that $f = \hat {T}(g)$ . Let $r(\sigma , n)$ where $\lvert \sigma \rvert> e$ be the outcome of the module ${\mathcal {S}}^n_{e}$ assigned to some and where $\xi ^{-} = (\alpha , \sigma )$ . Note that, for all $n, \sigma \in \mathrm {dom} \hat {T}$ with $\lvert \sigma \rvert> e$ , $\hat {T}(\sigma \widehat {\phantom {x}}\langle n\rangle ) \succ {\theta ^{m(\sigma , n)}_{0}}$ . This is because all modules of the form ${\mathcal {S}}^n_{e}, e \geq 0$ always output a leftmost branch extending the leftmost branch they receive as input.

If there is some $\tau \prec f$ not extended by any e-splitting extensions then by Lemma 6.19 we are done. So we may suppose this isn’t the case and show that this implies $g \leq _{\mathbf {T}} Y \oplus {X}^{\prime \prime }$ which, by Lemma 6.18 is equivalent to showing $f \leq _{\mathbf {T}} Y \oplus {X}^{\prime \prime }$ .

Suppose we know $\sigma , n'$ and that $\sigma \widehat {\phantom {x}}\langle n\rangle \prec g$ for some $n \geq n'$ (where $\lvert \sigma \rvert> e$ ) we demonstrate how to check if $n = n'$ or $n> n'$ computably in $Y \oplus {X}^{\prime \prime }$ . This will suffice since, applying this repeatedly, we can compute g from $Y \oplus {X}^{\prime \prime }$ .

Using ${X}^{\prime \prime }$ we can compute $\xi = m(\sigma , n')$ and $r(\sigma , n')$ . If $n = n'$ then we would have $f \succ {\theta ^{\xi }_{0}}$ while if $n> n'$ then $f \succ {\theta ^{\xi }_{k}}, k> 0$ .

If we have $r(\sigma , n') = \left \ulcorner {\,\not |\,}\right \urcorner $ then that entails ${\theta ^{\xi ^{-}}_{0}}$ has no e-splitting extensions. Thus, by our supposition f can’t extend ${\theta ^{\xi ^{-}}_{0}}$ , so we can conclude $n \neq n'$ .

Suppose instead that $r(\sigma , n') = \left \ulcorner (\uparrow , \hat {n},\hat {m})\right \urcorner $ . In this case, the module $\mathcal {S}^{n'}_{e}$ at $\xi ^{-}$ must have identified some e-splitting $\tau _0, \tau _1$ of $ {\theta ^{\xi ^{-}}_{0}}$ and that no ${\theta ^{\xi }_{k}}, k> 0$ has an extension in T which e-splits with either $\tau _0$ or $\tau _1$ . However, as $\Phi _{e}\left (f \oplus X\right )$ is total, if f doesn’t extend either $\tau _0$ or $\tau _1$ then some initial segment of f must e-split with either $\tau _0$ or $\tau _1$ ( $\Phi _{e}\left (f \oplus X\right )$ can’t agree with incompatible strings). Hence, we can’t have $f \succ {\theta ^{\xi }_{k}}, k> 0$ so we must have $n = n'$ .

This leaves only the case in which $r(\sigma , n')$ gives one of the incompatible (i.e., e-splitting) outcomes. In this case, we simply test if Y is compatible with $\Phi _{e}\left ({\theta ^{\xi }_{0}} \oplus X\right )$ . If so, then $n = n'$ . If not, then $n> n'$ .

These lemmas, taken together, verify all parts of Proposition 4.1 except 6 which is evident from the construction.