2.1 Meeting one $\mathcal {P}$ requirement

To meet the requirement $\mathcal {P}_e$ , we just need to choose an initial segment of A which ensures that $A \neq W_e$ . There is no dynamic action to take.

2.2 Meeting one $\mathcal {M}$ requirement

When working with Spector-style forcing, it is common to define a tree to be a map $T \colon 2^{< \omega } \to 2^{< \omega }$ such that $\sigma \preceq \tau $ implies $T(\sigma ) \preceq T(\tau )$ . We will need to allow a node to have more than two children; so for the purposes of this proof a tree will be a computable subset of $2^{< \omega }$ so that each node $\sigma $ on the tree has finitely many children $\tau \succeq \sigma $ . The children of $\sigma $ may be of any length, where by length we mean the length as a binary string. Our trees will be perfect and have no dead ends, and in fact every node will have at least two children. Moreover, the trees will be what one might call strongly computable: for each node on the tree, one can compute a complete finite list of all of its children. As usual, $[T]$ denotes the collection of paths through T. For a Turing functional $\Phi _e$ , we will say that T is e-splitting if for any two distinct paths $\pi _1$ and $\pi _2$ through T, there is x with

$$ \begin{align*}\Phi_e^{\pi_1}(x)\downarrow \ne \Phi_e^{\pi_2}(x)\downarrow.\\[-17pt]\end{align*} $$

If $\tau _1$ and $\tau _2$ are initial segments of $\pi _1$ or $\pi _2$ respectively witnessing this, i.e., with

$$ \begin{align*}\Phi_e^{\tau_1}(x)\downarrow \ne \Phi_e^{\tau_2}(x)\downarrow,\\[-17pt]\end{align*} $$

and with a common predecessor $\sigma $ , we say that they e-split over $\sigma $ , or that they are an e-split over $\sigma $ . Note that this definition is slightly weaker than the usual definition of e-splitting (which requires all children of a node to e-split with each other), but because the trees are strongly computable it is still the case that for an e-splitting tree T and $B \in [T]$ , if $\Phi _e^B$ is total then $\Phi _e^B \geq _T B$ .

The requirements $\mathcal {M}_e$ will be satisfied by an interesting new mix of forcing and full approximation. Following the standard Spector argument, to satisfy $\mathcal {M}_e$ we attempt to make A a path on a computable tree T with either:

1. (1) T is e-splitting, and so for any path $B \in [T]$ , if $\Phi _e^B$ is total then $\Phi _e^B \geq _T B$ ; or

2. (2) for all paths $B_1,B_2 \in [T]$ and all x, if $\Phi _e^{B_1}(x) \downarrow $ and $\Phi _e^{B_2}(x) \downarrow $ then $\Phi _e^{B_1}(x) = \Phi _e^{B_2}(x)$ , and so $\Phi _e^B$ is either partial or computable for any $B \in [T]$ .

Given such a tree, any path on T satisfies $\mathcal {M}_e$ .

The standard argument for building a minimal degree is a forcing argument. Suppose that we want to meet just the $\mathcal {M}$ and $\mathcal {P}$ requirements. We can begin with a perfect tree $T_{-1}$ . Then there is a computable tree $T_0 \subseteq T_{-1}$ which is either $0$ -splitting or forces $\Phi _0^A$ to be either computable or partial. We can then choose $A_0 \in T_0$ such that $A_0$ is not an initial segment of $W_e$ . Then there is a computable tree $T_1 \subseteq T_0$ with root $A_0$ which is either $1$ -splitting or forces $\Phi _1^A$ to be either computable or partial. We pick $A_1 \in T_1$ so that $A_1$ is not an initial segment of $W_1$ , then $T_2 \subseteq T_1$ with root $A_1$ , and so on. Then $A = \bigcup A_i$ is non-computable and is a path through each $T_i$ , and so is a minimal degree. Though each $T_i$ is computable, they are not uniformly computable; given $T_i$ , to compute $T_{i+1}$ we must know whether $T_{i+1}$ is to be $(i+1)$ -splitting, to force partiality, or to force computability.

Our construction will be much more complicated, as while building the splitting trees we will need to take into account the lowness requirements. Nevertheless, the basic idea is the same: either we can find “enough” e-splits, and put A on an e-splitting tree, or above some node we can find a subtree with no e-splits which forces that A is either partial or computable. Sometimes, in addition to options (1) and (2) above, we will sometimes choose to put A on a tree that forces $\Phi _e^A$ to be partial:

1. (3) there is an x such that for all paths $B \in [T]$ , $\Phi _e^B(x) \uparrow $ .

2.3 Meeting one $\mathcal {L}$ requirement

We use something similar to the Slaman–Beyer strategy from [Reference Bayer4] to meet the lowness requirements. The entire construction will take place on a tree $T_{-1}$ with the property that it is polynomial in $|\sigma |$ to determine whether $\sigma \in T_{-1}$ , and that moreover, for each n, there are polynomially many in n strings of length n on $T_{-1}$ . For example, let $\sigma \in T_{-1}$ if it is of the form

$$ \begin{align*} a_1^{2^0} a_2^{2^1} a_3^{2^2} a_4^{2^3} \cdots, \end{align*} $$

where each $a_i \in \{0,1\}$ . So, for example, $100111100000000 \in T_{-1}$ . In this tree, there are $2^n$ nodes of height $2^n$ on the nth level of the tree.

First we will show how to meet $\mathcal {L}_{\langle e,i \rangle }$ in the absence of any other requirements. For simplicity drop the subscripts e and i so that we write $\Psi = \Psi _{e}$ and $R = R_{i}$ . The idea is to construct a computable simulation $\Xi $ of $\Psi ^A$ , with $\Xi (x)$ computable in time polynomial in the running time of $\Psi ^A(x)$ , so that if $\Psi ^A = R$ then $\Xi = \Psi ^A$ . We compute $\Xi (x)$ as follows. We computably search over $\sigma \in T_{-1}$ (i.e., over potential initial segments $\sigma $ of A) and simulate the computations $\Psi ^{\sigma }(x)$ . When we find $\sigma $ with $\Psi ^{\sigma }(x) \downarrow $ , we set $\Xi (x) = \Psi ^{\sigma }(x)$ for the first such $\sigma $ . Of course, $\sigma $ might not be an initial segment of A, and so $\Xi $ might not be equal to $\Psi ^A$ ; this only matters if $\Psi ^A = R$ is total, as otherwise $\mathcal {L}$ is satisfied vacuously. Consider two cases:

