A nonlow_{2} r.e. degree with the extension of embeddings properties of a low_{2} degree

Richard A. Shore^{∗} Department of Mathematics Cornell Univeristy Ithaca NY 14853

Yue Yang Department of Mathematics National University of Singapore Singapore 119260

July 13, 2000

Abstract

We construct a nonlow_{2} r.e. degree d such that every extension of embedding property that holds below every low_{2} degree holds below d. Indeed, we can also guarantee the converse so that there is a low r.e. degree c such that that the extension of embedding properties true below c are exactly the ones true below d. Moreover, we can also guarantee that no b ≤ d is the base of a nonsplitting pair.

1 Introduction

Our goal in this paper is to show how constructions establishing properties shared by all low_{2} r.e. degrees (i.e. ones c such that c′′ = 0′′) can be modified to construct a nonlow_{2} degree with the same properties. This implies that none of the properties considered (nor indeed all of them together) can separate the low r.e. degrees from the nonlow_{2} ones. In particular, none of them can define the low_{2} r.e. degrees inside the structure R of all the r.e. degrees.

As examples, we consider the properties established for all low_{2} r.e. degrees in Shore and Slaman [1990]. In particular, in §1 we consider extension of embedding properties. (If X ⊆ Y are partial orderings with the same least and greatest elements 0 and 1, we say that a partial ordering P (with 0 and 1) satisfies the extension of embedding property for X and Y if every embedding of X into P (preserving 0 and 1) can be extended to one of Y.) Thus we construct a nonlow_{2} r.e. D such that every extension of embedding property that holds below every low_{2} r.e. degree (i.e. in R(≤ c), the r.e. degrees below c, for every low_{2} r.e. c) holds below d. We then explain in §2 how, in addition, we can make any such property which fails below some low_{2} r.e. degree also fail below d. As there is also a low r.e. c with this same property, we see that even the intersection of all of these properties fails to distinguish between the low or low_{2} r.e. degrees and the nonlow_{2} ones. In §3 we show how to simultaneously obtain a result previously obtained directly by Cooper, Li and Yi [ta] by making d not bound any base of a nonsplitting pair, i.e. for every u < v with u ≤ d there are v_{0} and v_{1} such that u < v_{0}, v_{1} < v and v_{0} ⊕ v_{1} ≡_{T} v.

∗Partially supported by NSF Grant DMS-9802843 and a Visiting Distinguished Professorship at the National University of Singapore.

In the case of low_{2} degrees, all these constructions proceed by converting what would, without the assumption of low_{2}-ness, be infinite injury requirements into finite ones. The crucial point typically is that some positive or negative action would become infinite when some functional involved in the requirement appears total by having the lim sup of its domain of convergence go to infinity but is not actually total. This problem is typically handled by using the low_{2}-ness of the oracle to guess at the totality the functional. The true outcome is guessed infinitely often and the priority tree can be arranged so that it is also the leftmost outcome guessed infinitely often. Thus, if we guess that the function is not total, no action is necessary. On the other hand, if we guess that it is total then we are assured of the guess being correct and we can act accordingly. In our constructions here, we replace the guessing at totality by a requirement that forces the specific functional being considered to actually be total if the lim sup of its domain goes to infinity. Not surprisingly, the natural mechanism for such a procedure is the restraint typically imposed to make a degree low_{2}. What we do here is intersperse these requirements with ones that instead make the set constructed nonlow_{2}. The conflict between these requirement is then the new feature of the construction. It is handled in the usual fashion of 0′′′ type priority arguments.

2 Extension of Embeddings

We first consider satisfying extension of embedding properties. We briefly recall the necessary definitions and notations and refer to Shore and Slaman [1990] for background and other information.

We begin with the nonextendibility conditions. Let

{x_{0}, …, x_{n}} = X ⊆ Y = {x_{0}, …, x_{n}, y_{0}, …, y_{m}}

be partial orderings (with x_{0} = 0, the least element of Y and x_{1} = 1, the greatest element of Y). The nonextendibility conditions are as follows.

i) For some i and j, x_{i} ≰ y_{i} but

∀x ∈ X [∀x′ ∈ X (x′ < y_{i} → x′ ≤ x) → x_{j} ≤ x].

ii) For some i and j, y_{i} ≰ x_{j} but

∀x ∈ X [∀x′ ∈ X (y_{i} ≤ x′_{i} → x ≤ x′) → x ≤ x_{j}].

iii) For some i and j, y_{i} ≰ y_{j} but

∀x, x′ ∈ X [∀x′′ ∈ X (x′′ < y_{j} → x′′ ≤ x) & ∀x′′ ∈ X (y_{i} ≤ x′′ → x′ ≤ x′′) → x′ ≤ x].

Shore and Slaman [1990] proved the following Non-Extendibility Lemma and Extendibility Lemma for low_{2} r.e. degrees.

Lemma 2.1 (Shore and Slaman [1990) ] If X ⊆ Y are partial orderings satisfying one of the nonextendibility conditions then there is a low_{2} c and a monomorphism f : X → R(≤ c) which cannot be extended to one of Y.

Lemma 2.2 (Shore and Slaman [1990) ] Let X ⊆ Y be finite partial orderings not satisfying any of the nonextendibility conditions. If c is an r.e. low_{2} degree and f : X → R(≤ c) is a monomorphism given by x_{i} ↦ deg X_{i} = x_{i} for x_{i} ∈ X, then there is an extension of f given by y_{i} ↦ deg Y_{i} = y_{i} for y_{i} ∈ Y.

Next, we recall some notations. For each y_{j} ∈ Y − X we let

X_{g,j} = ⊕{X_{i}|x_{i} ≤ y_{j}}

and

X_{l,j} = ⊕{X_{i}|∀x ∈ X (x ≥ y_{j} → x_{i} ≤ x)}.

Given enumerations W_{s} and Z_{s} of r.e. sets W and Z, the associated length of agreement function and maximum length of agreement function are defined as follows:

l(e, s, W, Z) = μx(¬[Φ_{e,s}^{W_{s}}(x) ↓= Z_{s}(x)])

and

m(e, s, W, Z) = max{l(e, t, W, Z)|t ≤ s}.

The strategies to satisfy various comparability and incomparability requirements are as follows.

a) The requirements that x_{i} ≤ y_{j} ⇒ X_{i} ≤_{T} Y_{j} are met by coding, i.e., making Y_{j}^{[0]} = {0} × X_{g,j}.

b) The requirements that y_{j} ≤ x_{i} ⇒ Y_{j} ≤ X_{i} are met by permitting. Any number entering Y_{j}^{[>0]} must be permitted by X_{l,j}. c) The requirements that y_{i} < y_{j} ⇒ Y_{i} ≤ Y_{j} are also met by coding, i.e., making

