Undecidability and 1-types in Intervals of the Computably Enumerable Degrees^{∗}

Klaus Ambos-Spies

Mathematisches Institut, Universität Heidelberg, D-69120 Heidelberg, Germany

Denis R. Hirschfeldt^{∗∗}

Department of Mathematics, Cornell University, Ithaca, NY 14853, USA

Richard A. Shore^{§}

Department of Mathematics, Cornell University, Ithaca, NY 14853, USA

March 20, 1999

Abstract

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

subject code classifications: 03D25 (03C65 03D35 06A06)

keywords: computably enumerable degrees; undecidability; one-types

0 Introduction

Early results in the study of the structure of the computably enumerable (c.e.) Turing degrees led to Sacks’s conjecture [11] that the theory of this structure is decidable. This conjecture turned out to be false. The undecidability of the theory of the partial ordering R = ⟨R, ⩽⟩ of the c.e. degrees was first proved by Harrington and Shelah [5], using a very complicated 0′′′ argument.

This proof underwent various changes and attempted simplifications, particularly by Harrington and Slaman, and a considerably simpler approach was later developed by Slaman and Woodin (see [9]). However, none of these proofs could be extended to establish a similar result for the theory of a given interval of R, or even a given ideal.

Ambos-Spies and Shore [2] gave a simpler infinite injury proof of the undecidability of the theory of R, as well as a proof that this theory has uncountably many 1-types (extending a result of Ambos-Spies and Soare [1]), and showed that both proofs combine with the permitting technique to yield similar results for any nontrivial ideal of the c.e. degrees. (The fact that the theory of R has infinitely many 3-types, and so is not ℵ_{0}-categorical, had been established in Lerman, Shore, and Soare [8], by proving the embeddability into the c.e. degrees of all finite lattices with a certain property. In 1989, Ambos-Spies, Lempp and Soare (unpublished) obtained embeddings of the same class of lattices into arbitrary intervals of the c.e. degrees, thereby showing that the theory of any such interval also has infinitely many 3-types and so is not ℵ_{0}-categorical.)

∗We wish to thank the referee for many useful comments and especially for a significant simplification of the definition of max min(σ, n, s) and so of Definition 2.15.

∗∗Partially supported by an Alfred P. Sloan Doctoral Dissertation Fellowship.

§Partially supported by NSF Grants DMS-9503503 and DMS-9802843.

The proofs in [2] required no more in the way of technique than the construction of branching and nonbranching degrees. Thus, in light of Slaman’s proof [13] of the density of branching degrees and Fejer’s proof [4] of the density of nonbranching degrees, it was hoped that the results could be extended to any nontrivial interval of the c.e. degrees. This is what we do in the present paper.

Our notation is for the most part standard (as in [14]). If W is a c.e. set then we assume we have fixed some enumeration of W and let W [s] denote the part of W enumerated after s + 1 many steps. However, for any c.e. set X we construct, X[s] will denote the part of X enumerated by some point during stage s of the construction, whose exact location will have to be inferred from the context. Instead of X[s](x) we write X(x)[s]. We let X ↾ m = X ∩ {0, …, m − 1}.

The e^{th} Turing functional with oracle X is denoted by Φ_{e}(X), and its value at x by Φ_{e}(X; x). We let Φ_{e}(X)[s] be the evaluation of Φ_{e}(X[s]) at some point during stage s, and Φ_{e}(X, x)[s] be the value of this evaluation at x. Again, the exact point during stage s to which these notations refer should always be clear from context; when there might be some doubt, we have pointed it out explicitly. The use functions of Φ_{e}(X; x) and Φ_{e}(X; x)[s] are denoted by φ_{e}(X; x) and φ_{e}(X; x)[s], respectively.

When we write Φ_{e}(X; x)[s] ≠ Φ_{e}(X; x)[t] this is understood to include the possibility that one side of the inequality converges while the other diverges.

When we mention a “fresh large number” in our construction, we mean a number larger than any appearing in the construction up to that point.

We adopt the following conventions, where we have in mind some fixed computable enumeration of the c.e. set X.

1. s < x ⇒ Φ_{e}(X; x)[s]↑.

2. x < y ∧ Φ_{e}(X; x)[s]↓ ∧Φ_{e}(X; y)[s]↓⇒ φ_{e}(X; x)[s] < φ_{e}(X; y)[s].

3. s < t ∧ Φ_{e}(X; x)[s]↓ ∧Φ_{e}(X; x)[t]↓⇒ φ_{e}(X; x)[s] ⩽ φ_{e}(X; x)[t].

4. x < y ∧ Φ_{e}(X; x)[s]↑⇒ Φ_{e}(X; y)[s]↑.

5. X_{0} ⊕ ⋯ ⊕ X_{n−1} = {x | x = nk + m, k ∈ X_{m}, m < n}.

6. We treat the use of a functional as if it were the largest number actually used in the computation, so that a change in X at or below φ_{e}(X; x) will be taken to destroy the current computation Φ_{e}(X; x), and hence will cause us to say that the computation has changed. However, if the oracle of a functional is given as the join of two or more sets, we redefine the use as follows: φ_{e}(X_{0} ⊕ ⋯ ⊕ X_{n−1}; x) = max{k | nk + m is used in the computation Φ_{e}(X_{0} ⊕ ⋯ ⊕ X_{n−1}; x) for some m < n}, and similarly for φ_{e}(X_{0} ⊕ ⋯ ⊕ X_{n−1}; x)[s]. (This means that we will act as if a change in any X_{i}, i < n, at or below φ_{e}(X_{0} ⊕ ⋯ ⊕ X_{n−1}; x) destroys a current computation Φ_{e}(X_{0} ⊕ ⋯ ⊕ X_{n−1}; x). It also means that when we make reference to “imposing a restraint r on X_{0} ⊕ ⋯ ⊕ X_{n−1}”, we mean that we impose a restraint r on each X_{i}, i < n.)

In addition, we make the following a rule of our construction. If any of the strategies described below acts at stages s and t of the construction and not at any stage strictly between s and t, Φ_{e}(X; x)[s] converges at the end of the strategy’s stage s action, and the computation Φ_{e}(X; x) changes between the end of the strategy’s stage s action and the beginning of its stage t action, then the strategy treats Φ_{e}(X; x)[t] as if it were divergent.

1 The main results

A set of sentences Σ is said to be strongly undecidable if there is no computable set R such that V ∩ Σ ⊆ R ⊆ Σ, where V is the set of logically valid sentences. Ershov and Taitslin [3] have shown that the set of all sentences in the language L(⩽) that are true in all finite partial orderings is strongly undecidable. This implies that, for any structure S in which all finite partial orderings are elementarily definable with parameters, the first-order theory Th(S) of S is undecidable. In particular, the following holds for upper semilattices.

1.1. Proposition. Let U = ⟨U, ⩽_{U}, ∪⟩ be an upper semilattice and let θ be a formula in the language of partial orderings with free variables x_{0}, …, x_{k−1} and y. Suppose that for any n ⩾ 1 and any partial ordering ⩽_{0} on {0, …, n − 1} there are elements a_{0}, …, a_{k−1}, b_{0}, …, b_{n−1} and c of U such that for any i, j < n,

i ≠ j ⇒ b_{i} ≠ b_{j},

{b_{0}, …, b_{n−1}} = {b ∈ U | U ⊨ θ_{x_{0},...,x_{k−1},y}[a_{0}, …, a_{k−1}, b]}, and
i ⩽_{0} j ⇔ b_{i} ⩽_{U} b_{j} ∪ c.

Then the first-order theory of ⟨U, ⩽_{U}⟩ is undecidable.

Let e < f be c.e. degrees. In order to apply Proposition 1.1 to the u.s.l. ⟨[e, f], ⩽, ∪⟩, we need an elementary property of this u.s.l. that, for varying parameters a_{0}, …, a_{k−1} ∈ [e, f], defines finite sets of arbitrary size. Following [2], we will get such a property in one parameter a by considering the branches of branching degrees in [e, f].

1.2. Definition. (a) A c.e. degree a is branching if there are c.e. degrees b and c such that a < b, a < c, and a = b ∩ c. Otherwise, a is nonbranching.

(b) Let a and b be c.e. degrees in [e, f] such that a < b. Then b is a-cappable in [e, f] if there is a c.e. degree c in [e, f] such that a < c and a = b ∩ c. The degree b is maximal-a-cappable in [e, f] if b is a-cappable in [e, f] and no degree d > b is a-cappable in [e, f].

Note that maximal-a-cappability is definable in the first-order language of partial orderings. Thus the following fact holds.

1.3. Proposition. Let e < f be c.e. degrees. There is a first-order formula θ in the language of partial orderings with two free variables x and y such that for any two degrees a, b ∈ [e, f],

⟨[e, f], ⩽, ∪⟩ ⊨ θ_{x,y}[a, b] ⇔ b is maximal-a-cappable in [e, f].

We now come to our main technical theorem.

1.4. Theorem. Let e < f be c.e. degrees and let ⩽_{0} be a partial ordering on {0, …, N − 1}. There are c.e. degrees a, b_{0}, …, b_{N−1}, c such that

a, b_{0}, …, b_{N−1}, c ∈ [e, f],  (1.0)

b_{i} | b_{j}, i ≠ j,  (1.1)

b_{i} is a-cappable in [e, f],  (1.2)

if d is a-cappable then d ⩽ b_{i} for some i < N, and  (1.3)

i ⩽_{0} j iff b_{i} ⩽ b_{j} ∪ c.  (1.4)

We will prove Theorem 1.4 in Section 2.

Combining Propositions 1.1 and 1.3 with Theorem 1.4 we get the following result.

1.5. Corollary. For any c.e. degrees e < f, the first-order theory of the partial ordering ⟨[e, f], ⩽⟩ of the c.e. degrees between e and f is undecidable.

By Theorem 1.4, for any two c.e. degrees e < f, any finite partial ordering can be elementarily defined in ⟨[e, f], ⩽⟩ with two parameters a and c. This implies that there are continuum many 2-types consistent with ⟨[e, f], ⩽⟩. As the next theorem shows, in certain cases the second parameter c can be defined from a. We will use this to show that there are in fact continuum many 1-types consistent with ⟨[e, f], ⩽⟩.

1.6. Theorem. Let ⩽_{0} be a partial ordering on {0, …, N −1} with at least three minimal elements. There are c.e. degrees a, b_{0}, …, b_{N−1}, c satisfying (1.0)–(1.4) and

c = ⋃_{i<N} (⋂_{j≠i} b_{j}) .  (1.5)

The proof of Theorem 1.6 will be given in Section 3.

1.7. Corollary. For any c.e. degrees e < f, the first-order theory of the partial ordering ⟨[e, f], ⩽⟩ of the c.e. degrees between e and f has 2^{ω} many 1-types.

Proof. It suffices to give a sequence ⟨η^{k} | k > 0⟩ of formulas with one free variable x such that for any nonempty finite set F of natural numbers there is a c.e. degree a_{F} ∈ [e, f] such that

⟨[e, f], ⩽⟩ ⊨ (η^{k})_{x}[a_{F}] ⇔ k ∈ F.

Fix θ as in Proposition 1.3 and define the formulas γ = γ_{x,u}, δ = δ_{x,v}, and η^{k} = (η^{k})_{x}, whose intended meanings are described below, as follows:

γ ≡ ∃y(θ ∧ ∀z(y ≠ z ∧ θ_{x,y}[x, z] → u ⩽ z) ∧ ∀w[∀z(y ≠ z ∧ θ_{x,y}[x, z] → w ⩽ z) → w ⩽ u]).

δ ≡ ∀u(γ → u ⩽ v) ∧ ∀t[∀u(γ → u ⩽ t) → v ⩽ t].
η^{k} ≡ ∃s_{0}, …, s_{k}(θ_{x,y}[x, s_{0}] ∧ ⋯ ∧ θ_{x,y}[x, s_{k}] ∧
∧∀v(δ_{x,v} → [s_{0} ⩽ s_{1} ∪ v ∧ ⋯ ∧ s_{k−1} ⩽ s_{k} ∪ v ∧ s_{1} ⩽̸ s_{0} ∪ v ∧ ⋯ ∧ s_{k} ⩽̸ s_{k−1} ∪ v]) ∧
∧∀s, v(θ_{x,y}[x, s] ∧ s ≠ s_{0} ∧ ⋯ ∧ s ≠ s_{k} ∧ δ_{x,v} →
→ [s ⩽̸ s_{0} ∪ v ∧ ⋯ ∧ s ⩽̸ s_{k} ∪ v ∧ s_{0} ⩽̸ s ∪ v ∧ ⋯ ∧ s_{k} ⩽̸ s ∪ v])).

(Where the symbols ≠, ∪, and ⩽̸ should be expressed in terms of ⩽.)

For any partial ordering ⩽_{0} on {0, …, N − 1} with at least three minimal elements and c.e. degrees a, b_{0}, …, b_{N−1}, c as in Theorem 1.6,

⟨[e, f], ⩽⟩ ⊨ θ[a, g] if and only if g ∈ {b_{0}, …, b_{N−1}}  (1.6)

(by (1.2) and (1.3)),

⟨[e, f], ⩽⟩ ⊨ γ[a, h] if and only if h ∈ {⋂_{j≠i} b_{j} | i < N}  (1.7)

(by (1.6)), and

⟨[e, f], ⩽⟩ ⊨ δ[a, i] if and only if i = c  (1.8)

(by (1.5) and (1.7)).

Thus, by (1.4), (1.6), and (1.8), ⟨[e, f], ⩽⟩ ⊨ η^{k}[a] if and only if ⩽_{0} contains a maximal chain of length k + 1 such that each number not contained in the chain is ⩽_{0}-incomparable with each member of the chain.

Now let F = {m_{0}, …, m_{p}} be a nonempty finite set of natural numbers. Say that a partial ordering ⩽_{0} on {0, …, N − 1} is of chain type F if it is the disjoint union of maximal ⩽_{0}-chains such that each maximal chain has length m_{l} + 1 for some l ⩽ p, for each l ⩽ p there is a maximal chain of length m_{l} + 1, and members of different maximal chains are ⩽_{0}-incomparable. Let ⩽_{0} be a partial ordering on {0, …, N − 1} of chain type F with at least three minimal elements, and let a be as in Theorem 1.6. Then

⟨[e, f], ⩽⟩ ⊨ (η^{k})_{x}[a] ⇔ k ∈ F.

Another interesting question is which fragments of the theory of a given interval of the c.e. degrees are undecidable. We will briefly address this question in Section 4.

2 Proof of Theorem 1.4

The case e = 0 is covered by Theorem 1.9 in [2]. Thus we can assume that e > 0. We can further assume that N > 1, since the case N = 1 follows by letting a = b_{0} = c be a nonbranching c.e. degree in [e, f), as constructed in [4].

Let E and F be c.e. sets in e and f, respectively. We construct sets A, B_{i}, C_{i}, and D_{i,k,l} (i < N; k, l ∈ ω), of which A, B_{i}, and C_{i} will be c.e. . These sets will satisfy the following conditions, the first seven of which are the same as conditions (2.0)–(2.6) in [2].

i ≠ j ⇒ C_{i} ⩽_{T} B_{j}.  (2.0)

C_{i} ⩽̸_{T} A.  (2.1)

If g is total and g ⩽_{T} A ⊕ B_{i} for all i < N then g ⩽_{T} A.  (2.2)

D_{i,k,l} ⩽_{T} W_{k} ⊕ A and D_{i,k,l} ⩽_{T} W_{l} ⊕ A.  (2.3)

If W_{k} ⩽̸_{T} A ⊕ B_{i} and W_{l} ⩽̸_{T} A ⊕ B_{i} then D_{i,k,l} ⩽̸_{T} A.  (2.4)

i ⩽_{0} j ⇒ B_{i} ⩽_{T} A ⊕ B_{j} ⊕ C, where C = ⨁_{n=0}^{N−1} C_{n}.  (2.5)

i ⩽̸_{0} j ⇒ B_{i} ⩽̸_{T} A ⊕ B_{j} ⊕ C.  (2.6)

E ⩽_{T} A.  (2.7)

A ⊕ B_{i} ⩽_{T} F.  (2.8)

Let A, B_{i}, C_{i}, and D_{i,k,l} be as above and let a = deg(A), b_{i} = deg(A ⊕ B_{i}), c_{i} = deg(A ⊕ C_{i}), and c = deg(A ⊕ C). We show that a, b, and c have the required properties.

We remark that Lachlan [6] has shown that for c.e. degrees x, y, and z, x is the infimum of y and z among the c.e. degrees if and only if x is the infimum of y and z among all degrees. This result is necessary for the ensuing because the sets D_{i,k,l} will not necessarily be c.e..

By (2.0), (2.7), and (2.8), a, b_{0}, …, b_{N−1}, c lie in [e, f]. By (2.0) and (2.1), a < c_{i} ⩽ b_{j} for i ≠ j < N, while, by (2.0) and (2.2), a = b_{i} ∩ c_{i}. So b_{i} and b_{j} are incomparable for i ≠ j and b_{i} is a-cappable in [e, f]. To show that (1.3) holds, assume for a contradiction that g is a-cappable but g ⩽̸ b_{i} for all i < N. Fix h > a such that a = g ∩ h. Since, by (2.2), a = b_{0} ∩ ⋯ ∩ b_{N−1} and since h > a, h ⩽̸ b_{i} for at least one i < N. So we may fix i < N such that g ⩽̸ b_{i} and h ⩽̸ b_{i}. Then, for any two c.e. sets W_{k} and W_{l} in g and h, respectively, W_{k} ⩽̸_{T} A ⊕ B_{i} and W_{l} ⩽̸_{T} A ⊕ B_{i}. Hence, for d = deg(D_{i,k,l}), d ⩽ g and d ⩽ h by (2.3), while by (2.4), d ⩽̸ a. So a ≠ g ∩ h, contrary to our assumption. Thus (1.3) holds. Finally, (1.4) follows immediately from (2.5) and (2.6).

In the following sections we will describe various kinds of strategies. In the eventual tree construction, there will be multiple copies of each strategy. A copy of a strategy X is designated by X^{σ}, where σ is a sequence coding the strategies of stronger priority than X^{σ} and their outcomes. A stage of the construction during which X^{σ} is active will be known as a σ-stage. Our construction will be such that each strategy in σ acts during any σ-stage, with Y^{α} acting before Z^{τ} for α ⊂ τ ⊆ σ.

For the purpose of keeping the actions of the various strategies from interfering with each other, we will assign infinite disjoint uniformly computable sets P_{σ} to each possible finite sequence σ of strategies and corresponding outcomes. Each strategy X^{σ} will work exclusively with numbers in P_{σ}.

The sections dealing with the satisfaction of (2.0)–(2.2) and (2.8) are a modification of the construction in [13], while that dealing with the satisfaction of (2.3) and (2.4) is based on the construction in [4]. The reader is referred to these papers for more detailed explanations of the ideas behind the strategies described in these sections.

Making the b_{i} a-cappable. We satisfy (2.0) and (2.7) by direct coding. Whenever one of the strategies described below enumerates x into C_{i}, it will also enumerate ⟨x, i⟩ into each B_{j}, j ≠ i, and we make sure no other numbers ever enter B_{j}^{[i]}. Similarly, we have a strategy K which will have the strongest priority of all and will act at every stage s > 0 by enumerating 2x into A for each x ∈ E[s] − E[s − 1], and we make sure this is the only way an even number can enter A.

Since elements of the sets P_{σ} mentioned above will be enumerated into A, B_{i}, or C_{i} by the various strategies described below, the above (together with another direct coding action described later) leads us to require that each P_{σ} be a subset of the intersection of the odd numbers with ω^{[⩾2N]}.

We break (2.2) into requirements

R_{e} : Φ_{e}(A ⊕ B_{0}) = Φ_{e}(A ⊕ B_{1}) = ⋯ = Φ_{e}(A ⊕ B_{N−1}) total ⇒ Φ_{e}(A ⊕ B_{0}) ⩽_{T} A.

That these requirements suffice to satisfy (2.2) follows by an observation of Posner (see IX.1.4 in [14]): If g ⩽_{T} A ⊕ B_{i} for all i < N then there are indices e_{i} such that

Φ_{e_{0}}(A ⊕ B_{0}) = Φ_{e_{1}}(A ⊕ B_{1}) = ⋯ = Φ_{e_{N−1}}(A ⊕ B_{N−1}) = g.

On the other hand, each C_{i} will be non-empty, so we can pick c_{0}, …, c_{N−1}, c_{i} ∈ C_{i}, and by the coding described above we will have that ⟨c_{i}, i⟩ ∉ B_{j} if and only if i = j. Let e be such that Φ_{e}(X; x) = Φ_{e_{i}}(X; x) for the least i < N such that 2⟨c_{i}, i⟩ + 1 ∉ X, if such an i exists, and Φ_{e}(X; x)↑ otherwise. Now

Φ_{e}(A ⊕ B_{0}) = Φ_{e}(A ⊕ B_{1}) = ⋯ = Φ_{e}(A ⊕ B_{N−1}) = g,

whence R_{e} ensures that if g is total then g ⩽_{T} A.