1. (1) If x is such that $\Xi (x) \downarrow \neq R(x) \downarrow $ , then there is some $\sigma \in T_{-1}$ witnessing that $\Psi ^{\sigma }(x) = \Xi (x)$ . In this case the requirement $\mathcal {L}$ asks that A extend $\sigma $ , so that $\Psi ^A(x) \neq R(x)$ and $\mathcal {L}$ is satisfied. This is the finitary outcome.

2. (2) If there is no x such that $\Xi (x) \downarrow \neq R(x) \downarrow $ , then if $\Xi $ and R both total, then $\Xi = R$ . So either $\mathcal {L}$ is vacuously satisfied, or $\Xi = \Psi ^A = R$ . The is the infinitary outcome.

In the second case we need to make sure that $\Xi $ is only polynomially slower than $\Psi ^A$ . We can do this by appropriately arranging the simulations so that if $\Psi ^{\sigma }(x) \downarrow $ in time $t(x)$ , the simulation $\Xi $ will test this computation in a time which is only polynomially slower than $t(x)$ , and will define $\Xi (x) = \Psi ^{\sigma }(x)$ if it is not already defined, so that $\Xi (x) \downarrow $ in time which is only polynomially slower than $t(x)$ . It is important here that $T_{-1}$ has only polynomially many nodes at height n and that we can test membership in $T_{-1}$ in polynomial time. (If $T_{-1}$ was, for example, the full binary tree, then there would be $2^n$ different finite oracles $\sigma $ of length n for which we must simulate computations $\Psi ^{\sigma }(x)$ ; it might be that one of these computations converges in time $\leq n$ , but that it takes time exponential in n before we get to simulating this computation and defining $\Xi (x)$ .)

Think of the simulations $\Xi $ as being greedy and taking any computation that they find; and then, at the end, we can non-uniformly choose the initial segment of A to get a diagonalization $\Phi ^A \neq R$ or to force that either the simulation $\Xi $ is actually correct.

In the rest of the paper, we will sometimes say that $\mathcal {L}$ simulates the computation $\Psi ^{\sigma }(x)$ , that $\mathcal {L}$ simulates $\sigma $ , or that $\mathcal {L}$ simulates computations above $\sigma $ . These are informal notions which will be helpful to explain the construction; the simulation process is defined more formally in Section 8.3. When we say that $\mathcal {L}$ simulates the computation $\Psi ^{\sigma }(x)$ , what we mean is that $\mathcal {L}$ computes $\Psi ^{\sigma }(x)$ and, if it converges and $\Xi (x)$ is so far undefined, sets $\Xi (x) = \Psi ^{\sigma }(x)$ . When we say that $\mathcal {L}$ simulates $\sigma $ , what we mean is that $\mathcal {L}$ simulates the computations $\Psi ^{\sigma }(x)$ for $x \leq |\sigma |$ , setting $\Xi (x) = \Psi ^{\sigma }(x)$ if possible. Finally, when we say that $\mathcal {L}$ simulates computations above $\sigma $ , we mean that $\mathcal {L}$ simulates computations $\Psi ^\tau (x)$ for various $\tau $ extending $\sigma $ , and sets $\Xi (x) = \Psi ^\tau (x)$ whenever it finds such a computation for which $\Xi (x)$ has not yet been defined. We will also sometimes say that $\mathcal {L}$ stops simulating computations above  $\sigma $ .

2.4 Meeting one $\mathcal {M}$ requirement and one $\mathcal {L}$ requirement

The interactions between the requirements get more complicated. Consider now two requirements $\mathcal {M} = \mathcal {M}_e$ and $\mathcal {L}$ , with $\mathcal {M}$ is of higher priority than $\mathcal {L}$ . Write $\Phi = \Phi _e$ . $\mathcal {L}$ will work with $\Psi $ , R, and $\Xi $ .

Assume that for each $\sigma \in T_{-1}$ , there are x and $\tau _1,\tau _2 \succeq \sigma $ such that $\Phi ^{\tau _1}(x) \downarrow \neq \Phi ^{\tau _2}(x) \downarrow $ ; and that for each $\sigma \in T_{-1}$ and x there is $\tau \succeq \sigma $ such that $\Phi ^{\tau }(x) \downarrow $ . Otherwise, we could find a subtree of $T_{-1}$ which forces that $\Phi ^A$ is either partial or computable, and satisfy $\mathcal {M}$ by restricting to that subtree. This assumption implies that we can also find any finite number of extensions of various nodes that pairwise e-split, e.g., given $\sigma _1$ and $\sigma _2$ , there are extensions of $\sigma _1$ and $\sigma _2$ that e-split. Indeed, find extensions $\tau _1,\tau _2$ of $\sigma _1$ that e-split, say $\Phi ^{\tau _1}(x) \downarrow \neq \Phi ^{\tau _2}(x) \downarrow $ , and an extension $\rho $ of $\sigma _2$ with $\Phi ^{\tau }(x) \downarrow $ . Then $\rho \ e$ -splits with one of $\tau _1$ or $\tau _2$ .

The requirement $\mathcal {L}$ non-uniformly guesses at whether or not $\mathcal {M}$ will succeed at building an e-splitting tree. Suppose that it guesses that $\mathcal {M}$ successfully builds such a tree. $\mathcal {M}$ begins with the special tree $T_{-1}$ described above, and it must build an e-splitting tree $T \subseteq T_{-1}$ . (Of course in general $\mathcal {M}$ must build an e-splitting subtree of the tree produced by some other minimality requirement, which will introduce additional complexity; we will deal with this later.)

While $\mathcal {M}$ is building the tree, $\mathcal {L}$ will be simulating various computations $\Psi ^{\sigma }$ . The tree T might be built very slowly, while $\mathcal {L}$ has to simulate computations relatively quickly in order to define $\Xi $ with only a polynomial delay. So when a node is removed from T, $\mathcal {L}$ will stop simulating computations above it; but $\mathcal {L}$ will have to simulate computations $\Psi ^{\sigma }$ for nodes $\sigma $ which are extensions of nodes in T as it has been defined so far, but which have not yet been determined to be in or not in T. This leads to the following problem: Suppose that $\gamma $ is a leaf of T at stage s, $\rho $ extends $\gamma $ , and $\mathcal {L}$ simulates $\Psi ^\rho (x)$ and sees that it converges, and so defines $\Xi (x) = \Psi ^\rho (x)$ . But then the requirement $\mathcal {M}$ finds an e-split $\gamma _1,\gamma _2 \succeq \gamma $ and wants to set $\gamma _1$ and $\gamma _2$ to be the successors of $\gamma $ on T, with both $\gamma _1$ and $\gamma _2$ incompatible with $\rho $ . If we allow $\mathcal {M}$ to do this, then since $\mathcal {M}$ has higher priority than $\mathcal {L}$ , $\mathcal {M}$ has determined that A cannot extend $\rho $ as $\mathcal {M}$ restricts A to be a path through T. So $\mathcal {L}$ has lost its ability to diagonalize and it might be that $\Psi ^A = R$ (say, because this happens on all paths through T) but $\Psi ^A(x) \neq \Psi ^\rho (x) = \Xi (x)$ . This means that $\mathcal {M}$ needs to take some action to keep computations that $\mathcal {L}$ has found on the tree. We begin by describing the most basic strategy for keeping a single node $\rho $ on the tree.