Y_{j}^{[i+1]} = {i + 1} × Y_{i}^{[>0]}.

d) The requirements that x_{j} ≰ y_{i} ⇒ X_{j} ≰_{T} Y_{i} are met by Sacks preservation. We keep numbers out of Y_{i} to preserve the computations of Φ_{e}^{Y_{i}} through the maximum length agreement m(e, s, Y_{i}, X_{j}).

e) The requirements that y_{i} ≰ x_{j} ⇒ Y_{i} ≰_{T} X_{j} are met by Sacks coding. We code X_{l,i} into Y_{i} up to the maximum length of agreement m(e, s, X_{j}, Y_{i}).

f) The requirements that y_{i} ≰ y_{j} ⇒ Y_{i} ≰_{T} Y_{j} are met by both preservation and coding. We keep numbers out of Y_{j} to preserve the computations of Φ_{e}^{Y_{j}} up to m(e, s, Y_{j}, Y_{i}) and simultaneously code X_{l,i} up to this length of agreement into Y_{i}.

In Shore and Slaman [1990], the condition that the top set C is low_{2} is used to guess the totality of various functionals on the true path. We now see that there is a nonlow_{2} set which has the same extension of embedding properties.

Theorem 2.3 There is a nonlow_{2} r.e. degree d such that every extension of embedding property that holds below every low_{2} r.e. degree holds below d, in other words, if X ⊆ Y are finite partial orderings not satisfying any of the nonextendibility conditions and f : X → R(≤ d) is a monomorphism given by x_{i} ↦ deg X_{i} = x_{i} for x_{i} ∈ X, then there is an extension of f given by y_{i} ↦ deg Y_{i} = y_{i} for y_{i} ∈ Y.

Description of Strategies We construct an r.e. set D. The primary requirements are of two types. M_{e} for the extension of embeddings and R_{e} for nonlow_{2}-ness.

M_{e} is the e^{th} instance of an extension of embedding problem as in Lemma 2.2. It specifies finite partial orders X_{e} ⊆ Y_{e} with elements x_{i}, i < n_{e} of X_{e} and y_{j}, j < m_{e} of Y_{e} − X_{e} and an ordering ⪯_{e} and representatives X_{e,i}, i < n_{e} of the elements of X_{e} as r.e. sets along with functionals computing them from D, Φ_{e,i}^{D}(x) = X_{e,i}(x). In later constructions, we only use X_{e,i} up to Φ_{e,i}^{D}, that is, even if a number x has entered X_{e,i} by stage s, we still wait for confirmation that Φ_{e,i}^{D}(x) ↓= 1 before we act on the basis of x’s being in X_{e,i}. We assure that the positive ordering facts about ⪯_{e} are reflected in ≤_{T} on the X_{e,i} by requiring that if i ≺_{e} j then X_{e,j}^{[i]} = {i} × X_{e,i} for i, j < n_{e}. M_{e} acts, if it can, to guarantee the totality of the Φ_{e,i} by a restraint imposing requirement similar to those used to make sets low_{2}.

• M_{e}: If the maximum length of agreement functions m(⟨e, i⟩, s, D, X_{e,i}) between Φ_{e,i}^{D} and X_{e,i} go to infinity for all i < n_{e} then these functions are all total (and so Φ_{e,i}^{D} = X_{e,i} for all i < n_{e}).

This goal is met by requiring that, each time a new maximum length of agreement has been reached for every i < n_{e}, lower priority requirements can injure computations below this new maximum t only a finite number of times altogether. Roughly speaking, each such requirement of lower priority with a candidate to put into D can use its current candidate but all new ones appointed later must wait for the length of agreement at M_{e} to increase and then be chosen larger than all uses for numbers ≤ t. Alternatively, a requirement higher up on the priority tree but associated with some global requirement R_{i} of higher priority than M_{e} may be allowed to injure all computations of some Φ_{e,i}^{D}(m) for all sufficiently large m. However, its injuring M_{e} infinitely often corresponds to satisfying R_{i}. In such cases, we restart M_{e} above this outcome in the typical 0′′′ fashion.

The outcomes for M_{e} are as usual: ∞ for the maximum length of agreement going to infinity and 0 for its having a finite lim sup. In the latter case, we satisfy M_{e} by default and so do not put any subrequirements for M_{e} on the tree above the outcome 0.

Above the outcome ∞, we expect to enumerate sets Y_{e,j}, j < m_{e} so that we produce an order monomorphism from Y into R as long as the map given by x_{e,i} ↦ deg(X_{e,i}) is itself an order monomorphism. The positive aspects of the order preserving map conditions are met by overriding coding and permitting requirements (a), (b), (c) on the enumerations as in Shore and Slaman [1990]. The negative aspects of the order preserving map conditions are achieved by the subrequirements N_{e,i}, P_{e,i} and Q_{e,i} associated with M_{e}. They correspond to the requirements of type (d), (e) and (f), respectively, in Shore and Slaman [1990]. These subrequirements act the same way as the corresponding requirements in Shore and Slaman [1990] as far as imposing restraint on, and enumerating numbers into, the Y_{e,j}. Note that as far as these actions are concerned they do nothing to D and are not influenced by any requirements other than N_{e,k}, P_{e,k} and Q_{e,k} for k ∈ ω as in Shore and Slaman [1990]. In addition, they replace the oracle guessing at totality using low_{2}-ness from Shore and Slaman [1990] by imposing low_{2}-like restraint to guarantee the totality of the relevant functionals if the associated maximum length of agreement goes to infinity.

We let i = ⟨a, b, c⟩ and Ψ_{c} list the partial recursive functionals for c ∈ ω. We list the types of subrequirements. Their actions for coding into and preservation on the Y_{e,j} are as described in Shore and Slaman [1990]. In addition, they each have some functional computed from D. We specify this functional below in terms of oracles involving X_{e,j} and Y_{e,k} but as all of these sets are uniformly computable from D (recall that the set D is X_{e,1}, which is the top set of the partial ordering), we may uniformly view the functional as one with oracle D. The requirements attempt to make this functional total if its maximal length of agreement goes to infinity by appropriate restraint. Of course, computations from the given oracles are only accepted when the required information about the X_{e,j} is computed from D. It is worth pointing out that all computations are automatically “believable” ones. In a typical tree argument we are often required to use believable computations, i.e., ones not in conflict with the nodes assumptions about the action of positive requirements below of higher priority, which may be expected to put infinite recursive sets into the oracle. As we shall see later in the construction, if, at s, a node α expects a higher priority node β to put numbers less than s into the oracle, then whenever α is accessible, β has already put in those numbers.