Each strategy R_{e}^{σ} for satisfying R_{e} uses movable markers Γ_{σ}(n), n ∈ ω, which take positions in P_{σ}. We will denote the position of Γ_{σ}(n) at stage s by γ_{σ}(n, s). The movement of these markers will be subject to the following rules:

1. Suppose that s is a σ-stage and, at the beginning of R_{e}^{σ}’s stage s action, Φ_{e}(A⊕B_{0})[s] ↾ n+1 = Φ_{e}(A ⊕ B_{1})[s] ↾ n + 1 = ⋯ = Φ_{e}(A ⊕ B_{N−1})[s] ↾ n + 1, Φ_{e}(A ⊕ B_{i}; n)[s] ↓ for all i < N, and Γ_{σ}(n) does not have a position. Then at stage s, Γ_{σ}(n) must be assigned a position larger than any number previously mentioned in the construction. Furthermore, this is the only situation in which a Γ-marker is assigned a new position.

2. If s is a σ-stage, Γ_{σ}(n) has a position γ_{σ}(n, s) assigned at stage t, and for all i < N, Φ_{e}(A ⊕ B_{i}; n)[s] ≠ Φ_{e}(A ⊕ B_{i}; n)[t], then at stage s, Γ_{σ}(n) must be removed from its position.

3. If Γ_{σ}(n) is removed from its position γ_{σ}(n, s) at a stage s then so must all Γ_{σ}(m), m > n, and some number less than or equal to γ_{σ}(n, s) must enter A at stage s.

4. Except finitely often, Γ_{σ}(n) may not be removed from position γ_{σ}(n, s) unless at least one computation Φ_{e}(A ⊕ B_{i}; n), i < N, has changed since Γ_{σ}(n) was assigned position γ_{σ}(n, s).

2.1. Lemma. If there are infinitely many σ-stages and the above rules are obeyed then R_{e} is satisfied.

Proof. Suppose g is total and g = Φ_{e}(A ⊕ B_{0}) = Φ_{e}(A ⊕ B_{1}) = ⋯ = Φ_{e}(A ⊕ B_{N−1}). By rules 1 and 4, γ_{σ}(n) = lim_{s} γ_{σ}(n, s) exists for all n. Let f(n) be the least σ-stage s such that γ_{σ}(n) = γ_{σ}(n, s) and Φ_{e}(A ⊕ B_{0}; n)[s] = Φ_{e}(A ⊕ B_{1}; n)[s] = ⋯ = Φ_{e}(A ⊕ B_{N−1}; n)[s]. By rule 3, f ⩽_{T} A. Finally, by rule 2, g(n) = Φ_{e}(A ⊕ B_{0}; n) = Φ_{e}(A ⊕ B_{1}; n) = ⋯ = Φ_{e}(A ⊕ B_{N−1}; n) = Φ_{e}(A ⊕ B_{0}; n)[f(n)]. Thus g ⩽_{T} A as required.

Whenever a number enters A or one of the B_{i}, there is a possibility that action will have to be taken to guarantee that rule 2 is obeyed. Thus we define the R_{e}^{σ} recovery process as follows:

Search for an x such that Γ_{σ}(x) has position γ_{σ}(x, s) assigned at stage t and for all i < N, Φ_{e}(A ⊕ B_{i}; x)[s] ≠ Φ_{e}(A ⊕ B_{i}; x)[t]. If such an x is found then enumerate γ_{σ}(x, s) into A, cancel the positions of all Γ_{σ}(y), y ⩾ x, and repeat the recovery process; otherwise, end the recovery process.

For a sequence σ of strategies, the σ-R recovery process consists of iterating the R_{e}^{τ} recovery processes for each R_{e}^{τ} in σ until each terminates without enumerating any numbers into A.

We make it a feature of our construction that every time a strategy X^{σ} enumerates a number into A or one of the B_{i}, it follows this enumeration with the σ-R recovery process. It will be important to distinguish between numbers enumerated into A directly by a given strategy X^{σ} and numbers that enter A during a recovery process run by X^{σ}. When we talk about numbers enumerated by X^{σ}, we mean only those enumerated directly by X^{σ}.

The action of R_{e}^{σ} at a σ-stage s is simple. It first runs the σ^{⌢}⟨R_{e}^{σ}⟩-R recovery process. Then it assigns fresh large positions to markers as necessary to obey rule 1, making sure that if j < k then γ_{σ}(j, s) < γ_{σ}(k, s).

Note that we have guaranteed that if s is a σ-stage then for every strategy X^{τ}, τ ⊃ σ, that acts during stage s, if Γ_{σ}(x) has a position assigned at stage t at the beginning of X^{τ}’s stage s action then Φ_{e}(A ⊕ B_{i}; x)[s] = Φ_{e}(A ⊕ B_{i}; x)[t] for some i < N.

We break (2.1) into requirements

S_{i,e} : Φ_{e}(A) ≠ C_{i}.

If there were no requirements of stronger priority, a strategy S_{i,e}^{σ} could satisfy S_{i,e} by the coding/preservation strategy used in the proof of Sacks’s Density Theorem [10]. The R-requirements make things more complicated.

In the spirit of the proof of the density theorem, we wish to ensure that

Φ_{e}(A) = C_{i} ⇒ C_{i} ⩽_{T} E  (2.9)

and

Φ_{e}(A) = C_{i} ⇒ F ⩽_{T} E ⊕ C_{i}  (2.10)

by “preserving” enough of A over E and coding enough of F into E-computable locations in C_{i}. Since E <_{T} F, this would be enough to satisfy S_{i,e}.

The problem is that, in general, the numbers enumerated into A in order to satisfy the rules for markers associated with a given R-strategy will not form an E-computable set. This makes it hard for E to compute Φ_{e}(A). (All strategies in this construction other than the R-strategies will enumerate E-computable sets into A, so that making sure E has a handle on the numbers put into A for the sake of the R strategies is really our main problem here.) As we will see, depending on the strategies and corresponding outcomes in σ, it will be the case that for certain of the R-strategies in σ, the numbers put into A in order to satisfy the rules for markers associated with these strategies will be guaranteed to form computable sets. These can safely be ignored in our description of S_{i,e}^{σ}. Let Active strategy(σ) be the set of R-strategies in σ that S_{i,e}^{σ} must respect, that is, those R-strategies that cannot be ignored for the reason mentioned above. (We will eventually give a formal definition of Active strategy(σ) (see page 28).) It will be the case that for R_{j}^{α}, R_{k}^{β} ∈ Active strategy(σ), α ⊂ β ⇔ j < k (see Lemma 2.24).

The idea for getting around our problem is based on the fact that a marker Γ_{τ}(x) corresponding to a strategy R_{j}^{τ} will not be removed from its position except to reflect a change in all the computations Φ_{j}(A ⊕ B_{k}; x), k < N. In particular, the removal of Γ_{τ}(x) from its position will never be the first reason for a change in A ⊕ B_{i}. To exploit this fact, we make the following definition.

2.2. Definition. A number v is a σ-i-configuration at stage s if for all R_{j}^{τ} ∈ Active strategy(σ) and all m, γ_{τ}(m, s) < v ⇒ [φ_{j}(A ⊕ B_{i}; m)[s] < v ∧ Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A ⊕ B_{i}; m)[t], where t is the stage at which Γ_{τ}(m) was assigned position γ_{τ}(m, s)].

We say that v is a permanent σ-i-configuration if it is a σ-i-configuration at almost all stages.

The following two lemmas are important consequences of Definition 2.2. The first follows immediately from Definition 2.2 and the definition of recovery process.

2.3. Lemma. Suppose that v is a σ-i-configuration at the beginning of a recovery process run by some strategy (not necessarily S_{i,e}^{σ}). Suppose further that if R_{k}^{α} ∉ Active strategy(σ) then no number in P_{α} is put into A ↾ v by the recovery process. Then no number is put into A ↾ v by the recovery process.

2.4. Lemma. Suppose that S_{i,e}^{σ} acts infinitely often and can restrain all numbers from entering A ⊕ B_{i} except for the enumeration of finitely many fixed E-computable sets and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ). Let f(v) be the least stage by which all these E-computable sets have stopped enumerating numbers into A ↾ v and B_{i} ↾ v. If v is a σ-i-configuration at the end of S_{i,e}^{σ}’s action at some stage s > f(v) and S_{i,e}^{σ} preserves this configuration, that is, it imposes a restraint v on A ⊕ B_{i} at stage s, then A ↾ v = A[s] ↾ v and B_{i} ↾ v = B_{i}[s] ↾ v.

Proof. Recall that, by the conventions of Section 0, placing a restraint v on A ⊕ B_{i} means placing a restraint v on A and placing a restraint v on B_{i}.

Assume for a contradiction that some number enters A ↾ v or B_{i} ↾ v after the end of S_{i,e}^{σ}’s stage s action. Since s > f(v), there must exist a strategy X^{τ} and a τ-stage t ⩾ s with the following properties.

1. Either τ ⊃ σ or t > s.

2. No number enters A ↾ v or B_{i} ↾ v between the end of S_{i,e}^{σ}’s stage s action and the beginning of the recovery process run by X^{τ} at stage t.

3. Some number is put into A ↾ v by the recovery process run by X^{τ} at stage t.

The first and second properties above imply that v is a σ-i-configuration at the beginning of the recovery process run by X^{τ} at stage t. Furthermore, the definition of f(v) implies that no number is put into A ↾ v after stage f(v) for the purpose of coding the movement of a Γ-marker corresponding to a strategy that is not in Active strategy(σ). Thus, the third property above contradicts Lemma 2.3.

A σ-i-configuration v at a stage s such that A ↾ v = A[s] ↾ v and B_{i} ↾ v = B_{i}[s] ↾ v will be called correct. Clearly, all permanent σ-i-configurations will eventually be correct.

Assume for the remainder of this section that the hypotheses of Lemma 2.4 are satisfied. Let f be the function defined in the statement of Lemma 2.4. Since f ⩽_{T} E, E can enumerate the correct σ-i-configurations preserved by S_{i,e}^{σ}.

Now, for each n such that Φ_{e}(A) ↾ n = C_{i} ↾ n and Φ_{e}(A; n) converges, S_{i,e}^{σ}’s preservation half will attempt to find and preserve a permanent σ-i-configuration greater than φ_{e}(A; n). If Φ_{e}(A) = C_{i} and all such attempts are successful then, by the comments in the previous paragraphs, (2.9) is satisfied. We will see that all of S_{i,e}^{σ}’s attempts to find configurations will be successful unless, for some R_{j}^{τ} ∈ Active strategy(σ), either Φ_{j}(A ⊕ B_{i}) is not total or it is not true that Φ_{j}(A ⊕ B_{0}) = ⋯ = Φ_{j}(A ⊕ B_{N−1}), in which case we will ensure that for some m, Γ_{τ}(m) does not have a limit position.

If this last possibility holds then R_{j}^{τ} is satisfied because its antecedent is false. Furthermore, either Γ_{τ}(m) is moved infinitely often or there is a stage in the construction after which Γ_{τ}(m) is never assigned a position. It is not hard to see that this implies that the numbers put into A in order to satisfy the rules for markers associated with R_{j}^{τ} will form a computable set. Now for α ⊃ σ, R_{j}^{τ} ∉Active strategy(α), and thus a strategy S_{i,e}^{α} can safely ignore R_{j}^{τ}. In our construction, we will make sure that such a strategy exists, so that eventually some copy of S_{i,e} will be successful in finding the desired configurations and hence, as we shall see, in satisfying S_{i,e}.

We now explain how S_{i,e}^{σ} acts to attempt to find a permanent σ-i-configuration greater than φ_{e}(A; n) for each n such that Φ_{e}(A) ↾ n = C_{i} ↾ n and Φ_{e}(A; n) converges. We will first consider the case in which there is only one R-strategy in Active strategy(σ), say R_{j}^{τ}.

The basic idea is that S_{i,e}^{σ} waits for a σ-stage s such that Φ_{e}(A)[s] ↾ n = C_{i}[s] ↾ n and Φ_{e}(A; n)[s] converges, and then takes control of a marker Γ_{τ}(m_{n}), where m_{n} is a fresh large number, and keeps γ_{τ}(m_{n}, t) clear of φ_{j}(A ⊕ B_{i}; m_{n})[t], t ⩾ s, by removing Γ_{τ}(m_{n}) from its position every time the computation Φ_{j}(A ⊕ B_{i}; m_{n}) diverges or changes. (In order to satisfy the rules governing Γ_{τ}(m_{n})’s movement, if S_{i,e}^{σ} removes Γ_{τ}(m_{n}) from its position during stage t + 1 then it also removes each Γ_{τ}(m), m > m_{n}, from its position and enumerates γ_{τ}(m_{n}, t) into A.) If the computation Φ_{e}(A; n) ever changes then S_{i,e}^{σ} releases control of Γ_{τ}(m) for m ⩾ m_{n}.

If Φ_{j}(A ⊕ B_{i}) is total then Γ_{τ}(m_{n}) will have a limiting position γ_{τ}(m_{n}). We would like to claim that γ_{τ}(m_{n}) is a permanent σ-i-configuration. Indeed, γ_{τ}(m) < γ_{τ}(m_{n}) ⇒ m < m_{n} ⇒ φ_{j}(A ⊕ B_{i}; m) < φ_{j}(A ⊕ B_{i}; m_{n}) < γ_{τ}(m_{n}), and if t is the stage at which Γ_{τ}(m_{n}) achieves position γ_{τ}(m_{n}) then the computation Φ_{j}(A⊕B_{i}; m_{n}) will not change after stage t, which by the conventions in Section 0 implies that for all m < m_{n} the computation Φ_{j}(A⊕B_{i}; m) will not change after stage t.

However, this does not guarantee that, for all m < m_{n}, if t is the stage at which Γ_{τ}(m) achieves its final position then Φ_{j}(A ⊕ B_{i}; m) = Φ_{j}(A ⊕ B_{i}; m)[t]. This is because Γ_{τ}(m) might achieve its final position much earlier than Γ_{τ}(m_{n}). Thus, we need S_{i,e}^{σ} to remove Γ_{τ}(m_{n}) from its position whenever there exists an m < m_{n} such that Γ_{τ}(m) has a position and the value of Φ_{j}(A ⊕ B_{i}; m) is different from what it was when this position was assigned.

Now if Γ_{τ}(m_{n}) has a limiting position then this position is a permanent σ-i-configuration. In this case, S_{i,e}^{σ} cancels the positions of markers only finitely often, and hence it respects the rules for the movement of the Γ_{τ}-markers.

On the other hand, if Γ_{τ}(m_{n}) does not have a limiting position then either Φ_{j}(A ⊕ B_{i}) is not total or for some m there exist infinitely many s such that Γ_{τ}(m) has a position at stage s that was assigned at stage t and Φ_{j}(A ⊕ B_{i}; m)[s] ≠ Φ_{j}(A ⊕ B_{i}; m)[t]. But it is not hard to see that the latter case cannot happen if Φ_{j}(A ⊕ B_{0}) = ⋯ = Φ_{j}(A ⊕ B_{N−1}). Thus, if Γ_{τ}(m_{n}) does not have a limiting position then R_{j} is satisfied because its antecedent is false. Furthermore, either Γ_{τ}(m_{n}) has no position from some point on or S_{i,e}^{σ} cancels the position of Γ_{τ}(m_{n}) infinitely often. In either case, the numbers put into A for the purpose of coding the movement of Γ_{τ}-markers form a computable set.

In the general case, in which there are multiple R-strategies in Active strategy(σ), whenever S_{i,e}^{σ} finds a σ-stage s such that Φ_{e}(A)[s] ↾ n = C_{i}[s] ↾ n and Φ_{e}(A; n)[s] converges, instead of taking control of a single marker, it takes control of a marker Γ_{τ}(m_{n,τ}^{σ}) for each R_{j}^{τ} ∈ Active strategy(σ). We would like S_{i,e}^{σ} to keep the position of each of these markers clear of all the uses φ_{j}(A⊕B_{i}; m_{n,τ}^{σ}), R_{j}^{τ} ∈ Active strategy(σ).

It might seem that S_{i,e}^{σ} could do this simply by moving all the markers under its control whenever necessary. The problem is that, if for some R_{j}^{τ} ∈ Active strategy(σ) it turns out that Φ_{j}(A⊕B_{i}; m_{n,τ}^{σ}) is not convergent, then for some other R_{k}^{α} ∈ Active strategy(σ), S_{i,e}^{σ} might have to remove Γ_{α}(m_{n,α}^{σ}) from its position infinitely often without corresponding changes in the computation Φ_{k}(A⊕B_{i}; m_{n,α}^{σ}), thus violating R_{k}^{α}’s rules. If α ⊃ τ this will not be a problem, since we will then guarantee the existence of another copy of R_{k} following this outcome of S_{i,e}^{σ}. Since we will now also remove R_{j}^{τ} from the list of active strategies, it will be true that each R_{k} will have only finitely many copies on a given path. However, we cannot allow R_{j}^{τ} to injure R_{k}^{α} if α ⊂ τ, since in this case R_{k}^{α} has stronger priority than R_{j}^{τ}. If we were to allow such injury to happen, copies of R_{k} might get injured infinitely often, and hence R_{k} might never be satisfied.

Thus, we proceed as follows: At a given σ-stage t ⩾ s, if there exists an R_{j}^{τ} ∈ Active strategy(σ) such that Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ}) diverges, or for some m < m_{n,τ}^{σ}, Γ_{τ}(m) has a position assigned at some stage t and Φ_{j}(A ⊕ B_{i}; m)[s] ≠ Φ_{j}(A ⊕ B_{i}; m)[t], or γ_{β}(m_{n,β}^{σ}, t) ⩽ φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[t] for some R_{k}^{β} ∈ Active strategy(σ), then for the greatest such j, S_{i,e}^{σ} releases control of Γ_{α}(m_{n,α}^{σ}) and changes the value of m_{n,α}^{σ} for α ⊂ τ, while for each α ⊇ τ and each m ⩾ m_{n,α}^{σ}, it removes Γ_{α}(m) from its position, enumerating the least among the previous positions of these markers into A.

Now, unless there is an R_{j}^{τ} ∈ Active strategy(σ) such that Φ_{j}(A ⊕ B_{i}) is not total or it is not the case that Φ_{j}(A ⊕ B_{0}) = ⋯ = Φ_{j}(A ⊕ B_{N−1}), S_{i,e}^{σ} will find a permanent σ-i-configuration greater than φ_{e}(A; n) for each n such that Φ_{e}(A) ↾ n = C_{i} ↾ n and Φ_{e}(A; n) converges.

We are still left with the question of how to satisfy (2.10). This can be accomplished as follows: For each n we have a marker δ(n) with position δ(n, s) at stage s. S_{i,e}^{σ} moves δ(n) to a fresh large position each time the n^{th} σ-i-configuration it is preserving changes. If n enters F and δ(n) has a position then S_{i,e}^{σ} puts this position into C_{i}.

Now if for all n, S_{i,e}^{σ} eventually finds a permanent σ-i-configuration larger than φ_{e}(A; n) then we can E ⊕ C_{i}-computably determine F as follows: Given n, find a stage s such that S_{i,e}^{σ} is preserving a correct σ-i-configuration larger than φ_{e}(A; n) at the beginning of stage s. (As we have seen, E can do this.) Now n ∈ F if and only if either n ∈ F [s] or δ(n, s) ∈ C_{i}.

On the other hand, if there is an n such that Φ_{e}(A; n) ≠ C_{i}(n) or there is no permanent σ-i-configuration larger than φ_{e}(A; n) then S_{i,e}^{σ} codes a computable set into C_{i}, since for all but finitely many n, δ(n) is moved from each position it occupies, and each time it is reassigned a position, this position is larger than the stage at which it is assigned.

We now describe in greater detail the action of S_{i,e}^{σ} at a σ-stage s. Let r(−1, s) = 0. The preservation half of S_{i,e}^{σ} acts first and proceeds in cycles, beginning with the cycle for 0. The n^{th} cycle operates as follows:

1. If Φ_{e}(A)[s] ↾ n = C_{i}[s] ↾ n and Φ_{e}(A; n)[s] converges then go to step 2. Otherwise, cancel the value of m_{n′,τ}^{σ} and the position of δ(n′) for n′ ⩾ n and R_{j}^{τ} ∈ Active strategy(σ); preserve A ↾ r(n − 1, s) and B_{i} ↾ r(n − 1, s) and end stage s activity with outcome ⟨d, n, r(n − 1, s)⟩. (Here d stands for “disagree”. If this outcome is repeated infinitely often then Φ_{e}(A) ≠ C_{i}, so that S_{i,e} is satisfied.)

2. Assign fresh large values in P_{σ} to each m_{n,τ}^{σ}, R_{j}^{τ} ∈ Active strategy(σ), that is not defined.

3. Search for the longest τ ⊆ σ, if any, such that R_{j}^{τ} ∈ Active strategy(σ) and at least one of the following conditions holds.

(a) Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s]↑.

(b) For some m < m_{n,τ}^{σ}, Γ_{τ}(m) has a position assigned at some stage t and Φ_{j}(A⊕B_{i}; m)[s] ≠

Φ_{j}(A ⊕ B_{i}; m)[t].