Suppose that at stage s the requirement $\mathcal {M}$ wants to add children to a leaf node $\gamma $ on T, and that $\mathcal {L}$ is simulating computations above $\gamma $ (i.e., $\gamma $ is an observation node for $\mathcal {L}$ , to be defined). The tree is supposed to be an e-splitting tree, so we need to look for e-splits above $\gamma $ . While looking for e-splits, we also need to simulate computations by $\Psi $ . It might be that, perhaps before finding any e-splits at all, we simulate a computation $\Psi _t^\rho (y) \downarrow $ and set $\Xi (y)$ to be equal to this simulated computation. For the sake of $\mathcal {L}$ we must keep $\rho $ on the tree. (Soon we will extend the strategy to worry about what happens if we have found multiple such computations, but for now assume that there is just one.) Eventually we will find some e-splits, but this might be much later; in particular, we look for $\gamma _1,\gamma _2,\gamma _3$ extending $\gamma $ such that they pairwise e-split: for any two $\gamma _i,\gamma _j$ , there is $x_{i,j}$ such that $\Phi _e^{\gamma _i}(x_{i,j}) \downarrow \neq \Phi _e^{\gamma _j}(x_{i,j}) \downarrow $ .

To begin, we stop simulating any computations extending $\rho $ . This means that we are now free to extend the tree however we like above $\rho $ without worrying about how this affects the $\mathcal {L}$ -simulations. We also stop simulating any other computations not compatible with $\gamma _1$ , $\gamma _2$ , or $\gamma _3$ . We keep simulating above $\gamma _1$ , $\gamma _2$ , and $\gamma _3$ with the expectation that, in the infinitary outcome where $\Xi = R$ , A will extend one of these.

Now look for an extension $\rho ^*$ of $\rho $ that e-splits with at least two of $\gamma _1$ , $\gamma _2$ , and $\gamma _3$ . We can find such a $\rho ^*$ by looking for one with $\Phi ^{\rho ^*}$ defined on the values $x_{i,j}$ witnessing the e-splitting of $\gamma _1$ , $\gamma _2$ , and $\gamma _3$ , e.g., if $\Phi ^{\gamma _i}(x_{i,j}) \neq \Phi ^{\gamma _j}(x_{i,j})$ , and $\Phi ^{\rho ^*}(x_{i,j}) \downarrow $ , then $\rho ^*$ must e-split with either $\gamma _i$ or $\gamma _j$ . Say that $\rho ^* \ e$ -splits with $\gamma _1$ and $\gamma _2$ . Then we define the children of $\gamma $ to be $\gamma _1$ , $\gamma _2$ , and $\rho ^*$ and stop simulating computations above $\gamma _3$ .

So of the extensions of $\gamma $ , some are still simulated by $\mathcal {L}$ , and others are not. Recall that $\Psi ^{\rho }(y)$ converged, and we defined $\Xi (y) = \Psi ^{\rho }(y)$ . If $R(y) \neq \Psi ^{\rho }(y)$ then $\mathcal {L}$ will insist that A extend $\rho ^*$ to diagonalize; this is the finitary outcome of $\mathcal {L}$ . Since in this case $\mathcal {L}$ is satisfied with the finitary outcome by having $\Psi ^A \neq R$ , computations extending $\rho ^*$ do not have to be simulated. We call $\rho ^*$ a diagonalization node (for $\mathcal {L}$ ); it is kept on the tree so that we can, if needed, meet the requirement $\mathcal {L}$ with the finitary outcome. On the other hand, if $\mathcal {L}$ fails to diagonalize and has the infinitary outcome, then A will need to extend the nodes $\gamma _1$ and $\gamma _2$ that are simulated. (If A extended $\rho ^*$ , then it might be that $\Psi ^A(z) \downarrow $ using an oracle extending $\rho ^*$ , but $\Xi (z)$ was not defined because $\mathcal {L}$ did not simulate this computation.) We say that $\gamma _1$ and $\gamma _2$ are observation nodes (for $\mathcal {L}$ ); by this we mean that computations above them are still simulated by $\mathcal {L}$ . We need two observation children $\gamma _1$ and $\gamma _2$ rather than just one in order to meet the requirements $\mathcal {P}$ . The terms diagonalization node and observation node will not be used formally in the construction, but they will make explaining the construction easier.

We also note that we assumed that $\mathcal {L}$ was still simulating computations above $\gamma $ at the start of the construction. What we mean is that $\gamma $ itself was an observation node for $\mathcal {L}$ , as was its parent, and so on, back to some node which $\mathcal {L}$ knows, via its guesses at the higher priority requirements, is an initial segment of A.

There are still some gaps in the above strategy that we must fix. What if, while looking for $\rho ^*$ , we simulate a computation $\Psi ^{\gamma _3}(z) \downarrow $ , and set $\Xi (z) = \Psi ^{\gamma _3}(z)$ , and then only after this find that $\rho ^* \ e$ -splits with $\gamma _1$ and $\gamma _2$ ? We can no longer remove $\gamma _3$ from the tree. Moreover, there might be many different nodes $\rho $ that we cannot remove from the tree—indeed, it might be that around stage s, we cannot remove any nodes at height s from the tree, because each of them has some computation that we have simulated. To deal with this, we have to build e-splitting trees in a weaker way. It will no longer be the case that every pair of children of a node $\sigma \ e$ -split, but we will still make sure that every pair of paths e-split.

So suppose again that we are trying to extend $\gamma $ . Look for a pair of nodes $\gamma _1,\gamma _2$ that e-split. Suppose that $\rho _1,\ldots ,\rho _n$ are nodes for which we have found computations $\Psi ^{\rho _i}(y_i) \downarrow $ and set $\Xi (y_i) = \Psi ^{\rho _i}(y_i)$ . Like $\rho $ above, we must keep $\rho _1,\ldots ,\rho _n$ on the tree.Footnote ¹ We stop simulating computations above $\rho _1,\ldots ,\rho _n$ .

The nodes $\gamma _1$ and $\gamma _2$ are observation nodes for $\mathcal {L}$ and the $\rho _i$ are diagonalization nodes for $\mathcal {L}$ .