We now list the subrequirements of M_{e} explicitly to fix our notation.

• N_{e,i}: x_{e,a} ≰ y_{e,b} ⇒ Ψ_{c}^{Y_{e,b}} ≠ X_{e,a}; Ψ_{c}^{Y_{e,b}} total if lim m(c, s, Y_{e,b}, X_{e,a}) = ∞.

• P_{e,i}: y_{e,a} ≰ x_{e,b} ⇒ Ψ_{c}^{X_{e,b}} ≠ Y_{e,a}; Ψ_{c}^{X_{e,b}} total if lim m(c, s, X_{e,b}, Y_{e,a}) = ∞.

• Q_{e,i}: y_{e,a} ≰ y_{e,b} ⇒ Ψ_{c}^{Y_{e,b}} ≠ Y_{e,a}; Ψ_{c}^{Y_{e,b}} total if lim m(c, s, Y_{e,b}, Y_{e,a}) = ∞.

The outcomes for N, P and Q type requirements are again ∞ for the maximum length of agreement going to infinity and 0 for its having a finite lim sup. If any of these requirements, say Q, has an infinitary outcome ∞, i.e. the associated maximum length of agreement goes to infinity, then the associated functional is total and we win M_{e} by demonstrating that one of the negative facts assumed about ⪯_{e} is false. (In Shore and Slaman [1990], this corresponds to the argument that, as we are there assuming that all these facts about ⪯_{e} are true, all the outcomes of requirements of type (d), (e) and (f) are finite.) In this case, we restart all requirements of lower priority than M_{e} above the infinitary outcome of Q but not, of course, M_{e} (or any of its subrequirements). In particular, note that if there is some R_{i} originating at a node between M_{e} and this subrequirement (and so of lower priority than M_{e}) then R_{i} is restarted above the infinitary outcome of Q as described below and so no subrequirements of the version of R_{i} originating between M_{e} and Q is put on the tree above the infinitary outcome of Q. If, along the true path, all subrequirements of M_{e} have finitary outcomes, we argue that the sets Y_{e,j} constructed satisfy the requirements to meet all the goals of M_{e}.

We now consider the requirements for making D not low_{2}. We build a single functional Λ(D; x, m) and guarantee (via requirements R_{e}) that for the eth Σ_{3} set

Σ_{e} = {x|∃m∀y∃z(θ_{e}(x, m, y, z) ↓)}

there is an x such that Λ_{x}^{D} = {m|Λ(D; x, m) ↓} is infinite if and only if x ∉ Σ_{e}. The point here is that {x|Λ_{x}^{D} is infinite} is a Π_{2}^{D} set and these requirements will guarantee that it is not a Σ_{3} set. Thus D cannot be low_{2}.

• R_{e}: There is an x such that Λ_{x}^{D} = {m|Λ(D; x, m) ↓} is infinite if and only if x ∉ Σ_{e}.

R_{e} begins by choosing a witness x for diagonalization. As time goes by and R_{e} is accessible, it enumerates axioms for Λ(D; x, m) for each m. It has subrequirements S_{e,x,m} for each m. They test for m being a witness to the Σ_{3} fact that x ∈ Σ_{e} by looking for verifications of the associated Π_{2} fact ∀y∃z(θ_{e}(x, m, y, z)) ↓ for successive y’s. The outcomes of such a subrequirement are either ∞ or 0 depending on whether the Π_{2} fact is true or not. Each time it finds a witness for a new y, it tries to make Λ(D; x, n) ↑ for each n ≥ m to the extent that its priority allows by enumerating a number less than the use λ(x, n) into D. In the ∞ outcome for S_{e,x,m} we get a win on R_{e} by guaranteeing that Λ(D; x, n) ↑ for all sufficiently large n. Above this outcome, we restart all requirements of lower priority than R_{e} but of course not R_{e} itself nor any of its subrequirements. In particular, an M requirement between R_{e} and S_{e,x,m} will be restarted, because M will be injured when S_{e,x,m} puts the use λ(x, n) (n ≥ m) into D (these uses are selected by R_{e} which is of higher priority than M). The cost here is an infinite recursive set is put into D and its members are chosen at the node at which R_{e} appointed x. (Of course, in the finite outcome only finitely many elements are put into D.) If an M_{i} of higher priority than R_{e} is satisfied by some subrequirement, say Q_{i,j}, having an infinitary outcome, we restart R_{e} at an appropriate later node by choosing a new witness x′ and putting the corresponding subrequirements S_{e,x′,m} on the tree above the version of R_{e} with witness x′.

Fix a recursive priority list of the requirements and subrequirements such that the subrequirements N_{e,i}, P_{e,i}, and Q_{e,i} (S_{e,x,m}, respectively) appear after M_{e} (R_{e}, respectively).

We define the priority tree T recursively in the usual manner. We label each node on T with a requirement or a subrequirement. We assume that the tree T grows upwards. The root node on T is labelled M_{0}. Suppose that τ is a node on T. If τ is labelled R_{e} then τ has a unique outgoing edge labelled ∞; otherwise τ has two outgoing edges labelled ∞ and 0, with ∞ <_{L} 0.

Let t⃗ be a finite path in T starting from the root node and ending with the node τ and α a node on t⃗ labelled M_{e}. We say that M_{e} is Σ_{3}-injured at α on t⃗ if there is a node β labelled R_{i} (with witness x), and a node γ labelled S_{i,x,m} such that

βˆ ∞ ⊆ α ⊂ γˆ ∞ ⊆ τ.

(Namely, M_{e} is between the pair R_{i} and S_{i,x,m}, where S_{i,x,m} demonstrates that R_{i} has a Σ_{3}-outcome.) We define R_{e} is Σ_{3}-injured at α on t⃗ similarly.

We say that a requirement M_{e} is satisfied on t⃗ if there is a node α ∈ t⃗ labelled M_{e} such that either αˆ 0 is in t⃗ or α is not Σ_{3}-injured on t⃗ and there is γ labelled with a subrequirement of M_{e} such that

α ⊂ γˆ ∞ ⊆ τ.

If M_{e} is satisfied on t⃗ then all its subrequirements are satisfied on t⃗. Similarly we can define R_{e} and its subrequirements being satisfied on t⃗.

Continuing the recursive definition of T, if t⃗ is a finite path in T which ends with the node τ, then τ is labelled with the highest priority U such that U is either a requirement which never appeared before on t⃗ or all its copies are Σ_{3}-injured on t⃗ or U is a new subrequirement of an unsatisfied requirement on t⃗.

