# A ${\Pi}^{0}_{2}$ Singleton of Minimal Arithmetic Degree

Peter M. Gerdes  Indiana University, Bloomington
Department of Mathematics
Bloomington, IN<EMAIL_ADDRESS>http://invariant.org

###### Abstract.

In the study of the arithmetic degrees the $\omega\mathchar
45\relax\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\mathchar 45\relax\text{REA}$
sets in that structure than about the Turing degrees. Indeed, even basic
questions such as the existence of a $\omega\mathchar 45\relax\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\mathchar
45\relax\text{REA}$ set is arithmetically minimal. Finally, it constructs a
${\Pi}^{0}_{2}$ singleton of minimal arithmetic degree. Not only is this a
result of considerable interest in it’s own right, constructions of
${\Pi}^{0}_{2}$ singletons often pave the way for constructions of
$\omega\mathchar 45\relax\text{REA}$ sets with similar properties. Along the
way, a number of interesting results relating arithmetic reducibility and
rates of growth are established.

###### Key words and phrases:

computability theory,arithmetic degrees,arithmetic reducibility,minimal
degree,singleton,REA,arithmetic singleton,implicit definability,Turing
reducibility

###### 2020 Mathematics Subject Classification:

Primary 03D28, 03D30; Secondary (03D60)

##  1\. Introduction

In the study of the arithmetic degrees (the degree structure induced by
relative arithmetic definability, $\leq_{\mathbf{a}}$) the $\omega\mathchar
45\relax\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\mathchar
45\relax\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}}}^{\prime})$ (the Turing degrees less than or equal
to ${{\mathbf{0}}}^{\prime}$) via the Shoenfield jump inversion [13] the
$\omega\mathchar 45\relax\text{REA}$ sets allow us to similarly identify the
range of the arithmetic jump on
$\mathscr{D}_{\mathbf{a}}({\mathbf{0}_{\mathbf{a}}}^{\prime})$ with the
degrees of the sets $\omega\mathchar 45\relax\text{REA}$ in
${\mathbf{0}_{\mathbf{a}}}^{\prime}$ [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\mathchar
45\relax\text{REA}$ sets in that structure. Even seemingly basic questions
remain open. For instance, whether or not there are any $\omega\mathchar
45\relax\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\mathchar 45\relax\text{REA}$ sets suggests that $\omega\mathchar
45\relax\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\mathchar
45\relax\text{REA}$ sets which join to ${\mathbf{0}_{\mathbf{a}}}^{\prime}$
[14] in contrast to the non-diamond theorem in the r.e. degrees [8].

While we don’t settle the existence of an $\omega\mathchar 45\relax\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
${\Pi}^{0}_{2}$ singleton not arithmetically equivalent to any
${\mathbf{0}}^{(\alpha)}$).

######  Corollary 4.3.

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

While the degrees of $\omega\mathchar 45\relax\text{REA}$ sets are properly
contained in the degrees of singletons, results about ${\Pi}^{0}_{2}$
singletons have often paved the way for corresponding results about
$\omega\mathchar 45\relax\text{REA}$ sets, e.g., Harrington’s construction of
an arithmetically low ${\Pi}^{0}_{2}$ singleton [5] or arithmetically
incomparable ${\Pi}^{0}_{2}$ singletons [4] both111These are both unpublished
notes that sketch the approach. See [15] or (draft work) [3] for more rigorous
write ups of some of the results. foreshadowed related constructions of
$\omega\mathchar 45\relax\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\mathchar 45\relax\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_{e}^{X}}$ 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)}\mathpunct{\downarrow}$ and
${\Phi_{i}\\!\left(X;y\right)}\mathpunct{\uparrow}$ respectively. Convergence
in $s$-steps is denoted by
${\Phi_{i}\\!\left(X;y\right)}\mathpunct{\downarrow}_{s}\iff{\Phi_{i,s}\\!\left(X;y\right)}\mathpunct{\downarrow}$
and it’s negation by ${\Phi_{i}\\!\left(X;y\right)}\mathpunct{{}_{s}}$.