Now at the next step we need to add extensions to $\gamma _1$ and $\gamma _2$ just as we added extensions of $\gamma $ . We look for extensions $\gamma _1^*$ and $\gamma _1^{**}$ of $\gamma _1$ , $\gamma _2^*$ and $\gamma _2^{**}$ of $\gamma _2$ , and $\rho _i^*$ and $\rho _i^{**}$ of $\rho _i$ such that all of these pairwise e-split. While we are looking for these, $\mathcal {L}$ must simulate more computations at nodes $\tau $ above $\gamma _1$ and $\gamma _2$ and for some of them we might see that $\Psi ^\tau (y) \downarrow $ for some y and set $\Xi (y) = \Psi ^\tau (y)$ . Just as we had to ensure that $\rho _1,\rho _2,\ldots $ remained on the tree, we also have to ensure that these $\tau $ remain on the tree. On the other hand, we no longer simulate computations above the $\rho _i$ , and so we can just look for e-splits above each $\rho _i$ without having to worry about $\mathcal {L}$ .

Here $\gamma _1^*$ , $\gamma _1^{**}$ , $\gamma _2^*$ , and $\gamma _2^{**}$ are observation nodes for $\mathcal {L}$ , since we still simulate computations above them. The $\tau $ are diagonalization nodes for $\mathcal {L}$ . The $\rho _i^*$ and $\rho _i^{**}$ are neither observation nodes nor diagonalization nodes for $\mathcal {L}$ (though of course they are extensions of diagonalization nodes).

Now at the next step of extending the tree we need to extend all of these nodes to extensions that e-split with each other; but in doing so we will introduce further extensions (above $\gamma _1^{*}$ , $\gamma _1^{**}$ , $\gamma _2^*$ , and $\gamma _2^{**}$ ) that do not e-split. So at no finite step do we get that everything e-splits with each other, but in the end every pair of paths will e-split with each other.

4.1 One $\mathcal {M}$ requirement, two $\mathcal {L}$ requirements

Consider three requirements: $\mathcal {M} = \mathcal {M}_e$ of highest priority, $\mathcal {L}_0$ of middle priority, and $\mathcal {L}_1$ of lowest priority. Write $\Psi _0$ , $R_0$ , and $\Xi _0$ and $\Psi _1$ , $R_1$ , and $\Xi _1$ for the functionals and sets corresponding to $\mathcal {L}_0$ and $\mathcal {L}_1$ respectively. Suppose that both $\mathcal {L}_0$ and $\mathcal {L}_1$ correctly guess that $\mathcal {M}$ has the infinitary outcome, building a splitting tree. Suppose also that $\mathcal {L}_1$ correctly guesses that $\mathcal {L}_0$ has the infinitary outcome, which means that if $\Psi _0^A = R_0$ is total, then we must have $\Xi _0 = \Psi _0^A$ ; this means that $\mathcal {L}_0$ must simulate every initial segment of A, i.e., they must all be observation nodes for $\mathcal {L}_0$ .

Suppose that the requirement $\mathcal {M}$ is trying to extend a node $\gamma $ . We use the same strategy as before to extend $\gamma $ , keeping certain nodes $\rho _1,\rho _2,\ldots $ on the tree. These $\rho _i$ might be kept on the tree either for the requirement $\mathcal {L}_0$ (because we defined $\Xi _0(y_i) = \Psi _0^{\rho _i}(y_i)$ ) or for the requirement $\mathcal {L}_1$ (because we defined $\Xi _1(z_i) = \Psi _1^{\rho _i}(z_i)$ ). Indeed, for each $\rho _i$ , it might be that both requirements want to keep $\rho _i$ on the tree.

The requirement $\mathcal {L}_1$ has guessed that the outcome of $\mathcal {L}_0$ is the infinitary outcome, which means that $\mathcal {L}_0$ does not need to force A to extend one of $\rho _1,\rho _2,\ldots $ . This means that $\mathcal {L}_1$ can use the same strategy as in the previous section with only one lowness requirement, and stop simulating computations above the $\rho _i$ .

Now depending on the outcome of $\mathcal {L}_1$ it might force A to extend any one of these nodes. (For example, if $\mathcal {L}_1$ has the finitary outcome $\rho _i$ , then A must extend $\rho _i$ in order to obtain a diagonalization $\Psi _1^A \neq R_1$ ; and if $\mathcal {L}_1$ has the infinitary outcome, then A will extend one of $\gamma _1$ or $\gamma _2$ .) $\mathcal {L}_0$ must simulate initial segments of A, but it does not know the outcome of $\mathcal {L}_1$ which is a lower priority requirement. So $\mathcal {L}_0$ must simulate computations through all of these nodes.

Here $\gamma _1$ and $\gamma _2$ are the observation nodes for $\mathcal {L}_1$ , while the $\rho _i$ are diagonalization nodes for $\mathcal {L}_1$ . All of $\gamma _1$ , $\gamma _2$ , and the $\rho _i$ are observation nodes for $\mathcal {L}_0$ . All of the observed and diagonalization nodes for $\mathcal {L}_1$ are observation nodes for $\mathcal {L}_0$ .

Now in the next step we found extensions $\gamma _1^{*}$ and $\gamma _1^{**}$ of $\gamma _1$ , $\gamma _2^{*}$ and $\gamma _2^{**}$ of $\gamma _2$ , and $\rho _1^*$ and $\rho _1^{**}$ of $\rho _1$ that e-split with each other. Before, we could simply extend $\rho _1$ to $\rho _1^*$ and $\rho _1^{**}$ . Now, while we are looking for the extensions, $\mathcal {L}_0$ might simulate other computations, say $\tau _1$ extending $\rho _1$ , $\tau _2$ extending $\rho _2$ , and so on. If $\mathcal {L}_0$ sees that $\Psi _0^{\tau _i}(z_i) \downarrow $ and sets $\Xi _0(z_i) = \Psi _0^{\tau _i}(z_i)$ , then $\tau _i$ must be kept on the tree. (Of course, in general, each $\rho _i$ might have many such nodes extending it.) Above each $\rho _i$ , we are essentially in the case from the previous section of having only one $\mathcal {L}$ requirement; so as before, $\mathcal {L}_0$ stops simulating above the $\tau _i$ but continues simulating above the $\rho _i^*$ and $\rho _i^{**}$ . Above $\gamma _1$ and $\gamma _2$ , we do the same thing that we did above $\gamma $ .