Before we give the formal construction and verifications, let us analyze the conflicts and how they are solved informally.

We first describe the interactions between a typical requirement Q_{e,i} = Q at node β imposing restraint on D to make its functional total and the various requirements S_{j,x,m} that attempt to put numbers into D. Suppose Q at node β is a subrequirement (or the requirement itself, for that matter) of the last version of M_{e} on the current path which is at α ⊆ β. Note that we can ignore the believability issue here too. As we shall see, the subrequirements of M_{e} will be arranged in such a way that no nodes between α and β labelled with a subrequirement of M_{e} can have infinite outcome. Therefore, we consider a node δ above β devoted to some S_{j,x,m} with R_{j} originating at γ. If δ ⊇ βˆ 0 then Q’s actions are finitary and impose only finite restraint on S_{j,x,m}. If γ ⊇ βˆ ∞ then lim m(c, s, Y_{b}, Y_{a}) = ∞ (really, of course the β version of this functional) and Q tries to make Ψ_{c}^{Y_{b}} total and so attempts to impose infinitary restraint on δ.

The case when R_{j} < M_{e} < Q_{e,i} < S_{j,x,m}. If R_{j} has higher priority than M_{e}, then by construction γ ⊆ α. In this case we allow δ to injure all computations from D needed by Q on inputs larger than (the code of) δ. If the outcome of δ is ∞ then, of course, we may ruin Q by making it diverge at all numbers bigger than δ but we get a global win on R_{j} and so restart M_{e} above this outcome. On the other hand, if the outcome of δ is 0 then it destroys the computation needed by Q at each number greater than δ only finitely often. This allows Q to eventually impose its restraint successfully against lower priority requirements.

The case when M_{e} < Q_{e,i} < R_{j} < S_{j,x,m}. If R_{j} has lower priority than M_{e}, γ ⊇ α. As we are assuming that δ ⊇ β, the construction guarantees that γ ⊇ β as well. (There are no subrequirements of nodes between α and β put on the tree above βˆ ∞.) In this case, the axioms for Λ(D; x, m) that δ tries to kill are chosen at γ ⊇ β. Suppose some action for δ has injured a computation at z required by Q. The next time a choice of axiom for Λ(D; x, m) is made must be at a stage at which the functional reaches a new maximal length of agreement at β. We then require (essentially automatically) that the use of this axiom be larger than that of the functional at z as computed at node β. Thus δ can injure the computation at z at most once. In addition, we require that it can never injure computations at z for z < δ. Thus if lim m(c, s, Y_{b}, Y_{a}) = ∞ the restraint imposed by Q at β will succeed in making its functional total. (Only finitely many lower priority requirements can ever injure the computation at a fixed z and each of them can do so only finitely often.) On the other hand, this restraint does not interfere with the success of an S_{j,x,m} whose outcome is ∞. Each time it acts to destroy a computation of Λ(D; x, m) and so perhaps Q^{’}s computation at some z, the next axiom is chosen above the use of Q’s functional at z, but Q in no way restrains δ from putting in the use of this new axiom at any later stage.

We now describe the stage by stage construction. At stage s we specify a string δ_{s} of length s, called the accessible string. We initialize all nodes to the right of δ_{s}, that is, cancel all actions desired by these nodes and cancel all restraint imposed by these nodes and any previous choice of witnesses or killing points. We begin at stage 0 by initializing all nodes.

We say that s is an α-expansionary stage, if the associated maximum length agreement function as measured at α reaches a new height at stage s.

Construction (stage s): The root of the tree is always accessible. Suppose that α is accessible if |α| = s we let α = δ_{s}. If |α| < s, we define the next

accessible node and its actions depending on the label of α.

(1) α is labelled M_{e}.

We first execute coding strategies (a) and (c), i.e., for each j < m_{e} if x has entered X_{g,j} by stage s − 1, then enumerate ⟨0, x⟩ into Y_{e,j}; for each i, j < m_{e} such that y_{e,i} ≺_{e} y_{e,j}, if z has entered Y_{e,i}^{[>0]} by stage s − 1 then put ⟨i + 1, z⟩ into Y_{e,j}. Furthermore, execute the coding strategies which are promised by any subrequirement of M_{e}. For example, if Q_{e,i} promised to put the coding marker ⟨c, e, b, a, 1, v⟩ into Y_{e,a} , it has not been initialized since making that promise and v enters X_{l,⟨e,a⟩} at stage s, then enumerate ⟨c, e, b, a, 1, v⟩ into Y_{e,a}.

α measures the maximum length of agreement m(⟨e, i⟩, s, D, X_{e,i}) for all i < n_{e}. If s is an α-expansionary stage, then αˆ ∞ is accessible. If s is not α-expansionary, then αˆ 0 is accessible.

(2) α is labelled a subrequirement, say Q_{e,i}, of M_{e}. The actions for N_{e,i} and P_{e,i} are similar and even simpler, because Q has to deal with both preserving and coding strategies, whereas N (P respectively) only deals with preserving (coding, respectively).

α measures the length of agreement m(c, s, Y_{e,b}, Y_{e,a}). If s is an α-expansionary stage, then αˆ ∞ is accessible. We act as follows.

(i) (preservation) set a restraint on Y_{e,b} with value

max{ψ_{c}^{Y_{e,b}}(v, s)|v < m(c, s, Y_{e,b}, Y_{e,a})}.

to preserve the computations Ψ_{c}^{Y_{e,b}}(v) for all v < m(c, s, Y_{e,b}, Y_{e,a}).

(ii) (coding) Promise that at any stage t > s, if α has not been initialized between s and t, we will put ⟨c, e, b, a, 1, v⟩ into Y_{e,a} for every v < m(c, s, Y_{e,b}, Y_{e,a}) such that v ∈ X_{l,⟨e,a⟩,t} and v ∉ X_{l,⟨e,a⟩,s}. (The number 1 in the coding tuple is used as a tag for subrequirements of type Q. The number 0 is used for subrequirements of type P.)

If s is not an α-expansionary stage, then αˆ 0 is accessible and no action is taken.

(3) α is labelled R_{e}. Let x be α’s witness for R_{e}. (If x is not defined, then pick one which is big, that is, larger than any number which we have seen so far in this construction.) Let n be the least number at which Λ^{D}(x, n) ↑. Pick a use λ^{D}(x, n) which is big. Define Λ^{D}(x, p) = 1 with use λ^{D}(x, n) for s > p ≥ n. Let αˆ ∞ (which is the only leaving edge anyway) be accessible.