(c) γ_{β}(m_{n,β}^{σ}, s) ⩽ φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s] for some R_{k}^{β} ∈ Active strategy(σ).

If such a τ exists then proceed as follows. Enumerate min{γ_{α}(m_{n,α}^{σ}, s) | R_{k}^{α} ∈ Active strategy(σ) and α ⊇ τ} into A (if this set is non-empty) and run the σ-R recovery process. For each R_{k}^{α} ∈ Active strategy(σ), if α ⊇ τ then cancel the position of Γ_{α}(y) for all y ⩾ m_{n,α}^{σ}, otherwise cancel the value of m_{n,α}^{σ}. For each x > n and each R_{k}^{α} ∈ Active strategy(σ), cancel the value of m_{x,α}^{σ}. For each x ⩾ n, cancel the position of δ(x). Let r = max(r(n − 1, s), φ_{e}(A; n)[s] + 1). Preserve A ↾ r and B_{i} ↾ r and end stage s activity with outcome ⟨c, m_{n,τ}^{σ}, n, j, r⟩. (Here c stands for “change”. If this outcome is repeated infinitely often then either Φ_{j}(A ⊕ B_{i}) is not total or it is not the case that Φ_{j}(A ⊕ B_{0}) = ⋯ = Φ_{j}(A ⊕ B_{N−1}), so that R_{j} is satisfied.)

4. Define

r(n, s) = min{γ_{τ}(m_{n,τ}^{σ}, s) | R_{j}^{τ} ∈ Active strategy(σ)}.

If this set is empty then define

r(n, s) = max({φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s] | R_{j}^{τ} ∈ Active strategy(σ)}∪
∪{φ_{e}(A; n)[s] + 1} ∪ {r(n, t) | t < s}).

If δ(n) does not have a position then assign its new position δ(n, s) to be a fresh large number in P_{σ}. Begin the (n + 1)st cycle.

The coding half of S_{i,e}^{σ} acts as follows. If δ(k) has a current position then let t be the stage at which it was assigned this position. If k ∈ F [s] − F [t] then enumerate δ(k, t) into C_{i} and ⟨δ(k, t), i⟩ into each B_{j}, j ≠ i, and run the σ-R recovery process.

Since we have made it a convention that Φ_{e}(A; n)[s] diverges for all n > s, there are only finitely many cycles in S_{i,e}^{σ}’s action at any given stage. Note that if s < t and r(n, s) and r(n, t) are both defined then r(n, s) ⩽ r(n, t).

2.5. Lemma. Let n ∈ ω. Suppose there is a σ-stage s satisfying the following conditions.

1. The computation Φ_{e}(A; n) has stabilized by the beginning of stage s, and so has each computation Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ}), R_{j}^{τ} ∈ Active strategy(σ). (Implicit in this is that m_{n,τ}^{σ} has reached a permanent value for each R_{j}^{τ} ∈ Active strategy(σ).)

2. Let R_{j}^{τ} ∈ Active strategy(σ). For each m < m_{n,τ}^{σ}, if Γ_{τ}(m) has a position at the beginning of S_{i,e}^{σ}’s stage s action that was assigned at stage t then Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A ⊕ B_{i}; m)[t].

3. The preservation half of S_{i,e}^{σ} reaches step 3 of its n^{th} cycle during its stage s action.

Then r(n, s) is defined and is a permanent σ-i-configuration greater than φ_{e}(A; n).

Proof. By 1 and 2, the preservation half of S_{i,e}^{σ} reaches step 4 of its n^{th} cycle during its stage s action, and thus r(n, s) is defined. That r(n, s) > φ_{e}(A; n) is obvious from the definition of r(n, s) and the way the m_{n,τ}^{σ} are assigned values. Now let R_{j}^{τ} ∈ Active strategy(σ) and u ⩾ s and suppose that γ_{τ}(m, u) < r(n, s). Then m < m_{n,τ}^{σ}, so that

φ_{j}(A ⊕ B_{i}; m)[u] < φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[u] = φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s] ⩽ r(n, s).

Furthermore, at the beginning of S_{i,e}^{σ}’s stage s action, if Γ_{τ}(m) has a position assigned at some stage t then Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A ⊕ B_{i}; m)[t]. If the computation Φ_{j}(A ⊕ B_{i}; m) changes after stage s then so does the computation Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ}), contrary to our assumption. So Φ_{j}(A ⊕ B_{i}; m)[u] = Φ_{j}(A ⊕ B_{i}; m)[t].

If the hypotheses of Lemma 2.5 hold then we say that S_{i,e}^{σ} finds a permanent σ-i-configuration greater than φ_{e}(A; n) and that this configuration has stabilized by stage s.

2.6. Lemma. Let R_{j}^{τ} ∈ Active strategy(σ). Suppose that m_{n,τ}^{σ} has a permanent value for which Φ_{j}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}. Then there exists a u such that for each m < m_{n,τ}^{σ} and each s > u, if Γ_{τ}(m) has a position at stage s that was assigned at stage t then Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A ⊕ B_{i}; m)[t].

Proof. This lemma follows immediately from the fact that Γ_{τ}(m) is not assigned a position at stage t unless Φ_{j}(A ⊕ B_{0})[t] ↾ m = ⋯ = Φ_{j}(A ⊕ B_{N−1})[t] ↾ m.

2.7. Corollary. If condition 2 of Lemma 2.5 is not satisfied for R_{j}^{τ} ∈ Active strategy(σ) at all sufficiently large stages then it is not the case that Φ_{j}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

We can now formally describe the possible behaviors of S_{i,e}^{σ}. When we say that a Γ-marker has its position canceled by S_{i,e}^{σ} infinitely often, this includes the possibility that the marker never has a position from some point on.

2.8. Lemma. Suppose that S_{i,e}^{σ} acts infinitely often and can restrain all numbers from entering any A ⊕ B_{l}, l < N, except for the enumeration of finitely many fixed E-computable sets and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ). Suppose further that there is a stage s_{0} after which no δ-marker used by the coding half of S_{i,e}^{σ} can have its position canceled except during S_{i,e}^{σ}’s action. Then one of the following holds.

1. There is an n such that S_{i,e}^{σ} finds permanent σ-i-configurations greater than φ_{e}(A; n′) for all n′ < n and either Φ_{e}(A; n − 1)↓≠ C_{i}(n − 1) or Φ_{e}(A; n)↑.

Let s be a stage by which all of these configurations have stabilized, and let r be their supremum. S_{i,e}^{σ}’s outcome is infinitely often equal to ⟨d, n, r⟩, and it is never of the form ⟨d, n′, r′⟩, n′ < n, ⟨c, m, n′, j, r′⟩, n′ < n, or ⟨d, n, r′⟩, r′ < r, after stage s.

S_{i,e}^{σ} cancels the position of any particular marker only finitely often.

2. There is an n such that Φ_{e}(A) ↾ n = C_{i} ↾ n, Φ_{e}(A; n) ↓, and S_{i,e}^{σ} finds permanent σ-i-configurations greater than φ_{e}(A; n′) for all n′ < n but no permanent σ-i-configuration greater than φ_{e}(A; n).

There exist j and τ with the following properties. R_{j}^{τ} ∈ Active strategy(σ), m_{n,τ}^{σ} has a permanent value, and either Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})↑ or it is not the case that Φ_{j}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}. For each k and α ⊃ τ such that R_{k}^{α} ∈ Active strategy(σ), m_{n,α}^{σ} has a permanent value for which Φ_{k}(A ⊕ B_{i}; m_{n,α}^{σ})↓.

Let r be the larger of the supremum of the permanent configurations found by S_{i,e}^{σ} and φ_{e}(A; n)+ 1. Let s be a stage by which all of these configurations have stabilized and so have the computation Φ_{e}(A; n) and each computation Φ_{k}(A ⊕ B_{i}; m_{n,α}^{σ}), R_{k}^{α} ∈ Active strategy(σ), α ⊃ τ. S_{i,e}^{σ}’s outcome is infinitely often equal to ⟨c, m_{n,τ}^{σ}, n, j, r⟩ and is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, j′, r′⟩, n′ < n, or ⟨c, m′, n, j′, r′⟩, j′ > j or (j′ = j and m′ < m_{n,τ}^{σ}) or (j′ = j, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s.

For α ⊂ τ, S_{i,e}^{σ} cancels the position of any Γ_{α}-marker only finitely often, while for α ⊇ τ, any Γ_{α}-marker whose position is canceled by S_{i,e}^{σ} after stage s has its position canceled by it infinitely often.

In either case, S_{i,e}^{σ} enumerates a computable set into each A ⊕ B_{l}, l < N.

Proof. Assume for a contradiction that Φ_{e}(A) = C_{i} and S_{i,e}^{σ} finds permanent σ-i-configurations greater than φ_{e}(A; n) for all n. Since every permanent σ-i-configuration is eventually correct, S_{i,e}^{σ} finds correct σ-i-configurations greater than φ_{e}(A; n) for all n. Let f be as in Lemma 2.4. Since f ⩽_{T} E, Lemma 2.4 implies that E can enumerate the correct σ-i-configurations, which means that C_{i} = Φ_{e}(A) ⩽_{T} E.

On the other hand, we can E ⊕ C_{i}-computably determine F as follows. Given n, E-computably find a stage s > s_{0} such that S_{i,e}^{σ} is preserving a correct σ-i-configuration larger than φ_{e}(A; n) at the beginning of stage s and C_{i}[s − 1] ↾ n = C_{i} ↾ n. At any σ-stage greater than or equal to s, the preservation half of S_{i,e}^{σ} reaches the (n + 1)^{st} cycle of its action. It is easy to check that this implies that the position of δ(n) is not canceled at any stage greater than or equal to s, which means that if n enters F at any stage greater than or equal to s then the coding half of S_{i,e}^{σ} puts δ(n, s) into C_{i}. So n ∈ F if and only if either n ∈ F [s] or δ(n, s) ∈ C_{i}, and hence F ⩽_{T} E ⊕ C_{i}.

The previous two paragraphs show that F ⩽_{T} E⊕C_{i} ≡_{T} E. Since F ⩽̸_{T} E, this is a contradiction. Thus we have only two possibilities.

Case 1. There is an n such that S_{i,e}^{σ} finds permanent σ-i-configurations greater than φ_{e}(A; n′) for all n′ < n and either Φ_{e}(A; n − 1) ↓≠ C_{i}(n − 1) or Φ_{e}(A; n) ↑. Let s be a stage by which all of these configurations have stabilized, and let r be their supremum.

In this case, each time S_{i,e}^{σ} acts at a stage t ⩾ s, its preservation half reaches its n^{th} cycle, so that S_{i,e}^{σ}’s outcome at stage t is not of the forms ⟨d, n′, r′⟩, n′ < n, ⟨c, m, n′, j, r′⟩, n′ < n, or ⟨d, n, r′⟩, r′ < r. Moreover, it will infinitely often be the case that S_{i,e}^{σ}’s preservation half stops at step 1 of its n^{th} cycle (otherwise Φ_{e}(A; n − 1) = C_{i}(n − 1) and Φ_{e}(A; n)↓). So infinitely often S_{i,e}^{σ}’s outcome is ⟨d, n, r⟩.

Now each time S_{i,e}^{σ}’s outcome is ⟨d, n, r⟩, the values of all m_{n′,τ}^{σ}, n′ ⩾ n, are canceled. When later reassigned, these values will be fresh large numbers. It is not hard to see that this implies that

lim_{s→∞} min{m | S_{i,e}^{σ} cancels the position of a marker Γ_{τ}(m) at stage s} = ∞.

Thus S_{i,e}^{σ} cancels the position of any particular marker only finitely often.

Case 2. If the above does not hold then there is an n such that Φ_{e}(A) ↾ n = C_{i} ↾ n, Φ_{e}(A; n) ↓, and S_{i,e}^{σ} finds permanent σ-i-configurations greater than φ_{e}(A; n′) for all n′ < n but no permanent σ-i-configuration greater than φ_{e}(A; n).

In this case, for all but finitely many σ-stages, S_{i,e}^{σ}’s preservation half reaches step 3 of its n^{th} cycle. By Lemma 2.5, this means that for some j there is a τ such that R_{j}^{τ} ∈ Active strategy(σ) and either m_{n,τ}^{σ} does not have a permanent value or it does but, for this value, either Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})↑ or for infinitely many s there exists an m < m_{n,τ}^{σ} such that Γ_{τ}(m) has a position at the beginning of S_{i,e}^{σ}’s stage s action that was assigned at some stage t and Φ_{j}(A ⊕ B_{i}; m)[s] ≠ Φ_{j}(A ⊕ B_{i}; m)[t]. Let j be the largest number with this property.

By the maximality of j, for each k and α ⊃ τ such that R_{k}^{α} ∈ Active strategy(σ), m_{n,α}^{σ} has a permanent value for which Φ_{k}(A ⊕ B_{i}; m_{n,α}^{σ}) ↓ and such that for all sufficiently large stages s, if m < m_{n,α}^{σ} and Γ_{α}(m) has a position at the beginning of S_{i,e}^{σ}’s stage s action that was assigned at stage t then Φ_{k}(A ⊕ B_{i}; m)[s] = Φ_{k}(A ⊕ B_{i}; m)[t].

Since S_{i,e}^{σ}’s preservation half reaches step 3 of its n^{th} cycle at all but finitely many σ-stages, the above implies that the value of m_{n,τ}^{σ} is not canceled infinitely often. Thus m_{n,τ}^{σ} has a permanent value. So, for this value, either Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})↑, or for infinitely many s there exists an m < m_{n,τ}^{σ} such that Γ_{τ}(m) has a position at the beginning of S_{i,e}^{σ}’s stage s action that was assigned at some stage t and Φ_{j}(A ⊕ B_{i}; m)[s] ≠ Φ_{j}(A ⊕ B_{i}; m)[t]. If the latter possibility holds then, by Corollary 2.7, it is not the case that Φ_{j}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

Let r be the larger of the supremum of the permanent configurations found by S_{i,e}^{σ} and φ_{e}(A; n)+ 1. Let s be a stage by which all of these configurations have stabilized and so have the computation Φ_{e}(A; n) and each computation Φ_{k}(A ⊕ B_{i}; m_{n,α}^{σ}), R_{k}^{α} ∈ Active strategy(σ), α ⊃ τ. At any stage after s during which it acts, S_{i,e}^{σ}’s preservation half reaches step 3 of its n^{th} cycle, and the search conducted at that step does not stop at any α ⊃ τ. Thus, S_{i,e}^{σ}’s outcome is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, j′, r′⟩, n′ < n, or ⟨c, m′, n, j′, r′⟩, j′ > j or (j′ = j and m′ < m_{n,τ}^{σ}) or (j′ = j, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s, and infinitely often it is equal to ⟨c, m_{n,τ}^{σ}, n, j, r⟩.

Arguing as in the previous case, we can now show that any particular Γ_{α}-marker, α ⊂ τ, is removed from its position only finitely often by S_{i,e}^{σ}. It is also clear from the description of S_{i,e}^{σ}’s action that, after stage s, the only markers Γ_{α}(x), R_{k}^{α} ∈ Active strategy(σ), α ⊇ τ, whose positions are canceled by S_{i,e}^{σ} are those with x ⩾ m_{n,α}^{σ}, and that these have their positions canceled each time S_{i,e}^{σ}’s outcome after stage s is ⟨c, m_{n,τ}^{σ}, n, j, r⟩.

In either case, it is easy to see that S_{i,e}^{σ}’s preservation half enumerates a computable set into A. As previously remarked, the fact that there exists an n such that either Φ_{e}(A; n) ≠ C_{i}(n) or there is no permanent σ-i-configuration larger than φ_{e}(A; n) found by S_{i,e}^{σ} means that S_{i,e}^{σ} codes a computable set into C_{i}.

Making the b_{i} maximal-a-cappable. We break (2.4) into requirements

N_{i,k,l,e} : W_{k}, W_{l} ⩽̸_{T} A ⊕ B_{i} ⇒ D_{i,k,l} ≠ Φ_{e}(A),

with corresponding strategies N_{i,k,l,e}.

For each i < N and k, l, x ∈ ω we have standard markers ζ_{i,k,l}(x) and ζ̃_{i,k,l}(x) which take values ζ_{i,k,l}(x, s) and ζ̃_{i,k,l}(x, s), respectively, at stage s. For each sequence σ of strategies and outcomes, these values are in P_{σ} for x ∈ P_{σ}. These markers are subject to the following rules: Each time W_{k} changes below x, ζ_{i,k,l}(x) is moved; each time W_{l} changes below x, ζ̃_{i,k,l}(x) is moved. If x either enters or leaves D_{i,k,l} at stage s then min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)) is put into A. (It will never be the case that D_{i,k,l}(x) changes at a stage s such that min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)) ∈ A[s − 1].) This coding guarantees that (2.3) is satisfied.

In its attempt to satisfy N_{i,k,l,e}, a strategy N_{i,k,l,e}^{σ} will launch attacks at σ-stages s and through numbers x such that Φ_{e}(A; x)[s] = D_{i,k,l}(x)[s] and there exists a σ-i-configuration r(x) greater than φ_{e}(A; x)[s] but less than min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)).

The idea is to change D_{i,k,l} at such an x and preserve the corresponding configuration by imposing a restraint r(x) on A⊕B_{i}, in the hope that we have thus made D_{i,k,l} and Φ_{e}(A) permanently different at x. We will have done so if r(x) is correct. In order to respect the rules for ζ_{i,k,l}(x) and ζ̃_{i,k,l}(x), N_{i,k,l,e}^{σ} will also enumerate min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)) into A. This is the reason we require r(x) to be less than min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)).

With an eye toward satisfying (2.8), we will not launch an attack through x unless we have F -permission, that is, unless a number has entered F below x since the last time N_{i,k,l,e}^{σ} was active. This will ensure that if F ↾ n = F [s] ↾ n and s is a σ-stage then no x < n is put into A by N_{i,k,l,e}^{σ} at any stage after s, a fact which we will need later in the proof of Lemma 2.17.

Of course, an attack can be canceled by a change in A ⊕ B_{i} below the attack’s associated configuration. We will need to allow for the possibility of multiple simultaneous attacks, as well as multiple consecutive attacks through the same number. (The reason for this will become clear in the proof of Lemma 2.34.) However, in order to keep the restraint due to N_{i,k,l,e}^{σ} finite, we make sure that while an attack through x is in effect, no attack through y > x can be launched. (Recall that, under the use conventions of Section 0, x < y ∧ Φ_{e}(A; x)[s] ↓ ∧Φ_{e}(A; y)[s] ↓⇒ φ_{e}(A; x)[s] < φ_{e}(A; y)[s].) We will be able to show that for some copy of N_{i,k,l,e} there is an attack that is never canceled.

We will rely on S-strategies of weaker priority than N_{i,k,l,e}^{σ} to find the necessary correct configurations described above. We will see later that each N_{i,k,l,e} has a copy for which these weaker priority strategies do indeed find arbitrarily large correct configurations. However, even if N_{i,k,l,e}^{σ} is such a copy, we still need to guarantee that there will be enough numbers x such that there is a stage s and a correct σ-i-configuration at stage s that is greater than φ_{e}(A; x)[s] but smaller than min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)). For this we need to have enough numbers x such that W_{k}[f(x)] ↾ x ≠ W_{k} ↾ x and W_{l}[f(x)] ↾ x ≠ W_{l} ↾ x, where f(x) denotes the least σ-stage at which a correct σ-i-configuration greater than φ_{e}(A; x)[s] exists.

Since being a correct σ-i-configuration at a given stage is an A ⊕ B_{i}-computable condition, we will be able to see that this is the case with the help of two applications of the following lemma, which appears as the lemma to Theorem 2 of Chapter 18 in [12]. (See the proof of Lemma 2.34 for details.)

2.9. Lemma. If X is c.e., W_{m} ⩽̸_{T} X, Y is c.e. in X and infinite, and f is computable in X, then {y ∈ Y | W_{m} ↾ y ≠ W_{m}[f(y)] ↾ y} is c.e. in X and infinite.

For a proof of this lemma, see [4] or [12].

We now describe in greater detail the action of N_{i,k,l,e}^{σ} at a σ-stage s.

1. For each x, if N_{i,k,l,e}^{σ} is under attack through x and A ⊕ B_{i}[s] ↾ r(x) ≠ A ⊕ B_{i}[t] ↾ r(x), where t is the last σ-stage before s, then cancel the attack.

2. Search for x < s such that x ∈ P_{σ} and the following hold.

(a) Φ_{e}(A; x)[s] = D_{i,k,l}(x)[s].

(b) There exists a σ-i-configuration v > φ_{e}(A; x)[s] such that q = min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)) > v.

(c) q is greater than all restraints in σ.

(d) q ∉ A[s].

(e) F [s] ↾ x ≠ F [t] ↾ x, where t is the last σ-stage before s if one exists, t = 0 otherwise.

(f) x < y for all y such that N_{i,k,l,e}^{σ} was under attack through y at the beginning of stage s.

Choose the least such x (if one exists). If x ∉ D_{i,k,l}[s] then put x into D_{i,k,l}, otherwise remove x from D_{i,k,l}. Put min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)) into A and run the σ-R recovery process. Declare that N_{i,k,l,e}^{σ} is under attack through x and define r(x) to be the least v satisfying (b).