Here $\gamma _1^*$ , $\gamma _1^{**}$ , $\gamma _2^{*}$ , and $\gamma _2^{**}$ are observation nodes for $\mathcal {L}_1$ , while the other (unnamed) children of $\gamma _1$ and $\gamma _2$ are diagonalization nodes for $\mathcal {L}_1$ . The $\rho _i^*$ , $\rho _i^{**}$ , and $\tau _i$ are neither observation nodes nor diagonalization nodes for $\mathcal {L}_1$ but they extend the diagonalization nodes $\rho _i$ . All of the children of $\gamma _1$ and $\gamma _2$ , together with the $\rho _i^*$ and $\rho _i^{**}$ , are observation nodes for $\mathcal {L}_0$ . The $\tau _i$ are diagonalization nodes for $\mathcal {L}_0$ . Again, all of the observed and diagonalization nodes for $\mathcal {L}_1$ are observation nodes for $\mathcal {L}_0$ .

Note that, for example, $\tau _1$ may not e-split with $\gamma _1^{*}$ . This is because we were not able to choose $\rho _1$ or $\tau _1$ ; they were both forced onto the tree by the lowness requirements. But we have still made some progress: computations above $\tau _1$ are not being simulated, and so when we extend $\tau _1$ , we can find extensions that e-split with the e-splitting extensions of the other nodes.

Note that the number of levels we wait to find e-splits is now two, since there are two lowness requirements, whereas in Section 2.4 we only had to wait one level. In general, the more lowness requirements we are considering, the longer we have to wait before we can find e-splits along all paths. So it is important that we only deal with finitely many lowness requirements at a time, so that we eventually arrive at a point where parts of the tree are no longer being simulated by any lowness requirement. In the full construction, there will be some important bookkeeping to manage which lowness requirements are being considered at any particular time, so that we sufficiently delay the introduction of new lowness requirements. (This will be accomplished by giving each element of the tree a scope; see Section 5.)

Note also that every node simulated by $\mathcal {L}_1$ is also simulated by the lower priority requirement $\mathcal {L}_0$ , but that there are nodes simulated by $\mathcal {L}_0$ which are not simulated by $\mathcal {L}_1$ . Moreover, every diagonalization node for $\mathcal {L}_1$ is an observation node for $\mathcal {L}_0$ and so the nodes above diagonalization nodes for $\mathcal {L}_1$ are simulated by $\mathcal {L}_0$ . This is the first example of a relationship between the nodes simulated by one requirement and the nodes simulated by another requirement. There will be further such relationships as well.

4.2 Two $\mathcal {M}$ requirements and one $\mathcal {L}$ requirement

Consider three requirements: $\mathcal {M}_0$ of highest priority, $\mathcal {M}_1$ of middle priority, and $\mathcal {L}$ of lowest priority. Suppose that $\mathcal {M}_0$ is trying to build a $0$ -splitting tree $T_0$ , and that $\mathcal {M}_1$ and $\mathcal {L}$ correctly guess that it is successful in doing so and has the infinitary outcome. Suppose further that $\mathcal {M}_1$ is trying to build a $1$ -splitting tree $T_1$ , and $\mathcal {L}$ is working with $\Xi $ , $\Psi $ , and R.

When $\mathcal {M}_0$ is building $T_0$ we follow the same strategy as before. When extending a node $\gamma $ which is simulated by $\mathcal {L}$ , we have two children which are observation nodes, and a number of other children which are diagonalization nodes.

So we can think of the tree $T_0$ as a finitely branching tree which has, embedded in it, a subtree of nodes which are observation nodes for $\mathcal {L}$ ; each such node $\mathcal {L}$ has at least two children which are themselves observation nodes for $\mathcal {L}$ . We can picture the tree $T_0$ as looking something like this. We show the observation nodes with filled in circles, and the diagonalization nodes with open circles.

The children along bold lines are observations nodes which are children of observation nodes and so on back to the root node.Footnote ³

4.3 Two $\mathcal {M}$ requirements and two $\mathcal {L}$ requirements

Now consider four requirements: $\mathcal {M}_0$ of highest priority, $\mathcal {M}_1$ of middle priority, and $\mathcal {L}_0$ and $\mathcal {L}_1$ of lowest priority. As above, suppose that $\mathcal {M}_0$ has the infinitary outcome, successfully building a $0$ -splitting tree $T_0$ , and that all of the other requirements correctly guess this. Suppose that $\mathcal {L}_0$ guesses that $\mathcal {M}_1$ has the infinitary outcome, successfully building a $1$ -splitting subtree $T_1$ of $T_0$ , and suppose that $\mathcal {L}_1$ guesses that $\mathcal {M}_1$ has the finitary outcome, failing to build a $1$ -splitting tree. ( $\mathcal {L}_0$ and $\mathcal {L}_1$ might be of any priority ordering relative to each other, or might even be instances of the same lowness requirement which have different guesses about $\mathcal {M}_1$ .) This is the combination of the situations described in Sections 4.2.1 and 4.2.2. The observations there create a dependence between $\mathcal {L}_0$ and $\mathcal {L}_1$ :

1. (1) When $\mathcal {M}_1$ looks for a $1$ -split extending an observation node for $\mathcal {L}_0$ , it should look through extensions which are also observation nodes (Section 4.2.1).

2. (2) The diagonalization nodes for $\mathcal {L}_1$ must be among those through which $\mathcal {M}_1$ looks for $1$ -splits (Section 4.2.2).

Taken together, this means that $\mathcal {L}_0$ must simulate computations at the diagonalization nodes for $\mathcal {L}_1$ , i.e., the diagonalization nodes for $\mathcal {L}_1$ should be observation nodes for $\mathcal {L}_0$ . This might seem somewhat odd, because $\mathcal {L}_0$ and $\mathcal {L}_1$ are incompatible in the sense that they have different guesses at the outcome of the higher priority requirement $\mathcal {M}_1$ , and because $\mathcal {L}_0$ and $\mathcal {L}_1$ might be of any priority ordering relative to each other. Nevertheless, they are entangled; this is a significant source of combinatorial complexity in the full construction.

Now let us return to the construction of $T_0$ by $\mathcal {M}_0$ in the presence of these two requirements $\mathcal {L}_0$ and $\mathcal {L}_1$ . The construction goes in exactly the same way as in Section 4.1, though some of the reasoning is slightly different. In Section 4.1 the requirement $\mathcal {L}_0$ was of higher priority than $\mathcal {L}_1$ , and $\mathcal {L}_1$ guessed that $\mathcal {L}_0$ has the infinitary outcome. Now $\mathcal {L}_0$ might be of lower priority than $\mathcal {L}_1$ (or $\mathcal {L}_0$ and $\mathcal {L}_1$ might even be different instances of the same requirement); but there is some minimality requirement $\mathcal {M}_1$ such that $\mathcal {L}_0$ guesses that $\mathcal {M}_1$ has the infinitary outcome and $\mathcal {L}_1$ guesses that it has the finitary outcome. As $\mathcal {M}_0$ has higher priority than $\mathcal {M}_1$ , $\mathcal {M}_0$ does not know the outcome of $\mathcal {M}_1$ , and hence does not know which of $\mathcal {L}_0$ or $\mathcal {L}_1$ has guessed correctly. Thus it has to take both of them into account.