(4) α is labelled S_{e,x,m}. Let t_{0} be the last stage at which α was initialized. Let y be the least number such that (∀z < s_{0})θ_{e}(x, m, y, z) ↑, where s_{0} is the stage when α was last accessible or initialized. Choose a killing point m^{∗} as follows. Let γ be the last node below α which has label R_{e}. For any β between γ and α labelled with a requirement of type M or any of its subrequirements, such that M is not Σ_{3}-injured at α, let u_{β} be the biggest use at β for numbers less than or equal to |α|. For any node δ below α labelled with S_{e′,x′,m′} such that δˆ ∞ ⊂ α, let m_{δ} be the killing point chosen by δ. For any node δ below α labelled with S_{e,x,m′} such that δˆ 0 ⊂ α, let λ_{δ} be the number λ^{D}(x, m_{δ}) where m_{δ} is the killing point chosen by δ. Let m^{∗} be

max({t_{0}} ∪ {u_{β} : γ ⊂ βˆ ∞ ⊂ α} ∪ {m_{δ} : δˆ ∞ ⊂ α}∪

{λ_{δ} : δˆ 0 ⊂ α and δ is labelled S_{e,x,m′}}).

If ∃z < sθ_{e}(x, m, y, z) ↓ then enumerate λ^{D}(x, m^{∗}) into D. Let αˆ ∞ be accessible. Otherwise, let αˆ 0 be accessible and do nothing.

This finishes the construction. We now verify that the construction works.

Lemma 2.4 Suppose P is an infinite path in T. For every requirement or subrequirement U, there is a unique node α on P labelled U such that either for all n > |α|, U is never Σ_{3}-injured on P ↾ n or for all n > |α|, it is satisfied on P ↾ n.

Proof. The Lemma follows by an easy induction on e where U is M_{e}, R_{e} or one of their subrequirements. □

Let P be the true path in T, that is, P is the leftmost path which is accessible infinitely often. We argue by induction along P that every requirement is satisfied or, more precisely, that the following Lemma holds.

Lemma 2.5 For each e ∈ ω all requirements R_{e} and M_{e} are satisfied. Indeed, if U is a requirement or subrequirement and α is the unique node on the true path P associated with U as defined in Lemma 2.4, then

(a) If U is R_{e}, then there is a stage s_{0} such that R_{e} does not change its witness x at any s > s_{0}.

(b) If U is S_{e,m,x} and is working for R_{e} at node γ ⊆ α with witness x, as defined in Lemma 2.4, then there is a stage s such that for all t > s, α does not change its selection of killing point m^{∗} at stage t. Moreover, if αˆ 0 ⊂ P, then for all n ≤ m^{∗}, Λ^{D}(x, n) is defined; if αˆ ∞ ⊂ P, then for all n ≥ m^{∗}, Λ^{D}(x, n) is undefined. In fact this is true for any node on the true path labelled with S_{e,m,x}.

(c) If U is M_{e} and αˆ 0 ⊂ P, then X_{e} is not a partial ordering as specified by M_{e}; if αˆ ∞ ⊂ P, then for each z the computation Φ_{e,i}^{D}(z) is eventually preserved and so the functionals Φ_{e,i}^{D} are total.

(d) If U is Q_{e,i} (or N_{e,i}, P_{e,i} respectively), i = ⟨a, b, c⟩and αˆ 0 ⊂ P, then Ψ_{c}^{Y_{e,b}} ≠ Y_{e,a} (or Ψ_{c}^{Y_{e,b}} ≠ X_{e,a}, Ψ_{c}^{X_{e,b}} ≠ Y_{e,a}, respectively); if αˆ ∞ ⊂ P, then the functional Ψ_{c}^{Y_{e,b}} (or Ψ_{c}^{Y_{e,b}}, Ψ_{c}^{X_{e,b}}, respectively) is total and the third (first, second, respectively) nonextendibility condition is satisfied or X_{e} is not a partial ordering as specified by M_{e}.

Proof. We prove (a)-(d) by simultaneous induction and then argue that the requirements R_{e} and M_{e} are satisfied.

(a) Let α be the unique node on the true path labelled R_{e} as defined in Lemma 2.4. Let s_{0} be the first stage after which no node to the left of α is accessible. Let x be the witness for R_{e} at α chosen at some stage s_{1} ≥ s_{0}. Then for all s > s_{1}, α never changes the witness x it uses for R_{e} because R_{e} only changes x when it is either initialized or some previous version of R_{e} is Σ_{3}-injured at α.

(b) We first argue that the killing point m^{∗} used by α is eventually fixed. As α is on the true path, all nodes below it are also on the true path and there is a last stage t_{0} at which it is initialized. By induction, the statements (a)-(d) apply to the nodes below α. For any δ below α labelled with S_{e′,x′,m′}, the killing point m_{δ} chosen by δ is eventually fixed by the inductive hypothesis for (b). Furthermore, if δˆ 0 ⊂ α, then λ^{D}(x, m_{δ}) is eventually fixed. For any β′ labelled with a requirement M or one of its subrequirement such that γ ⊂ β′ˆ ∞ ⊂ α, the computations at β′ on numbers less than or equal to |α| are eventually preserved by (c) and (d). In particular, the uses u_{β′} for those computations are eventually fixed. By the definition of the killing point m^{∗}, it is fixed once the numbers t_{0}, u_{β′}, m_{δ} and λ_{δ} are fixed.

Now suppose αˆ 0 ⊂ P. Let s_{0} be the first stage after which α’s killing point m^{∗} is fixed and αˆ 0 is accessible. When γ is first accessible after stage s_{0}, say at s_{1}, it will define Λ^{D}(x, m^{∗}) with big use λ^{D}(x, m^{∗}) (if it is not already defined). We claim that this computation of Λ^{D}(x, m^{∗}) will never be injured, which also implies that for all n ≤ m^{∗}, Λ^{D}(x, n) is defined. The reason is as follows. The nodes below γ will not make Λ^{D}(x, m^{∗}) ↑, because those nodes act before Λ^{D}(x, m^{∗}) is defined and at later stages choose only larger numbers as candidates to enter D; the nodes to the right of αˆ 0 are handled by the initialization. (Ones to the right of γ are initialized at s_{1}; ones above γ and to the right of αˆ 0 were initialized at s_{0} and have not been accessible between s_{0} and s_{1}.) For the nodes β′ between γ and α, we argue based on the outcome of β′. If β′ˆ ∞ ⊂ α, then by the assignment of requirements on the priority tree we know that β′ is labelled S_{e′,j,n} for some e′ ≠ e, moreover the last copy of R_{e′} is assigned to a node γ′ ⊃ γ. Thus when R_{e′} chooses its axiom λ′ at or after stage s_{1}, λ′ will be larger than λ^{D}(x, m^{∗}). (Note that β acted at s_{0} and so R_{e′} needs to choose a new axiom for β’s killing point when it is first accessible at s ≥ s_{1}.) Therefore the action of β′, which puts λ′ into D will not injure Λ^{D}(x, m^{∗}). If β′ˆ 0 ⊂ α, then by the choice of s_{0} it will not act, otherwise, the node β′ˆ ∞ which is to the left of α would be accessible. It remains to look at the nodes above αˆ 0, they will not injure Λ^{D}(x, m^{∗}) by their choices of killing points. Therefore Λ^{D}(x, m^{∗}) is defined.