3. Let r = max{r(x) | N_{i,k,l,e}^{σ} is under attack through x}, r = 0 if N_{i,k,l,e}^{σ} is not currently under attack. Preserve A ↾ r and B_{i} ↾ r and end stage s activity with outcome r.

In the eventual tree construction, N_{i,k,l,e}^{σ} will have to respect other restraints beyond the ones in σ, and we will emend condition 2(c) accordingly (see page 29).

2.10. Proposition. D_{i,k,l} is well-defined and D_{i,k,l} ⩽_{T} W_{k} ⊕ A, W_{l} ⊕ A, so that (2.3) is satisfied.

Proof. Fix x and let q(s) = min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)). If D_{i,k,l}(x) changes at stage s then q(s) is put into A. Since this requires that q(s) not have been previously put into A, and since q(s) can change only finitely often, this means that D_{i,k,l}(x) can change at most finitely often. This gives us the first part of the proposition.

For the second part, we notice that we can W_{k} ⊕ A-computably (W_{l} ⊕ A-computably) determine D_{i,k,l} as follows: Given x, find the limit n of ζ_{i,k,l}(x, s) (ζ̃_{i,k,l}(x, s)) as s → ∞. Let s be such that A[s] ↾ n + 1 = A ↾ n + 1. Now x ∈ D_{i,k,l} if and only if x ∈ D_{i,k,l}[s].

2.11. Lemma. If N_{i,k,l,e}^{σ} acts infinitely often then there is an r such that the outcome of N_{i,k,l,e}^{σ} is infinitely often equal to r.

Proof. First suppose there is a stage t such that N_{i,k,l,e}^{σ} comes under attack through some x at t and this attack is never canceled. Then the outcome of N_{i,k,l,e}^{σ} at any σ-stage v > t is less than or equal to the outcome at t. This is because, by rule (f) above, any attacks on N_{i,k,l,e}^{σ} launched after stage t will be through y < x, and we have seen that in this case r(y) < r(x).

The other possibility is that all attacks on N_{i,k,l,e}^{σ} are eventually canceled. But no attack through x can be launched at a stage after t until all attacks through y < x in effect at stage t have been canceled, and only finitely many attacks can be launched through any given number. Since no attack is ever launched at the same stage that another attack through a smaller number is canceled, this means that in this case there will be infinitely many σ-stages during which no attacks on N_{i,k,l,e}^{σ} are left uncanceled at the end of N_{i,k,l,e}^{σ}’s action. At any such stage, N_{i,k,l,e}^{σ}’s outcome is equal to 0.

2.12. Lemma. Suppose that N_{i,k,l,e}^{σ} can restrain all numbers from entering A ⊕ B_{i} except for the enumeration of an E-computable set W, numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ), and numbers enumerated by N_{i,k,l,e}^{σ} itself. Suppose further that there is a stage s after which an attack on N_{i,k,l,e}^{σ} through x cannot be canceled except by a change in A or B_{i} below r(x). Then the set V of numbers enumerated into A by N_{i,k,l,e}^{σ} is also E-computable.

Proof. Let f(m) be the least σ-stage after s such that no numbers less than m are put into A or B_{i} by the enumeration of W during or after stage f(m). By hypothesis, f ⩽_{T} E.

If some m enters V at a stage t > f(m) then it must be the case that an attack on N_{i,k,l,e}^{σ} is launched at stage t through x such that m = min(ζ_{i,k,l}(x, t), ζ̃_{i,k,l}(x, t)). But then t > f(m) ⩾ f(r(x)), so this attack will not be canceled unless an attack on N_{i,k,l,e}^{σ} through y < x is later launched, since if no such attack is launched then, by Lemma 2.3, r(x) is a correct σ-i-configuration. In this case, this new attack will not be canceled unless an attack on N_{i,k,l,e}^{σ} through z < y is later launched, and so on. Eventually, there will be an attack on N_{i,k,l,e}^{σ} that is never canceled, so that, by rule (f) above, V is finite.

If, on the other hand, no m enters V after stage f(m) then V ⩽_{T} f ⩽_{T} E.

Coding ⩽_{0}. We satisfy (2.5) by direct coding. Whenever a number x is enumerated into B_{i} directly, that is, for any purpose other than the coding of a C_{k} or B_{k} into B_{i}, we require that ⟨x, N + i⟩ be enumerated into all B_{j} such that i <_{0} j. The only strategies that put numbers into B_{i} directly are the O_{i,j,e} described below, so this does not affect any of the preceding.

We break (2.6) into requirements

O_{i,j,e} : B_{i} ≠ Φ_{e}(A ⊕ B_{j} ⊕ C)

for i ⩽̸_{0} j, with corresponding strategies O_{i,j,e}. A copy O_{i,j,e}^{σ} of such a strategy will act very much as S_{j,e}^{σ} would.

That is, O_{i,j,e}^{σ} ensures that

Φ_{e}(A ⊕ B_{j} ⊕ C) = B_{i} ⇒ B_{i} ⩽_{T} E,  (2.11)
Φ_{e}(A ⊕ B_{j} ⊕ C) = B_{i} ⇒ F ⩽_{T} E ⊕ B_{i}.  (2.12)

via a coding/preservation strategy which differs from the way a strategy S_{j,e}^{σ} would act only in that

1. O_{i,j,e}^{σ} attempts to find permanent σ-j-configurations greater than n for each n such that Φ_{e}(A⊕ B_{j} ⊕ C) ↾ n = B_{i} ↾ n and Φ_{e}(B_{j} ⊕ A ⊕ C; n) converges, and

2. instead of coding F into C_{i}, O_{i,j,e}^{σ} codes F into B_{i} (and hence also into each B_{k}, i <_{0} k, in accordance with the coding required to satisfy (2.5)).

Notice that the coding half of O_{i,j,e}^{σ} does not put any numbers into A ⊕ B_{j}. This is what allows us to use σ-j-configurations in this case.

Formally, O_{i,j,e}^{σ} acts as follows at a σ-stage s. Let r(−1, s) = 0. The preservation half of O_{i,j,e}^{σ} acts first and proceeds in cycles, beginning with the cycle for 0. The n^{th} cycle operates as follows:

1. If Φ_{e}(A ⊕ B_{j} ⊕ C)[s] ↾ n = B_{i}[s] ↾ n and Φ_{e}(A ⊕ B_{j} ⊕ C; n)[s] converges then go to step 2. Otherwise, cancel the value of m_{n′,τ}^{σ} and the position of δ(n′) for n′ ⩾ n and R_{k}^{τ} ∈ Active strategy(σ); preserve A ↾ r(n − 1, s) and B_{j} ↾ r(n − 1, s) and end stage s activity with outcome ⟨d, n, r(n − 1, s)⟩.

2. Assign fresh large values in P_{σ} to each m_{n,τ}^{σ}, R_{k}^{τ} ∈ Active strategy(σ), that is not defined.

3. Search for the longest τ ⊆ σ, if any, such that R_{k}^{τ} ∈ Active strategy(σ) and at least one of the following conditions holds.

(a) Φ_{k}(A ⊕ B_{j}; m_{n,τ}^{σ})[s]↑.

(b) For some m < m_{n,τ}^{σ}, Γ_{τ}(m) has a position assigned at some stage t and Φ_{k}(A⊕B_{j}; m)[s] ≠ Φ_{k}(A ⊕ B_{j}; m)[t].

(c) γ_{β}(m_{n,β}^{σ}, s) ⩽ φ_{k}(A ⊕ B_{j}; m_{n,τ}^{σ})[s] for some R_{l}^{β} ∈ Active strategy(σ).

If such a τ exists then proceed as follows. Enumerate min{γ_{α}(m_{n,α}^{σ}, s) | R_{l}^{α} ∈ Active strategy(σ) and α ⊇ τ} into A (if this set is non-empty) and run the σ-R recovery process. For each R_{l}^{α} ∈ Active strategy(σ), if α ⊇ τ then cancel the position of Γ_{α}(y) for all y ⩾ m_{n,α}^{σ}, otherwise cancel the value of m_{n,α}^{σ}. For each x > n and each R_{l}^{α} ∈ Active strategy(σ), cancel the value of m_{x,α}^{σ}. For each x ⩾ n, cancel the position of δ(x). Let r = max(r(n − 1, s), φ_{e}(A ⊕ B_{j} ⊕ C; n)[s] + 1). Preserve A ↾ r and B_{j} ↾ r and end stage s activity with outcome ⟨c, m_{n,τ}^{σ}, n, k, r⟩.

4. Define

r(n, s) = min{γ_{τ}(m_{n,τ}^{σ}, s) | R_{k}^{τ} ∈ Active strategy(σ)}.

If this set is empty then define

r(n, s) = max({φ_{k}(A ⊕ B_{j}; m_{n,τ}^{σ})[s] | R_{k}^{τ} ∈ Active strategy(σ)}∪
∪{φ_{e}(A ⊕ B_{j} ⊕ C; n)[s] + 1} ∪ {r(n, t) | t < s}).

If δ(n) does not have a position then assign its new position δ(n, s) to be a fresh large number in P_{σ}. Begin the (n + 1)st cycle.

The coding half of O_{i,j,e}^{σ} acts as follows. If δ(k) has a current position then let t be the stage at which it was assigned this position. If k ∈ F [s] − F [t] then enumerate δ(k, t) into B_{i} and ⟨δ(k, t), N + i⟩ into each B_{k}, i <_{0} k, and finally run the σ-R recovery process.

Corresponding to Lemma 2.8, we have the following lemma.

2.13. Lemma. Suppose that O_{i,j,e}^{σ} acts infinitely often and can restrain all numbers from entering any A⊕B_{p}, p < N, except for the enumeration of finitely many fixed E-computable sets and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ). Suppose further that there is a stage after which no δ-marker used by the coding half of O_{i,j,e}^{σ} can have its position canceled except during O_{i,j,e}^{σ}’s action. Then one of the following holds.

1. There is an n such that O_{i,j,e}^{σ} finds permanent σ-j-configurations greater than φ_{e}(A⊕B_{j}⊕C; n′) for all n′ < n and either Φ_{e}(A ⊕ B_{j} ⊕ C; n − 1)↓≠ B_{i}(n − 1) or Φ_{e}(A ⊕ B_{j} ⊕ C; n)↑.

Let s be a stage by which all of these configurations have stabilized, and let r be their supremum. O_{i,j,e}^{σ}’s outcome is infinitely often equal to ⟨d, n, r⟩, and it is never of the form ⟨d, n′, r′⟩, n′ < n, ⟨c, m, n′, l, r′⟩, n′ < n, or ⟨d, n, r′⟩, r′ < r, after stage s.

O_{i,j,e}^{σ} cancels the position of any particular marker only finitely often.

2. There is an n such that Φ_{e}(A ⊕ B_{j} ⊕ C) ↾ n = B_{i} ↾ n, Φ_{e}(A ⊕ B_{j} ⊕ C; n) ↓, and O_{i,j,e}^{σ} finds permanent σ-j-configurations greater than φ_{e}(A ⊕ B_{j} ⊕ C; n′) for all n′ < n but no σ-j-configuration greater than φ_{e}(A ⊕ B_{j} ⊕ C; n).

There exist l and τ with the following properties. R_{l}^{τ} ∈ Active strategy(σ), m_{n,τ}^{σ} has a permanent value, and either Φ_{l}(A ⊕ B_{j}; m_{n,τ}^{σ})↑ or it is not the case that Φ_{l}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{l}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}. For each k and α ⊃ τ such that R_{k}^{α} ∈ Active strategy(σ), m_{n,α}^{σ} has a permanent value for which Φ_{k}(A ⊕ B_{j}; m_{n,α}^{σ})↓.