As in Section 4.1 suppose that $\mathcal {M}_0$ is extending a node $\gamma $ which is simulated by both $\mathcal {L}_0$ and $\mathcal {L}_1$ , and suppose that $\mathcal {M}_0$ must keep nodes $\rho _1,\rho _2,\ldots $ on $T_0$ because we have set $\Xi _1(x_i) = \Psi _1^{\rho _i}(x_i)$ . As in Section 4.1 we will make the extension as follows:

This is exactly the same as in Section 4.1, but now the argument that $\mathcal {L}_0$ must continue to simulate computations above $\rho _1,\rho _2,\ldots $ is different from before. It is now because the $\rho _i$ are diagonalization nodes for $\mathcal {L}_1$ and, as argued above, as a consequence of (1) and (2) these must be observation nodes for $\mathcal {L}_0$ .

4.4 The relation of watching

We have already seen two situations in which a requirement $\mathcal {L}_1$ must ensure that the diagonalization nodes for another requirement $\mathcal {L}_0$ are all observation nodes for $\mathcal {L}_1$ , thereby ensuring that $\mathcal {L}_1$ simulates computations above these diagonalization nodes for $\mathcal {L}_0$ .

We will introduce a relation $\mathcal {L}_{d_1}^{\nu _1} \rightsquigarrow \mathcal {L}_{d_2}^{\nu _2}$ to represent this. We suggest reading $\mathcal {L}_{d_1}^{\nu _1} \rightsquigarrow \mathcal {L}_{d_2}^{\nu _2}$ as “ $\mathcal {L}_{d_1}^{\nu _1}$ watches $\mathcal {L}_{d_2}^{\nu _2}$ .” The two situations we have seen are:

1. (1) If $d_1 < d_2$ and $\nu _1 \prec \nu _2$ then we should have $\mathcal {L}_{d_1}^{\nu _1} \rightsquigarrow \mathcal {L}_{d_2}^{\nu _2}$ (Section 4.1).

2. (2) If $\mathcal {L}_{d_1}^{\nu _1}$ and $\mathcal {L}_{d_2}^{\nu _2}$ first disagree on the outcome of a minimality requirement $\mathcal {M}$ , $\mathcal {L}_{d_1}^{\nu _1}$ guesses that $\mathcal {M}$ will have the infinitary outcome, and $\mathcal {L}_{d_2}^{\nu _2}$ guesses that it will have the finitary outcome, then we should have $\mathcal {L}_{d_1}^{\nu _1} \rightsquigarrow \mathcal {L}_{d_2}^{\nu _2}$ (Section 4.3).

The reader will immediately notice that this resembles a lexicographic ordering. We will give a formal definition of $\rightsquigarrow $ which captures (1) and (2).

Definition 4.1. Given a string of outcomes $\nu $ , define $\Delta (\nu ) \in \{\mathsf {f},\infty \}^{< \omega }$ to be the string

$$ \begin{align*} \langle \nu(\mathcal{M}_0),\nu(\mathcal{M}_1),\nu(\mathcal{M}_2),\ldots \rangle ,\end{align*} $$

except that we replace any entry which is not $\infty $ with $\mathsf {f}$ . Put an ordering $\precsim $ on these using the lexicographic order with $\infty < \mathsf {f}$ .

$\mathcal {L}_{d_1}^{\nu _1} \rightsquigarrow \mathcal {L}_{d_2}^{\nu _2}$ means that, given a node $\sigma $ which is an observation node for both requirements, any child of $\sigma $ which is an observation or diagonalization node for $\mathcal {L}_{d_2}^{\nu _2}$ should be an observation node for $\mathcal {L}_{d_1}^{\nu _1}$ .

4.5 Two $\mathcal {M}$ requirements and one $\mathcal {L}$ requirement, sandwiched

In Section 4.2 we considered the case of four requirements: $\mathcal {M}_0$ of highest priority, $\mathcal {M}_1$ of middle priority, and $\mathcal {L}$ of lowest priority. Consider now three requirements: $\mathcal {M}_e$ of highest priority, $\mathcal {L}_e$ of middle priority, and $\mathcal {M}_{e+1}$ of lowest priority. Suppose that $\mathcal {M}_e$ successfully builds an e-splitting tree $T_e$ , and that $\mathcal {L}$ correctly guess this.

Consider the diagram from Section 4.2 of the tree $T_e$ , with the observation nodes for $\mathcal {L}$ given in bold. We show the observation nodes with filled in circles, and the diagonalization nodes with open circles.

Suppose moreover that $\mathcal {L}_e$ has the infinitary outcome. This means that $\mathcal {L}_e$ was not able to obtain a diagonalization by having A extend one of the diagonalization nodes. So as previously described, $\mathcal {L}_e$ requires that A be a path through the observation nodes for $\mathcal {L}_e$ . The way that we will enforce this is to ensure that when $\mathcal {M}_{e+1}$ builds an $e+1$ -splitting tree $T_1$ , or a tree $T_{e+1}^*$ with no $e+1$ -splits, it builds it as a subtree of the observation nodes for $\mathcal {L}_e$ . (Recall also from Section 4.4 that $\mathcal {L}_e$ is minimal under the watching relation among all instances of lowness requirements of lower priority than $\mathcal {M}_e$ ; this means that all of the diagonalization nodes for these requirements are observation nodes for $\mathcal {L}_e$ , and so these diagonalization nodes can all be preserved on the tree built by $\mathcal {M}_{e+1}$ .)

6.1 One $\mathcal {M}$ requirement and one $\mathcal {L}$ requirement, redux

We begin by revisiting Section 2.4. We have two requirements $\mathcal {M} = \mathcal {M}_e$ and $\mathcal {L} = \mathcal {L}_e$ , so that $\mathcal {M}$ is of higher priority than $\mathcal {L}$ . Let $T_{e-1}$ be the tree built by $\mathcal {M}_{e-1}$ , and assume that we have enough e-splits on $T_{e-1}$ . $\mathcal {M}$ is building an e-splitting tree T and $\mathcal {L}$ is guessing that it is successful.

Suppose that we have determined that $\gamma $ is on T and we are trying to extend it. Suppose also that $\operatorname {\mathrm {scope}}_e(\gamma ) = 0$ so that we are only concerned with the single requirement $\mathcal {L}$ . We are then assigning labels from $\mathtt {Labels}_1 = \{ \top \succ \varnothing \}$ . Suppose that $\gamma $ has the label $\top $ , and is an observation node for $\mathcal {L}$ . We look for a pair of nodes $\gamma _1,\gamma _2$ on