Finally, suppose that αˆ ∞ ⊂ P. Let s be the stage after which no node to the left of αˆ ∞ is accessible and the killing point m^{∗} is fixed. The action of α, when it is accessible, makes Λ^{D}(x, n) undefined for all n ≥ m^{∗}.

(c) Let α be the node on the true path which is labelled M_{e} and never Σ_{3} injured on P ↾ n for all n greater than the length of α. For notational simplicity, we drop the index e of X and Y and their elements in the discussions below.

If αˆ 0 ⊂ P, then clearly the X_{i}’s cannot be r.e. sets as specified by M_{e}.

If αˆ ∞ ⊂ P, we show that the Φ_{e,i}^{D}’s are total. Let s_{0} be a stage after which no node to the left of αˆ ∞ is accessible. For each i and z, we argue that the computation Φ_{e,i}^{D}(z) can only be injured finitely often after stage s_{0}. Let us look at the nodes on different regions on the tree. We only need to consider those nodes δ which are labelled with S_{j,x,m} type subrequirements, because only those nodes put numbers into D. If δ is to the left of α, it is never accessible after s_{0} and so never injures any computation after s_{0}. If δ is strictly to the right of αˆ ∞, it is initialized whenever αˆ ∞ is accessible and so never considers putting in any number less than the use of the computations seen by α. If δ is below α, then when α is accessible, so is δ. Thus when we see the computation Φ_{e,i}^{D}(z) ↓ at α for the first time, δ has acted. At later stages, when R_{j}, which is the main requirement of S_{j,x,m}, chooses its use λ, λ will be larger than the use φ_{e,i}^{D}(z). Hence the action of δ will not injure the computation Φ_{e,i}^{D}(z).

The only remaining worry is those δ above αˆ ∞ labelled S_{e′,x,m}, which are subrequirements of some R_{e′}. First, let us consider the case that R_{e′} is assigned to a node above αˆ ∞. When Φ_{e,i}^{D}(z) is first defined at some stage after s_{0}, there are only finitely many such R’s which have chosen their λ’s and each of them can injure Φ_{e,i}^{D}(z) at most once. The reason is as follows. At the stage when S_{e′,x,m} puts λ into D destroying the computation Φ_{e,i}^{D}(z), it also makes all axioms having uses larger than λ undefined. At the next stage when R requirements (not necessarily the same R_{e′}) which are assigned above αˆ ∞ select their new use λ′ after Φ_{e,i}^{D}(z) has reconverged, hence λ′ will be larger the new use for Φ_{e,i}^{D}(z). Finally, we look at the case that R_{e′} is assigned to a node γ below α. If |δ| ≤ z, then S_{e′,x,m} can only act finitely often, otherwise, the version of S_{e′,x,m} on the true path would have outcome ∞, (because they all test the same Π_{2} condition (∀y)(∃z)θ_{e′}(x, m, y, z) ↓), which implies M_{e} is Σ_{3}-injured by the pair γ and δ. Let s_{1} be the stage after which all these finitary δ’s will not act. If |δ| > z and α is not Σ_{3}-injured at δ, then S_{e′,x,m} will not injure Φ_{e,i}^{D}(z) by the choice of its killing point. If α is Σ_{3}-injured at δ, let (γ_{0}, δ_{0}) be the innermost pair of R and S requirements, which Σ_{3}-injures α. After stage s_{1}, the δ’s having length less than z will not act, thus we may assume that |δ_{0}| > z. Then δ_{0}’s killing point m_{0}^{∗} is too large to injure Φ_{e,i}^{D}(z), so is the killing point m^{∗} for δ, since m^{∗} > m_{0}^{∗}.

(d) Let us assume that α is labelled Q_{e,i} and i = ⟨a, b, c⟩. The arguments for P and N type subrequirements are similar and we omit them.

If αˆ 0 ⊂ P, then clearly Ψ_{c}^{Y_{e,b}} ≠ Y_{e,a}.

If αˆ ∞ ⊂ P, then Ψ_{c}^{Y_{b}} is total because it is recursive in D and so our explicit actions to preserve it succeed as for the functional preserved by M_{e} requirements.

We now show that the third nonextendibility condition is satisfied or X_{e} is not the partial ordering specified by M_{e}.

We are given that y_{a} ≰ y_{b}. As Ψ_{c}^{Y_{b}} is total and lim m(c, s, Y_{b}, Y_{a}) = ∞, Ψ^{Y_{b}} = Y_{a}. Now, the only requirements affecting the sets Y_{a} and Y_{b} are subrequirements of M_{e}. By the definition of the priority tree, all of them on P of higher priority than α have outcome 0 and so act only finitely often. The usual argument for Sacks coding strategies then shows that X_{l,a} ≤_{T} Y_{a}: Given a number z larger than all higher priority restraint on Y_{a}, wait for a stage t > s_{0} such that m(e, t, Y_{b}, Y_{a}) > z, then z ∈ X_{l,a} if and only if either z ∈ X_{l,a,t} or the coding marker ⟨c, e, b, a, 1, z⟩ is in Y_{a}.

On the other hand, the usual argument for Sacks preservation strategies shows that we can compute Y_{a} from X_{g,b}: Given a number z, wait for a stage t after all positive action for higher priority strategies affecting Y_{b} have ceased acting such that m(c, t, Y_{b}, Y_{a}) > z and Y_{b}^{[0]} ↾ u = X_{g,b} ↾ u, where u is the maximal use in the computation Ψ_{c}^{Y_{b}}(v) for v < m(c, t, Y_{b}, Y_{a}). Then this computation is never injured. Thus, Y_{a} ≤ X_{g,b}. Consequently, we have X_{l,a} ≤ X_{g,b}.