Let r be the larger of the supremum of the permanent configurations found by O_{i,j,e}^{σ} and φ_{e}(A⊕ B_{j} ⊕ C; n) + 1. Let s be a stage by which all of these configurations have stabilized and so have the computation Φ_{e}(A ⊕ B_{j} ⊕ C; n) and each computation Φ_{k}(A ⊕ B_{j}; m_{n,α}^{σ}), R_{k}^{α} ∈ Active strategy(σ), α ⊃ τ. O_{i,j,e}^{σ}’s outcome is infinitely often equal to ⟨c, m_{n,τ}^{σ}, n, l, r⟩ and is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, l′, r′⟩, n′ < n, or ⟨c, m′, n, l′, r′⟩, l′ > l or (l′ = l and m′ < m_{n,τ}^{σ}) or (l′ = l, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s.

For α ⊂ τ, O_{i,j,e}^{σ} cancels the position of any Γ_{α}-marker only finitely often, while for α ⊇ τ, any Γ_{α}-marker whose position is canceled by O_{i,j,e}^{σ} after stage s has its position canceled by it infinitely often.

In either case, O_{i,j,e}^{σ} enumerates a computable set into each A ⊕ B_{p}, p < N.

The proof of this lemma is completely analogous to that of Lemma 2.8.

Producing F-computable sets. We wish to satisfy condition (2.8). From the previous sections it can be seen that there are four ways for numbers to enter A or some B_{i} or C_{i}:

1. A number enters E and this fact is coded into A by K.

2. A number is put into A by some N-strategy as part of an attack on that strategy.

3. A number is put into A in order to code the movement of a marker Γ_{σ}(m).

4. A number enters F and this fact is coded into some C_{i} (B_{i}) by an S-strategy (O-strategy), and subsequently into B_{j}, j ≠ i (i <_{0} j).

Clearly, the numbers coded into A by K form an F -computable set.

As mentioned on page 17, no number n ∈ P_{σ} can be put into A by N_{i,k,l,e}^{σ} as part of the realization of an attack on that strategy after a σ-stage s such that F [s] ↾ n + 1 = F ↾ n + 1. Thus the numbers put into A for this reason also form an F -computable set.

In order to ensure that the numbers entering A as codes for the movement of markers associated with R-strategies form an F -computable set, we will define the concept of a σ-configuration, which will be similar to a σ-i-configuration except that it will use A ⊕ B_{j} computations for every j < N, instead of only using A ⊕ B_{i} computations. We will then describe, for each k, a strategy M_{k}^{σ} which acts to guarantee, for each R_{e}^{τ} in σ and each m, that Γ_{τ}(m) either moves past position k without occupying it, occupies it and is later moved, or there is a permanent σ-configuration that keeps Γ_{τ}(m) from moving from position k. Since F will be able to enumerate such permanent configurations uniformly, this will give us the desired result. (Whenever a new position is assigned to a marker, this position is larger than any number previously mentioned in the construction. Thus, if Γ_{τ}(m) does not have a position at stage k then we can consider Γ_{τ}(m) to have moved past position k.)

This leaves us with the task of ensuring that the numbers entering some C_{i} or B_{i} for reason 4 above form an F -computable set. The problem here is the following. Suppose that F [s] ↾ n = F ↾ n and that an S-strategy (O-strategy) X acts at a stage t > s. Let k < n and let δ(k) be the corresponding marker employed by the coding half of X. Let u be the last stage before t at which X acted and suppose that δ(k, t) = δ(k, s) = δ(k, u). If u < s then it is possible that k ∈ F [t]−F [u], so that δ(k, s) will be put into some C_{i} (B_{i}) by X. This means that, in order to be sure that no numbers less than n will enter any C_{i} or B_{i} after stage s, it is not enough to know that F [s] ↾ n = F ↾ n. We must also know that none of the S-strategies and O-strategies that still have δ-markers with positions less than n at the end of stage s and that do not act during stage s will ever act after stage s. We will be able to show that this is the case if s is a σ-stage and M_{n}^{σ} preserves a correct σ-configuration greater than n at stage s (see Definition 2.21). We will also show that, for every n ∈ ω, some strategy M_{n}^{σ} eventually preserves a correct σ-configuration greater than n, and that F can enumerate the correct σ-configurations uniformly. This will be enough to show that the numbers entering some C_{i} or B_{i} for reason 4 above form an F -computable set. We will discuss this further in the paragraphs following Corollary 2.20.

The M-strategies will work similarly to the preservation half of the S-strategies. That is, they will take control of certain markers and keep their positions clear of appropriate configurations. Since the M-strategies do not have coding halves, they will be able to use A ⊕ B_{i} computations for every i < N. Furthermore, we will see that the activity of such a strategy is finitely bounded, so that it can be allowed to move any marker without danger of violating the rules for its movement.

Before describing the M-strategies, we impose an additional convention on our use functions, namely that if Φ_{e}(A ⊕ B_{i}; n)[s]↓ through a computation that exists for the first time at stage s then for all t < s and j < N such that Φ_{e}(A ⊕ B_{j}; n)[t] ↓, φ_{e}(A ⊕ B_{i}; n)[s] ⩾ φ_{e}(A ⊕ B_{j}; n)[t]. It is easy to check that this new convention does not alter any of the preceding.

For each strategy R_{e}^{σ}, if γ_{σ}(n, s) is defined then let

max min(σ, n, s) = min{φ_{e}(A ⊕ B_{i}; n)[s] | Φ_{e}(A ⊕ B_{i}; n)[s] = Φ_{e}(A ⊕ B_{i}; n)[t], i < N},

where t is the stage at which Γ_{σ}(n) was assigned position γ_{σ}(n, s). If γ_{σ}(n, s) is defined then, due to our new convention on uses, max min(σ, n, s) is the maximum of the lengths of the shortest computations that have kept the R_{e}^{σ} recovery process from moving Γ_{σ}(n) during the stages between t and s.

2.14. Lemma. Suppose that R_{e}^{σ} acts infinitely often and γ_{σ}(n, s) is defined for infinitely many s. If max min(σ, n, s) goes to infinity as a function of s then so does γ_{σ}(n, s).

Proof. Assume for a contradiction that max min(σ, n, s) goes to infinity as a function of s and there exists a t such that Γ_{σ}(n) gets assigned a position at stage t and γ_{σ}(n, s) = γ_{σ}(n, t) for all s > t. Let U be the set of all i < N such that Φ_{e}(A ⊕ B_{i}; n)[s] = Φ_{e}(A ⊕ B_{i}; n)[t] for infinitely many s. Let u ⩾ t be a stage such that for all i < N, i ∉ U, and all s ⩾ u, Φ_{e}(A ⊕ B_{i}; n)[s] ≠ Φ_{e}(A ⊕ B_{i}; n)[t].

For each i ∈ U, Φ_{e}(A⊕B_{i}; n) diverges, since otherwise max min(σ, n, s) would have a finite limit. Given x ∈ ω, let f(x) be the first stage greater than or equal to u such that for each i ∈ U there exists an s < f(x) such that φ_{e}(A ⊕ B_{i}; n)[s] > 2x.

Suppose that some x enters E at a stage s > f(x). Then 2x enters A at stage s, which means that at the first σ-stage v after s, R_{e}^{σ} will treat each computation Φ_{e}(A ⊕ B_{i}; n)[v], i ∈ U, as divergent.

Thus, since v > u, it will be the case that for all i < N, Φ_{e}(A ⊕ B_{i}; n)[v] ≠ Φ_{e}(A ⊕ B_{i}; n)[t], and hence Γ_{σ}(n) will have its position canceled at stage v.

Since we have assumed that γ_{σ}(n, s) = γ_{σ}(n, t) for all s > t, we conclude that no number x enters E at a stage after f(x). In other words, E(x)[f(x)] = E(x) for all x ∈ ω. However, f(x) is clearly computable, so we have contradicted the noncomputability of E.

It should be noted that if v is a σ-i-configuration at stage s then our new convention on uses implies that for all R_{j}^{τ} ∈ Active strategy(σ) and all m, γ_{τ}(m, s) < v ⇒ max min(τ, m, s) < v.

We now proceed with the description of M_{k}^{σ}.

We first consider the case in which K and R_{e}^{τ} are the only strategies in σ. In this case, we define a σ-configuration at stage s to be a number v such that γ_{τ}(m, s) < v ⇒ max min(τ, m, s) < v.

M_{k}^{σ} fixes a number move_{σ} in advance and removes Γ_{τ}(move_{σ}) from its position every time the smallest σ-configuration greater than k is larger than the position of Γ_{τ}(move_{σ}). Otherwise, M_{k}^{σ} preserves the smallest σ-configuration greater than k.

Suppose that M_{k}^{σ} acts infinitely often. Let U be the set of all numbers m < move_{σ} such that γ_{τ}(m, s) has a limit γ_{τ}(m). By Lemma 2.14, for each m ∈ U, max min(τ, m, s) has a limit max min(τ, m).

Let L be the least number greater than k such that for all m ∈ U, γ_{τ}(m) < L ⇒ max min(τ, m) < L. Let s be a σ-stage such that γ_{τ}(m, s) = γ_{τ}(m) and max min(τ, m, s) = max min(τ, m) for all m ∈ U, and all Γ_{τ}(n), n < move_{σ}, n ∉ U, have moved past L by stage s. (Such an s exists by Lemma 2.14.) The smallest σ-configuration greater than k at stage s is greater than or equal to L, so if γ_{τ}(move_{σ}, s) is less than L then Γ_{τ}(move_{σ}) will be removed from its position by M_{k}^{σ}. So for all stages t > s, γ_{τ}(m, t) < L ⇒ m ∈ U ⇒ max min(τ, m, t) < L, and thus L is a permanent σ-configuration greater than k. Furthermore, it is clear from its definition that L is the smallest such configuration.

All M_{k}^{σ} does after stage s is to preserve L, so its action is finite.

In the general case, the definition of σ-configuration is a little more complicated.

2.15. Definition. A number v is a σ-configuration at stage s if it satisfies the following conditions.

1. For each ⟨R_{e}^{τ}⟩ ∈ σ, γ_{τ}(m, s) < v ⇒ max min(τ, m, s) < v.

2. v is greater than all restraints in σ.

3. If ⟨X^{τ}, c, m, n, l, r⟩ ∈ σ, where X is one of S_{i,e} or O_{j,i,e}, R_{k}^{α} ∈ Active strategy(τ), k > l, and the computation Φ_{k}(A ⊕ B_{i}; m_{n,α}^{τ}) still exists at the end of X^{τ}’s stage s action, then v > φ_{k}(A ⊕ B_{i}; m_{n,α}^{τ})[s].

The third clause of this definition may seem mysterious at this point, but it will become necessary later on when we prove Lemma 2.32.

The following two lemmas are important consequences of Definition 2.15. The first follows immediately from Definition 2.15 and the definition of recovery process.

2.16. Lemma. Suppose that v is a σ-configuration at the beginning of a recovery process run by some strategy. Suppose further that if α ⊈ σ then no number in P_{α} is put into A ↾ v by the recovery process. Then no number is put into A ↾ v by the recovery process.

We say that a σ-configuration v at stage s is F and E-correct if F [s] ↾ v = F ↾ v and E[s] ↾ v = E ↾ v.

2.17. Lemma. Suppose that M_{k}^{σ} preserves an F and E-correct σ-configuration v larger than k at some σ-stage s such that for each strategy X^{τ}, τ ⊆ σ, the only strategies that can be the first to put a number less than the restraint due to X^{τ} into A or any B_{i} or C_{i}, i < N, after stage s are those mentioned in τ. Then A[s] ↾ v = A ↾ v and, for all i < N, B_{i}[s] ↾ v = B_{i} ↾ v and C_{i}[s] ↾ v = C_{i} ↾ v.

Proof. By Lemma 2.16, it is enough to show that for all strategies X^{α} in σ, X^{α} cannot be the first strategy in the construction to put a number into A ↾ v or some B_{i} ↾ v or C_{i} ↾ v, i < N, after stage s. We assume by induction that the lemma is true for each strategy M_{k′}^{α}, α ⊂ σ, and remark that it will be the case that for any such strategy, k′ < k (see Lemma 2.24).

The case X = K follows immediately from the fact that E[s] ↾ v = E ↾ v.

The case X^{α} = R_{e}^{α} follows from Lemma 2.16.

If X^{α} = M_{k′}^{α} then, by induction, M_{k′}^{α} is preserving a permanent α-configuration at stage s. Thus M_{k′}^{α} has completed its action by stage s.

If X^{α} = N_{i,j,l,e}^{α} then the only sets into which N_{i,j,l,e}^{α} puts numbers are A and D_{i,j,l}, and, as mentioned on page 17, the fact that F [s] ↾ v = F ↾ v implies that N_{i,j,l,e}^{α} does not put any numbers into A ↾ v after stage s.

The other two possibilities can be handled simultaneously. Suppose that X^{α} is one of S_{i,e}^{α} or O_{j,i,e}^{α}.

The coding half of X^{α} does not put numbers into A, and the fact that F [s] ↾ v = F ↾ v implies that it does not put any numbers into B_{p} ↾ v or C_{p} ↾ v, p < N, after stage s. We claim that the preservation half of X^{α}, which only puts numbers into A, does not put any numbers into A ↾ v after stage s.

Indeed, the configurations preserved by X^{α} at stage s are all less than v, and hence will not be violated after stage s unless some other strategy creates a change in A ↾ v or B_{i} ↾ v. Thus, unless such a change occurs, none of the markers that still have positions at the end of X^{α}’s stage s action will be removed from their positions by X^{α} after stage s. Since any positions later assigned to markers that do not have positions at the end of X^{α}’s stage s action will be larger than v, this establishes our claim and completes the proof of the lemma.

As in the simplified case described above, M_{k}^{σ} fixes a number move_{σ} (greater than all restraints in σ) in advance. At a σ-stage s, M_{k}^{σ}’s action is as follows.

1. Find the smallest σ-configuration w > k.

2. If there is no R_{e}^{τ} in σ such that γ_{τ}(move_{σ}, s) < w then let v = w and proceed to step 5.

3. Cancel the position of all markers Γ_{α}(n), ⟨R_{e′}^{α}⟩ ∈ σ, n ⩾ move_{σ}, enumerate the least of their positions into A, and run the σ-R recovery process.

4. Find the smallest σ-configuration v > k.

5. Impose a restraint equal to v on A ⊕ B_{i} and C_{i}, i < N, and end stage s activity with outcome v. (The fact that the restraint is also imposed on C_{i} will be important in the proof of Lemma 2.32.)

Notice that v, whether defined at step 2 or step 4, is the smallest σ-configuration greater than k and is less than all numbers γ_{τ}(move_{σ}, s), R_{e}^{τ} ∈ σ.

We can now show that, under certain conditions, M_{k}^{σ} will eventually preserve an F and E-correct σ-configuration greater than k. Later we will see that each M_{k} has a copy for which these conditions obtain.

2.18. Lemma. Suppose that

1. M_{k}^{σ} acts infinitely often,

2. there is a stage t after which the restraints in σ are respected,

3. for each S_{i,e}^{τ} (O_{j,i,e}^{τ}) in σ, the hypotheses of Lemma 2.8 (Lemma 2.13) are satisfied, and

4. if X is one of S_{i,e} or O_{j,i,e} and ⟨X^{τ}, c, m, n, l, r⟩ ∈ σ then for some u, X^{τ}’s outcome at a stage after u is never of the form ⟨c, m′, n,′ , l′, r′⟩, n′ < n, ⟨d, n′, r′⟩, n′ ⩽ n, or ⟨c, m′, n, l′, r′⟩, l′ > l.

Then M_{k}^{σ} eventually preserves a permanent σ-configuration greater than k.

Proof. If S_{i,e}^{τ} (O_{j,i,e}^{τ}) is as in hypothesis 4, then the second case of Lemma 2.8 (Lemma 2.13) holds, so that if R_{l}^{α}, R_{l′}^{β} ∈ Active strategy(τ) and β ⊃ α then m_{n,β}^{τ} has a final position for which Φ_{l′}(A ⊕ B_{i}; m_{n,β}^{τ}) converges. This implies that there exists a v that satisfies the third part of Definition 2.15 at all sufficiently large σ-stages. We can now argue very much as we did in the special case in which K and R_{e}^{τ} were the only strategies in σ.

That is, for each ⟨R_{e}^{τ}⟩ ∈ σ, let U(τ) be the set of all numbers m < move_{σ} such that γ_{τ}(m, s) has a limit γ_{τ}(m). By Lemma 2.14, for each m ∈ U(τ), max min(τ, m, s) has a limit max min(τ, m). Let s_{0} be such that for all ⟨R_{e}^{τ}⟩ ∈ σ and all m ∈ U(τ), γ_{τ}(m, s_{0}) = γ_{τ}(m) and max min(τ, m, s_{0}) = max min(τ, m).

Let v be the least number that satisfies the second and third parts of Definition 2.15 at all sufficiently large σ-stages and let s_{1} > s_{0} be such that v satisfies the second and third parts of Definition 2.15 at all σ-stages after s_{1}. Let L be the least number that satisfies each of the following conditions.

1. L > k.

2. L ⩾ v.

3. For all ⟨R_{e}^{τ}⟩ ∈ σ and all m ∈ U(τ), γ_{τ}(m) < L ⇒ max min(τ, m) < L.

Let s_{2} > s_{1} be such that if ⟨X^{τ}, c, m, n, l, r⟩ ∈ σ, where X is one of S_{i,e} or O_{j,i,e}, and R_{k}^{α} ∈ Active strategy(τ), k > l, then the computation Φ_{k}(A ⊕ B_{i}; m_{n,α}^{τ}) has settled down by stage s_{2}.

By Lemma 2.14, all Γ_{τ}(n), ⟨R_{e}^{τ}⟩ ∈ σ, n < move_{σ}, n ∉ U(τ), will have moved past L by some σ-stage s ⩾ s_{2}. So if γ_{τ}(move_{σ}, s) is less than L then Γ_{τ}(move_{σ}) will be removed from its position by M_{k}^{σ}. Thus L is a permanent σ-configuration greater than k. Furthermore, it is clear from its definition that L is the smallest such configuration.

The previous lemma has the following immediate consequences.

2.19. Corollary. Under the same conditions as in Lemma 2.18, M_{k}^{σ} cancels the positions of markers only finitely often.

2.20. Corollary. Under the same conditions as in Lemma 2.18, M_{k}^{σ} eventually preserves an F and E-correct σ-configuration greater than k.

We would like to argue that Corollary 2.20, together with Lemma 2.17, gives us (2.8). However, though it is certainly true that F can recognize when a strategy is preserving an F and E-correct configuration, it is not quite the case that if M_{k}^{σ} preserves an F and E-correct σ-configuration greater than k at stage s then A[s] ↾ k = A ↾ k and B_{i}[s] ↾ k = B_{i} ↾ k, i < N.

This is because the fact that M_{k}^{σ} preserves an F and E-correct configuration does not imply that the hypothesis of Lemma 2.17 is satisfied. It will also be true that this hypothesis cannot be verified by F uniformly. We will discuss this further after we have given the details of the tree of strategies and the construction.

We will then see that we need additional conditions on a configuration, leading to the definition of a correct σ-configuration, for the hypothesis of Lemma 2.17 to hold. Since it will be the case that F can recognize when a strategy is preserving a correct configuration and that every M_{k} will have a copy that eventually preserves such a configuration, we will be able to satisfy (2.8).

2.21. Definition. A σ-configuration v at stage s is said to be correct if it is F and E-correct and satisfies the following condition. Let X be one of S_{i,e} or O_{j,i,e}. If ⟨X^{β}, c, m, n, l, r⟩ ∈ σ then for all R_{k}^{τ} ∈ Active strategy(β), k > l, the computation Φ_{k}(A ⊕ B_{i}; m_{n,τ}^{β}) exists at the end of stage s.

2.22. Lemma. If M_{k}^{σ} satisfies the hypotheses of Lemma 2.18 then there is a σ-stage s at which it preserves a correct σ-configuration greater than k.

Proof. By Corollary 2.20, there is an s_{0} such that M_{k}^{σ} preserves an F and E-correct σ-configuration greater than k at all stages after s_{0}.

Now let X be one of S_{i,e} or O_{j,i,e} and suppose that ⟨X^{β}, c, m, n, l, r⟩ ∈ σ. Arguing as in the proof of Lemma 2.18, there is a t_{β} such that for all R_{k}^{τ} ∈ Active strategy(β), k > l, the computation Φ_{k}(A ⊕ B_{i}; m_{n,τ}^{β}) exists at the end of stage t_{β} and does not change after stage t_{β}. Let t be the maximum of all t_{β}, ⟨S_{i,e}^{β}, c, m, n, l, r⟩ ∈ σ or ⟨O_{j,i,e}^{β}, c, m, n, l, r⟩ ∈ σ.

Let s be the least σ-stage greater than s_{0} and t. It follows from the definition that M_{k}^{σ} preserves a correct σ-configuration greater than k at stage s.

After presenting our formal construction, we will see that every M_{k} has a copy satisfying the hypotheses of Lemma 2.18 and will be able to show (Lemma 2.32) that if M_{k}^{σ} preserves a correct σ-configuration v at stage s then A[s] ↾ v = A ↾ v and B_{i}[s] ↾ v = B_{i} ↾ v for all i < N. We will then conclude from Lemma 2.22 that (2.8) is satisfied.

The tree of strategies. The strategies described above are organized along with their possible outcomes into a tree T. We define T by recursion on the length of its nodes. In order to keep the recursion going, we need some auxiliary notions. Let L be a priority list of all the requirements in the construction (including requirements M_{k} corresponding to the strategies M_{k}), such that if i < j then R_{i} is listed before R_{j} and M_{i} is listed before M_{j}. If σ ∈ T then we make the following definitions.

1. R_{e} is satisfied in σ if there are τ ⊆ σ, i, j, e′, m, n, and r such that ⟨S_{i,e′}^{τ}, c, m, n, e, r⟩ ∈ σ or ⟨O_{i,j,e′}^{τ}, c, m, n, e, r⟩ ∈ σ.

2. S_{i,e} is satisfied in σ if there are τ ⊆ σ, n, and r such that ⟨S_{i,e}^{τ}, d, n, r⟩ ∈ σ.

3. O_{i,j,e} is satisfied in σ if there are τ ⊆ σ, n, and r such that ⟨O_{i,j,e}^{τ}, d, n, r⟩ ∈ σ.

4. R_{e}^{τ} is injured in σ if ⟨R_{e}^{τ}⟩ ∈ σ and there are α, j < e, i, e′, k, m, n, and r such that τ ⊂ α ⊆ σ and either ⟨S_{i,e′}^{α}, c, m, n, j, r⟩ ∈ σ or ⟨O_{i,k,e′}^{α}, c, m, n, j, r⟩ ∈ σ.

5. N_{i,k,l,e}^{τ} is injured in σ if there is an r such that ⟨N_{i,k,l,e}^{τ}, r⟩ ∈ σ and there are τ ⊂ α ⊆ σ, j, i′, e′, k′, m, n, and r′ such that R_{j} has stronger priority (that is, appears earlier in L) than N_{i,k,l,e} and either ⟨S_{i′,e′}^{α}, c, m, n, j, r′⟩ ∈ σ or ⟨O_{i′,k′,e′}^{α}, c, m, n, j, r′⟩ ∈ σ.

The root of T is ⟨K^{λ}⟩, where λ is the empty sequence. Suppose that we have defined “σ ∈ T ” for all σ of length k. Let σ ∈ T be of length k. We define the immediate successors of σ as follows:

Say that a requirement X requires attention at σ if

1. X = R_{e}, R_{e} is not satisfied in σ, and every strategy R_{e}^{τ} in σ is injured in σ,

2. X = S_{i,e} and S_{i,e} is not satisfied in σ,

3. X = O_{i,j,e} and O_{i,j,e} is not satisfied in σ,

4. X = N_{i,k,l,e} and every strategy N_{i,k,l,e}^{τ} in σ is injured in σ, or

5. X = M_{k} and no strategy for M_{k} appears in σ. Let X be the first strategy in L that requires attention at σ. Let

Active index(σ) = {j | some R_{j}^{τ} appears in σ and R_{j} is not satisfied in σ}.

We have the following cases:

1. X = R_{e}. Then the only immediate successor of σ is σ^{⌢}⟨R_{e}^{σ}⟩.

2. X = S_{i,e}. Then let

Outcome = {⟨c, m, n, j, r⟩ , ⟨d, n, r⟩ | j ∈ Active index(σ), m, n, j, r ∈ ω}.

The immediate successors of σ are the sequences of the form σ^{⌢}⟨S_{i,e}^{σ}, o⟩, where o ∈Outcome.

3. X = O_{i,j,e}. Then let Outcome be as above. The immediate successors of σ are the sequences of the form σ^{⌢}⟨O_{i,j,e}^{σ}, o⟩, o ∈Outcome.

4. X = N_{i,k,l,e}. Then the immediate successors of σ are the sequences of the form σ^{⌢}⟨N_{i,k,l,e}^{σ}, r⟩, r ∈ ω.

5. X = M_{k}. Then the immediate successors of σ are the sequences of the form σ^{⌢}⟨M_{k}^{σ}, r⟩, r ∈ ω.

There is a notion of α being to the left of β in T derived from the well-ordering of the immediate successors of σ ∈ T generated from the following rules. (This may not appear to be a well-ordering because of clauses 2(c) and 3(c) below, but notice that if S_{i,e}^{σ} is the strategy corresponding to σ then σ has successors of the form ⟨S_{i,e}^{σ}, c, m, n, k, r⟩ for only finitely many k, and similarly for O_{i,j,e}^{σ}.)

1. The strategy corresponding to σ is R_{e}^{σ}. Then σ has only one immediate successor.

2. The strategy corresponding to σ is S_{i,e}^{σ}. Then

(a) ⟨S_{i,e}^{σ}, d, n, r⟩ < ⟨S_{i,e}^{σ}, d, n, r′⟩ if r < r′;

(b) ⟨S_{i,e}^{σ}, d, n, r⟩ < ⟨S_{i,e}^{σ}, c, m, n, j, r′⟩;

(c) ⟨S_{i,e}^{σ}, c, m, n, j, r⟩ < ⟨S_{i,e}^{σ}, c, m′, n, j′, r′⟩ if j > j′ or if j = j′ and m < m′ or if j = j′, m = m′, and r < r′;

(d) ⟨S_{i,e}^{σ}, c, m, n, j, r⟩ < ⟨S_{i,e}^{σ}, d, n + 1, r′⟩.

3. The strategy corresponding to σ is O_{i,j,e}^{σ}. Then

(a) ⟨O_{i,j,e}^{σ}, d, n, r⟩ < ⟨O_{i,j,e}^{σ}, d, n, r′⟩ if r < r′;

(b) ⟨O_{i,j,e}^{σ}, d, n, r⟩ < ⟨O_{i,j,e}^{σ}, c, m, n, k, r′⟩;

(c) ⟨O_{i,j,e}^{σ}, c, m, n, k, r⟩ < ⟨O_{i,j,e}^{σ}, c, m′, n, k′, r′⟩ if k > k′ or if k = k′ and m < m′ or if k = k′, m = m′, and r < r′;

(d) ⟨O_{i,j,e}^{σ}, c, m, n, k, r⟩ < ⟨O_{i,j,e}^{σ}, d, n + 1, r′⟩.

4. The strategy corresponding to σ is N_{i,k,l,e}^{σ}. Then ⟨N_{i,k,l,e}^{σ}, r⟩ < ⟨N_{i,k,l,e}^{σ}, r′⟩ if r < r′.

5. The strategy corresponding to σ is M_{k}^{σ}. Then ⟨M_{k}^{σ}, r⟩ < ⟨M_{k}^{σ}, r′⟩ if r < r′.

2.23. Definition. For α, β ∈ T, say that α is to the left of β, α <_{L} β, if there exist σ, τ, ρ ∈ T such that τ and ρ are immediate successors of σ, τ(|σ| + 1) < ρ(|σ| + 1), τ ⊆ α, and ρ ⊆ β.

Define

Active strategy(σ) = {R_{e}^{τ} | τ ⊂ σ, e ∈ Active index(σ), and R_{e}^{τ} is not injured in σ}.

We establish two properties of our tree of strategies that we have been assuming throughout this proof.

2.24. Lemma. 1. If the strategies corresponding to α and β are M_{j}^{α} and M_{k}^{β}, respectively, and α ⊂ β then j < k.

2. If R_{j}^{α}, R_{k}^{β} ∈ Active strategy(σ) and α ⊂ β then j < k.

Proof. The first part of the lemma follows from the fact that if j < k then M_{j} appears before M_{k} in our priority list.

Now suppose that R_{j}^{α}, R_{k}^{β} ∈ Active strategy(σ) and α ⊂ β. Since R_{k} requires attention at β, every R_{k}^{τ} in β is injured in β, and hence in σ. Thus τ ⊂ β ⇒ R_{k}^{τ} ∉ Active strategy(σ), which implies that j ≠ k.

Assume for a contradiction that j > k. In this case, R_{k} appears before R_{j} in our priority list, so R_{k} does not require attention at α. (Otherwise, the strategy corresponding to α would be R_{k}^{α}.) So either R_{k} is satisfied in α or there is a strategy R_{k}^{τ} in α that is not injured in α. The first case cannot hold, since if R_{k} were satisfied in α then it would also be satisfied in β and hence the strategy corresponding to β would not be R_{k}^{β}. So the second case holds. Since R_{k} requires attention at β, R_{k}^{τ} is injured in β. But this means that R_{j}^{α} is injured in β, which implies that R_{j}^{α} is injured in σ, contradicting the hypothesis that R_{j}^{α} ∈ Active strategy(σ). This establishes the second part of the lemma.

The construction. As mentioned earlier, we assign infinite disjoint uniformly computable sets P_{σ} in the intersection of the odd numbers with ω^{[⩾2N]} to each σ ∈ T.

The construction proceeds in stages. At each stage s > 0, a finite path σ[s] will be defined and the strategies in σ[s] will act. For a given node τ, if σ[s] <_{L} τ then all actions taken by X^{τ}, the strategy corresponding to τ, during previous stages are canceled. We say that X^{τ} has been initialized. In particular, any variables X^{τ} may have defined (such as m_{n,α}^{τ} or move_{τ}) have their values canceled; if later redefined, these variables will be assigned fresh large numbers. If X^{τ} is an N-strategy, this initialization process includes canceling all attacks on X^{τ} currently in effect.

On the other hand, if τ <_{L} σ[s] then any action taken by X^{τ} during previous stages remains intact, and any uncanceled restraint imposed by it is respected during stage s. In particular, any number through which an N-strategy in σ[s] launches an attack during stage s must be greater than any such restraint. Thus, we modify clause (c) of the requirements for a strategy N_{i,k,l,e}^{σ} to launch an attack through x (see page 17). Recall that, in this context, q = min(ζ_{i,k,l}(x, s), ζ̃_{i,k,l}(x, s)).

(c) q is greater than all restraints in σ and all uncanceled restraints previously imposed by strategies X^{τ} with τ <_{L} σ.

At stage 0, let A[0] = B_{i}[0] = C_{i}[0] = D_{i,k,l}[0] = ∅ for i < N and k, l ∈ ω.

During stage s > 0, there are s many substages, beginning with substage 0. Substage m begins with a value for σ = σ[s] ↾ m ∈ T and proceeds as follows.

Let X^{σ} be the strategy that appears as the first coordinate in each of σ’s immediate successors. Play X^{σ} as described in previous sections until it completes its activity with outcome o. Let σ[s](m) = ⟨X^{σ}, o⟩. Cancel the history of the activity of strategies associated with τ such that σ[s] ↾ m + 1 <_{L} τ.

This completes the description of the construction. As usual, we define the true path T P of the construction to be the leftmost path in T visited infinitely often by σ[s]. We will abuse notation and say that a strategy X^{σ} is on T P if σ is on T P.

We now wish to show that T P is infinite. We begin with an auxiliary lemma.

2.25. Lemma. Suppose that σ ∈ T P and all strategies on σ other than the R-strategies enumerate E-computable sets into each A ⊕ B_{l}, l < N. If R_{k}^{α} is on σ and R_{k}^{α} ∉ Active strategy(σ) then the numbers put into A for the purpose of coding the movement of the Γ_{α} markers form a computable set.

Proof. Let R_{k}^{α} on σ be such that R_{k}^{α} ∉ Active strategy(σ). There exist τ ⊂ σ, i, j, e, m, n, r ∈ ω, and k′ ⩽ k such that either ⟨S_{i,e}^{τ}, c, m, n, k′, r⟩ ∈ σ or ⟨O_{i,j,e}^{τ}, c, m, n, k′, r⟩ ∈ σ. Let us assume that ⟨S_{i,e}^{τ}, c, m, n, k′, r⟩ ∈ σ, since the proof in the other case is analogous.

We can assume by induction that the lemma holds of τ, which means that the hypotheses of Lemma 2.8 are satisfied. Thus, for all but finitely many m, either the marker Γ_{α}(m) has no position from some point on or S_{i,e}^{τ} removes it from its position infinitely often.

Let m be the least number such that Γ_{α}(m) does not have a limiting position, and let s be a stage by which all markers Γ_{α}(n), n < m, have reached their limiting positions. For x ∈ ω, let f(x) be the least stage after s such that all markers Γ_{α}(n), n ⩾ m, have moved past x by stage f(x). Clearly, f is computable, and no strategy puts a number into A ↾ x for the purpose of coding the movement of a Γ_{α} marker after stage f(x).

2.26. Lemma. T P is infinite.

Proof. Let σ ∈ T P and assume by induction that all strategies on σ other than the R-strategies enumerate E-computable sets into each A ⊕ B_{l}, l < N. Let X^{σ} be the strategy corresponding to σ.

By the definition of T P, X^{σ} acts infinitely often and can restrain all numbers from entering any A ⊕ B_{l}, l < N, except for the finite set of numbers enumerated by strategies to the left of σ, numbers put in by strategies on σ, and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with an R-strategy in σ. Thus, by Lemma 2.25, X^{σ} can restrain all numbers from entering any A ⊕ B_{l}, l < N, except for the enumeration of finitely many fixed E-computable sets and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ). So we conclude the following.