We write elements of $2^{<\omega}$ and $\omega^{<\omega}$ (referred to as
strings) like
$\mathopen{\langle}x_{0},x_{1},\ldots,x_{n-1}\mathclose{\rangle}$ with
$\mathopen{\langle}\mathclose{\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
$\mathrel{\mid}$, compatibility by ${\mathrel{\,\not|\,}}$ and use
$\mathbin{<_{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 $\mathopen{\langle}i\mathclose{\rangle}^{n}$ to denote
$\mathopen{\langle}i\mathclose{\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)}\mathpunct{\downarrow}$
and relativize to define ${\Phi_{e}\\!\left(\sigma\mathbin{\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}}\mathopen{\langle}i\mathclose{\rangle}\right\urcorner<\left\ulcorner\alpha\widehat{\phantom{x}}\mathopen{\langle}j\mathclose{\rangle}\right\urcorner$
and $\left\ulcorner\mathopen{\langle}\mathclose{\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
$\mathopen{\langle}x,y\mathclose{\rangle}=\frac{1}{2}(x+y)(x+y+1)+y$ (this is
a bijection of $\omega^{2}$ with $\omega$) and we let
$\left(\mathopen{\langle}a,b\mathclose{\rangle}\right)_{0}=a$ and
$\left(\mathopen{\langle}a,b\mathclose{\rangle}\right)_{1}=b$. We define
$A\mathbin{\oplus}B$, $\mathbin{\oplus}_{n\in S}X_{n}$, ${X}^{[n]}$ and
${X}^{[<n]}$ 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}}}^{\prime}$. 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 $\widehat{T}\subset T$.

We abuse notation and write $T\mathpunct{\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\\}}$,
$\mathchoice{\text{\raise 4.30554pt\hbox{$T$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T\,/\,\sigma}{T\,/\,\sigma}{T\,/\,\sigma}$ for
${\left\\{\tau\mid\sigma\widehat{\phantom{x}}\tau\in T\right\\}}$ (with
$\mathchoice{\text{\raise 4.30554pt\hbox{$\tau$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{\tau\,/\,\sigma}{\tau\,/\,\sigma}{\tau\,/\,\sigma}$
the unique element of $\mathchoice{\text{\raise
4.30554pt\hbox{${\left\\{\tau\right\\}}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{{\left\\{\tau\right\\}}\,/\,\sigma}{{\left\\{\tau\right\\}}\,/\,\sigma}{{\left\\{\tau\right\\}}\,/\,\sigma}$
) and
$T^{\left\langle\sigma\right\rangle}=\sigma\mathbin{\ast}\mathchoice{\text{\raise
4.30554pt\hbox{$T$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T\,/\,\sigma}{T\,/\,\sigma}{T\,/\,\sigma}$ 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
over222In $2^{<\omega}$ we can, computably in $T$, find the least extension of
$\sigma\in T$ which either has no extensions in $T$ or two extensions in $T$,
provided we assume such an extension always exists. $2^{<\omega}$. We use the
term f-tree for a $\prec,\mathbin{<_{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}}\mathopen{\langle}n\mathclose{\rangle})(\lvert
T(\sigma)\rvert)$ is strictly monotonic in $n$ (on it’s domain). A f-tree
$\widehat{T}$ is a subtree of an f-tree $T$ if
$\operatorname{rng}\widehat{T}\subset\operatorname{rng}T$. An f-tree $T$ is
branching if every non-terminal element in $\operatorname{dom}T$ has multiple
immediate successors, (weakly) $\omega$-branching if every non-terminal
element in $\operatorname{dom}T$ has infinitely many immediate successors and
$\omega$-branching if whenever $\sigma\in\operatorname{dom}T$ is non-terminal
than
$\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\in\operatorname{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}$,
$\mathchoice{\text{\raise 4.30554pt\hbox{$T$}\Big{/}\lower
4.30554pt\hbox{$\tau$}}}{T\,/\,\tau}{T\,/\,\tau}{T\,/\,\tau}$ ,
$\sigma\mathbin{\ast}T$ and $T^{\left\langle\tau\right\rangle}$ to f-trees in
the obvious way.

We write $\sigma\mathrel{{\Vdash}}\psi$ to denote forcing over $2^{<\omega}$
or $\omega^{<\omega}$ and $\sigma\mathrel{{\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. ${\Pi}^{0}_{n}$ Classes and $\omega\mathchar 45\relax\text{REA}$
sets

A ${\Pi}^{0}_{n}$ set class is the set of elements in
$\mathcal{P}\left(\omega\right)$ (identified with $2^{\omega}$) that satisfy
some ${\Pi}^{0}_{n}$ formula with a free set variable. A ${\Pi}^{0}_{n}$
function class is defined likewise for elements in $\omega^{\omega}$. We will
use the term ${\Pi}^{0}_{n}$ class without further specification to refer to a
${\Pi}^{0}_{n}$ set class. We note that if $n>0$ then
$\mathscr{F}\subset\omega^{\omega}$ is a ${\Pi}^{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
QyR(f\mathpunct{\restriction_{y}},x,\ldots,y)$ (and likewise for a
${\Pi}^{0}_{n}$ set class).

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

######  Lemma 2.1.

Every ${\Pi}^{0}_{1}$ function class is homeomorphic with a ${\Pi}^{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}}\mathopen{\langle}1\mathclose{\rangle}^{\omega}\mid\sigma\in
2^{<\omega}\right\\}}$ given by setting
$\Gamma(\mathopen{\langle}\mathclose{\rangle})=\mathopen{\langle}\mathclose{\rangle}$
and
$\Gamma(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle})=\Gamma(\sigma)\widehat{\phantom{x}}\mathopen{\langle}1\mathclose{\rangle}^{i}\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle}$.

The other direction is slightly more tricky. Given a ${\Pi}^{0}_{2}$ class
$\mathscr{C}$ such that $X\in\mathscr{C}\iff\left(\forall
z\right)\\!\left(\exists y\right)\\!R(X\mathpunct{\restriction_{y}},z,y)$
define $\Gamma(X)(2z)$ to be the least $y$ such that
$R(X\mathpunct{\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\mathbin{\oplus}\epsilon$ and place $\sigma\in T$ iff
$\left(\forall
l<\lvert\tau\rvert\right)\\!R(\epsilon\mathpunct{\restriction_{l}},\tau(l),l)$.
If $\lvert\sigma\rvert\equiv 1\pmod{2}$ then place $\sigma\in T$ iff either
$\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle}\in T$ or
$\sigma\widehat{\phantom{x}}\mathopen{\langle}1\mathclose{\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 ${\Pi}^{0}_{n}$ singleton is a set/function
that’s the only element in a ${\Pi}^{0}_{n}$ class. Recall that every
$\omega\mathchar 45\relax\text{REA}$ set is a ${\Pi}^{0}_{2}$ singleton but
not vice-versa. For the interested reader unfamiliar with the $\omega\mathchar
45\relax\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\mathbin{\oplus}{W_{i}^{X}}$ $\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\mathbin{\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
$\lVert\kappa\rVert_{\mathcal{O}}$. $\overrightarrow{\mathcal{O}}$ is the set
of limit notations, $\vphantom{\mathcal{O}}{}^{+}{\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}}\left(n\right)$. 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\mathrel{\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\mathpunct{\restriction_{x}}=A_{s}\mathpunct{\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 ${\Pi}^{0}_{2}$
singletons.

######  Lemma 2.2.

If $f$ is a ${\Pi}^{0}_{1}$ function singleton then every $g$ majorizing $f$
uniformly computes $f$. If $X$ is a ${\Pi}^{0}_{2}$ singleton then there is
some $f\mathrel{\equiv_{\mathbf{T}}}X$ such that every $g$ majorizing $f$
uniformly computes $X$. Moreover, if $X$ isn’t arithmetic than 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 $\widehat{T}$ consist of all $\sigma\in T$
majorized by $g$ (on $\operatorname{dom}\sigma$). To compute
$f\mathpunct{\restriction_{l}}$ from $g$, search for some $\sigma,k$ such that
$\lvert\sigma\rvert=l$ and
$\left(\forall\tau\in\widehat{T}\right)\\!\left(\lvert\tau\rvert=k\implies\tau\succ\sigma\right)$.
As $\widehat{T}$ is finitely branching and
$[\widehat{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\mathchar
45\relax\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\mathchar
45\relax\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 (e.g., see Sack’s proof of the Density
theorem [10]). However, translating this approach to the $\omega\mathchar
45\relax\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\mathchar 45\relax\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 ${\Pi}^{0}_{2}$ singleton (and hence
$\omega\mathchar 45\relax\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}}}^{\prime}$-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 forcing333However, a modification of the same argument will
allow one to show that no amount of non-domination is enough to compute a
generic with respect to local forcing on some sufficiently definable pruned
perfect tree $T_{e}$. The construction is as before, except now we compute a
pair $T_{e},X_{e}$ from each path on $T$. We proceed much as before but with
the addition that we achieve immediate victory if we can force $X_{e}$ to
leave $T_{e}$. However, this leaves open the possibility we compute some
$\omega$-generic relative to local forcing on some more complicated tree. 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 a arithmetically escaping function.

This possibility is rendered more plausible by the fact that the 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 $\mathrel{{\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

$\varphi\overset{\text{\tiny 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^{\prime}\right)\\!\left(\psi(x,y)\land\psi(x,y^{\prime})\implies
y=y^{\prime}\right)$

By assumption, $X\models\varphi$ and therefore there is some $\sigma\prec
X,\sigma\in T_{m}$ with $\sigma\mathrel{{\Vdash}_{T_{m}}}\varphi$. Let
$\widehat{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}\mathrel{{\Vdash}_{T_{m}}}\psi(x,y_{i})$ such that every path through
$[\widehat{T}]$ extends some $\tau_{i}$. Since all $Y\in[\widehat{T}]$ are $m$
locally generic every such $Y\models\varphi$. Thus, for all
$Y\in[\widehat{T}]$ there are $x,y$ such that
$Y\mathrel{{\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 $\widehat{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[\widehat{T}]$ then $g$ majorizes the function $f_{Y}$ where
$f_{Y}(x)=y\iff Y\models\psi(x,y)$ and as $X\in[\widehat{T}]$ it follows that
$g$ majorizes $f$. As $T_{m}\geq_{\mathbf{T}}\widehat{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}}}^{\prime}$
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 a 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}}\mathopen{\langle}m\mathclose{\rangle}$ such that
$T(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle})\mathpunct{\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)}\mathrel{\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)}\mathpunct{\uparrow}\right)$

  2. (2)

(Non $e$-splitting) for all $\tau,\tau^{\prime}\in T_{e}$,
$\tau,\tau^{\prime}$ don’t $e$-split

  3. (3)

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

We then build $f\in\mathop{\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 $\mathrel{{\Vdash}}$ a condition $\sigma$ and a
sentence $\psi$ with a single free (number) variable let
$\psi^{\mathrel{{\Vdash}}}\left(\sigma\right)$ denote the longest string
$\tau\in 2^{<\omega}$ such that $n\in\operatorname{dom}\tau$ implies
$\sigma\mathrel{{\Vdash}}\psi(n)\land\tau(n)=1$ or
$\sigma\mathrel{{\Vdash}}\lnot\psi(n)\land\tau(n)=0$. We extend this in the
obvious way to infinite paths.

In other words, $\psi^{\mathrel{{\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 ${\Pi}^{0}_{n}$ formula with a single
free variable then

  1. (1)

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

  2. (2)

A pruned f-tree $T$ is totally non-$e$-fsplitting if there are no
$\tau,\tau^{\prime}$ 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^{\prime}$ then
$T(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle})$,
$T(\sigma\widehat{\phantom{x}}\mathopen{\langle}n^{\prime}\mathclose{\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 $\mathrel{{\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\mathbin{\oplus}T$.

###### Proof.

As every path through $T$ is $n$-generic with respect to
$\mathrel{{\Vdash}_{T}}$ if $f\mathrel{{\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}^{\mathrel{{\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}^{\mathrel{{\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 $\widehat{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 $\mathrel{{\Vdash}_{T}}$. Moreover, we note that
since
$\sigma\mathrel{{\Vdash}_{T}}\psi\implies\sigma\mathrel{{\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}\mathbin{\cup}{\Pi}^{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$,
$\widehat{T}$ arithmetic in $T$ that is either totally non-$e$-fsplitting or
totally $e$-fsplitting.

We consider two cases.

  1. Case 1

: Suppose some $\sigma\in\operatorname{rng}T$ isn’t extended by any
$e$-fsplit $\tau_{0},\tau_{1}\in\operatorname{rng}T$. Let
$\widehat{T}=T^{\left\langle\sigma\right\rangle}$, the subtree of $T$ above
$\sigma$. Clearly, $\widehat{T}$ is totally non-$e$-fsplitting.

  2. Case 2

: Suppose Case 1 doesn’t hold. We now seek to build a perfect pruned
$\omega$-branching totally $e$-fsplitting subtree $\widehat{T}$ of $T$. Absent
the need to be $\omega$ branching we could simply search for an $e$-fsplitting
pair extending $\widehat{T}(\sigma)$ on $T$ to define
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle}),\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}1\mathclose{\rangle})$.
However, if we then later tried to define
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle})$
we might be unable to choose a value for
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle})$
which $e$-fsplits with
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle})$.
We could further extend
$T(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\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
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle})$
it $e$-fsplits with extensions of infinitely many other strings of the form
$\widehat{T}(\sigma)\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle}$.

To define
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}1\mathclose{\rangle})$
we essentially repeat the above process and choose one of the infinitely many
extensions which $e$-fsplits with
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\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
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle})$
and ensure that we have an infinite set of options that $e$-fsplit with
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}i^{\prime}\mathclose{\rangle}),i^{\prime}\leq
i$ to use for
$\widehat{T}(\sigma\widehat{\phantom{x}}\mathopen{\langle}i^{\prime}\mathclose{\rangle}),i^{\prime}>i$
(and to do this for every $\sigma$).

We build an f-tree $V\\!:\omega^{<\omega}\mapsto\omega^{<\omega}$ and define
$\widehat{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\mathopen{\langle}\mathclose{\rangle}\right\urcorner$ we
begin by defining
$V(\mathopen{\langle}\mathclose{\rangle})=\mathopen{\langle}\mathclose{\rangle}$.
Note that, since
$i<j\implies\left\ulcorner\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle}\right\urcorner<\left\ulcorner\sigma\widehat{\phantom{x}}\mathopen{\langle}j\mathclose{\rangle}\right\urcorner$
if
$\left\ulcorner\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\right\urcorner=s$
then we’ve already defined
$V(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\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}}\mathopen{\langle}i\mathclose{\rangle})$ for
$V(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle})$ not yet
defined at $s$. To ensure that $\widehat{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}}\mathopen{\langle}n\mathclose{\rangle})$, i.e.,
$\left\ulcorner\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\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}}\mathopen{\langle}n\mathclose{\rangle})=\tau_{i}$
and $S^{\sigma}_{s+1}=U_{i}$, initialize
$S^{\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}}$ to
${\left\\{\tau_{i}\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\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 $\widehat{T}=T\circ V$
arithmetically in $T$.

We claim that $\widehat{T}$ is a totally $e$-fsplitting perfect
$\omega$-branching subtree of $T$. Our definition of $S^{\sigma}_{s}$ ensures
that $\widehat{T}$ is $\omega$-branching and that $\widehat{T}$ is perfect.
Since whenever we define
$V(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle})$ we
limit
$T(V(\sigma\widehat{\phantom{x}}\mathopen{\langle}n^{\prime}\mathclose{\rangle})),n^{\prime}>n$
to extensions of strings which $e$-fsplit with
$T(V(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}))$ it
follows that $\widehat{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}\mathpunct{\restriction_{n}}=T_{n}\mathpunct{\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\mathpunct{\restriction_{e+1}}$ then $\mathchoice{\text{\raise
4.30554pt\hbox{$f$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{f\,/\,\sigma}{f\,/\,\sigma}{f\,/\,\sigma}\in[T^{\sigma}_{e+1}]$
and thus, as $T^{\sigma}_{e+1}$ is arithmetic, by Lemma 3.7 either $X$ is
arithmetic or $\mathchoice{\text{\raise 4.30554pt\hbox{$f$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{f\,/\,\sigma}{f\,/\,\sigma}{f\,/\,\sigma}\mathrel{\equiv_{\mathbf{T}}}f$
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}}}^{\prime}$). And maybe we don’t
have to completely give up the idea of using non-domination strength to show
that no $\omega\mathchar 45\relax\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}}}^{\prime}$
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 less 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\mathchar 45\relax\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 ${\Pi}^{0}_{n}$
singleton. Similarly, no $n$-generic $f\in\omega^{\omega}$ is a
${\Pi}^{0}_{n}$ function singleton.