We now assume that X_{e} is a partial ordering (with respect to ≤_{T}) as specified by M_{e} and show that X and Y satisfy the nonextendibility condition (iii) with witnesses y_{a} and y_{b}. For any x_{i} ∈ X, if ∀x′′ ∈ X [x′′ < y_{b} → x′′ < x_{i}], then X_{i} ≥_{T} X_{g,b}. For any x_{j} ∈ X, if ∀x′′ ∈ X [y_{a} < x′′ → x′ < x′′], then X_{j} ≤_{T} X_{l,a}. Since X_{l,a} ≤_{T} X_{g,b}, X_{j} ≤_{T} X_{i}. Thus x_{j} ≤ x_{i} as required in (iii).

Now we argue that the requirements R_{e} are satisfied. We consider two cases based on whether R_{e} has a global Σ_{3} outcome.

Case 1 There is a node β on P labelled S_{e,x,m} such that βˆ ∞ ⊂ P.

At each of the infinitely many stages when βˆ ∞ is accessible, β finds a new y such that (∃z)θ_{e}(x, m, y, z) ↓. Therefore, (∀y)(∃z)θ_{e}(x, m, y, z) ↓. Hence m is the Σ_{3}-witness that x is in Σ_{e}. On the other hand, by (a), Λ^{D}(x, n) undefined for all n ≥ m^{∗}. It follows that Λ_{x}^{D} is finite.

Case 2 For all nodes β_{m} on P labelled S_{e,x,m}, β_{m}ˆ 0 ⊂ P.

In this case, we argue that x is not in Σ_{e} and Λ_{x}^{D} = ω by showing that for all m in ω, (∃y)(∀z)θ_{e}(x, m, y, z) ↑ and Λ^{D}(x, m) ↓.

Fix m. Let s_{m} be the stage after which no node to the left of β_{m} is accessible. Let y_{m} be the least number such that (∀z < s_{m})θ_{e,s_{m}}(x, m, y_{m}, z) ↑. Then for all z ≥ s_{m} we still have θ_{e}(x, m, y_{m}, z) ↑, since otherwise β_{m}ˆ ∞ would be accessible. Since this is true for all m, x is not is Σ_{e}. On the other hand, by (a), every Λ^{D}(x, m) is eventually defined.

In both cases, the requirement R_{e} is satisfied.

Finally we argue that for all e, M_{e} is satisfied.

If α is labelled M_{e} is as in Lemma 2.4 and has outcome 0 on P, then M_{e} is trivially satisfied by (c). If it has outcome ∞ on P, we consider the following two cases.

Case 1. For all β on P labelled with some subrequirement of M_{e},

αˆ ∞ ⊂ βˆ 0 ⊂ P.

In this case we argue that we successfully extended the monomorphism f : X → R to an extension of f which has domain Y.

The argument is easy. We consider the requirements (a)-(f) as listed before Theorem 2.3. For the comparability requirements, the direct coding requirements (a) and (c) are satisfied by the action in case (1) when M_{e}ˆ ∞ is accessible; (b) is done by permitting as stated in action (2)(ii). Let us consider the incomparability requirements (d). Suppose that x_{a} ≰ y_{b}. Then, by statement (c) of our Lemma, the finitary outcome of N_{e,i} on true path shows that Ψ_{c}^{Y_{b}} ≠ X_{a} for all c. The arguments for requirements (e) and (f) are similar.

Case 2. There is β which is labelled some subrequirement of M_{e}, say Q_{e,i}, such that

αˆ ∞ ⊂ βˆ ∞ ⊂ P.

In this case, (c) of our Lemma says that X and Y satisfy the third nonextendibility condition or X_{e} is not a partial ordering as specified by M_{e}.

Thus the requirements M_{e} are satisfied. □

3 Nonextension of Embeddings

Our goal in this section is to show that there are individual r.e. degrees c and d which are low and nonlow_{2}, respectively, such that each extension of embedding property (as specified by a pair X ⊆ Y) is satisfied below each of them if and only if it is satisfied below every low_{2} r.e. degree, i.e. X and Y fail to satisfy each of the nonextendibility conditions (i)-(iii) listed at the beginning of §2. The existence of such a low c follows directly from the proof of Lemma 2.1 in Shore and Slaman [1990]. It is shown there that given X and Y which satisfy one of the nonembeddability conditions, it suffices to get an embedding of X into a finite distributive lattice L with the supremum of the image of one subset A of X greater than equal to the infimum of the image of another subset B of X. One then embeds L in R as a lattice with top degree low. The image of X under the composition of these embeddings can then not be extended to one of Y. Now each of these lattices L can be embedded as a lattice with 0 and 1 into the atomless Boolean algebra. Thus we can take c to be the low top of an embedding of the atomless Boolean algebra into R. In this case all of these lattices can be embedded into R(≤ c) preserving 0 and 1 and so any extension of embedding problem satisfying one of the nonextendibility conditions fails in R(≤ c).

Now we could argue that we can make the nonlow_{2} degree d constructed in §1 simultaneously the top of an embedding of the atomless Boolean algebra. This construction seems rather difficult so instead we revert to an earlier analysis of the nonembedding conditions that is easier to implement. In Fejer and Shore [1985] it is shown that one can divide the argument into two pieces. If the set B mentioned above does not consist precisely of just the 1 of the partial ordering X then it suffices to embed the lattice L into the degrees below d preserving just 0. Thus to take care of these cases, it suffices to make the d of Theorem 2.3 be above the top of an embedding of the atomless Boolean algebra into R. The cases in which B = {1} are handled separately by showing that one can assume that A = {x|x < 1} and that there is more than one maximal element of A. It then suffices to embed X into R(≤ d) in such a way that the supremum of the image of A is d. Thus it suffices to prove the following two propositions.

Proposition 3.1 The degree d of Theorem 2.3 can be constructed so that, in addition to the properties described there, there is an r.e. a ≤_{T} d such that there is an embedding of the atomless Boolean algebra into R(≤ a) preserving 0 and 1.

Proof. We incorporate a standard minimal pair and finite injury construction (as, for example, in Soare [1987]) of an embedding of the atomless Boolean algebra into R with top a into the construction of Theorem 2.3 replacing d by d ⊕ a. The only interactions between our construction and that of the embedding is that ours imposes additional finite restraints on the (minimal pair type) construction of a and the embedding construction requires additional finite positive actions which, of course, go into d ⊕ a. Clearly the addition of these finitary positive requirements does not cause any new problems for the restraint that our construction requires. The positive actions from our construction of d do not affect the sets built for the embedding of the atomless Boolean algebra below a as they do not put numbers into a. Similarly, they are not affected by the minimal pair restraint on a which applies only to numbers going into a. Thus the minimal pair type restraints needed to construct a as required are successful as well. □

Proposition 3.2 For every r.e. degree d and every partial ordering X with 0 and 1 and more than one maximal element strictly below 1, there is an embedding of X into R(≤ d) preserving 0 and 1 such that the join of the images of all the elements x of X with x < 1 is d.