1. If X^{σ} = R_{e}^{σ} then of course σ has a leftmost successor visited infinitely often.

2. If X^{σ} = S_{i,e}^{σ} then the hypotheses of Lemma 2.8 are satisfied, and thus, by that lemma, σ has a leftmost successor visited infinitely often and S_{i,e}^{σ} enumerates a computable set into each A ⊕ B_{l}, l < N.

3. If X^{σ} = O_{i,j,e}^{σ} then the hypotheses of Lemma 2.13 are satisfied, and thus, by that lemma, σ has a leftmost successor visited infinitely often and O_{i,j,e}^{σ} enumerates a computable set into each A ⊕ B_{l}, l < N.

4. If X^{σ} = N_{i,k,l,e}^{σ} then the hypotheses of Lemmas 2.11 and 2.12 are satisfied. Thus, by Lemma 2.11, σ has a leftmost successor visited infinitely often, while by Lemma 2.12, N_{i,k,l,e}^{σ} enumerates an E-computable set into each A ⊕ B_{l}, l < N.

5. Suppose that X^{σ} = M_{k}^{σ}. The above shows that the first three hypotheses of Lemma 2.18 are satisfied. That the fourth hypothesis is also satisfied follows from the definition of T P. Thus, by Corollary 2.19, M_{k}^{σ}’s action is finite, which immediately gives us that σ has a leftmost successor visited infinitely often and M_{k}^{σ} enumerates a computable set into each A⊕B_{l}, l < N.

Thus, by induction, T P is infinite.

Examining the various direct codings in our construction, we get the following fact.

2.27. Proposition. (2.0), (2.5), and (2.7) are satisfied.

Say that a requirement is satisfied in T P if it is satisfied in some σ ∈ T P and that a strategy is injured in T P if it is injured in some σ ∈ T P.

2.28. Lemma. For each requirement X there are only finitely many σ ∈ T P at which X requires attention. Let e, k, l ∈ ω, i, j < N.

1. Either R_{e} is satisfied in T P or there exists an R_{e}^{σ} on T P that is not injured in T P.

2. There exists a σ ∈ T P such that N_{i,k,l,e}^{σ} is not injured in T P.

3. Both S_{i,e} and O_{i,j,e} are satisfied in T P.

4. There exists exactly one σ such that M_{k}^{σ} is on T P.

Proof. Let X be a requirement in our priority list and assume by induction that, for each requirement Y of stronger priority, there are only finitely many σ ∈ T P at which Y requires attention. We have three cases.

1. X = R_{e} and R_{e} is not satisfied in T P or X = N_{i,k,l,e}. If X^{α} is on T P and is injured in β ∈ T P then there exists a j ∈ Active index(β) such that R_{j} has stronger priority than X and is satisfied in β. Now for all τ ⊃ β, j ∉ Active index(τ). Thus there can only be finitely many α such that X^{α} is on T P and is injured in T P. Let σ be the shortest string on T P that is longer than all such α and such that no requirement of stronger priority than X requires attention at σ. (Such a σ exists by the induction hypothesis.) Then the strategy corresponding to σ is X^{σ} and this strategy is not injured in T P.

2. X = S_{i,e} or X = O_{i,j,e}. If ⟨X^{α}, c, m, n, j, r⟩ is on T P then for some j ∈ ω and β ⊂ α, R_{j}^{β} ∈ Active strategy(α). It must be the case that R_{j} has stronger priority than S_{i,e}, since if S_{i,e} had stronger priority than R_{j} then the strategy corresponding to β would be S_{i,e}^{β}. Now for all τ ⊃ α, j ∉ Active index(τ). So there can only be finitely many α such that for some m, n, j, r ∈ ω, ⟨S_{i,e}^{α}, c, m, n, j, r⟩ is on T P. Let σ be the shortest string on T P that is longer than all such α and such that no requirement of stronger priority than S_{i,e} requires attention at σ. Then for some n, r ∈ ω, ⟨S_{i,e}^{σ}, d, n, r⟩ is on T P, and thus S_{i,e} is satisfied in T P.

3. X = M_{k}. Let σ be the shortest string on T P such that no requirement of stronger priority than M_{k} requires attention at σ. Then the strategy corresponding to σ is M_{k}^{σ} and M_{k} does not require attention at any τ ⊃ σ.

In any case, there are only finitely many σ ∈ T P at which X requires attention.

2.29. Proposition. For each i < N and e ∈ ω, S_{i,e} is satisfied.

Proof. By Lemma 2.28, there exist σ, n, and r such that ⟨S_{i,e}^{σ}, d, n, r⟩ is on T P. By Lemma 2.8, S_{i,e}^{σ} succeeds in satisfying S_{i,e}.

A similar argument establishes the following proposition.

2.30. Proposition. For each i, j < N and e ∈ ω, if i ⩽̸_{0} j then O_{i,j,e} is satisfied.

2.31. Proposition. For each e ∈ ω, R_{e} is satisfied.

Proof. If there exists either ⟨S_{i,e′}^{τ}, c, m, n, e, r⟩ or ⟨O_{i,j,e′}^{τ}, c, m, n, e, r⟩ on T P then, by Lemmas 2.8 and 2.13, we are done. Otherwise, by Lemma 2.28, there exists an R_{e}^{σ} on T P that is not injured in T P.

In this case, by Lemmas 2.8 and 2.13, each S or O-strategy on T P cancels the position of any particular Γ_{σ}-marker only finitely often. The same is true of each M-strategy on T P, since by Lemma 2.18 each such strategy eventually preserves a permanent configuration, and thus has finite action. Strategies to the left of T P act only finitely often, while those to the right of T P are initialized infinitely often, and thus each S, O, or M-strategy not on T P also cancels the position of any particular Γ_{σ}-marker only finitely often. N-strategies and R-strategies do not cancel the position of Γ_{σ} markers at all, except possibly while running a recovery process. Finally, no strategy X^{τ} can cancel the position of a marker Γ_{σ}(n) if n is less than the least τ-stage, except while running a recovery process. Thus, the rules for the movement of the Γ_{σ}-markers are respected. So Lemma 2.1 applies and R_{e} is satisfied.

By Lemma 2.22, any M_{k}^{σ} on T P will eventually preserve a correct σ-configuration. The following lemma is the last element we need in order to show that (2.8) holds. It is not necessarily true that if M_{k}^{σ} preserves an F and E-correct configuration then the construction never again moves to the left of σ. For this to hold, we need the configuration to be correct.

2.32. Lemma. Suppose that M_{k}^{σ} preserves a correct σ-configuration v larger than k at a σ-stage s. Then no number enters A ↾ v or any B_{p} ↾ v, p < N, after stage s.

Proof. By Lemma 2.17, it is enough to show that for all t > s, σ[t] ≮_{L} σ. We proceed by double induction on stages t > s and, during a stage t, along σ. That is, given t > s and α ⊆ σ, we assume that

1. for all stages u such that s < u < t, σ[u] ≮_{L} σ and

2. for all β ⊂ α, σ[t] ≮_{L} β,

and show that σ[t] ≮_{L} α.

Notice that, by the proof of Lemma 2.17, the inductive hypothesis implies that no number has entered A ↾ v or any B_{p} ↾ v or C_{p} ↾ v, p < N, since the end of M_{k}^{σ}’s stage s action.

Let β ∈ T, X^{β}, and o be such that α = β^{⌢}⟨X^{β}, o⟩. If β <_{L} σ[t] then we are done, so assume that β ⊆ σ[t].

If X^{β} = R_{e}^{β} then α is the only immediate successor of β, so there is nothing to show.

If X^{β} = M_{k′}^{β} then, by induction, M_{k′}^{β} is still preserving the β-configuration it was preserving at stage s. Thus its outcome at stage t is o.

If X^{β} = N_{i,j,l,e}^{β} then there are two possibilities. If o = 0 then we are done. Otherwise, the restraint o imposed by N_{i,j,l,e}^{β} at stage s has not been violated, so that N_{i,j,l,e}^{β}’s outcome at stage t must be equal to o.

The two remaining possibilities are very similar. We do the case X^{β} = S_{i,e}^{β}. In this case o has one of the forms ⟨d, n, r⟩ or ⟨c, m, n, l, r⟩.

If u < w and r(n − 1, u) and r(n − 1, w) are both defined then r(n − 1, u) ⩽ r(n − 1, w). Thus if o = ⟨d, n, r⟩ then S_{i,e}^{β}’s outcome at stage t cannot be of the form ⟨d, n, r′⟩, r′ < r, while if o = ⟨c, m, n, l, r⟩ then it cannot be of the form ⟨c, m, n, l, r′⟩, r′ < r.

For all n′ < n, v > φ_{e}(A; n′)[s] ⩾ n′, Φ_{e}(A)[s] ↾ n′ = C_{i}[s] ↾ n′, and Φ_{e}(A; n′)[s] converges. So, for all n′ < n, Φ_{e}(A)[t] ↾ n′ = C_{i}[t] ↾ n′ and Φ_{e}(A; n′)[t] converges. This means that S_{i,e}^{β}’s outcome at stage t cannot be of the form ⟨d, n′, r′⟩, n′ < n.

Now let n′ < n and R_{j}^{τ} ∈ Active strategy(β). Clearly, Φ_{j}(A ⊕ B_{i}; m_{n′,τ}^{β})[s] converges, for all m < m_{n′,τ}^{β}, if Γ_{τ}(m) has a position at stage s which was assigned at stage u then Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A⊕B_{i}; m)[u], and, for all R_{k}^{τ′} ∈ Active strategy(β), if γ_{τ′}(m_{n′,τ′}^{β}, s) is defined then γ_{τ′}(m_{n′,τ′}^{β}, s) > φ_{j}(A ⊕ B_{i}; m_{n′,τ}^{β})[s]. It follows from the definition of r and the fact that v > r that these facts still hold with s replaced by t. This means that S_{i,e}^{β}’s outcome at stage t cannot be of the form ⟨c, m′, n′, l′, r′⟩, n′ < n.

If o = ⟨d, n, r⟩ then we are done.

So assume that o = ⟨c, m, n, l, r⟩. By the monotonicity of the assignment of values to the m_{n,τ}^{β}’s, S_{i,e}^{β}’s outcome at stage t cannot be of the form ⟨c, m′, n, l, r′⟩, m′ < m. We need to show that it also cannot be of either of the forms ⟨d, n, r′⟩ or ⟨c, m′, n, l′, r′⟩, l′ > l.

Since now r > φ_{e}(A; n)[s], Φ_{e}(A)[s] ↾ n = C_{i}[s] ↾ n, and Φ_{e}(A; n)[s] converges, the same argument as before takes care of the first form.

The fact that v > max{φ_{k}(A ⊕ B_{i}; m_{n,τ}^{β})[s] | R_{k}^{τ} ∈ Active strategy(β), k > l} means that no numbers less than this maximum have entered A or B_{i} since the end of stage s. Thus each computation Φ_{k}(A ⊕ B_{i}; m_{n,τ}^{β}), R_{k}^{τ} ∈ Active strategy(β), k > l, has not changed between the end of stage s (when it existed, by Definition 2.21) and stage t. This takes care of the second form.

2.33. Proposition. For each i < N, A ⊕ B_{i} ⩽_{T} F.

Proof. F can tell when M_{k}^{σ} preserves a correct configuration at a σ-stage s. By Lemma 2.22, such s and M_{k}^{σ} exist (take any M_{k}^{σ} on T P), while by Lemma 2.32, for any such s and M_{k}^{σ}, A[s] ↾ k = A ↾ k and B_{i}[s] ↾ k = B_{i} ↾ k.

2.34. Lemma. If N_{i,k,l,e}^{σ} is on T P and is not injured in T P then it satisfies N_{i,k,l,e}.

Proof. Assume for a contradiction that W_{k}, W_{l} ⩽̸_{T} A ⊕ B_{i} and D_{i,k,l} = Φ_{e}(A). Then every attack on N_{i,k,l,e}^{σ} is eventually canceled.

Let x ∈ ω. Since N_{i,k,l,e}^{σ} is not injured in T P, some weaker priority strategy S_{e′,i}^{τ} on T P will eventually find and preserve a correct σ-i-configuration greater than φ_{e}(A; x). Indeed, it follows from the fact that Active strategy(σ) ⊆ Active strategy(α) for all α such that σ ⊆ α ∈ T P that we can take any S_{e′,i}^{τ}, σ ⊂ τ ∈ T P, that succeeds in satisfying S_{e′,i} and such that Φ_{e′}(A) ↾ φ_{e}(A; x)+1 = C_{i} ↾ φ_{e}(A; x) + 1.

Let s_{0} be least stage such that for all s > s_{0}, σ[s] ≮_{L} σ. Let s(x) be the least stage after s_{0} at which a correct σ-i-configuration greater than φ_{e}(A; x) exists and let v(x) be the least such configuration at stage s(x). Notice that A ⊕ B_{i} can compute s(x) and v(x). No attack on N_{i,k,l,e}^{σ} through y ⩽ x can be launched during or after stage s(x), for otherwise this attack would never be canceled.

Since s(x) is total and computable in A ⊕ B_{i},

U = {x ∈ P_{σ} | W_{k}[s(x)] ↾ x ≠ W_{k} ↾ x ∧ W_{l}[s(x)] ↾ x ≠ W_{l} ↾ x}

is infinite and computably enumerable in A ⊕ B_{i}. (This is by two applications of Lemma 2.9.) Let

V = {x ∈ U | x is greater than all restraints in σ and all numbers mentioned at stages t with σ[t] <_{L} σ}.

V is infinite and c.e. in A ⊕ B_{i}. For x ∈ V, define w(x) to be the least σ-stage after s(x) such that

1. min(ζ_{i,k,l}(x, w(x)), ζ̃_{i,k,l}(x, w(x))) ∉ A[w(x)],

2. min(ζ_{i,k,l}(x, w(x)), ζ̃_{i,k,l}(x, w(x))) > v(x),

3. D_{i,k,l}(x)[w(x)]=Φ_{e}(A; x)[w(x)] and the computation Φ_{e}(A; x) has settled down by stage w(x), and

4. all attacks on N_{i,k,l,e}^{σ} launched before stage s(x) have been canceled by the beginning of stage w(x).

(Such a stage exists by the definition of U, which implies that both ζ_{i,k,l}(x) and ζ̃_{i,k,l}(x) move after stage s(x), and the hypothesis that D_{i,k,l} = Φ_{e}(A).)

Clearly, w is an A ⊕ B_{i}-computable partial function. Now notice that 1, 2, and 3 above continue to hold with any t > w(x) substituted in for w(x). Thus, conditions 2(a), 2(b), and 2(d) on page 17, as well as the modified condition 2(c) on page 29, hold for x at all stages greater than or equal to w(x). The fact, mentioned above, that no attack through y ⩽ x can be launched after stage s(x), combined with 4, implies that for all stages t ⩾ w(x), there is no attack on N_{i,k,l,e} through y ⩽ x in effect at stage t, so that condition 2(f) on page 17 also holds.

This implies that if F [t + 1] ↾ x ≠ F [t] ↾ x for some t ⩾ w(x) then, at the first σ-stage after t, conditions 2(a), 2(b), and 2(d)–2(f) on page 17, as well as the modified condition 2(c) on page 29, will hold, so that an attack on N_{i,k,l,e}^{σ} through some y ⩽ x will be launched. Since we know this cannot happen, F [w(x)] ↾ x = F ↾ x.

As V is infinite and c.e. in A ⊕ B_{i} and w(x) is a partial A ⊕ B_{i}-computable function defined for all x ∈ V, this means that F ⩽_{T} A ⊕ B_{i}. Now let j < N be such that j ≠ i. By Proposition 2.33, A ⊕ B_{j} ⩽_{T} F ⩽_{T} A ⊕ B_{i}. However, as shown on page 6, it follows from (2.0), (2.1), and (2.2) (which in turn follow from Propositions 2.27, 2.29, and 2.31, respectively) that deg(A ⊕ B_{i}) and deg(A ⊕ B_{j}) are incomparable. Thus we have a contradiction.

By Lemma 2.28, for all i < N, k, l, e ∈ ω, there exists an N_{i,k,l,e}^{σ} satisfying the hypothesis of the previous lemma. Thus we have the following result.

2.35. Proposition. For all i < N, k, l, e ∈ ω, N_{i,k,l,e} is satisfied.

Propositions 2.10, 2.27, 2.29, 2.30, 2.31, 2.33, and 2.35 imply that conditions (2.0)–(2.8) are satisfied. This completes the proof of Theorem 1.4. ■

3 Proof of Theorem 1.6

In this section we prove the following theorem.

1.6. Theorem. Let ⩽_{0} be a partial ordering on {0, …, N −1} with at least three minimal elements. There are c.e. degrees a, b_{0}, …, b_{N−1}, c satisfying (1.0)–(1.4) and

c = ⋃_{i<N} (⋂_{j≠i} b_{j}) .  (1.5)

The proof of Theorem 1.6 is similar to that of Theorem 1.4, so we describe only the necessary changes. As before, we construct sets A, B_{i}, C_{i}, and D_{i,k,l} (i < N; k, l ∈ ω), of which A, B_{i}, and C_{i} are c.e., satisfying (2.0)–(2.8). To ensure that (1.5) is satisfied, we have additional requirements