that e-split. Since we assumed that these exist, at some point we will find them at stage s. Now let $\rho _1,\ldots ,\rho _n$ be the other nodes on $T_{e-1}[s]$ . $\mathcal {L}$ stops simulating computations above $\rho _1,\ldots ,\rho _n$ .

The nodes $\gamma _1$ and $\gamma _2$ are the main children of $\gamma $ and are also labeled $\top $ , while the $\rho _i$ are secondary children and are labeled $\varnothing $ .

Now at the next step we look for $\gamma _1^*$ and $\gamma _1^{**}$ on

, $\gamma _2^*$ and $\gamma _2^{**}$ on

, and $\rho _i^*$ and $\rho _i^{**}$ on

such that all of these pairwise e-split. The nodes $\gamma _1$ and $\gamma _2$ also get children $\tau $ .

Here $\gamma _1^*$ , $\gamma _1^{**}$ , $\gamma _2^*$ , and $\gamma _2^{**}$ are labeled $\top $ , and the $\tau $ , $\rho _i^*$ , and $\rho _i^{**}$ are labeled $\varnothing $ . The main children of $\gamma _1$ are $\gamma _1^*$ and $\gamma _1^{**}$ ; the main children of $\gamma _2$ are $\gamma _2^*$ and $\gamma _2^{**}$ ; and the main children of $\rho _i$ are $\rho _i^*$ and $\rho _i^{**}$ . The $\tau $ are secondary children.

6.2 One $\mathcal {M}$ requirement and two $\mathcal {L}$ requirements, redux

We now revisit Section 4.1. Consider three requirements: $\mathcal {M}_e$ of highest priority, $\mathcal {L}_{e}$ of middle priority, and $\mathcal {L}_{e+1}$ of lowest priority. Because $\mathcal {L}_{e+1}$ is guessing at the outcome of $\mathcal {M}_{e+1}$ , and $\mathcal {M}_e$ does not know this outcome, $\mathcal {M}_e$ has to consider both instances $\mathcal {L}_{e+1}^{\mathsf {f}}$ and $\mathcal {L}_{e+1}^{\infty }$ which guess that $\mathcal {M}_{e+1}$ has the finitary or infinitary outcome respectively. (We omit from the superscript of the instance the guesses at the outcomes of requirements $\mathcal {M}_0,\ldots ,\mathcal {M}_e$ .)

Suppose that the requirement $\mathcal {M}_e$ is trying to extend a node $\gamma $ and that $\operatorname {\mathrm {scope}}(\gamma ) = 1$ so that we are only concerned with $\mathcal {L}_e$ , $\mathcal {L}_{e+1}^{\mathsf {f}}$ , and $\mathcal {L}_{e+1}^{\infty }$ . We have

$$ \begin{align*} \mathtt{Labels}_{2} = \{ \top \succ \mathsf{f} \succ \infty \succ \varnothing\}.\end{align*} $$

The labels $\varnothing $ , $\mathsf {f}$ , and $\infty $ correspond respectively to $\mathcal {L}_e$ , $\mathcal {L}_{e+1}^{\mathsf {f}}$ and $\mathcal {L}_{e+1}^{\infty }$ . So we have

$$ \begin{align*} \mathcal{L}_e \rightsquigarrow \mathcal{L}_{e+1}^{\infty} \rightsquigarrow \mathcal{L}_{e+1}^{\mathsf{f}}.\end{align*} $$

At the first level, we have:

At the next level, we have:

It is only at the following stage that we get some nodes which are labeled $\varnothing $ and which are not observation nodes for $\mathcal {L}_{e+1}^\infty $ .

6.3 Two $\mathcal {M}$ requirements and one $\mathcal {L}$ requirement, sandwiched, redux

Finally, we revisit Section 4.5. We consider three requirements: $\mathcal {M}_e$ of highest priority, $\mathcal {L}_{e}$ of middle priority, and $\mathcal {M}_{e+1}$ of lowest priority. Suppose that $\mathcal {M}_e$ successfully builds an e-splitting tree $T_e$ , and that $\mathcal {L}_e$ correctly guesses this. If $\mathcal {L}_e$ has the infinitary outcome, then we need A to live within the observation nodes for $\mathcal {L}_e$ . Recall that the way that we ensure that this happens is that $\mathcal {M}_{e+1}$ will work only within the observation nodes for $\mathcal {L}_e$ when it builds its $1$ -splitting tree.

Let $\eta $ be the guesses by $\mathcal {L}_e$ at the higher priority requirements. Since $\mathcal {L}_e$ is the highest priority requirement after $\mathcal {M}_e$ , we have $\Delta _{> e}(\eta ) = \varnothing $ . Thus the nodes labeled $\varnothing $ are those that might be diagonalization nodes for $\mathcal {L}_e$ , and those with labels $\succ \varnothing $ are observation nodes for $\mathcal {L}_e$ . Thus if $\rho $ is the node at which we want to start building $T_{e+1}$ , then we want to build $T_{e+1}$ as a subtree of .

6.4 A new issue

There is one more issue which we have glossed over previously (and so some of the previous examples are somewhat misleading without keeping this issue in mind). Consider the requirements $\mathcal {M}_{e-1}$ , with corresponding tree $T_{e-1}$ , and $\mathcal {M}_e$ , which is building an e-splitting subtree of $T_{e-1}$ . Suppose that $\mathcal {M}_e$ has the infinitary outcome. Let $\mathcal {L}^\nu $ be an instance of a requirement of lower priority than $\mathcal {M}_e$ . The issue is that the labels on $T_{e-1}$ might affect the labels on $T_e$ : essentially, if we determine that a node on $T_{e-1}$ is not an observation node for $\mathcal {L}^\nu $ , then this means that $\mathcal {L}^\nu $ stops simulating computations above that node, and so no node extending that node should be an observation node on $T_{e}$ .

Let $\eta = \Delta _{> e}(\nu )$ . Assume that $\mathcal {L}$ guesses correctly that $\mathcal {M}_e$ has the infinitary outcome, so that $\Delta _{> e-1}(\nu ) = \infty \eta $ .

Suppose that we have determined on $T_e$ that $\sigma ^*$ should be a child of $\sigma $ , with $\sigma $ an observation node for $\mathcal {L}$ on both $T_{e-1}$ and $T_e$ . On $T_{e-1}$ , we might have a sequence of children $\sigma = \sigma _0,\sigma _1,\ldots ,\sigma _n = \sigma ^*$ . If any of these is not an observation node for $\mathcal {L}^\nu $ on $T_{e-1}$ —that is, if $\ell _{e-1}(\sigma _i) \nsucc \infty \eta $ —then $\sigma ^*$ should not be an observation node for $\mathcal {L}^\nu $ on $T_e$ —that is, we should have $\ell _e(\sigma ^*) \nsucc \eta $ .