Proof. Let X = {0, 1, x_{2}, …, x_{n}}. As in Fejer and Shore [1985], we use the technique of the Sacks splitting theorem to produce degrees d_{2}, … d_{n} such that ⊕{d_{i}|2 ≤ i ≤ n} ≡_{T} d and d_{i} ≰_{T} ⊕{d_{j}|2 ≤ j ≠ i} for each i ≥ 2. The required embedding of X into R(≤ d) is now given by sending x_{i} to ⊕{d_{j}|x_{j} ≤ x_{i}}, 0 to 0 and 1 to d. □

Thus we have a low r.e. degree c and a nonlow_{2} one d which satisfy exactly the same extension of embedding properties. This shows that no collection of such properties can separate the low r.e. degrees from the nonlow_{2} ones in R and so that no set of such properties can define the class of low_{2} degrees in R.

4 Nonsplitting bases

Finally, we modify the construction in §1 and §2 to make sure that no degree u ≤ d is the base of a nonsplitting pair.

Theorem 4.1 There is an r.e. nonlow_{2} degree d such that it satisfies the statements of Theorem 2.3 and Proposition 3.1 and for any u ≤ d and any v > u there is a splitting v_{0}, v_{1} of v above u, i.e. u <_{T} v_{0}, v_{1} <_{T} v and v_{0} ⊕ v_{1} ≡_{T} v.

For simplicity, let us call the set we are constructing in Proposition 3.1 D rather than D ⊕ A. In addition to the requirement of that construction, we have the following splitting requirements T_{e} for e ∈ ω.

• T_{e}: If U_{e} = Φ_{e}^{D} and V_{e} ≥_{T} U_{e} then there exist V_{e,0} and V_{e,1} such that

V_{e,0} ⊔ V_{e,1} = V_{e} ∧ V_{e} ≰_{T} U_{e} ⊕ V_{e,0}, U_{e} ⊕ V_{e,1}.

The requirements T_{e} list the candidate degrees u ≤ d and companion degrees v ≥ u. They are responsible for an enumeration of a set splitting V_{e,0}, V_{e,1} of V_{e} and have subrequirements Z_{e,j,k} that try to guarantee that Ψ_{j}^{U⊕V_{e,k}} ≠ V_{e}.

• Z_{e,j,k}: Ψ_{j}^{U_{e}⊕V_{e,k}} ≠ V_{e}.

These subrequirements act by preserving U ⊕ V_{e,k} on the Ψ_{j} use up to the maximal length of agreement. The use on U is preserved by restraining D; that on V_{e,k}, by putting numbers enumerated in V_{e} into V_{e,1−k} as in the Sacks splitting theorem. If one of these subrequirements has an infinitary outcome it makes V_{e,k} recursive and so preserving Ψ_{j}^{U⊕V_{e,k}} is equivalent to making a functional with oracle D total if the corresponding length of agreement goes to infinity.

Without loss of generality, we can assume that V_{e}^{[0]} = U_{e}. The strategy for T_{e} is as follows. T_{e} tries to make Φ_{e}^{D} total if the length of agreement with U_{e} has infinite lim sup as we did for M_{e} in Theorem 2.3. In addition, it enumerates sets V_{e,k}, k = 0, 1. When accessible it enumerates every number that has appeared in V_{e} since the last such stage into precisely one of the V_{e,k} in accordance with the priority of the desires of its subrequirements as in the Sacks splitting theorem. That is, it determines the subrequirement Z_{e,i,k} of highest priority that would be injured by enumerating the new numbers that have entered V_{e} into V_{e,k} and puts them all into V_{e,1−k}.

The strategy for subrequirement Z_{e,j,k} is as follows. We compute the maximal length of agreement between Ψ_{j}^{U_{e}⊕V_{e,k}} and V_{e} as usual. Z_{e,j,k} tries to protect these computations (and so in effect asks that no number below the use corresponding to the maximal length of agreement be enumerated into V_{e,k}). In addition, it acts to guarantee, by the low_{2}-like strategy, that Ψ_{j}^{U_{e}⊕V_{e,k}} is total if this maximum length of agreement goes to infinity. Note that its restraint for the low_{2}-like preservation strategy is imposed directly only on U_{e} via its computation from D but not on the V_{e,k}. The restraint on the V_{e,k} is imposed by the Sacks splitting type strategy implemented by T_{e} and produced by its respecting the requests of the Z_{e,j,k} for preserving computations. If the length of agreement goes to infinity, the combined effect of these two procedures is to make V_{e,k} recursive and Ψ_{j}^{U_{e}⊕V_{e,k}} total. In this case, we win the global requirement T_{e} because we have shown that V_{e} ≤_{T} U_{e}.

Thus below the infinitary outcome of Z_{e,j,k}, there are no more subrequirements for T_{e} and all strategies of lower priority than T_{e} are restarted.

If the length of agreement has a finite limit then the actions of Z_{e,j,k} are finitary. It then behaves like the finitary subrequirements of M_{e} and so does not interfere with satisfying the R requirements. Moreover, if the Z_{e,j,k} are finite for all j, k, then the usual argument for the Sacks splitting theorem shows that we satisfy T_{e}.

The interactions between the T_{e} requirements and their subrequirements Z_{e,j,k} with the nonlow_{2}-ness requirements R and the infimum requirements N of Theorem 2.3 are essentially the same as those of the M_{e} and their subrequirement. There are no interactions between the M_{e} and T_{e} requirements or their subrequirements. Indeed, other than the interactions with the R type requirements, the Z_{e,j,k} interact only with other subrequirements of the same T_{e} and then only by directing it as to which V_{e,k} numbers enumerated in V_{e} should be put into by T_{e}. As in the analysis for Proposition 3.1 the interactions with the embedding construction are also trivial. Hence all the strategies can be combined.

5 Bibliography

S. B. Cooper, A. Li and X. Yi [ta], On the distribution of Lachlan nonsplitting bases, University of Leeds, Department of Pure mathematics, 1998 Preprint series no. 37. P. A. Fejer and R. A. Shore [1985], Embeddings and extension of embeddings in the r.e. tt and wtt degrees, in Recursion Theory Week: Proceedings, Oberwolfach 1984, H. D.

Ebbinghaus, G. H. Müller and G. E. Sacks, eds., Springer-Verlag, Berlin, 1985, 121-140. R. A. Shore and T. A. Slaman [1990], Working below a low_{2} recursively enumerable degree, Arch. Math. Logic 29, 201-211. R. I. Soare [1987], Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer–Verlag, Heidelberg, 1987.