###### Proof.

Suppose that $X$ is the unique set such that $X\models\psi$ for some
${\Pi}^{0}_{n}$ formula (with a set constant) $\psi$. By $n$-genericity we
must have $X\mathpunct{\restriction_{l}}\mathrel{{\Vdash}_{T}}\psi$ for some
$l$. As $T$ is perfect there is some $n$-generic path $Y\succ
X\mathpunct{\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\mathrel{{\Vdash}}\lnot\Psi(x)\right)\right\\}}$. $S$
is a ${\Sigma}^{1}_{n}$ set and if no element in $S$ extended $\tau$ then
$\tau\mathrel{{\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{\Pi}^{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 ${\Pi}^{0}_{1}$
singleton and any ${{\mathbf{0}}}^{\prime}$-escaping function computes a set
that’s not a ${\Pi}^{0}_{2}$ singleton444Since ${\Pi}^{0}_{2}$ singletons are
closed under Turing equivalence, we could say not of ${\Pi}^{0}_{2}$ singleton
degree.. 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 ${\Pi}^{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 ${\Pi}^{0}_{n}$ singleton for any $n$). If true, this
would prove that no $\omega\mathchar 45\relax\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 ${\Pi}^{0}_{2}$ singleton, and
hence no $\omega\mathchar 45\relax\text{REA}$ set, is of minimal arithmetic
degree.

###### Proof.

Suppose, for contradiction, $X$ is a ${\Pi}^{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\mathrel{\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
${\Pi}^{0}_{2}$ formula defining $X$ and that $\psi(\Psi(Y))=Y$.
Contradiction. ∎

##  4\. A Arithmetically Minimal ${\Pi}^{0}_{2}$ Singleton

We will now prove that our seemingly plausible conjectures (once again) fail
and that there is a ${\Pi}^{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
${\Pi}^{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 $\widehat{T}$ such that

  1. (1)

$\operatorname{rng}\widehat{T}\subset T$ and $[\widehat{T}]=[T]$

  2. (2)

$\widehat{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\mathbin{\oplus}{X}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}{\left(\widehat{T}\\!\left(g\right)\mathbin{\oplus}X\right)}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}\widehat{T}\\!\left(g\right)\mathbin{\oplus}{X}^{\prime\prime}$.

  5. (5)

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

  6. (6)

For all $\sigma\in 2^{<\omega}$,
$\lvert\widehat{T}\\!\left(\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,\widehat{\Upsilon}$ so that whenever
$\Upsilon_{2}({X}^{\prime\prime})=S$ then $\Upsilon(X)=T$ and
$\widehat{\Upsilon}({X}^{\prime\prime})=\widehat{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^{\mathrm{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)}\mathrel{\equiv_{\mathbf{T}}}f\mathbin{\oplus}{\mathbf{0}}^{(\beta)}$
and, indeed,
${f}^{(\alpha)}\mathrel{\equiv_{\mathbf{T}}}f\mathbin{\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\mathbin{\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 ${\Pi}^{0}_{2}$ singleton
of minimal arithmetic degree.

######  Corollary 4.3.

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

###### Proof.

Taking $T_{\omega}={\left\\{\mathopen{\langle}0^{n}\mathclose{\rangle}\mid
n\in\omega\right\\}}$ immediately produces a ${\Pi}^{0}_{1}$ function
singleton of minimal arithmetic degree and applying Lemma 2.1 transforms this
into a ${\Pi}^{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 ${\Pi}^{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 ${\Pi}^{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 contain 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\mathrel{\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}}\mathopen{\langle}i\mathclose{\rangle})$ is
large at at $n=\lvert\Gamma^{\omega}_{0}(\sigma)\rvert$. Thus, we can apply
the same approach as in 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 ${\Pi}^{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
${\Pi}^{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\mathchar 45\relax\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\mathchar 45\relax\text{REA}$ arithmetic degree.

At first glance, one might think that this question stands or falls with the
existence of an $\omega\mathchar 45\relax\text{REA}$ set of minimal arithmetic
degree. After all, the question must have a negative answer if there is such
an $\omega\mathchar 45\relax\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\mathchar
45\relax\text{REA}$ set is of minimal arithmetic degree. This would require
that there is some non-arithmetic $\omega\mathchar 45\relax\text{REA}$ set $A$
such that every $B\leq_{\mathbf{a}}A$ is arithmetically equivalent to an
$\omega\mathchar 45\relax\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 ${\Pi}^{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\operatorname{HYP}$. However, the methods in
[5] might allow the definition of a perfect ${\Pi}^{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 ${\Pi}^{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 ${\Pi}^{0}_{2}$ singletons $A,B$ of minimal arithmetic
degree such that
$A\mathbin{\oplus}B\mathrel{\equiv_{\mathbf{a}}}{\mathbf{0}}^{(\omega)}$ (or
even $\mathrel{\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 ${\Pi}^{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}}\left(n\right)=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 $S=\mathchoice{\text{\raise
4.30554pt\hbox{$T_{\beta+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\beta+2}\,/\,\sigma}{T_{\beta+2}\,/\,\sigma}{T_{\beta+2}\,/\,\sigma}$
and $X={\mathbf{0}}^{(\beta)}$ produces $T=\mathchoice{\text{\raise
4.30554pt\hbox{$T_{\beta}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\beta}\,/\,\sigma}{T_{\beta}\,/\,\sigma}{T_{\beta}\,/\,\sigma}$
and $\widehat{T}$ where
$\sigma\widehat{\phantom{x}}\widehat{T}\\!\left(\tau\right)=\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\mathbin{\oplus}{\mathbf{0}}^{(\beta)}$.

  3. (3)

${f}^{(\beta)}\mathrel{\equiv_{\mathbf{T}}}f\mathbin{\oplus}{\mathbf{0}}^{(\beta)}\mathrel{\equiv_{\mathbf{T}}}g_{\beta}\mathbin{\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}\mathbin{\oplus}{\mathbf{0}}^{(\beta)}$ then
either $Y\leq_{\mathbf{T}}{\mathbf{0}}^{(\beta)}$ or
$g_{\beta}\leq_{\mathbf{T}}Y\mathbin{\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)}\mathbin{\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}\mathpunct{\restriction_{l^{\Diamond}(\beta)}}$ and note that
by 3 of Proposition 5.2 for $\beta<_{\mathcal{O}}\alpha$ the tree
$\mathchoice{\text{\raise 4.30554pt\hbox{$T_{\beta}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\beta}\,/\,\sigma}{T_{\beta}\,/\,\sigma}{T_{\beta}\,/\,\sigma}$
is the result of Proposition 4.1 applied to $\mathchoice{\text{\raise
4.30554pt\hbox{$T_{\beta+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\beta+2}\,/\,\sigma}{T_{\beta+2}\,/\,\sigma}{T_{\beta+2}\,/\,\sigma}$
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}\mathpunct{\restriction_{l^{\Diamond}(\gamma)}}$. By
3 of Proposition 5.2 the tree $\mathchoice{\text{\raise
4.30554pt\hbox{$T_{\gamma}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\gamma}\,/\,\sigma}{T_{\gamma}\,/\,\sigma}{T_{\gamma}\,/\,\sigma}$
is the result of Proposition 4.1 applied to $\mathchoice{\text{\raise
4.30554pt\hbox{$T_{\gamma+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\gamma+2}\,/\,\sigma}{T_{\gamma+2}\,/\,\sigma}{T_{\gamma+2}\,/\,\sigma}$.
Thus, by point 4 of Proposition 4.1 we have
${\left(g_{\gamma}\mathbin{\oplus}{\mathbf{0}}^{(\gamma)}\right)}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}g_{\gamma}\mathbin{\oplus}{\mathbf{0}}^{(\gamma+2)}\mathrel{\equiv_{\mathbf{T}}}g_{\gamma+2}\mathbin{\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\mathbin{\oplus}{\mathbf{0}}^{(\beta)}$ can compute ${f}^{(\gamma)}$
for notations $\gamma<_{\mathcal{O}}\beta$. Hence
$f\mathbin{\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\mathbin{\oplus}{\mathbf{0}}^{(\beta)}\mathrel{\equiv_{\mathbf{T}}}g\mathbin{\oplus}{\mathbf{0}}^{(\beta)}$
completing the verification. ∎

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

###### Proof.

Take $\alpha^{\prime}$ 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)}\mathrel{\equiv_{\mathbf{T}}}f\mathbin{\oplus}{\mathbf{0}}^{(\beta)}\mathrel{\equiv_{\mathbf{T}}}g_{\beta}\mathbin{\oplus}{\mathbf{0}}^{(\beta)}$
from part 3 of Lemma 5.3 gives the first claim in Theorem 4.2 on it’s 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}\mathbin{\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 the
appendix. 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 the appendix.
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 $\widehat{\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}\mathpunct{\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 than $\tilde{T}^{\prime}_{\lambda}=\tilde{T}_{\lambda}$.

For $\sigma^{\prime}$ with $\lvert\sigma^{\prime}\rvert>l^{\Diamond}(\beta)$
let $\sigma^{\prime}=\sigma\widehat{\phantom{x}}\tau$ where
$\lvert\sigma\rvert=l^{\Diamond}(\beta)$. Set $\sigma^{\prime}\notin
T_{\beta}$ if $\sigma\notin\tilde{T}^{\prime}_{\lambda}$. If
$\sigma\in\tilde{T}^{\prime}_{\lambda}$ then apply Proposition 4.1 to
$\tilde{T}^{\sigma}_{\beta+2}\overset{\text{\tiny
def}}{=}\mathchoice{\text{\raise
4.30554pt\hbox{$\tilde{T}_{\beta+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{\tilde{T}_{\beta+2}\,/\,\sigma}{\tilde{T}_{\beta+2}\,/\,\sigma}{\tilde{T}_{\beta+2}\,/\,\sigma}$
to yield some $T^{\sigma}_{\beta}$ and place $\sigma^{\prime}\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}\mathpunct{\restriction_{l^{\Diamond}(\beta)}}\subset
T_{\beta+2}\mathpunct{\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,\widehat{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 $\mathchoice{\text{\raise
4.30554pt\hbox{$\tilde{T}_{\beta+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{\tilde{T}_{\beta+2}\,/\,\sigma}{\tilde{T}_{\beta+2}\,/\,\sigma}{\tilde{T}_{\beta+2}\,/\,\sigma}$
not $\mathchoice{\text{\raise 4.30554pt\hbox{$T_{\beta+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\beta+2}\,/\,\sigma}{T_{\beta+2}\,/\,\sigma}{T_{\beta+2}\,/\,\sigma}$
to ensure we get the f-tree $\widehat{T}$ associated with the construction of
$\mathchoice{\text{\raise 4.30554pt\hbox{$T_{\beta}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{T_{\beta}\,/\,\sigma}{T_{\beta}\,/\,\sigma}{T_{\beta}\,/\,\sigma}$.

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 $\lvert\sigma^{\prime}\rvert>l^{\Diamond}(\beta)$
then let
$\sigma=\sigma^{\prime}\mathpunct{\restriction_{l^{\Diamond}(\beta)}}$ and if
$\sigma\notin\tilde{T}_{\beta+2}$ then
$\Gamma^{\beta+2}_{\beta}(\sigma^{\prime})\mathpunct{\uparrow}$. Otherwise, we
define
$\Gamma^{\beta+2}_{\beta}(\sigma^{\prime})=\sigma\widehat{\phantom{x}}\widehat{T}\\!\left(\tau\right)$
where , $\sigma^{\prime}=\sigma\widehat{\phantom{x}}\tau$ and $\widehat{T}$ is
the f-tree produced by Proposition 4.1 as applied to $\mathchoice{\text{\raise
4.30554pt\hbox{$\tilde{T}_{\beta+2}$}\Big{/}\lower
4.30554pt\hbox{$\sigma$}}}{\tilde{T}_{\beta+2}\,/\,\sigma}{\tilde{T}_{\beta+2}\,/\,\sigma}{\tilde{T}_{\beta+2}\,/\,\sigma}$.
For $\beta^{\prime}<_{\mathcal{O}}\beta$ we define
$\Gamma^{\beta+2}_{\beta^{\prime}}$ to be
$\Gamma^{\beta+2}_{\beta}\circ\tilde{\Gamma}^{\beta}_{\beta^{\prime}}$.

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 a f-tree that’s a homeomorphism of
$[T_{\beta}]$ with $[T_{\gamma}]$ and then observe that if
$\beta=\beta^{\prime}+2$ then since
$\Gamma^{\beta^{\prime}+2}_{\beta^{\prime}}$ 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 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 it’s 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 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}}}^{\prime}$
$\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}}}^{\prime}$ 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\operatorname{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 $\widehat{T}$ to be computable in ${X}^{\prime}$. While we aren’t
guaranteed that $\widehat{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 $\widehat{T}_{s}$ to $\widehat{T}$. We will organize the
construction of by drawing on ideas from ${\Pi}^{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 ${\Pi}^{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 $\widehat{T}\\!\left(\sigma\right)$ for
some $\sigma$. Thus, rather than working on
$\mathbb{T}\subset\omega^{<\omega}$ we work on
$\mathbb{T}\subset\omega^{<\omega}\mathbin{\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
$\operatorname{dom}\widehat{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)
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\right)$
and above/to define
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}m^{\prime}\mathclose{\rangle}\right)$.

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=\mathopen{\langle}\mathclose{\rangle}$ but some modules will have
successors both of the form $(o,\mathopen{\langle}\mathclose{\rangle})$ and
$(o,\mathopen{\langle}n\mathclose{\rangle})$ (for some particular value $n$).
Thus, we will only every we working on finitely many modules simultaneously 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(\mathopen{\langle}a,b\mathclose{\rangle}\right)_{0}=a$ and
$\left(\mathopen{\langle}a,b\mathclose{\rangle}\right)_{1}=b$.

######  Definition 6.2.

$\mathbb{T}$ is the smallest set of pairs
$\mathopen{\langle}\alpha,\sigma\mathclose{\rangle}$ closed under the
following conditions

  * •

$\mathopen{\langle}\mathopen{\langle}\mathclose{\rangle},\mathopen{\langle}\mathclose{\rangle}\mathclose{\rangle}\in\mathbb{T}$

  * •

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

We define $\lvert\xi\rvert\in\mathbb{T}=\lvert\left(\xi\right)_{0}\rvert$ and
say $\xi\prec\xi^{\prime}$ if $\prec$ holds on both components (i.e.
$\left(\xi\right)_{i}\prec\left(\xi^{\prime}\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=\mathopen{\langle}\alpha,\sigma\mathclose{\rangle}$ are modified to be of
the form $\mathopen{\langle}o,\sigma\mathclose{\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 it’s not longer
visually accurate) and extend this to a set of nodes as follows.

######  Definition 6.3.

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

Our truepath, and its approximations, will no longer be single paths but sets
of nodes. Informally speaking, we define $\mathbbm{f}_{s}$ 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 $\mathbbm{f}_{s}$ as the largest set satisfying the following
closure conditions

  * •

$\mathopen{\langle}\mathclose{\rangle}\in\mathbbm{f}_{s}$

  * •

If $\xi\in\mathbb{T},\xi\in\mathbbm{f}_{s}$, $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}}\mathopen{\langle}o\mathclose{\rangle}$
then $\nu\in\mathbb{T}$.

Where $s_{\xi}$ is defined to be
$\lvert{\left\\{t\mid\xi\in\mathbbm{f}_{t}\land t<s\right\\}}\rvert$.

We define $\xi\in\mathbbm{f}$ iff $\left(\exists s\right)\\!\left(\forall
s^{\prime}>s\right)\\!\left(\lnot\mathbbm{f}_{s}\mathbin{<_{L}}\xi\right)\land\left(\exists^{\infty}s\right)\\!\left(\xi\in\mathbbm{f}_{s}\right)$

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

######  Condition 1.

If $s^{\prime}>s$ and
$\xi\in\mathbbm{f}_{s},\mathbbm{f}_{s^{\prime}}\mathbin{<_{L}}\xi$ then for
all $t\geq s^{\prime}$ $\xi\notin\mathbbm{f}_{t}$.

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=\mathop{\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
$\widehat{T}$. Each module ${\mathcal{M}}_{\xi}$ receives a string
$\delta^{\xi}$ and specifies a string $\delta^{\nu}$ for each successor to
$\xi$. If $\xi=\mathopen{\langle}\alpha,\sigma\mathclose{\rangle}$ then we
understand the module $\xi$ to be executing on the guess that
$\delta^{\xi}\prec\widehat{T}\\!\left(\sigma\right)$.

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
$\widehat{T}\\!\left(\sigma\right)$. 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 $\xi\in\mathbbm{f}_{s}\land s_{\xi}=0$ 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}}\mathopen{\langle}k_{n}\mathclose{\rangle}$
with $n\mapsto k_{n}$ monotonic, injective function of $n$.

  2. (2)

If $\xi\in\mathbbm{f}_{s}\land s_{\xi}=n$ 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 it’s output promptly. However,
a few points deserve mentioning. The requirement that $\delta^{\xi}\in
T_{s+1}$ will ensure that $\operatorname{rng}\widehat{T}\subset T$. The final
condition will enable multiple modules who all want to ensure the leftmost
branch extending $\widehat{T}\\!\left(\sigma\right)$ 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 $\xi\in\mathbbm{f}$ 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 $\widehat{T}$ such that

  1. (1)

$\operatorname{rng}\widehat{T}\subset T$ and $[\widehat{T}]=[T]$

  2. (2)

$\widehat{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\mathbin{\oplus}{X}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}{\left(\widehat{T}\\!\left(g\right)\mathbin{\oplus}X\right)}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}\widehat{T}\\!\left(g\right)\mathbin{\oplus}{X}^{\prime\prime}$.

  5. (5)

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

  6. (6)

For all $\sigma\in 2^{<\omega}$,
$\lvert\widehat{T}\\!\left(\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,\widehat{\Upsilon}$ so that whenever
$\Upsilon_{2}({X}^{\prime\prime})=S$ then $\Upsilon(X)=T$ and
$\widehat{\Upsilon}({X}^{\prime\prime})=\widehat{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 $\widehat{T}^{-}\\!\left(\sigma\right)$ to
denote an extension of $\widehat{T}\\!\left(\sigma^{-}\right)$ that would be
extended by $\widehat{T}\\!\left(\sigma\right)$ 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 later555We could define
$\widehat{T}^{-}\\!\left(\sigma\right)$ to be $\delta^{\xi}$ for the unique
$\xi$ along the truepath of the form $(\alpha,\sigma)$ such that $\xi$
implements ${\mathcal{H}}_{\sigma}$ but, as it’s unnecessary for the proof, we
feel doing so would unnecessarily multiply notation..

($\mathscr{P}_{e}$)
$\displaystyle\widehat{T}\\!\left(\sigma\right)\mathrel{\mid}{\Phi_{e}\\!\left(X\right)}\lor{\Phi_{e}\\!\left(X\right)}\mathpunct{\uparrow}$
($\mathscr{L}_{e}$) $\displaystyle\left(\forall
f\in[T],f\succ\widehat{T}\\!\left(\sigma\right)\right)\\!\left({\Phi_{e}\\!\left(f\mathbin{\oplus}X\right)}\mathpunct{\uparrow}\right)\lor\left(\forall
f\in[T],f\succ\widehat{T}\\!\left(\sigma\right)\right)\\!\left({\Phi_{e}\\!\left(f\mathbin{\oplus}X\right)}\mathpunct{\downarrow}\right)$
($\mathscr{H}_{\sigma}$) $\displaystyle\begin{aligned}
S(\sigma)\mathpunct{\downarrow}=0&\implies\widehat{T}\\!\left(\sigma\right)\mathpunct{\downarrow}\land\left(\forall
m\right)\\!\left(\widehat{T}\\!\left(\sigma\right)\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\notin
T\right)\\\
S(\sigma)\mathpunct{\downarrow}=1&\implies\widehat{T}\\!\left(\sigma\right)\mathpunct{\downarrow}\in
T^{\langle\infty\rangle}\iff\sigma\in S^{\langle\infty\rangle}\\\
S(\sigma)\mathpunct{\uparrow}&\implies\widehat{T}\\!\left(\sigma\right)\mathpunct{\uparrow}\land\widehat{T}^{-}\\!\left(\sigma\right)\notin
T^{\langle\infty\rangle}\end{aligned}$ (3)
$\displaystyle\begin{gathered}T^{\left\langle\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\right)\right\rangle}\text{
is totally non-$e$-splitting }\lor m>n\implies\\\
\widehat{T}^{-}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\right)\text{
and
}\widehat{T}^{-}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\right)e-\text{split}\end{gathered}$

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

Each requirement gets it’s own module to assist in meeting it, however, some
modules get helper modules. For instance, we break up meeting the requirement
Hσ into a module ${\mathcal{H}}^{+}_{\sigma^{-}}$ responsible for creating an
$\omega$-branching above $\widehat{T}\\!\left(\sigma^{-}\right)$ and a module
${\mathcal{H}}_{\sigma}$ responsible for ensuring
$\widehat{T}\\!\left(\sigma\right)$ 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
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\right)$
from those modules working to define
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\right),m>n$.

######  Definition 6.5.

Modules are be assigned to nodes on $\mathbb{T}$ as follows

  1. (1)

If
$\xi=(\mathopen{\langle}\mathclose{\rangle},\mathopen{\langle}\mathclose{\rangle})$
then $\xi$ implements
${\mathcal{H}}^{+}_{\mathopen{\langle}\mathclose{\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 $\nu\mathrel{\vbox{\hbox{\text{\oalign{\kern
0.66112pt\cr$\prec$\cr\kern-0.19997pt\cr\begin{picture}(0.0,0.4)\put(0.0,0.2){\hbox{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=5.9301pt}} \put(0.0,0.0){\hbox{\vrule
height=1.72218pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=1.72218pt}} \end{picture}\cr}}}}}\xi$.

  6. (6)

If $\xi^{-}$ implements ${\mathcal{P}}_{i}$ then $\xi$ implements
${\mathcal{L}}_{e}$ for the least $e$ such that no
$\nu\mathrel{\vbox{\hbox{\text{\oalign{\kern
0.66112pt\cr$\prec$\cr\kern-0.19997pt\cr\begin{picture}(0.0,0.4)\put(0.0,0.2){\hbox{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=5.9301pt}} \put(0.0,0.0){\hbox{\vrule
height=1.72218pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=1.72218pt}} \end{picture}\cr}}}}}\xi$
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\mathpunct{\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\mathpunct{\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
$\widehat{T}\\!\left(\sigma\right)$ and wish to define
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\right)$
we start with the module ${\mathcal{H}}^{+}_{\sigma}$ which will specify a
bunch of immediate extensions of $\widehat{T}\\!\left(\sigma\right)$ (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
$\widehat{T}\\!\left(\sigma\right)$ $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
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle}\right)$
extends the leftmost branch as extended by all the modules
${\mathcal{S}}^{0}_{e^{\prime}},e^{\prime}\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
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle}\right)$
and another part where ${\mathcal{S}}^{1}_{e}$ starts working to define the
node which will be extended by
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}1\mathclose{\rangle}\right)$.
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^{\prime}},e^{\prime}\leq e$ we implement the next helper
module of the form ${\mathcal{L}}^{m}_{e^{\prime}}$. Finally, after those
modules, comes the module
${\mathcal{H}}_{\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}}$
(assuming we took the path working on
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\right)$)
which guesses whether or not
$\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}\in S$. If
it determines
$\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}$ is in $S$
then we go on to
${\mathcal{H}}^{+}_{\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\rangle}}$.
If it determines that
$\sigma\widehat{\phantom{x}}\mathopen{\langle}m\mathclose{\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 $\widehat{T}$ and
its stagewise approximation.

######  Definition 6.6.

We define $\widehat{T}_{s}\\!\left(\sigma\right)=\delta^{\xi}$ where
$\xi=(\alpha,\sigma)\in\mathbbm{f}_{s}$ and $\xi^{-}$ implements the module
${\mathcal{H}}_{\sigma}$. If no such $\xi\in\mathbbm{f}_{s}$ then it is
undefined. We define $\widehat{T}\\!\left(\sigma\right)$) in a similar manner
except we require that $\xi\in\mathbbm{f}$.

###  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\mathbin{<_{L}}\left\ulcorner\mathpunct{\uparrow}\right\urcorner$
and $(o,\delta)\in\mathfrak{O}(\xi)$ iff
$\delta=\mathopen{\langle}\mathclose{\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)}\mathrel{\mid}\tau$. If found set the outcome to
$\left\ulcorner\neq\right\urcorner$ and
$\delta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}\left\ulcorner\neq\right\urcorner\mathclose{\rangle},\sigma\mathclose{\rangle}}$
to be a $\prec$ maximal extension of $\tau$ in $T_{s}$. Otherwise, set the
outcome to $\left\ulcorner\mathpunct{\uparrow}\right\urcorner$ and, if this is
the first stage at which that outcome is visited, set
$\delta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}\left\ulcorner\mathpunct{\uparrow}\right\urcorner\mathclose{\rangle},\sigma\mathclose{\rangle}}=\delta^{\xi}$.

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

The module ${\mathcal{L}}_{e}$ has outcomes
$\left\ulcorner\mathpunct{\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=\mathopen{\langle}\mathclose{\rangle}$. The outcome
$\left\ulcorner\mathpunct{\downarrow}\right\urcorner$ corresponds to the state
where ${\Phi_{e}\\!\left(X\mathbin{\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^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}\left\ulcorner\nu\right\urcorner\mathclose{\rangle},\sigma\mathclose{\rangle}}$
satisfy ${\Phi_{e}\\!\left(X\mathbin{\oplus}f;n\right)}\mathpunct{\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 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=\mathpunct{\uparrow},\delta=\mathpunct{\uparrow}$. If $s_{\xi}>0$
and $\upsilon\mathpunct{\uparrow}$ then we visit the outcome
$\left\ulcorner\mathpunct{\downarrow}\right\urcorner$ with
$\delta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}\left\ulcorner\mathpunct{\downarrow}\right\urcorner\mathclose{\rangle},\sigma\mathclose{\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\mathpunct{\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)}\mathpunct{\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\mathpunct{\downarrow}\right\urcorner$ as above.
Otherwise, visit the outcome $\left\ulcorner\upsilon\right\urcorner$ with
$\delta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}\left\ulcorner\upsilon\right\urcorner\mathclose{\rangle},\sigma\mathclose{\rangle}}=\delta$.

####  6.3.3. Module ${\mathcal{L}}^{n}_{e}$

This node only has a single outcome $0$ and
$\mathfrak{O}(\xi)={\left\\{(0,\mathopen{\langle}\mathclose{\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^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle},\sigma\mathclose{\rangle}}$.

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

This node only has a single outcome $0$ and
$\mathfrak{O}(\xi)={\left\\{(0,\mathopen{\langle}\mathclose{\rangle})\right\\}}$.
Let
$\nu=(\alpha\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\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}}\mathopen{\langle}k\mathclose{\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,\mathopen{\langle}n\mathclose{\rangle}),(0,\mathopen{\langle}\mathclose{\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^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle},\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\mathclose{\rangle}}=\theta^{\xi}_{0}$,
$\delta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle},\sigma\mathclose{\rangle}}=\delta^{\xi}$
and
$\theta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}0\mathclose{\rangle},\sigma\mathclose{\rangle}}_{n}=\theta^{\xi}_{n+1}$.

####  6.3.6. Module ${\mathcal{S}}^{n}_{e}$

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

The outcome $\left\ulcorner{\mathrel{\,\not|\,}}\right\urcorner$ corresponds
to the case where $\theta^{\xi}_{0}$ isn’t extended by an $e$-splitting in $T$
(as ${\mathrel{\,\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\mathrel{\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(\mathrel{\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(\mathpunct{\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=\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}o\mathclose{\rangle},\sigma\mathclose{\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{\mathrel{\,\not|\,}}\right\urcorner$ or
$o=\left\ulcorner(\mathpunct{\uparrow},n,m)\right\urcorner$. In the later
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\mathbin{\oplus}X\right)}\mathpunct{\uparrow}$). Since we
don’t want to accidentality extend
$\theta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}o^{\prime}\mathclose{\rangle},\sigma\mathclose{\rangle}}_{0}$
to an infinite path if $o^{\prime}$ isn’t the true outcome we’ll ensure that
every outcome except $\left\ulcorner{\mathrel{\,\not|\,}}\right\urcorner$
corresponds to an incompatible value for
$\theta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}o^{\prime}\mathclose{\rangle},\sigma\mathclose{\rangle}}_{0}$
of length at most $1+\max\lvert\tau_{0}\rvert,\lvert\tau_{1}\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
$\widehat{n}=\widehat{m}=0$. For $s_{\xi}>0$ we consider the following cases.

  1. Case

$\tau_{0}\mathpunct{\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{\mathrel{\,\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 $\widehat{m}=\widehat{n}=n$ and visit outcome
$o=\left\ulcorner\mathrel{\mid}_{0}\right\urcorner$ setting
$\theta^{\nu}_{0}=\tau_{0}$.

  2. Case

$\tau_{0}\mathpunct{\downarrow}$ : We break this up into a number of subcases.
We search for some $n\leq s_{\xi}$ and
$\tau^{\prime}\succ\theta^{\xi}_{n},\tau^{\prime}\in T_{s}$ that satisfy the
following (picking the first case satisfied)

    1. Case

$\tau^{\prime},\tau_{0}$ $e$-split with $\widehat{n}<n\leq s_{\xi}$: In this
case, we let $o=\left\ulcorner\mathrel{\mid}_{0}\right\urcorner$ and set
$\theta^{\nu}_{s_{\nu}}$ to be a $\prec$ maximal extension of $\tau^{\prime}$
in $T_{s}$. Finally, we set $\widehat{n}=\widehat{m}=n$.

    2. Case

$\tau^{\prime},\tau_{1}$ $e$-split with $\widehat{m}<n\leq s_{\xi}$: In this
case, we let $o=\left\ulcorner(\mathrel{\mid}_{1},\widehat{n})\right\urcorner$
and set $\widehat{m}=n$ and $\theta^{\nu}_{s_{\nu}+1}$ be a $\prec$ maximal
extension of $\tau^{\prime}$ 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}}\mathopen{\langle}k\mathclose{\rangle}$
placing $\theta^{\nu}_{0}$ into $T_{s+1}$.

    3. Case

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

####  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,\widehat{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 $\widehat{n}$ indicates the value at
which $\rho_{1}$ achieves it’s 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,\widehat{n})$ has
been visited. Thus, the actual outcomes will be of the form
$\left\ulcorner(i,\widehat{n},m)\right\urcorner=2\mathopen{\langle}\widehat{n},m\mathclose{\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,\widehat{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=\mathopen{\langle}\mathclose{\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,\widehat{n},m)\right\urcorner$ has been visited. Choose the
lexicographically least pair $(i,\widehat{n})$ such that for all
$n\in[\widehat{n},\widehat{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 $\widehat{n}$ we have $k=0$
and $\rho(\sigma,\widehat{n},0)\in{\left\\{0,1\right\\}}$. We now visit the
outcome $o=\left\ulcorner(i,\widehat{n},m)\right\urcorner$ where $m$ is the
number of times that we’ve visited an outcome of the form
$\left\ulcorner(i^{\prime},n,m)\right\urcorner$ with $(i^{\prime},n)$
lexicographically before $(i,\widehat{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}}\mathopen{\langle}c\mathclose{\rangle}$ into
$T_{s+1}$ and set
$\delta^{\mathopen{\langle}\alpha\widehat{\phantom{x}}\mathopen{\langle}o\mathclose{\rangle},\sigma\mathclose{\rangle}}=\tau\widehat{\phantom{x}}\mathopen{\langle}c\mathclose{\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 $\xi\in\mathbbm{f}$ 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=\lvert\delta^{\nu}\rvert$ but
$\tau\nsucc\delta^{\widehat{\xi}}$ for $\widehat{\xi}\in\mathbbm{f}$,
$\widehat{\xi}^{-}=\xi$. Then there are only finitely many stages at which any
module at $\widehat{\nu}\succ\xi$ enumerates an element
$\tau^{\prime}\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 $\widehat{\nu}$ with
$\widehat{\nu}\mathrel{\vbox{\hbox{\text{\oalign{\kern
0.66112pt\cr$\prec$\cr\kern-0.19997pt\cr\begin{picture}(0.0,0.4)\put(0.0,0.2){\hbox{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=5.9301pt}} \put(0.0,0.0){\hbox{\vrule
height=1.72218pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=1.72218pt}} \end{picture}\cr}}}}}\xi$ and
$\delta^{\widehat{\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,\widehat{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\mathpunct{\downarrow}\right\urcorner$ then the claim follows
because $\delta^{\nu}\succ\delta^{\widehat{\xi}}$ for all $\nu$ with
$\nu^{-}=\xi$ when $\widehat{\xi}$ corresponds to the infinitary outcome. ∎

######  Lemma 6.8.

Suppose that $\xi\in\mathbbm{f}$ 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}}\mathopen{\langle}k\mathclose{\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}}\mathopen{\langle}k\mathclose{\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}}\mathopen{\langle}k\mathclose{\rangle}$. So
suppose that
$\theta^{\xi}_{n}\succ\delta^{\xi}\widehat{\phantom{x}}\mathopen{\langle}k\mathclose{\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}}\mathopen{\langle}k\mathclose{\rangle}$.

This leaves only the case where
$\theta^{\xi}_{0}\succ\delta^{\xi}\widehat{\phantom{x}}\mathopen{\langle}k\mathclose{\rangle}$.
If $\xi$ corresponds to an outcome
$\left\ulcorner(\mathpunct{\uparrow},n,m)\right\urcorner$ or
$\left\ulcorner{\mathrel{\,\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\mathrel{\mid}_{0}\right\urcorner$ or
$\left\ulcorner(\mathrel{\mid}_{1},n)\right\urcorner$. In this case, we can
take $l=1+\max\lvert\tau_{0}\rvert,\lvert\tau_{1}\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(\widehat{T}\\!\left(g\right)=f\right)$.

###### Proof.

For the if direction suppose that $\widehat{T}\\!\left(g\right)=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
$\widehat{T}\\!\left(g\right)\in T$. For the other direction, suppose
$f\neq\widehat{T}\\!\left(g\right)$ 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 $\nu\mathrel{\vbox{\hbox{\text{\oalign{\kern
0.66112pt\cr$\prec$\cr\kern-0.19997pt\cr\begin{picture}(0.0,0.4)\put(0.0,0.2){\hbox{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=5.9301pt}} \put(0.0,0.0){\hbox{\vrule
height=1.72218pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=1.72218pt}} \end{picture}\cr}}}}}\xi^{-}$ 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\mathpunct{\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.

$\operatorname{rng}\widehat{T}\subset T$ and $[\widehat{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 $\xi\in\mathbbm{f}$ and $\xi$ implements ${\mathcal{H}}_{\sigma}$ then
$\xi$ has a well-defined outcome iff $S(\sigma)\mathpunct{\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,\widehat{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>\widehat{n}$ we have
$\rho_{1}(\sigma,n)=1-i$. Thus, for some $k$ we have
$\rho(\sigma,n,k^{\prime})=1-i$ for all $k^{\prime}\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)\mathpunct{\uparrow}$.

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

######  Lemma 6.12.

For all $g\in\omega^{\omega}$, $\widehat{T}\\!\left(g\right)$ is total iff
$g\in[S]$ iff $\widehat{T}\\!\left(g\right)\in[T]$. Moreover,
$\widehat{T}\\!\left(\sigma\right)\mathpunct{\downarrow}$ iff
$S(\sigma)\mathpunct{\downarrow}$ and all
$\sigma^{\prime}\mathrel{\vbox{\hbox{\text{\oalign{\kern
0.66112pt\cr$\prec$\cr\kern-0.19997pt\cr\begin{picture}(0.0,0.4)\put(0.0,0.2){\hbox{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=5.9301pt}} \put(0.0,0.0){\hbox{\vrule
height=1.72218pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=1.72218pt}} \end{picture}\cr}}}}}\sigma$ are in
$S$.

###### Proof.

We first verify the moreover claim. Note that, for any module besides
${\mathcal{H}}_{\sigma}$ there is always is a well-defined true outcome. Thus,
by an examination of the construction, we can see that the only way for
$\widehat{T}\\!\left(\sigma\right)$ to be undefined is either if for some
$\sigma^{\prime}\mathrel{\vbox{\hbox{\text{\oalign{\kern
0.66112pt\cr$\prec$\cr\kern-0.19997pt\cr\begin{picture}(0.0,0.4)\put(0.0,0.2){\hbox{\vrule
height=0.0pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=5.9301pt}} \put(0.0,0.0){\hbox{\vrule
height=1.72218pt,depth=0.0pt,width=0.0pt\vrule
height=0.0pt,depth=0.0pt,width=1.72218pt}} \end{picture}\cr}}}}}\sigma$ the
module of the form ${\mathcal{H}}_{\sigma^{\prime}}$ on the truepath doesn’t
have a true outcome guessing $\sigma^{\prime}\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
$\widehat{T}\\!\left(\sigma\right)\mathpunct{\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.

$\widehat{T}$ is an f-tree

###### Proof.

As $\widehat{T}$ is clearly $\prec$ respecting it is enough to show that
whenever $\widehat{T}\\!\left(\sigma\right)$ isn’t terminal then $i<j$ implies
that
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle}\right)$
and
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}j\mathclose{\rangle}\right)$
extend incompatible immediate extensions of
$\widehat{T}\\!\left(\sigma\right)$ and
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}i\mathclose{\rangle}\right)$
is lexicographically below
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}j\mathclose{\rangle}\right)$.
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.

$\widehat{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 $\widehat{T}$.
Evidently, both $\widehat{T}$ and its inverse are continuous so it remains
only to show that $\widehat{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,\widehat{\Upsilon}$ such that if
$\Upsilon_{2}({X}^{\prime\prime})=S$ then $\Upsilon(X)=T$ and
$\widehat{\Upsilon}({X}^{\prime\prime})=\widehat{T}$ where $T,\widehat{T}$ are
as constructed above.

###### Proof.

To compute $\widehat{T}\\!\left(\sigma\right)$ from ${X}^{\prime\prime}$ we
simply (iteratively) identify the leftmost outcome of nodes on $\mathbb{T}$ to
identify elements in $\mathbbm{f}$ and search for a node $\xi\in\mathbbm{f}$
and $\xi^{-}$ implementing ${\mathcal{H}}_{\sigma}$ and return $\delta^{\xi}$.
It’s possible that when working to compute $\widehat{T}\\!\left(\sigma\right)$
we next discover such a node $\xi$. However, this can only happen when $S$
fails to converge on some $\sigma^{\prime}\prec\sigma$ in which case
$\widehat{T}\\!\left(\sigma\right)$ 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=\widehat{T}\\!\left(g\right)$. Thus, for some $\xi\in\mathbbm{f}$ with
$\xi^{-}$ implementing ${\mathcal{P}}_{e}$ we have $f\succ\delta^{\xi}$. As
$f=\widehat{T}\\!\left(g\right)$ we know that $\mathbbm{f}$ 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}\mathrel{\mid}{\Phi_{e}\\!\left(X\right)}$ contradicting the
supposition. ∎

######  Lemma 6.17.

Suppose $\xi\in\mathbbm{f},f\in[T],f\succ\delta^{\xi}$ and $\xi^{-}$
implements ${\mathcal{L}}_{e}$ then
${\Phi_{e}\\!\left(f\mathbin{\oplus}X\right)}$ is total iff the true outcome
of $\xi^{-}$ is $\left\ulcorner\mathpunct{\downarrow}\right\urcorner$

###### Proof.

Suppose $\xi^{-}$ has true outcome
$\left\ulcorner\mathpunct{\downarrow}\right\urcorner$ but that
${\Phi_{e}\\!\left(f\mathbin{\oplus}X;n\right)}\mathpunct{\uparrow}$. For some
$\nu\in\mathbbm{f},\tau=\delta^{\nu}$ 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\mathpunct{\downarrow}\right\urcorner$ if
${\Phi_{e}\\!\left(\tau\mathbin{\oplus}X;n\right)}\mathpunct{\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\mathbin{\oplus}X;n\right)}\mathpunct{\downarrow}$ then
we wouldn’t have true outcome $\left\ulcorner\nu\right\urcorner$. Hence, we
must have
${\Phi_{e}\\!\left(f\mathbin{\oplus}X;n\right)}\mathpunct{\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\mathbin{\oplus}{X}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}{\left(\widehat{T}\\!\left(g\right)\mathbin{\oplus}X\right)}^{\prime\prime}\mathrel{\equiv_{\mathbf{T}}}\widehat{T}\\!\left(g\right)\mathbin{\oplus}{X}^{\prime\prime}$.
That is claim 4 of Proposition 4.1 holds.

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

###### Proof.

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

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

∎

######  Lemma 6.19.

If $f\in[T],Y={\Phi_{e}\\!\left(f\mathbin{\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\mathpunct{\restriction_{n}}$ from $X$ by returning
${\Phi_{e}\\!\left(\tau^{\prime}\mathbin{\oplus}X\right)}\mathpunct{\restriction_{n}}$
for the first $\tau^{\prime}\succ\tau$ in $T$ we can find for which this is a
string of length $n$. As $Y={\Phi_{e}\\!\left(f\mathbin{\oplus}X\right)}$ and
$f\succ\tau,f\in[T]$ there must be some such $\tau^{\prime}$ 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\mathbin{\oplus}X$ then either
$Y\leq_{\mathbf{T}}X$ or
$f\leq_{\mathbf{T}}Y\mathbin{\oplus}{X}^{\prime\prime}$. That is claim 5 of
Proposition 4.1 holds.

###### Proof.

Suppose that $Y={\Phi_{e}\\!\left(f\mathbin{\oplus}X\right)}$ and, by Lemma
6.14, that $f=\widehat{T}\\!\left(g\right)$. Let $r(\sigma,n)$ where
$\lvert\sigma\rvert>e$ be the outcome of the module ${\mathcal{S}}^{n}_{e}$
assigned to some $(\alpha,\sigma)\in\mathbbm{f}$ and
$m(\sigma,n)=\xi\in\mathbbm{f}$ where $\xi^{-}=(\alpha,\sigma)$. Note that,
for all $n,\sigma\in\operatorname{dom}\widehat{T}$ with
$\lvert\sigma\rvert>e$,
$\widehat{T}\\!\left(\sigma\widehat{\phantom{x}}\mathopen{\langle}n\mathclose{\rangle}\right)\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\mathbin{\oplus}{X}^{\prime\prime}$
which, by Lemma 6.18 is equivalent to showing
$f\leq_{\mathbf{T}}Y\mathbin{\oplus}{X}^{\prime\prime}$.

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

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

If we have