R̂_{i,e} : f = Φ_{e}(A ⊕ B_{0}) = ⋯ = Φ_{e}(A ⊕ B_{i−1}) = Φ_{e}(A ⊕ B_{i+1}) = ⋯
⋯ = Φ_{e}(A ⊕ B_{N−1}) total ⇒ f ⩽_{T} A ⊕ C_{i}.

The requirements R̂_{i,e} ensure that

b_{o} ∩ ⋯ ∩ b_{i−1} ∩ b_{i+1} ∩ ⋯ ∩ b_{N−1} = c_{i},

which implies (1.5).

Each strategy R̂_{i,e}^{σ} for satisfying R̂_{i,e} will work very much like R_{e}^{σ} would, but the positions of its markers Γ̂_{σ}(n) will be coded into C_{i} (and hence also into each B_{j}, j ≠ i) instead of into A.

More formally, each strategy R̂_{i,e}^{σ} for satisfying R_{i,e} uses movable markers Γ̂_{σ}(n), n ∈ ω, which take positions in P_{σ}. We denote the position of Γ̂_{σ}(n) at stage s by γ̂_{σ}(n, s). The movement of these markers are subject to the following rules:

1. Suppose that s is a σ-stage and, at the beginning of R̂_{i,e}^{σ}’s stage s action, Φ_{e}(A⊕B_{0})[s] ↾ n+1 = ⋯ = Φ_{e}(A ⊕ B_{i−1})[s] ↾ n + 1 = Φ_{e}(A ⊕ B_{i+1})[s] ↾ n + 1 = ⋯ = Φ_{e}(A ⊕ B_{N−1})[s] ↾ n + 1, Φ_{e}(A ⊕ B_{k}; n)[s] ↓ for all k < N, k ≠ i, and Γ̂_{σ}(n) does not have a position. Then at stage s, Γ̂_{σ}(n) must be assigned a position larger than any number previously mentioned in the construction. Furthermore, this is the only situation in which a Γ̂-marker is assigned a new position.

2. If s is a σ-stage, Γ̂_{σ}(n) has a position γ̂_{σ}(n, s) assigned at stage t and for all k < N, k ≠ i, Φ_{e}(A ⊕ B_{k}; n)[s] ≠ Φ_{e}(A ⊕ B_{k}; n)[t], then at stage s, Γ̂_{σ}(n) must be removed from its position.

3. If Γ̂_{σ}(n) is removed from its position at a stage s then so must all Γ̂_{σ}(m), m > n, and some number less than or equal to γ̂_{σ}(n, s) must enter C_{i} at stage s.

4. Except finitely often, Γ̂_{σ}(n) may not be removed from position γ̂_{σ}(n, s) unless at least one computation Φ_{e}(A ⊕ B_{k}; n), k < N, k ≠ i, has changed since Γ̂_{σ}(n) was assigned position γ̂_{σ}(n, s).

Arguing as in the proof of Lemma 2.1, we have the following lemma.

3.1. Lemma. If there are infinitely many σ-stages and the above rules are obeyed then R̂_{i,e} is satisfied.

The R̂_{i,e}^{σ} recovery process is defined as follows:

Search for an x such that Γ̂_{σ}(x) has position γ̂_{σ}(x, s) assigned at stage t and for all j < N, j ≠ i, Φ_{e}(A ⊕ B_{j}; x)[s] ≠ Φ_{e}(A ⊕ B_{j}; x)[t]. If such an x is found then enumerate γ̂_{σ}(x, s) into C_{i}, and ⟨γ̂_{σ}(x, s), i⟩ into each B_{j}, j ≠ i; cancel the positions of all Γ̂_{σ}(y), y ⩾ x, and repeat the recovery process. Otherwise, end the recovery process.

For a sequence σ of strategies we redefine the σ-R recovery process to consist of iterating the R_{i}^{τ} and R̂_{j,e}^{α} recovery processes for each R_{i}^{τ} and each R̂_{j,e}^{α} in σ until each such process terminates without enumerating any numbers into A or any C_{j}, j < N.

The action of R̂_{i,e}^{σ} at a σ-stage s now consists of running the σ^{⌢}⟨R̂_{i,e}^{σ}⟩-R recovery process and assigning fresh large positions to markers as necessary to obey rule 1, making sure that if j < k then γ̂_{σ}(j, s) < γ̂_{σ}(k, s).

Definition 2.2 must be replaced by the following definition.

3.2. Definition. A number v is a σ-i-configuration at stage s if

1. for all R_{j}^{τ} ∈ Active strategy(σ) and all m, γ_{τ}(m, s) < v ⇒ [φ_{j}(A ⊕ B_{i}; m)[s] < v ∧ Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A ⊕ B_{i}; m)[t], where t is the stage at which Γ_{τ}(m) was assigned position γ_{τ}(m, s)], and

2. for all R̂_{k,j}^{τ} ∈ Active strategy(σ), k ≠ i, and all m, γ̂_{τ}(m, s) < v ⇒ [φ_{j}(A ⊕ B_{i}; m)[s] < v ∧ Φ_{j}(A ⊕ B_{i}; m)[s] = Φ_{j}(A ⊕ B_{i}; m)[t], where t is the stage at which Γ̂_{τ}(m) was assigned position γ̂_{τ}(m, s)].

As before, if v is a σ-i-configuration at stage s then the new convention on uses described on page 22 implies that

1. for all R_{j}^{τ} ∈ Active strategy(σ) and all m, γ_{τ}(m, s) < v ⇒ max min(τ, m, s) < v, and

2. for all R̂_{k,j}^{τ} ∈ Active strategy(σ), k ≠ i, and all m, γ̂_{τ}(m, s) < v ⇒ max min(τ, m, s) < v.

(max min(σ, n, s) has the same meaning for R̂_{i,e}^{σ} as it would for R_{e}^{σ}, namely it is the maximum of the lengths of the shortest computations that have kept R̂_{i,e}^{σ} from moving Γ̂_{σ}(n) during the stages between the one at which Γ̂_{σ}(n) was assigned position γ̂_{σ}(n, s) and s.)

We must also alter the description of the action of S_{i,e}^{σ} to take into account the presence of the R̂-strategies. This includes redefining the meaning of the “change” outcomes of S_{i,e}^{σ} so that an outcome of the form ⟨c, m, n, 2j, r⟩ will now correspond to a change in a computation associated with a strategy R_{j}^{τ}, while an outcome of the form ⟨c, m, n, 2⟨q, j⟩ + 1, r⟩ will correspond to a change in a computation associated with a strategy R̂_{q,j}^{τ}.

This should become clear from the following modified description of the action of the preservation half of S_{i,e}^{σ} at a σ-stage s. (The coding half acts as before.)

Let r(−1, s) = 0. The preservation half of S_{i,e}^{σ} proceeds in cycles, beginning with the cycle for 0. The n^{th} cycle operates as follows:

1. If Φ_{e}(A)[s] ↾ n = C_{i}[s] ↾ n and Φ_{e}(A; n)[s] converges then go to step 2. Otherwise, cancel the value of m_{n′,τ}^{σ} and the position of δ(n′) for each n′ ⩾ n and R_{j}^{τ} ∈ Active strategy(σ) or R̂_{q,j}^{τ} ∈ Active strategy(σ), q ≠ i; preserve A ↾ r(n − 1, s) and B_{i} ↾ r(n − 1, s) and end stage s activity with outcome ⟨d, n, r(n − 1, s)⟩.

2. Assign fresh large values in P_{σ} to each undefined m_{n,τ}^{σ} such that R_{j}^{τ} ∈ Active strategy(σ) or R̂_{q,j}^{τ} ∈ Active strategy(σ), q ≠ i.

3. Search for the longest τ ⊆ σ, if any, such that either R_{j}^{τ} ∈ Active strategy(σ) or R̂_{p,j}^{τ} ∈ Active strategy(σ), p ≠ i, and at least one of the following holds.

(a) Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s]↑.

(b) For some m < m_{n,τ}^{σ}, Γ_{τ}(m) has a position assigned at some stage t and Φ_{j}(A⊕B_{i}; m)[s] ≠ Φ_{j}(A ⊕ B_{i}; m)[t].

(c) For some R_{k}^{β} ∈ Active strategy(σ), γ_{β}(m_{n,β}^{σ}, s) ⩽ φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s].

(d) For some R̂_{q,k}^{β} ∈ Active strategy(σ), q ≠ i, γ̂_{β}(m_{n,β}^{σ}, s) ⩽ φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s].

If such a τ exists then proceed as follows. Enumerate min{γ_{α}(m_{n,α}^{σ}, s) | R_{k}^{α} ∈ Active strategy(σ) and α ⊇ τ} into A and for q ≠ i, enumerate m = min{γ̂_{α}(m_{n,α}^{σ}, s) | R̂_{q,k}^{α} ∈ Active strategy(σ) and α ⊇ τ} into C_{q} and ⟨m, q⟩ into each B_{p}, p ≠ q. Follow this with the σ-R recovery process. For each R_{k}^{α} ∈ Active strategy(σ), if α ⊇ τ then cancel the position of Γ_{α}(y) for all y ⩾ m_{n,α}^{σ}, otherwise cancel the value of m_{n,α}^{σ}. For each R̂_{q,k}^{α} ∈ Active strategy(σ), q ≠ i, if α ⊇ τ then cancel the position of Γ̂_{α}(y) for all y ⩾ m_{n,α}^{σ}, otherwise cancel the value of m_{n,α}^{σ}. For each x > n, each R_{k}^{α} ∈ Active strategy(σ), and each R̂_{q,k}^{β} ∈ Active strategy(σ), q ≠ i, cancel the value of m_{x,α}^{σ} and m_{x,β}^{σ}. For each x ⩾ n, cancel the position of δ(x). Let r = max(r(n − 1, s), φ_{e}(A; n)[s] + 1). Preserve A ↾ r and B_{i} ↾ r.

If R_{j}^{τ} ∈ Active strategy(σ) then end stage s activity with outcome ⟨c, m_{n,τ}^{σ}, n, 2j, r⟩. If R̂_{p,j}^{τ} ∈ Active strategy(σ) then end stage s activity with outcome ⟨c, m_{n,τ}^{σ}, n, 2⟨p, j⟩ + 1, r⟩.

4. Define

r(n, s) = min({γ_{τ}(m_{n,τ}^{σ}, s) | R_{j}^{τ} ∈ Active strategy(σ)}∪
∪{γ̂_{τ}(m_{n,τ}^{σ}, s) | R̂_{q,j}^{τ} ∈ Active strategy(σ), q ≠ i}).

If this set is empty then define

r(n, s) = max({φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})[s] | R_{j}^{τ} ∈ Active strategy(σ) or
R̂_{q,j}^{τ} ∈ Active strategy(σ), q ≠ i} ∪ {φ_{e}(A; n)[s] + 1} ∪ {r(n, t) | t < s}).

If δ(n) does not have a position then assign its new position δ(n, s) to be a fresh large number in P_{σ}. Begin the (n + 1)st cycle.

The following version of Lemma 2.8 can now be proved in much the same way as before. The key fact to notice is that we do not need to worry about strategies R̂_{i,k}^{τ}, since they do not put numbers into B_{i}, and hence do not threaten σ-i-configurations.

3.3. Lemma. Suppose that S_{i,e}^{σ} acts infinitely often and can restrain all numbers from entering any A ⊕ B_{p}, p < N, except for the enumeration of finitely many fixed E-computable sets and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ). Suppose further that there is a stage after which no δ-marker used by the coding half of S_{i,e}^{σ} can have its position canceled except during S_{i,e}^{σ}’s action. Then one of the following holds.

1. There is an n such that S_{i,e}^{σ} finds permanent σ-i-configurations greater than φ_{e}(A; n′) for all n′ < n and either Φ_{e}(A; n − 1)↓≠ C_{i}(n − 1) or Φ_{e}(A; n)↑.

Let s be a stage by which all of these configurations have stabilized, and let r be their supremum. S_{i,e}^{σ}’s outcome is infinitely often equal to ⟨d, n, r⟩, and it is never of the form ⟨d, n′, r′⟩, n′ < n, ⟨c, m, n′, j, r′⟩, n′ < n, or ⟨d, n, r′⟩, r′ < r, after stage s.

S_{i,e}^{σ} cancels the position of any particular marker only finitely often.

2. There is an n such that Φ_{e}(A) ↾ n = C_{i} ↾ n, Φ_{e}(A; n) ↓, and S_{i,e}^{σ} finds permanent σi-configurations greater than φ_{e}(A; n′) for all n′ < n but no σ-i-configuration greater than φ_{e}(A; n).

There exist j and τ with the following properties.

(a) Either R_{j}^{τ} ∈ Active strategy(σ) or there is a q ≠ i such that R̂_{q,j}^{τ} ∈ Active strategy(σ).

(b) m_{n,τ}^{σ} has a permanent value.

(c) Either Φ_{j}(A ⊕ B_{i}; m_{n,τ}^{σ})↑ or one of the following holds.

i. R_{j}^{τ} ∈ Active strategy(σ) and it is not the case that Φ_{j}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