7.1 Procedure for constructing splitting trees

We are now ready to describe the procedure for constructing splitting trees. Given the tree $T_{e-1}$ constructed by $\mathcal {M}_{e-1}$ , we will describe the (attempted) construction by $\mathcal {M}_{e}$ of an e-splitting subtree T. This construction will be successful if there are enough e-splittings in $T_{e-1}$ . The construction will happen above some root node $\rho $ , which is determined by $T_{e-1}$ together with the outcomes of the requirements $\mathcal {L}_{e-1}$ and $\mathcal {P}_{e-1}$ . For example, if $\mathcal {L}_{e-1}$ has the finitary outcome, then $\rho $ will extend this.

The construction will be given by a procedure Procedure(e, $\rho $ , $T_{e-1}$ ) for building an e-splitting tree T with root $\rho $ in $T_{e-1}$ . We write $T[n]$ for the tree up to and including the nth level.

Procedure(e, $\rho $ , $T_{e-1}$ ):

Input: A value $e \geq 0$ , an admissible labeled tree $T_{e-1}$ with labels $\ell _{e-1}(\cdot )$ and scopes $\operatorname {\mathrm {scope}}_{e-1}(\cdot )$ , and a node $\rho $ on $T_{e-1}$ with $\ell _{e-1}(\rho ) = \top $ .

Output: A possibly partial labeled e-splitting tree T, built stage-by-stage.

Construction. To begin, the root node of T is $\rho $ with $\operatorname {\mathrm {scope}}(\rho ) = 1$ and $\ell (\rho ) = \top $ . This is the zeroth level of the tree, $T[0]$ . At each stage of the construction, if we have so far built T up to the nth level $T[n]$ , we try to add an additional ( $n+1$ )st level.

At stage s, suppose that we have defined the tree up to and including level n, and the last expansionary level $\leq n$ was $e_t$ . Look for a length l such that for each leaf $\sigma $ of $T[n]$ , there is an extension $\sigma '$ of $\sigma $ with with $\ell _{e-1}(\sigma ') = \top $ , and there are extensions $\sigma ^*$ and $\sigma ^{**}$ of $\sigma $ on , such that $\sigma ^*$ and $\sigma ^{**}$ are of length l, and such that all of these extensions pairwise e-split, i.e., for each pair of leaves $\sigma ,\tau $ of $T[n]$ , these extensions $\sigma ^*$ , $\sigma ^{**}$ , $\tau ^*$ , and $\tau ^{**}$ all e-split with each other. (At stage s, we look among the first s-many extensions of these leaves, and we run computations looking for e-splits up to stage s. If we do not find such extensions, move on to stage $s+1$ .)

If we do find such extensions, we will define $T[n+1]$ as follows. To begin, we must wait for $T_{e-1}[s]$ to be defined. In the meantime, we designate each $\sigma $ as waiting with main children $\sigma ^*$ and $\sigma ^{**}$ .Footnote ⁴ While waiting, we still count through stages of the construction, so that after we resume the next stage of the construction will not be stage $s+1$ but some other stage $t> s$ depending on how long we wait. Once $T_{e-1}[s]$ has been defined, for each leaf $\sigma $ of $T[n]$ , the children of $\sigma $ in $T[n+1]$ will be:

• • $\sigma ^*$ , with:

  1. – If no predecessor of $\sigma $ on T, including $\sigma $ itself, is a tth expansionary node, set $\operatorname {\mathrm {scope}}({\sigma }^*) = \operatorname {\mathrm {scope}}(\sigma )+1$ and $\ell ({\sigma }^*) = \top $ (so that $\sigma ^*$ is a tth expansionary node).

  2. – Otherwise, set $\operatorname {\mathrm {scope}}({\sigma }^*) = \operatorname {\mathrm {scope}}(\sigma )$ and $\ell ({\sigma }^*) = \ell (\sigma )$ .

• • $\sigma ^{**}$ , with:

  1. – If no predecessor of $\sigma $ on T, including $\sigma $ itself, is a tth expansionary node, set $\operatorname {\mathrm {scope}}({\sigma }^{**}) = \operatorname {\mathrm {scope}}(\sigma )+1$ and $\ell ({\sigma }^{**}) = \top $ (so that $\sigma ^{**}$ is a tth expansionary node).

  2. – Otherwise, set $\operatorname {\mathrm {scope}}({\sigma }^{**}) = \operatorname {\mathrm {scope}}(\sigma )$ and $\ell ({\sigma }^{**}) = \ell (\sigma )$ .

• • If $\ell (\sigma ) \succ \varnothing $ , each other maximal extension $\sigma ^\dagger $ of $\sigma $ on which is incompatible with $\sigma ^*$ and $\sigma ^{**}$ will be a child of $\sigma $ on T.Footnote ⁵ Put $\operatorname {\mathrm {scope}}(\sigma ^\dagger ) = \operatorname {\mathrm {scope}}(\sigma )$ . Define $\ell (\sigma ^\dagger )$ as follows. Let $n = \operatorname {\mathrm {scope}}(\sigma )$ . Let $\eta \in \mathtt {Labels}_{n}$ be greatest such that . Then:

  1. – If $\eta $ is $\top $ or begins with $\mathsf {f}$ , then let $\ell (\sigma ^\dagger ) = \operatorname {\mathrm {pred}}_{n}(\ell (\sigma ))$ .

  2. – If $\eta $ begins with $\infty $ , say $\eta = \infty \eta ^*$ , then $\ell (\sigma ^\dagger )$ will be the minimum, in $\mathtt {Labels}_{n}$ , of $\operatorname {\mathrm {pred}}_{n}(\ell (\sigma ))$ and $\eta ^*$ .Footnote ⁶

  Note that $\operatorname {\mathrm {pred}}_n(\ell (\sigma ))$ exists because $\ell (\sigma ) \succ \varnothing $ . (Recall that $\operatorname {\mathrm {pred}}_n$ is the predecessor relation on labels of length at most n.)

The children ${\sigma }^*$ and ${\sigma }^{**}$ are the main children of $\sigma $ , and the $\sigma ^\dagger $ , if they exist, are secondary children. This ends the construction at stage s.

End construction.

We say that the procedure is successful if it never gets stuck, and constructs the nth level of the tree T for every n. The next lemma is the formal statement that if $T_{e-1}$ has enough e-splits, then the procedure is successful.