ii. R̂_{q,j}^{τ} ∈ Active strategy(σ) and it is not the case that Φ_{j}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{q−1}) ↾ m_{n,τ}^{σ} = Φ_{j}(A ⊕ B_{q+1}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{j}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

(d) For each k and α ⊃ τ such that R_{k}^{α} ∈ Active strategy(σ) or R_{q′,k}^{α} ∈ Active strategy(σ), q′ ≠ i, m_{n,α}^{σ} has a permanent value for which Φ_{k}(A ⊕ B_{i}; m_{n,α}^{σ})↓.

Let r be the larger of the supremum of the permanent configurations found by S_{i,e}^{σ} and φ_{e}(A; n)+ 1. Let s be a stage by which all of these configurations have stabilized and so have the computation Φ_{e}(A; n) and each computation Φ_{k}(A ⊕ B_{i}; m_{n,α}^{σ}), R_{k}^{α} ∈ Active strategy(σ) or R̂_{q′,k}^{α} ∈ Active strategy(σ), q′ ≠ i, α ⊃ τ. If R_{j}^{τ} ∈ Active strategy(σ) then S_{i,e}^{σ}’s outcome is infinitely often equal to ⟨c, m_{n,τ}^{σ}, n, 2j, r⟩ and is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, j′, r′⟩, n′ < n, or ⟨c, m′, n, j′, r′⟩, j′ > 2j or (j′ = 2j and m′ < m_{n,τ}^{σ}) or (j′ = 2j, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s. If R̂_{q,j}^{τ} ∈ Active strategy(σ) then S_{i,e}^{σ}’s outcome is infinitely often equal to ⟨c, m_{n,τ}^{σ}, n, 2⟨q, j⟩ + 1, r⟩ and is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, j′, r′⟩, n′ < n, or ⟨c, m′, n, j′, r′⟩, j′ > 2⟨q, j⟩ + 1 or (j′ = 2⟨q, j⟩ + 1 and m′ < m_{n,τ}^{σ}) or (j′ = 2⟨q, j⟩ + 1, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s.

For α ⊂ τ, S_{i,e}^{σ} cancels the position of any Γ_{α}- or Γ̂_{α}-marker only finitely often, while for α ⊇ τ, any Γ_{α}- or Γ̂_{α}-marker whose position is canceled by S_{i,e}^{σ} after stage s has its position canceled by it infinitely often.

In either case, S_{i,e}^{σ} enumerates a computable set into each A ⊕ B_{p}, p < N.

The only modification that we need to make that requires more than essentially notational work is in the description of the O-strategies.

Whereas a computation Φ_{e}(A ⊕ B_{j}) cannot be affected by the action of a strategy R̂_{j,e′}, thus allowing us to disregard such strategies when dealing with S_{j,e}, the same is not true of a computation Φ_{e}(A ⊕ B_{j} ⊕ C). So it does not suffice for O_{i,j,e}^{σ} to find permanent σ-j-configurations greater than each n for which Φ_{e}(A ⊕ B_{j} ⊕ C) ↾ n = B_{i} ↾ n and Φ_{e}(A ⊕ B_{j} ⊕ C; n) converges, since these provide no assurance against the action of a strategy R̂_{j,e′}.

Thus, we need to make use of our assumption that ⩽_{0} has at least three minimal elements to choose, for each i, j < N such that i ⩽̸_{0} j, a number q_{i,j} < N such that j ≠ q_{i,j} and i ⩽̸_{0} q_{i,j}, and make the following definition.

3.4. Definition. A number v is a σ-j-q_{i,j}-configuration at stage s if it is a σ-j-configuration at s and, in addition, for all R̂_{j,k}^{τ} ∈ Active strategy(σ), and all m, γ̂_{τ}(m, s) < v ⇒ [φ_{k}(A ⊕ B_{q_{i,j}}; m)[s] < v ∧ Φ_{k}(A ⊕ B_{q_{i,j}}; m)[s] = Φ_{k}(A ⊕ B_{q_{i,j}}; m)[t], where t is the stage at which Γ̂_{τ}(m) was assigned position γ̂_{τ}(m, s)].

Now O_{i,j,e}^{σ} acts as before, except that it attempts to find permanent σ-j-q_{i,j}-configurations greater than each n for which Φ_{e}(A ⊕ B_{j} ⊕ C) ↾ n = B_{i} ↾ n and Φ_{e}(B_{j} ⊕ A ⊕ C; n) converges. We describe formally the action of the preservation half of O_{i,j,e}^{σ}. (The coding half acts as before.)

Let s be a σ-stage. Let r(−1, s) = 0. The preservation half of O_{i,j,e}^{σ} proceeds in cycles, beginning with the cycle for 0. The n^{th} cycle operates as follows:

1. If Φ_{e}(A ⊕ B_{j} ⊕ C)[s] ↾ n = B_{i}[s] ↾ n and Φ_{e}(A ⊕ B_{j} ⊕ C; n)[s] converges then go to step 2. Otherwise, cancel the value of m_{n′,τ}^{σ} and the position of δ(n′) for n′ ⩾ n and R_{k}^{τ} ∈ Active strategy(σ) or R̂_{q,k}^{τ} ∈ Active strategy(σ); preserve A ↾ r(n − 1, s) and B_{j} ↾ r(n − 1, s) and end stage s activity with outcome ⟨d, n, r(n − 1, s)⟩.

2. Assign fresh large values in P_{σ} to each undefined m_{n,τ}^{σ} such that R_{k}^{τ} ∈ Active strategy(σ) or R̂_{q,k}^{τ} ∈ Active strategy(σ).

3. Search for the longest τ ⊆ σ, if any, such that at least one of the following holds.

(a) R_{k}^{τ} ∈ Active strategy(σ) or R̂_{p,k}^{τ} ∈ Active strategy(σ), p ≠ j, and one of the following holds.

i. Φ_{k}(A ⊕ B_{j}; m_{n,τ}^{σ})[s]↑.

ii. For some m < m_{n,τ}^{σ}, Γ_{τ}(m) has a position assigned at some stage t and Φ_{k}(A ⊕

B_{j}; m)[s] ≠ Φ_{k}(A ⊕ B_{j}; m)[t].

iii. For some R_{l}^{β} ∈ Active strategy(σ), γ_{β}(m_{n,β}^{σ}, s) ⩽ φ_{k}(A ⊕ B_{j}; m_{n,τ}^{σ})[s].

iv. For some R̂_{q,l}^{β} ∈ Active strategy(σ), γ̂_{β}(m_{n,β}^{σ}, s) ⩽ φ_{k}(A ⊕ B_{j}; m_{n,τ}^{σ})[s].

(b) R̂_{j,k}^{τ} ∈ Active strategy(σ) and one of the following holds.

i. Φ_{k}(A ⊕ B_{q_{i,j}}; m_{n,τ}^{σ})[s]↑.

ii. For some m < m_{n,τ}^{σ}, Γ_{τ}(m) has a position assigned at some stage t and Φ_{k}(A ⊕ B_{q_{i,j}}; m)[s] ≠ Φ_{k}(A ⊕ B_{q_{i,j}}; m)[t].

iii. For some R_{l}^{β} ∈ Active strategy(σ), γ_{β}(m_{n,β}^{σ}, s) ⩽ φ_{k}(A ⊕ B_{q_{i,j}}; m_{n,τ}^{σ})[s].

iv. For some R̂_{q,l}^{β} ∈ Active strategy(σ), γ̂_{β}(m_{n,β}^{σ}, s) ⩽ φ_{k}(A ⊕ B_{q_{i,j}}; m_{n,τ}^{σ})[s].

If such a τ exists then proceed as follows. Enumerate min{γ_{α}(m_{n,α}^{σ}, s) | R_{l}^{α} ∈ Active strategy(σ) and α ⊇ τ} into A and for each q enumerate m = min{γ̂_{α}(m_{n,α}^{σ}, s) | R̂_{q,l}^{α} ∈ Active strategy(σ) and α ⊇ τ} into C_{q} and ⟨m, q⟩ into each B_{p}, p ≠ q. Follow this with the σ-R recovery process. For each R_{l}^{α} ∈ Active strategy(σ), if α ⊇ τ then cancel the position of Γ_{α}(y) for all y ⩾ m_{n,α}^{σ}, otherwise cancel the value of m_{n,α}^{σ}. For each R̂_{q,l}^{α} ∈ Active strategy(σ), if α ⊇ τ then cancel the position of Γ̂_{α}(y) for all y ⩾ m_{n,α}^{σ}, otherwise cancel the value of m_{n,α}^{σ}. For each x > n, each R_{l}^{α} ∈ Active strategy(σ), and each R̂_{q,l}^{β} ∈ Active strategy(σ), cancel the value of m_{x,α}^{σ} and m_{x,β}^{σ}. For each x ⩾ n, cancel the position of δ(x). Let r = max(r(n − 1, s), φ_{e}(A ⊕ B_{j} ⊕ C; n)[s] + 1). Preserve A ↾ r and B_{j} ↾ r.

If R_{k}^{τ} ∈ Active strategy(σ) then end stage s activity with outcome ⟨c, m_{n,τ}^{σ}, n, 2k, r⟩. If R̂_{p,k}^{τ} ∈ Active strategy(σ) then end stage s activity with outcome ⟨c, m_{n,τ}^{σ}, n, 2⟨p, k⟩ + 1, r⟩.

4. Define

r(n, s) = min({γ_{τ}(m_{n,τ}^{σ}, s) | R_{k}^{τ} ∈ Active strategy(σ)}∪
∪{γ̂_{τ}(m_{n,τ}^{σ}, s) | R̂_{q,k}^{τ} ∈ Active strategy(σ)}).

If this set is empty then define

r(n, s) = max({φ_{k}(A ⊕ B_{i}; m_{n,τ}^{σ})[s] | R_{k}^{τ} ∈ Active strategy(σ) or

R̂_{q,k}^{τ} ∈ Active strategy(σ), q ≠ j} ∪ {φ_{k}(A ⊕ B_{q_{i,j}}; m_{n,τ}^{σ})[s] | R̂_{j,k}^{τ} ∈ Active strategy(σ)}∪

∪{φ_{e}(A ⊕ B_{j} ⊕ C; n)[s] + 1} ∪ {r(n, t) | t < s}).

If δ(n) does not have a position then assign its new position δ(n, s) to be a fresh large number in P_{σ}. Begin the (n + 1)st cycle.

The fact that the coding half of O_{i,j,e}^{σ} does not put any numbers into A ⊕ B_{j} or A ⊕ B_{q_{i,j}} means that the following version of Lemma 2.13 can be established via essentially the same argument as before.

3.5. Lemma. Suppose that O_{i,j,e}^{σ} acts infinitely often and can restrain all numbers from entering any A⊕B_{p}, p < N, except for the enumeration of finitely many fixed E-computable sets and numbers put in during a recovery process for the purpose of coding the movement of a marker associated with a strategy in Active strategy(σ). Suppose further that there is a stage after which no δ-marker used by the coding half of O_{i,j,e}^{σ} can have its position canceled except during O_{i,j,e}^{σ}’s action. Then one of the following holds.

1. There is an n such that O_{i,j,e}^{σ} finds permanent σ-j-q_{i,j}-configurations greater than φ_{e}(A ⊕ B_{j} ⊕ C; n′) for all n′ < n and either Φ_{e}(A ⊕ B_{j} ⊕ C; n − 1)↓≠ B_{i}(n − 1) or Φ_{e}(A ⊕ B_{j} ⊕ C; n)↑.

Let s be a stage by which all of these configurations have stabilized, and let r be their supremum. O_{i,j,e}^{σ}’s outcome is infinitely often equal to ⟨d, n, r⟩, and it is never of the form ⟨d, n′, r′⟩, n′ < n, ⟨c, m, n′, l, r′⟩, n′ < n, or ⟨d, n, r′⟩, r′ < r, after stage s.

O_{i,j,e}^{σ} cancels the position of any particular marker only finitely often.

2. There is an n such that Φ_{e}(A ⊕ B_{j} ⊕ C) ↾ n = B_{i} ↾ n, Φ_{e}(A ⊕ B_{j} ⊕ C; n) ↓, and O_{i,j,e}^{σ} finds permanent σ-j-q_{i,j}-configurations greater than φ_{e}(A ⊕ B_{j} ⊕ C; n′) for all n′ < n but no σ-j-q_{i,j}-configuration greater than φ_{e}(A ⊕ B_{j} ⊕ C; n).

There exist l and τ satisfying the following conditions.

(a) One of the following holds.

i. R_{l}^{τ} ∈ Active strategy(σ), m_{n,τ}^{σ} has a permanent value, and either Φ_{l}(A ⊕ B_{j}; m_{n,τ}^{σ}) ↑ or it is not the case that Φ_{l}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{l}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

ii. There exists a p ≠ j such that R̂_{p,l}^{τ} ∈ Active strategy(σ), m_{n,τ}^{σ} has a permanent value, and either Φ_{l}(A ⊕ B_{j}; m_{n,τ}^{σ}) ↑ or it is not the case that Φ_{l}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{l}(A ⊕ B_{p−1}) ↾ m_{n,τ}^{σ} = Φ_{l}(A ⊕ B_{p+1}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{l}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

iii. R̂_{j,l}^{τ} ∈ Active strategy(σ), m_{n,τ}^{σ} has a permanent value, and either Φ_{l}(A⊕B_{q_{i,j}}; m_{n,τ}^{σ})↑ or it is not the case that Φ_{l}(A ⊕ B_{0}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{l}(A ⊕ B_{j−1}) ↾ m_{n,τ}^{σ} = Φ_{l}(A ⊕ B_{j+1}) ↾ m_{n,τ}^{σ} = ⋯ = Φ_{l}(A ⊕ B_{N−1}) ↾ m_{n,τ}^{σ}.

(b) For each k and α ⊃ τ,

i. R_{k}^{α} ∈ Active strategy(σ) ⇒ m_{n,α}^{σ} has a permanent value for which Φ_{k}(A ⊕ B_{j}; m_{n,α}^{σ})

converges, ii. R_{q′,k}^{α} ∈ Active strategy(σ), q′ ≠ j ⇒ m_{n,α}^{σ} has a permanent value for which Φ_{k}(A ⊕

B_{j}; m_{n,α}^{σ}) converges, and iii. R_{j,k}^{α} ∈ Active strategy(σ) ⇒ m_{n,α}^{σ} has a permanent value for which Φ_{k}(A⊕B_{q_{i,j}}; m_{n,α}^{σ})

converges.

Let r be the larger of the supremum of the permanent configurations found by O_{i,j,e}^{σ} and φ_{e}(A⊕ B_{j}⊕C; n)+1. Let s be a stage by which all of these configurations have stabilized and so have the computation Φ_{e}(A⊕B_{j}⊕C; n) and each computation Φ_{k}(A⊕B_{j}; m_{n,α}^{σ}), R_{k}^{α} ∈ Active strategy(σ) or R̂_{q′,k}^{α} ∈ Active strategy(σ), q′ ≠ j, α ⊃ τ, and each computation Φ_{k}(A ⊕ B_{q_{i,j}}; m_{n,α}^{σ}), R̂_{j,k}^{α} ∈ Active strategy(σ), α ⊃ τ. If R_{l}^{τ} ∈ Active strategy(σ) then O_{i,j,e}^{σ}’s outcome is infinitely often equal to ⟨c, m_{n,τ}^{σ}, n, 2l, r⟩ and is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, l′, r′⟩, n′ < n, or ⟨c, m′, n, l′, r′⟩, l′ > 2l or (l′ = 2l and m′ < m_{n,τ}^{σ}) or (l′ = 2l, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s. If R̂_{p,l}^{τ} ∈ Active strategy(σ) then S_{i,e}^{σ}’s outcome is infinitely often equal to ⟨c, m_{n,τ}^{σ}, n, 2⟨p, l⟩ + 1, r⟩ and is never of the form ⟨d, n′, r′⟩, n′ ⩽ n, ⟨c, m′, n′, l′, r′⟩, n′ < n, or ⟨c, m′, n, l′, r′⟩, l′ > 2⟨p, l⟩ + 1 or (l′ = 2⟨p, l⟩ + 1 and m′ < m_{n,τ}^{σ}) or (l′ = 2⟨p, l⟩ + 1, m′ = m_{n,τ}^{σ}, and r′ < r), after stage s.

For α ⊂ τ, O_{i,j,e}^{σ} cancels the position of any Γ_{α}- or Γ̂_{α}-marker only finitely often, while for α ⊇ τ, any Γ_{α}- or Γ̂_{α}-marker whose position is canceled by O_{i,j,e}^{σ} after stage s has its position canceled by it infinitely often.

In either case, O_{i,j,e}^{σ} enumerates a computable set into each A ⊕ B_{k}, k < N.

Definitions 2.15 and 2.21 must be replaced by the following definitions.

3.6. Definition. A number v is a σ-configuration at stage s if it satisfies the following conditions.

1. For each ⟨R_{e}^{τ}⟩ ∈ σ, γ_{τ}(m, s) < v ⇒ max min(τ, m, s) < v.

2. For each ⟨R̂_{i,e}^{τ}⟩ ∈ σ, γ̂_{τ}(m, s) < v ⇒ max min(τ, m, s) < v.

3. v is greater than all restraints in σ.

4. If ⟨X^{τ}, c, m, n, l, r⟩ ∈ σ, where X is one of S_{i,e} or O_{j,i,e}, R_{k}^{α} ∈ Active strategy(τ), 2k > l, and the computation Φ_{k}(A ⊕ B_{i}; m_{n,α}^{τ}) still exists at the end of X^{τ}’s stage s action, then v > φ_{k}(A ⊕ B_{i}; m_{n,α}^{τ})[s].

5. If ⟨X^{τ}, c, m, n, l, r⟩ ∈ σ, where X is one of S_{i,e} or O_{j,i,e}, R̂_{q,k}^{α} ∈ Active strategy(τ), 2⟨q, k⟩+1 > l, q ≠ i, and the computation Φ_{k}(A⊕B_{i}; m_{n,α}^{τ}) still exists at the end of X^{τ}’s stage s action, then v > φ_{k}(A ⊕ B_{i}; m_{n,α}^{τ})[s]. In addition, if X = O_{j,i,e}, R̂_{i,k}^{α} ∈ Active strategy(τ), 2⟨i, k⟩ + 1 > l, and the computation Φ_{k}(A ⊕ B_{q_{j,i}}; m_{n,α}^{τ}) still exists at the end of X^{τ}’s stage s action, then v > φ_{k}(A ⊕ B_{q_{j,i}}; m_{n,α}^{τ})[s].

3.7. Definition. A σ-configuration v at stage s is said to be correct if it is F and E-correct and satisfies the following conditions. Let X be one of S_{i,e} or O_{j,i,e}. If ⟨X^{β}, c, m, n, l, r⟩ ∈ σ then for all R_{k}^{τ} ∈ Active strategy(β), 2k > l, and all R̂_{q,k}^{τ} ∈ Active strategy(β), 2⟨q, k⟩ + 1 > l, q ≠ i, the computation Φ_{k}(A ⊕ B_{i}; m_{n,τ}^{β}) exists at the end of stage s. In addition, if X = O_{j,i,e} and R̂_{i,k}^{α} ∈ Active strategy(τ), 2⟨i, k⟩ + 1 > l, then the computation Φ_{k}(A ⊕ B_{q_{j,i}}; m_{n,α}^{τ}) still exists at the end of stage s.

As before, M_{k}^{σ} fixes a number move_{σ} in advance. At a σ-stage s, M_{k}^{σ}’s action is as follows.

1. Find the smallest σ-configuration w > k.

2. If there is no R_{e}^{τ} in σ such that γ_{τ}(move_{σ}, s) < w and no R̂_{i,e}^{τ} in σ such that γ̂_{τ}(move_{σ}, s) < v then let v = w and proceed to step 7.

3. Cancel the position of all markers Γ_{α}(n), ⟨R_{e′}^{α}⟩ ∈ σ, n ⩾ move_{σ}, and enumerate the least of their positions into A.

4. For each i′ < N, cancel the position of all markers Γ̂_{α}(n), ⟨R̂_{i′,e′}^{α}⟩ ∈ σ, n ⩾ move_{σ}, enumerate the least of their positions, m, into C_{i′}, and enumerate ⟨m, i′⟩ into each B_{p}, p ≠ i′.

5. Run the σ-R recovery process.

6. Find the smallest σ-configuration v > k.

7. Impose a restraint equal to v on A ⊕ B_{p} and C_{p}, p < N and end stage s activity with outcome v.

It is now straightforward to modify our previous proofs to establish Lemma 2.18, and hence Corollaries 2.19 and 2.20, as well as Lemmas 2.17, and 2.22.

We add the requirements R̂_{i,e} to our priority list L in such a way that R̂_{i,e} is listed after R_{⟨i,e⟩} but before R_{⟨i,e⟩+1}. If σ ∈ T then we make the following definitions.

1. R̂_{q,e} is satisfied in σ if there are τ ⊆ σ, i, j, e′, m, n, and r such that ⟨S_{i,e′}^{τ}, c, m, n, 2⟨q, e⟩ + 1, r⟩ ∈ σ or ⟨O_{i,j,e′}^{τ}, c, m, n, 2⟨q, e⟩ + 1, r⟩ ∈ σ.

2. R̂_{q,e}^{τ} is injured in σ if ⟨R̂_{q,e}^{τ}⟩ ∈ σ and there are α, j ⩽ 2⟨q, e⟩, i, e′, k, m, n, and r such that τ ⊂ α ⊆ σ and either ⟨S_{i,e′}^{α}, c, m, n, j, r⟩ ∈ σ or ⟨O_{i,k,e′}^{α}, c, m, n, j, r⟩ ∈ σ.

We also redefine some of the notions from the previous section as follows.

1. R_{e} is satisfied in σ if there are τ ⊆ σ, i, j, e′, m, n, and r such that ⟨S_{i,e′}^{τ}, c, m, n, 2e, r⟩ ∈ σ or ⟨O_{i,j,e′}^{τ}, c, m, n, 2e, r⟩ ∈ σ.

2. R_{e}^{τ} is injured in σ if ⟨R_{e}^{τ}⟩ ∈ σ and there are α, j < 2e, i, e′, k, m, n, and r such that τ ⊂ α ⊆ σ and either ⟨S_{i,e′}^{α}, c, m, n, j, r⟩ ∈ σ or ⟨O_{i,k,e′}^{α}, c, m, n, j, r⟩ ∈ σ.

3. N_{i,k,l,e}^{τ} is injured in σ if there is an r such that ⟨N_{i,k,l,e}^{τ}, r⟩ ∈ σ and there are τ ⊂ α ⊆ σ, j, i′, e′, k′, m, n, and r′ such that either

(a) R_{j} has stronger priority than N_{i,k,l,e} and either ⟨S_{i′,e′}^{α}, c, m, n, 2j, r′⟩ ∈ σ or ⟨O_{i′,k′,e′}^{α}, c, m, n,

2j, r′⟩ ∈ σ, or

(b) R̂_{q,j} has stronger priority than N_{i,k,l,e} and either ⟨S_{i′,e′}^{α}, c, m, n, 2⟨q, j⟩ + 1, r′⟩ ∈ σ or

⟨O_{i′,k′,e′}^{α}, c, m, n, 2⟨q, j⟩ + 1, r′⟩ ∈ σ.

R̂_{i,e} requires attention at σ if it is not satisfied in σ and every strategy R̂_{i,e}^{τ} in σ is injured in σ. If R̂_{i,e} is the first strategy in L that requires attention at σ then the only immediate successor

of σ is σ^{⌢}⟨R̂_{i,e}^{σ}⟩.

We redefine

1. Active index(σ) = {2e | some R_{e}^{τ} appears in σ and R_{e} is not satisfied in σ} ∪ ∪ {2⟨i, e⟩ + 1 | some R̂_{i,e}^{τ} appears in σ and R̂_{i,e} is not satisfied in σ};

2. Active strategy(σ) = {R_{e}^{τ} | τ ⊂ σ, 2e ∈ Active index(σ), and R_{e}^{τ} is not injured in σ} ∪ ∪ {R̂_{i,e}^{τ} | τ ⊂ σ, 2⟨i, e⟩ + 1 ∈ Active index(σ), and R̂_{i,e}^{τ} is not injured in σ}.

We can now prove Lemmas 2.26 and 2.32 and Proposition 2.33 in much the same way as before. By Lemma 3.3, Proposition 2.29 still holds, while by Lemma 3.5, the same is true of Proposition

2.30.

Propositions 2.10, 2.27, 2.31, and 2.35 still hold, by essentially the same arguments as before. Finally, arguing as in the proof of Proposition 2.31, we have the following result.

3.8. Proposition. For each i < N and each e ∈ ω, R̂_{i,e} is satisfied.

This completes the proof of Theorem 1.6. ■

4 Fragments of the theory

In this final section we address the question of which fragments of the theory of the c.e. degrees in a given interval are undecidable. Let Σ_{n} (Π_{n}) be the set of sentences in prenex normal form where the block of quantifiers starts with an existential (universal) quantifier and contains at most n − 1 alternations of quantifiers. For a structure S over a language L, the Π_{n}-theory of S is defined by

Π_{n}-Th(S) = {θ ∈ Π_{n} ∩ L | S ⊨ θ}.

We will show that the results of Section 1 imply that for any c.e. degrees e < f, the Π_{5}-theory of ⟨[e, f], ⩽⟩ over the language L(⩽) of partial orderings is undecidable. For this we need the following result. 4.1. Proposition. (Ambos-Spies and Shore [2]) The set of all Σ_{2} sentences that are true in every finite partial ordering is strongly undecidable.

Call a formula δ_{x_{0},...,x_{k},y} in the language L(⩽) a coding formula for a partial ordering S = ⟨S, ⩽_{S}⟩ if, for any finite partial ordering P = ⟨P, ⩽_{P} ⟩, there are elements a_{0}, …, a_{k} of S such that the partial ordering

⟨{b ∈ S | S ⊨ δ_{x_{0},...,x_{k},y}[a_{0}, …, a_{k}, b]}, ⩽_{S}⟩

is isomorphic to P. 4.2. Lemma. (Ambos-Spies and Shore [2]) Let S = ⟨S, ⩽_{S}⟩ be a partial ordering and let δ be a Σ_{m} coding formula for S. Then Π_{m+2}-Th(S) is undecidable. 4.3. Theorem. For any c.e. degrees e < f, the Π_{5}-theory of ⟨[e, f], ⩽⟩ is undecidable. Proof. By Lemma 4.2, it suffices to show that there is a Σ_{3} coding formula δ for ⟨[e, f], ⩽⟩. Now, by Theorem 1.4, the formula δ with free variables x_{0}, x_{1}, and y expressing that there is a maximalx_{0}-cappable degree z such that y is the join of x_{1} and z is a coding formula for ⟨[e, f], ⩽⟩. Formally, δ can be defined by

δ ≡ ∃z([x_{0} ⩽ z ∧ ∃v(x_{0} < v ∧ ∀w(w ⩽ v, z → w ⩽ x_{0}))] ∧

∧∀u([x_{0} ⩽ u ∧ ∃v(x_{0} < v ∧ ∀w(w ⩽ v, u → w ⩽ x_{0}))] → ¬(z < u)) ∧

∧[x_{1}, z ⩽ y ∧ ∀s(x_{1}, z ⩽ s → y ⩽ s)])

which, as one can easily check, is equivalent to a Σ_{3} formula. ■

We note that, for the structure R as a whole, Lempp, Nies, and Slaman [7] have shown that the Π_{3}-theory is undecidable by using a considerably more delicate coding procedure and various computability-theoretic constructions that do not seem available in arbitrary intervals.

References

[1] K. Ambos-Spies and R.I. Soare, The recursively enumerable degrees have infinitely many onetypes, Ann. Pure Appl. Logic 44 (1989) 1–23.

[2] K. Ambos-Spies and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Ann. Pure Appl. Logic 63 (1993) 3–37.

[3] Y. Ershov and M.A. Taitslin, The undecidability of certain theories, Algebra i Logika 2 (1963) 37–41 (in Russian).

[4] P.A. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983) 113–130.

[5] L. Harrington and S. Shelah, The undecidability of the recursively enumerable degrees (research announcement), Bull. Amer. Math. Soc. (N.S.) 6 (1982) 79–80.

[6] A.H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966) 537–569.

[7] S. Lempp, A. Nies, and T.A. Slaman, The Π_{3}-theory of the computably enumerable Turing degrees is undecidable, Trans. Amer. Math. Soc. 350 (1998) 2719–2736.

[8] M. Lerman, R.A. Shore, and R.I. Soare, The elementary theory of the recursively enumerable degrees is not ℵ_{0}-categorical, Adv. in Math. 53 (1984) 301–320.

[9] A. Nies, R.A. Shore, and T.A. Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77 (1998) 241–291.

[10] G.E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. 80(2) (1964) 300–312.

[11] G.E. Sacks, Degrees of Unsolvability, revised edition, Ann. of Math. Studies 55 (Princeton Univ. Press, Princeton, NJ, 1966).

[12] J.R. Shoenfield, Degrees of Unsolvability (North-Holland, Amsterdam, 1971).

[13] T.A. Slaman, The density of infima in the recursively enumerable degrees, Ann. Pure Appl. Logic 52 (1991) 155–179.

[14] R.I. Soare, Recursively Enumerable Sets and Degrees (Springer, Berlin, 1987).