DEGREE THEORETIC DEFINITIONS OF THE

LOW_{2} RECURSIVELY ENUMERABLE SETS

Rod Downey Mathematics Department Victoria University of Wellington P.O. Box 600 Wellington, New Zealand

Richard A. Shore Mathematics Department White Hall Cornell University Ithaca, N.Y. 14853 U.S.A.

1. Introduction.

The primary relation studied in recursion theory is that of relative complexity: A set or function A (of natural numbers) is reducible to one B if, given access to information about B, we can compute A. The primary reducibility is that of Turing, A ≤_{T} B, where arbitrary (Turing) machines, φ_{e}, can be used; access to information about (the oracle) B is unlimited and the lengths of computations are potentially unbounded. Many other interesting reducibilities result from restricitng one or more of these facets of the procedure. Thus, for example, the strongest notion considered is one–one reducibility on sets: A ≤_{1} B iff there is a one–one recursive (= effective) function f such that x ∈ A ⇔ f(x) ∈ B. Many–one (≤_{m}) reducibility simply allows f to be many–one. Other intermediate reducibilities include truth– table (≤_{tt}) and weak truth–table (≤_{wtt}). The latter imposes a recursive bound f(x) on the information about B that can be used to compute A(x). The former also bounds the length of computations by requiring that the computation of A(x) from B halt in at most f(x) many steps.

Each such reducibility r defines a notion of degree, deg_{r}(A) = {B : A ≤_{r} B ∧ B ≤_{r} A}, and a corresponding structure D_{r} of the r–degrees ordered by r– reducibility. (We typically denote the degree of A by a.) A major theme in recursion theory has been the investigation of the relation between a set’s place in these orderings (the algebraic properties of its degree) and other algorithmic, set–theoretic or

Typeset by AMS-TEX

Research partially supported by the NSF via Grants DMS–8912797, DMS–9204308; a U.S.-New Zealand Binational Cooperative Research Grant including NSF INT 87–22887 and INT 90–20558; by ARO through MSI, Cornell University via contract DAAL–03–C–0027; and IGC of Victoria University, Wellington.

definability type notions of complexity. Important examples of such other notions include rates of growth of functions, the types of approximation procedures which converge to the given function or set and the (syntactic) complexity of defining the set (or function) in arithmetic or analysis. A fundamental role in measuring such apparently external complexity notions is played by the jump operator :

A′ = {⟨x, y⟩ | the x^{th} Turing machine running on input y

with access to information about the oracle A halts}.

We denote the n^{th} iteration of the jump by A^{(n)} : A^{(0)} = A, A^{(1)} = A′, A^{(n+1)} = A^{(n)′}. This operator relates many notions of complexity. A′ is the complete set which can be enumerated recursively (with A as an oracle), i.e., if B can be so enumerated (B is r. e. in A) then B ≤_{1} A′ and A′ itself is r. e. in A. (Note that B being r. e. in A is the same as B being approximable recursively in A via a scheme which starts giving B(x) = 0 for every x and changes its mind at most once.) A classic theorem of Kleene and Post connects the jump operator to both enumerability and definability. We say A is Σ_{n}(Π_{n}) in B if y ∈ A is definable from B by a formula of arithmetic of the form ∃x_{1}∀x_{2} ⋯ Qx_{n}S(\overrightarrow{x}, y, B) (∀x_{1}∃x_{2} … \overline{Q}x_{n}S(\overrightarrow{x}, y, B) where S has only bounded quantifiers (or equivalently where S is a recursive relation). A is Δ_{n} in B if it is both Σ_{n} and Π_{n} in B.

Theorem. (Kleene and Post)

i) A is Σ_{n+1} in B iff A is r. e. in B^{(n)} iff A ≤_{m} B^{(n+1)} iff A ≤_{1} B^{(n+1)}.

ii) A is Δ_{n+1} in B iff A ≤_{T} B^{(n)}.

(A proof can be found in Soare [1987, IV]. We refer to this text for all unexplained notions and notations.)

There are many important connections between the jump operator and rates of growth properties. Some of them will play a crucial role in this paper.

Clearly the most remarkable result relating the jump operator to the ordering of degrees is Cooper’s recent theorem [1993] that the jump operator is definable, from ordering alone, in D_{T}, the Turing degrees with ≤_{T}. Slaman and Woodin [1996] have used this result to considerably improve our knowledge about definability within, and possible automorphisms of, D_{T}. One of their most remarkable results connects D_{T} with R_{T}, the Turing degrees of the r. e. sets: If R_{T} is rigid (i.e., has no nontrivial automorphisms), then so is D_{T}.

Although much is known about the global structure of the degrees as a whole under many reducibilities (see for example Nerode and Shore [1980 a,b] and Shore [1985] as well as Slaman and Woodin [1996]), almost nothing in this vein is known about the r. e. degrees. We believe that, as in the degrees as a whole, a key problem for the study of the r. e. sets and degrees should be the elucidation of the relation between their degree structure and the jump operator.

The standard approach to this problem is to examine the properties of the jump classes.

(1.1)Definition. A degree a < 0′ is high_{n} iff a^{(n)} = 0^{(n+1)} (its n^{th} jump is as high as possible). The degree is low_{n} iff a^{(n)} = 0^{(n)} (its n^{th} jump is as low as possible). We also use \overline{high}_{n} and \overline{low}_{n} to denote the nonhigh_{n} and nonlow_{n} degrees, respectively. If n = 1, we usually omit the subscript.

There have been many important results connecting the lattice structure E of the r. e. sets and these jump classes. The first was the characterization in Martin [1966] of the high r. e. sets A in terms of rates of growth (domination) properties and as the degrees containing co–atoms of E^{∗}, the lattice E modulo the ideal F of finite sets. The other jump class that has been characterized lattice theoretically is that of the nonlow_{2} r. e. degrees: a is nonlow_{2} iff there is an A ∈ a with no maximal superset (Lachlan [1968a] and Shoenfeld [1976]).

Although important relations have been found between the jump operator and algebraic properties of r. e. degree structures, there have been no characterizations or definability results. In the former category, an important early result is Cooper [1973]: If a is high then there are nonrecursive b, c < a such that b ∧ c = 0. In the latter category, the best results follow from Shore and Slaman [1990] and [1993]: There are definable properties in R_{T} which separate the high r. e. degrees from the low_{2} ones.

The most important result in this paper is that the low_{2} degrees are definable in R_{tt}, the structure of the r. e. truth–table degrees with ≤_{tt}.

Theorem 3.3. (ii) An r. e. set A is low_{2} if and only if its degree has a minimal cover in R_{tt}.

This result was suggested by A. Nies. It is proven by showing, on the one hand, that the nonlow_{2} r. e. truth table degrees are dense (Theorem 2.7 (i)) and, on the other, that every low_{2} r. e. degree has a minimal cover in R_{tt} (Theorem 3.3 (i)). The first result requires adapting techniques for dealing with nonlow_{2} sets in the non r. e. T –degrees to r. e. sets. These techniques exploit the characterization of nonlow_{2} sets (below 0′) in terms of domination properties. We use a full approximation procedure to adapt these techniques to the construction of r. e. sets. We have been able to use our techniques to give unified proofs of most known nonlow_{2} arguments for r. e. sets as well as other new results. For instance, we show that if an r. e. set A has minimal tt–degree then A is low_{2}. This answers an old question about R_{tt} (see Odifreddi [1981], [1989]). In a future paper we will extend these methods to prove some new embedding results in R_{T}, e.g., the basic nonmodular five element lattice 1–3–1 can be embedded in R_{T} below every nonlow_{2} degree. (Note that Downey [1990] shows that, for every r. e. a > 0, there is a nonrecursive r. e. d < a below which 1–3–1 cannot be embedded.)

The second result (on minimal covers) introduces techniques extending those of Shore and Slaman [1990] and [1993]. We also use these techniques to prove that the low_{2} r. e. sets can be defined using Turing reducibility and any one of the stronger reducibilities mentioned above.

Theorem 3.5. i) If c is low_{2} then there exists an incomplete 1–topped r. e. T – degree a ≥ c. (We say that a is r–topped if there is an r. e. A ∈ a such that every r. e. B Turing below A is, in fact, below A with respect to r–reducibility.)

As c being 1–topped implies it is r–topped for r = m, tt and wtt and each of these properties implies that c, if incomplete, is low_{2}, this theorem shows that the incomplete r. e. T –degrees with an r. e. r–topped degree above them are precisely the low_{2} r. e. degrees.

2. Working below a nonlow_{2} degree.

In this section we develop a reasonably general technique for working below a nonlow_{2} r. e. degree. In the global degrees, there is a well known technique to handle this problem. A degree d < 0′ is nonlow_{2} iff for every function h ≤_{T} ∅′, there is a function g recursive in d such that g is not dominated by h. This characterization is used for “\overline{low}_{2} permitting” as follows: Relying on specific properties of the requirements to be met, one defines “in advance” a function h which gives an appropriate “search space” inside of which one should look for witnesses to satisfy some requirements. This function will be recursive in ∅′ due to the specific nature of the relevant requirements. Now if d is nonlow_{2}, there is a strictly increasing function g recursive in d not dominated by h. The idea then is to use g to d–recursively bound searches and hence make the construction an oracle one recursive in d. By the way g and h have been constructed, the fact that g(s) > h(s) infinitely often guarantees that, by a priority argument, we get to meet all the requirements.

To illustrate this procedure consider the following example:

If a ∈ \overline{low}_{2} then ∃b < a such that b is 1–generic (Jockusch–Posner [1978]).

The reader should recall that A is 1–generic if, for all r. e. sets of strings V_{e}, either (∃σ)(σ ∈ V_{e} & σ ⊂ A) or (∃σ ⊂ A)(∀τ ⊇ σ)(τ ∉ V_{e}).

To prove the Jockusch–Posner result we build an ascending sequence of strings σ_{s} with the intention of setting A = ∪σ_{s}. (We systematically confuse a set and its characteristic function.) It clearly suffices to meet the requirements

R_{e} : ∃s[σ_{s} ∈ V_{e} or ∀τ ⊇ σ_{s}(τ ∉ V_{e})]

for those V_{e} which are closed under extensions, i.e., σ ∈ V_{e} & τ ⊇ σ → τ ∈ V_{e}. We begin by defining two functions.

k(τ, e) = \{ \begin{matrix}min\{s | (∃σ)(τ ⊆ σ&σ ∈ V_{e,s})\} if one exists \\ 0 otherwise. \end{matrix}

h(s) = max{k(τ, e) : e ≤ s&|τ| = s}.

.

Now h ≤_{T} ∅′ and hence there is an increasing g recursive in a not dominated by h. So (∃^{∞}s)(h(s) < g(s)). We procede as follows. Let σ_{0} = λ. At stage s + 1 look for the least unsatisfied e ≤ s for which there is a σ such that σ_{s} ⊆ σ, |σ| ≤ g(s) and σ ∈ V_{e,g(s)}. If e exists, choose the smallest such σ and let σ_{s+1} be the least string extending σ_{s} of length s + 1 contained in σ. (Note that we do not set σ_{s+1} = σ here, but only set it to be the initial segment of σ of length s + 1.) Declare e to be satisfied if σ ⊆ σ_{s+1}. If no such e exists, set σ_{s+1} = σ_{s} ∗ 0. Clearly the construction is recursive in a. It is easy to see that as g is bigger than h infinitely often, we will meet each R_{e}. By induction and the choice of g we may suppose σ_{s} meets R_{i} for i < e and g(s) > h(s). If ∀τ ⊇ σ_{s} (τ ∉ V_{e}) or ∃τ ⊆ σ_{s} (τ ∈ V_{e}) we have also met R_{e}. If not, then ∃τ ⊃ σ_{s} (τ ∈ V_{e}) and indeed, by the definition of h, ∃τ ⊇ σ_{s} (τ ∈ V_{e,h(s)}). By our choice of s, g(s) > h(s) and so the next steps of the construction will successively extend σ_{s} until it becomes its least extension in V_{e,g(s)}. □

If we try to modify the ideas above to suit the r. e. degrees we face special problems. The natural idea we pursue is to use the global characterization of \overline{low_{2}} and then approximate the functions g and h via the limit lemma. Now we will be given an r. e. set D of nonlow_{2} degree and a “witness” function h for the satisfaction of some requirements. Again h will be recursive in ∅′. We apply the limit lemma to h so that h(x) = lim_{s} h(x, s) with h(x, s) a recursive approximation to h. Let D = ∪_{s}D_{s} be an r. e. member of the nonlow_{2} r. e. degree d. Again, since D is not low_{2}, there will be a function g recursive in D not dominated by h which we can also approximate via the limit lemma. Since g is recursive in D, there is a reduction Γ(D) = g. The problem is that, as h(x) only equals lim_{s} h(x, s) and g(x) only equals lim_{s} g(x, s), we must be able to “correct” our mistakes. This is a serious problem since the objects we need to construct must not only be recursive in D but also r. e. A crucial theme in our constructions below nonlow_{2} r. e. sets will be that we can correct the mistakes that occur when g(x, s) does not have its final value by dumping elements into the set we are constructing whenever g(x, s) or even D ↾g(x, s) changes (we will tie g(x, s) to the standard approximation of Γ(D)). To facilitate this procedure we require that our recursive approximations h(x, s) and g(x, s) have certain properties. In particular, since we will only be concerned with values where g(x) is bigger than h(x), we can always presume approximations to D, g and h so that the following hold.

Conventions:

(i) g(x, x) > h(x, x),

(ii) If g(x, s + 1) ≠ g(x, s) then ∃z(z ∈ D_{s+1} − D_{s} and z < g(x, s)).

(iii) If g(x, s + 1) ≠ g(x, s) then g(x, s + 1) > h(x, s).

(iv) g(x, s) and h(x, s) are monotonic in both variables.

(v) If g(x, s) ≠ g(x, s + 1) then g(x, s + 1) = s.

(vi) g(x, s + 1) ≠ g(x, s) for at least one s.

We begin with some easy applications of our technique. Downey, Jockusch and Stob [1990] define a strong array S = {F_{x} : x ∈ ω} to be a very strong array (vsa) if, for all x, |F_{x+1}| > |F_{x}| and ∪_{x}{F_{x}} = ω. They call an r. e. set A S–anr (array nonrecursive) if, for all e, there is an x with F_{x}∩W_{e} = A∩F_{x}. Now it turns out that this notion is invariant in the following sense. If S_{1} and S_{2} are vsa’s and a contains an S_{1}–anr set, then a contains an S_{2}–anr set. Thus we can define an anr degree to be one containing an S–anr set for some vsa S. Such sets were introduced to capture the “multiple permitting” character of several arguments, such as Martin and Pour–El [1970] and Jockusch and Soare [1972]. One of their theorems, proven indirectly in Downey et al. [1990], was that the \overline{low}_{2} r. e. degrees are all anr. We give a simple direct proof that illustrates our ideas.

(2.1)Theorem. (Downey et al. [1990]) If a is \overline{low}_{2} and r. e. then a is anr. That is, a contains an anr r. e. set.

Proof Let S = {F_{x} : x ∈ ω} be a vsa. Let D be a nonlow_{2} r. e. set. We build an S–anr r. e. set A with A ≡_{T} D. We need to satisfy each requirement

R_{e} : (∃x)(F_{x} ∩ W_{e} = A ∩ F_{x}).

We devote {F_{⟨e+1,x⟩} : x ∈ ω} to meeting R_{e} and {F_{⟨0,x⟩} : x ∈ ω} to coding. So we automatically put all of F_{⟨0,x⟩} into A_{s} iff x ∈ D_{s}. Hence A _{T} ≥ D. Let

h(x) = (μs)(∀e ≤ x)(F_{⟨e+1,x⟩} ∩ W_{e,s} = F_{⟨e+1,x⟩} ∩ W_{e}).

Then h ≤_{T} ∅′. So, as D is \overline{low}_{2}, there is a function g ≤_{T} D not dominated by h, i.e., (∃^{∞}s)(g(s) > h(s)), with an approximation g(x, s) satisfying our conventions. Now, at stage s, we compute g(x, s) for all x ≤ s. If g(x, s) ≠ g(x, s − 1) we ensure that F_{⟨e+1,x⟩} ∩ W_{e,g(x,s)} = F_{⟨e+1,x⟩} ∩ A_{s} for all e ≤ s by enumerating numbers into A as necessary. As g(x, s) only changes if D changes by (ii), A ≤_{T} D. Finally, note that R_{e} is met. To see this, choose the least x > e such that g(x) > h(x). Now let s be the first stage > x at which g(x, s) = g(x). It follows that F_{⟨e+1,x⟩} ∩ W_{e,h(x,s)} = A ∩ F_{⟨e+1,x⟩} = F_{⟨e+1,x⟩} ∩ W_{e}, and hence R_{e} is met. □

The previous theorem was originally established via an index set argument. The next result is also a corollary of index set theorems (Yates [1969]). We supply a simple direct proof.

(2.2) Theorem. If A is r. e., \overline{low}_{2} and A ≢_{wtt} ∅′ then there exists an r. e. B ≡_{T} A such that B ≰_{wtt} A.

Proof: We are given A and construct B to meet each requirement

R_{e} : Δ_{e}(A) ≠ B,

where Δ_{e} is the e-th wtt reduction with partial recursive use function δ_{e}. We will meet R_{e} by attempting to code K into B^{(e+1)}, the (e + 1)^{st} column of B. Define h(x) to be the least y_{1} > x such that for all j ≤ x and all strings σ of length x, there is a y < y_{1} with K_{y_{1}} ↾y = K ↾y and Δ_{j}(A, ⟨j + 1, y⟩) ≠ Q^{σ}(y), where

(i) Q^{σ}(z) = σ(z) if z < x,

(ii) Q^{σ}(z) = K(z) if x ≤ z < y_{1}, (K is the standard 1–complete set), and (iii) Q^{σ}(z) = 0 otherwise. Note that as A <_{wtt} ∅′, h(x) is defined (as Δ_{j} is a wtt reduction) and recursive

in ∅′. The construction is again simple. We put ⟨0, x⟩ into B iff x ∈ A so that A ≤_{1} B. Now suppose g is not dominated by h and is approximated by g(x, s) as above. At stage s, for each x ≤ s and j ≤ x we set B_{s}(⟨j +1, x⟩) = K_{g(x,s)}(x). Note that this ensures that B ≤_{T} A, since A can compute g(x) and then, to compute if ⟨j + 1, x⟩ ∈ B, we need only compute K_{g(x)}(x).

To see that the construction succeeds for R_{e}, let q > e be such that g(q) exceeds h(q). Compute a stage s = s(q) where g(q, t) = g(q) for all t ≥ s, and with g(q, s) = s − 1. Let σ equal B^{(e+1)} ↾ q. Now as g(q) > h(q), there is a number y with q ≤ y < g(q) such that Δ_{e}(A; ⟨e + 1, y⟩) ≠ Q^{σ}(y). By construction, for all m with q ≤ m < g(q), B_{s}(⟨j+1, m⟩) = K_{n}(m) for some n ≥ g(q). As K_{g(q)}(y) = K(y), we see that B(⟨j + 1, y⟩) = Q^{σ}(y) as required. □

For the above result, the index set argument is perhaps simpler, but the construction used in our proof of (2.2) should be rather instructive.

We now give a new proof of Shoenfield’s theorem. For this result, we feel our proof is rather more perspicacious than the original.

(2.3) Theorem. (Shoenfield [1976]) Let A be r. e. and nonlow_{2}. Then there is an r. e. D ≡_{T} A with no hyperhypersimple superset.

Proof: Let D be the standard deficiency set of A for the enumeration f : D = {s | ∃t > s(f(t) < f(s))}. Of course D ≡_{T} A (see Soare [1987, p.81]). Let D_{t} be the natural enumeration of D: At stage t we enumerate s if f(t) < f(s) and s is not yet in D to get D_{t+1}. For our purposes, the crucial property of this enumeration is that if s is enumerated at t then all elements of the interval (s, t) not yet in D also enter D at t. (If r ∈ (s, t) th

en f(r) > f(s) as s ∉ D_{r+1} and so r ∈ D_{t+1}.) We call this property of an enumeration the dump property.

Now suppose that W is an r. e. coinfinite superset of D. We build a weak array {Q_{e} : e ∈ ω} that meets the following requirements.

R_{e} : |Q_{e} − W | ≥ 1.

Let h(x) = (μs)(s > x & |[x, s] ∩ \overline{W} | ≥ 4x + 3).

Then h ≤_{T} ∅′ as |\overline{W} | = ∞. Take a g ≤_{T} D not dominated by h with our conventional approximation g(x, s). We also assume that W_{s} ⊇ D_{s}.

Construction, stage s + 1: Let γ_{0}^{s} = 0 and γ_{i+1}^{s} = g(γ_{i}^{s}, s) for i ≤ s. For each j ≤ s add elements to Q_{i,s} (to get Q_{i,s+1}) for each i ≤ j in turn as follows: If Q_{i,s} ⊆ W_{s} and there is an x < s in (γ_{j}^{s}; γ_{j+1}^{s}) ∩ \overline{W_{s}} but not in Q_{k,s+1} for k < i or Q_{m,s} for m ≠ i, put the least such x into Q_{i,s}.

Verification Clearly the Q_{i} form a weak array. Let γ_{i} = lim_{s} γ_{i}^{s}. The idea of the construction is, first, that infinitely often the intervals (γ_{i}, γ_{i+1}) contain many elements of \overline{W} by our choice of g and its monotonicity. The second point is that the dump property will wipe out the effect of inappropriate enumerations into Q_{i}.

In particular, to see that R_{e} is met choose x > γ_{e+2} with g(x) > h(x) and let j be such that γ_{j−1} < x ≤ γ_{j}. (Necessarily, e < j ≤ x.) The monotonicity of g and the definition of the γ_{i} now guarantee that γ_{j−1} < x < h(x) < γ_{j+1}. By the definition of h(x) then either |(γ_{j−1}, γ_{j}) ∩ \overline{W} | ≥ 2x + 1 or |(γ_{j}, γ_{j+1}) ∩ \overline{W} | ≥ 2x + 1. The argument is symmetric and we assume |(γ_{j−1}, γ_{j}) ∩ \overline{W} | ≥ 2x + 1. Let s_{j−1}(s_{j}) be the stage at which γ_{j−1}(γ_{j}) reaches its final value. By our conventions, γ_{j−1} = s_{j−1} and γ_{j} = s_{j}. By construction, no numbers > γ_{j−1} = s_{j−1} have been enumerated in any Q_{i} before stage s_{j−1}. By the dump property of our enumeration of D and our convention that γ_{j}^{s} = g(γ_{j−1}, s), γ_{j}^{s} changes (at s > s_{j−1}) only when D ↾γ_{j}^{s} changes. Thus we see that (γ_{j}^{s_{j−1}}, γ_{j}) ⊆ D and so |(γ_{j−1}, γ_{j}^{s_{j−1}}) ∩ \overline{W} | ≥ 2x + 1 ≥ 2j + 1. By our construction, the numbers in (γ_{j−1}, γ_{j}^{s_{j}−1}) can be put into Q_{i} only for i < j and only when Q_{i,s} ⊆ W_{s}. Thus each such Q_{i}, including Q_{e}, must eventually get an element of (γ_{j−1}, γ_{j−1}^{s_{j}−1}) ∩ \overline{W} if not some other element of \overline{W}. □

An open question related to Theorem 2.3 is whether every nonlow_{2} r. e. degree contains an r. e. set with no r–maximal superset (Soare [1987], p.233). Although we cannot prove this, we have found an easy proof that sets without r–maximal supersets exist.

(2.4) Theorem. (Lachlan [1968]) There is a coinfinite r. e. set A with no r– maximal superset.

Proof: The proof is similar in structure to Martin’s proof of the existence of a coinfinite r. e. set with no maximal superset.

We divide ω into boxes as follows. W_{0}–boxes, B_{0,i}, consist of all pairs in order starting from one (i.e. {1, 2}, {3, 4}, …), so that B_{0,i} = {2i + 1, 2i + 2}. W_{n+1}- boxes are defined inductively by B_{n+1,i} = B_{n,2i+1} ∪ B_{n,2i+2}. Thus for each n and m, B_{n,m} has 2^{n+1} elements. B_{2,0}, for example, is {7, 8, ..., 13, 14}. The construction is as follows: For all W_{e} boxes B_{e,i}, when all but one element is in W_{e,s}, put the other element into A_{s+1} − A_{s}.

Note that this means that at most 2^{n+1} − 1 elements of B_{n,0} enter A so that |\overline{A}| = ∞. Finally, suppose A ⊆ W_{e} and W_{e} is r–maximal. By our action, for each W_{e}–box B we have that |B − W_{e}| ≠ 1. If, for almost all W_{e}–boxes we have |B − W_{e}| = 0 then W_{e} =^{∗} ω. Hence, there are infinitely many W_{e}–boxes B_{e,k} with 2 ≤ |B_{e,k} − W_{e}| ≤ 2^{e+1}. Pick the largest j with 2 ≤ j ≤ 2^{e+1} such that there are infinitely many B_{e,k} with |B_{e,k} − W_{e}| = j. Without loss of generality |B_{e,k} − W_{e}| ≤ j for all k.

We define sets Q and R as follows. For each W_{e}-box B_{e,k}, at the stage where |B_{e,k} − W_{e,s}| = j put half of the j elements into Q and the rest of B_{k} into R. So Q ∪ R = ω and Q ∩ R = ∅. By construction, |R − W_{e}| = |Q − W_{e}| = ∞ so W_{e} is not r–maximal. □

Remark. We note that that this construction is compatible with Martin’s (e.g. Soare [1987, Ch. X Exercise 5.5]). We can even ensure that A has no hh–simple superset.

We finish this section with some nice applications of our technique to tt– and wtt–degrees. We begin by solving an old question on the complexity of minimal tt–degrees. (See e.g. Odifreddi [1981, 1989]).

We say a Turing degree a of some type Δ (e.g. r. e. or ω–r. e.) is Δ (w)tt– bottomed if there is an A ∈ Δ of degree a such that A ≤_{(w)tt} B for every B ∈ a which is also in Δ.

(2.5) Theorem. (i) If A is \overline{low}_{2} and r. e. then there is an r. e. B ≡_{T} A such that B ≤_{tt} A but A ≰_{wtt} B.

(ii) In particular the following hold.

(a) No \overline{low}_{2} r. e. degree is r. e. tt− or wtt–bottomed.

(b) No \overline{low}_{2} r. e. degree contains a minimal r. e. tt–degree.

Proof: Call a string τ x–good if τ has at most x zeros. Let A be a given \overline{low}_{2} r. e. set. Let Δ_{e} denote the e–th partial wtt reduction with use δ_{e}.

Let h(x) = max_{j≤x} min{s : ∀σ(|σ| = s and σ is x-good implies

∃y(Δ_{j}(σ; y) ≠ A(y)) through a disagreement witnessed at stage s, that is, Δ_{j,s}(σ; y) ↓≠ A_{s}(y) = A(y), or K discovers that Δ_{j}(B; y) is not total for any B ⊇ σ by stage s}.

First let us explain how K discovers that Δ_{j}(B; y) is not total for any B ⊇ σ. For each y in turn, K first checks to see if the partial recursive use function δ_{j} associated with Δ_{j} is defined at y. If not Δ_{j}(B; y) ↑ for every B. If δ_{j}(y) ↓ < |σ|, then K asks if Δ_{j}(σ; y) ↓. If not Δ_{j}(B; y) ↑ for every B ⊇ σ. If δ_{j}(y) ↓ ≥ |σ|, no determination can be made about σ. Moreover, if, for any set C, Δ_{j}(C; y) is not total, this search procedure applied to all σ “simultaneously” eventually determines for some σ ⊆ C that Δ_{j}(B; y) is not total for any B ⊇ σ.

Now consider the tree of x–good strings σ such that Δ_{j}(σ; y), where defined, gives an initial segment of A and K cannot determine that Δ_{j}(B; y) is not total for every B ⊇ σ. If this tree were infinite then, by König’s lemma, it would have an infinite path defining a set B. By the definition of the tree, B would have at most x many zeros and Δ_{j}(B; y) = A(y) for every y. As this implies that A is recursive, the tree is finite and so h(x) is well defined. As h(x) ≤_{T} K, there is a g ≤_{T} A not dominated by h(x).

We build B via a standard movable marker construction where at stage s we move the x–th marker to a number bigger than g(x, s) + 1 + s when A ↾ g(x, 0) changes at s, dumping the old position and all intervening elements into B. Note that (vi) of the conventions for g(x, s) implies that we always move the x-th marker at least once. Thus it is clear from the construction that the principal function b(x) of \overline{B} dominates g(x) and hence b(x) is not dominated by h. Now A and B have the same T –degree: to compute A(x) from B run the construction till B is correct on the first x many members of its complement. A(x) cannot change again by the definition of B. Moreover, B ≤_{tt} A. To see if x ∈ B, look at stage x + 1 of the construction. If x is not yet in B then x is the position of some marker y. We claim that x ∈ B iff A↾g(y, x+1) ≠ A_{x+1} ↾g(y, x+1). If A↾g(y, x+1) = A_{x+1} ↾g(y, x+1), then by construction and convention (ii), (iv) none of the markers ≤ y ever move again and so x ∉ B. On the other hand, if A↾g(y, x + 1) ≠ A_{x+1} ↾g(y, x + 1) then, by construction, some marker z ≤ y is moved at a stage s > x + 1. It is moved to a number > s > x and so x is put into B.

Finally, we claim that A ≰_{wtt} B. Consider any wtt reduction Δ_{j} with Δ_{j}(B; y) total. We now choose an x > j with b(x) > h(x). As B ↾ b(x) is an x–good string (remember b(x) is the x^{th} element of \overline{B} so |\overline{B} ↾ b(x)| = x − 1) of length ≥ h(x) and Δ_{j}(B; y) is total, Δ_{j}(B ↾b(x); y)↓ ≠ A(y) for some y by the definition of h. □

We note that Andre Nies had previously found the following rather pretty index set proof of (2.5) (ii)(a).

Alternative proof of (2.5) (ii)(a) (A. Nies)

Let A be a given r. e. \overline{low}_{2} set. Suppose A is the (w)tt–bottom of the T –degree of A and S ∈ Σ_{3}^{A}. Then by Yates’ index theorem (see Soare [1987], XII.1.5) there is a recursive function g such that for every x, W_{g(x)} ≤_{T} A and x ∈ S iff W_{g(x)} ≡_{T} A.

Now, as A is the tt–bottom of the Turing degree of A, W_{g(x)} ≡_{T} A is equivalent to A ≤_{(w)tt} W_{g(x)} since W_{g(x)} ≤_{T} A. As the reductions are Σ_{3}, this means S ∈ Σ_{3} and hence A is low_{2}. □

Now (2.5) has several extensions. First we observe that it works for sets A which are ω–r. e. in the sense of Ershov’s difference hierarchy. These are the sets A with approximations A(x) = lim_{s} A_{s}(x) for which there exists a recursive function h such that for all x, |{s : A_{s+1}(x) ≠ A_{s}(x)}| ≤ h(x). They are also the sets A which are tt–reducible to K. The reader should consult e.g. Epstein, Haas, and Kramer [1981] for basic facts about these sets. One simply emulates our proof of (2.5) using such an approximation for A and a standard Δ_{2}^{0} marker construction. That is, we move the marker for x to a number bigger than g(x, s) + 1 + s when A_{s} ↾ g(x, s) ≠ A_{t} ↾ g(x, s) for any t < s. If A_{s} ↾ g(x, s) returns to a previous configuration (say to A_{s_{1}} ↾ g(x, s) with s_{1} < s), we must return the marker for x back to the place it had at stage s_{1}. With this modification, we see

(2.6) Corollary.

(i) If A is any \overline{low}_{2} ω–r. e. set then there exists an ω–r. e. B ≡_{T} A with B ≤_{tt} A yet B ≰_{wtt} A.

(ii) In particular no \overline{low}_{2} ω–r. e. degree is ω–r. e. tt− or wtt–bottomed nor does it contain a minimal ω–r. e. tt–degree.

We conclude with one further extension of (2.5).

(2.7) Theorem.

(i) The \overline{low}_{2} r. e. tt–degrees are dense.

(ii) So too are the \overline{low}_{2} ω–r. e. tt–degrees.

Remark. Other variations are again possible. For instance one can additionally avoid cones. Proof: We only prove (i). The proof of (ii) is translation of that of (i) to the realm of Δ_{2} approximations similar to, but more complicated than, that given for Theorem 2.5 above. Details can be found in Nies and Shore [ta].

Suppose we are given \overline{low}_{2} r. e. sets B <_{tt} A. We will construct C r. e. with B <_{tt} B ⊕ C <_{tt} A. For each potential tt reduction Δ_{e}, we aim to satisfy the requirements

R_{2e} : Δ_{e}(B) ≠ C
R_{2e+1} : Δ_{e}(B ⊕ C) ≠ A.

Following ideas from the proof of the density theorem of Ladner [1975] in the polynomial time degrees, we meet R_{2e} by making C locally copy A and we meet R_{2e+1} by making C locally look like ω. To meet R_{2e} we code A in C^{(q)} for some q. We perform the following process.

Define l(2e, q, s) = max{x : (∀y < x)(Δ_{e,s}(B_{s}; ⟨q, y⟩) = C_{s}(⟨q, y⟩))}. Initially we set C_{x}(⟨q, x⟩) = 1 for each stage x until a stage s_{0} occurs where l(2e, q, s_{0}) > 0. At the first such stage s_{0} we make ⟨q, s_{0}⟩ the coding marker for 0 in C^{(q)}, i.e., ⟨q, s_{0}⟩ ∈ C iff 0 ∈ A. More generally, if we have already defined coding markers ⟨q, s_{0}⟩, …, ⟨q, s_{x−1}⟩ for 0, …, x−1 in C^{(q)} we set C(⟨q, y⟩) = 1 for stages y > s_{x−1} until a stage s_{x} occurs with l(2e, q, s_{x}) > s_{x−1}. At the least such stage s_{x}, we make ⟨q, s_{x}⟩ the coding marker for x in C^{(q)}, i.e., ⟨q, s_{x}⟩ ∈ C iff x ∈ A. Note that this process makes C^{(q)} ≤_{tt} A uniformly in q: To compute C(⟨q, s⟩) run the construction for ⟨q, s⟩+1 many stages. If ⟨q, s⟩ has not been declared a coding marker, ⟨q, s⟩ ∈ C. If it has been made the coding marker for x in C^{(q)} then ⟨q, s⟩ ∈ C iff x ∈ A.

We claim that Δ_{e}(B) ≠ C and, in particular, there is an x such that Δ_{e}(B; ⟨q, x⟩) ≠ C(⟨q, x⟩). If not, l(2e, q, s) → ∞ and so, for each x, there is a marker ⟨q, s_{x}⟩ (which we can find recursively) such that x ∈ A iff ⟨q, s_{x}⟩ ∈ C, i.e., A ≤_{tt} C. As this would imply that A ≤_{tt} B, we have the desired contradiction. Next, note that Δ_{e}(B)^{(q)} ≠ C^{(q)} implies that \overline{lim} l(2e, q, s) < ∞ and so, by construction, C^{(q)} is cofinite. Finally, K can compute an index for C^{(q)} as a cofinite set. (To make the index of the requirement visible, we would label this set C_{2e}^{(q)}.)

Suppose R_{0} is met by applying the above procedure with q = 0 (= q(0, s)). To meet R_{1}, the basic idea is to keep setting C^{(d)} = ω^{(d)} for as many d > 0 as necessary to guarantee that Δ_{0}(B ⊕C) ≠ A. As this procedure threatens to make C recursive (C^{(0)} is co finite), A ≰_{tt} B and Δ_{0} is a possible tt–reduction, the procedure must eventually succeed. Moreover, K can find a number d such that setting C^{(0)} = C_{0}^{(0)} and C^{(i)} = ω^{(i)} for 0 < i < d guarantees that Δ_{0}(B ⊕ C) ≠ A. This d is the value of h(0) for the function h ≤_{T} K for which we will apply the nonlow_{2}–ness of A as in the previous arguments.

We expect to define a g ≤_{T} A not dominated by h and a recursive approximation g(x, s) as above. The plan is to make C^{(y)} = ω^{(y)} for all 1 ≤ y ≤ g(0) by putting all elements of ω^{(y)}, 1 ≤ y < s into C when A ↾ g(0, s) changes. Indeed, we set C^{(y)} = ω^{(y)} for every y for which we have made any commitments for C^{(y)}. This guarantees that C^{(y)} = ω^{(y)} for all y, 1 ≤ y ≤ g(0) by our conventions on g(x, s). Thus if g(0) > h(0), we meet R_{1}.

In this environment we meet R_{2} by following our strategy with the appropriate q. We let q(2, s) be the first column not yet filled in by our actions for R_{1}. We follow our strategy for the q at stage s. If t is the last stage at which A ↾ g(0, s) changes then q(2, t) = lim_{s} q(2, s) = q(2). We thus satisfy R_{2} by our construction of C^{(q(2))}.

Now we again turn to the odd requirements. First, note that we may not yet have met R_{1} (if g(0) < h(0)). We must define h(1) so large that filling in C^{(y)} for q(2) < y ≤ h(1) would satisfy both R_{1} and R_{3}. Note that we cannot, however, use the recursion theorem as h must be given directly recursively in ∅′. Our first task is to see how far we would have needed to make C^{(y)} = ω^{(y)} to meet both R_{1} and R_{3} (given that C^{(0)} = C_{0}^{(0)}). Suppose d_{0} suffices. If q(2) ≥ d_{0}, our action for R_{1} would actually meet both R_{1} and R_{3}. We next consider the possibility that some y < d_{0} is q(2), the column on which we meet R_{2}. To do this, we compute (indices for) C_{2}^{(y)} for 1 ≤ y ≤ d_{0} and then, for each y, we find d_{1,y} such that meeting R_{0} at C^{(0)} and R_{2} at C^{(y)} and all other columns being ω, making C^{(0)} = C_{0}^{(0)}, C^{(z)} = ω^{(z)} for 1 ≤ z < y, C^{(y)} = C_{2}^{(y)} and C^{(z)} = ω^{(z)} for y < z ≤ d_{1,y} meets both R_{1} and R_{3}. We let h(1) = d_{1} = max{d_{1,y} | y ≤ d_{0}}.

Our action for R_{3} is much like that for R_{1}. When A ↾ g(1, s) changes, we make C^{(y)} = ω^{(y)} for all y > q(2, s) for which we have ever made any commitments. Once again we argue that if g(1) > h(1) we satisfy both R_{1} and R_{3}: Either q(2) ≥ d_{0}, in which case we won already, or q(2) ≤ d_{0}. In this case, we also know by our definition of h that C_{0}^{(0)} ∪ C_{2}^{(q(2))} ∪ ω^{(k)} for k ≤ h(1), k ≠ q(0), q(2) forces a win for both R_{1} and R_{3}. Moreover, if g(1) > h(1) but g(0) ≤ q(2) < d_{0}, then it is clear that our construction produces this result for C^{(k)}, k ≤ d_{0}.

Of course, we satisfy R_{4} at the first column q(4, s) not used by our actions for R_{3}. The general plan for defining h(e) and satisfying R_{2e+1} (indeed R_{2i+1} for i ≤ e) is as for e = 1. We first compute d_{0} large enough to meet all of R_{1}, …, R_{2e+1}. We then compute d_{1} large enough to win all of them on the assumption that exactly one y < d_{0} is used for coding (i.e., is C_{0}^{(y)}). We then compute d_{2} on the assumption that exactly two columns below d_{1} are used as C_{0}^{(y_{0})} and C_{2}^{(y_{2})}. In this way, we compute d_{0}, d_{1}, …, d_{e}. The required d_{e} = h(e) is max{d_{i} | i < e}.

The crucial observation is that for any g(e) exceeding h(e), no matter what the previous pattern, we will be able to win all of Δ_{0}, …, Δ_{e}. Thus we meet all the requirements.

To see that C ≤_{tt} A, consider computing C(⟨q, x⟩). Run the construction until a stage s at which C^{(q)} is set equal to ω^{(q)} or q = q(2e, s) and ⟨q, x⟩ is either already put into C or is assigned as a coding marker for some y ∈ A. (It should be clear from the construction that one of these events eventually occurs.) Suppose n is the largest number such that g(n, s) ≤ q. If A ↾ g(n, s) ever changes, i.e., A_{s} ↾ g(n, s) ≠ A ↾ g(n, s) then all of ω^{(q)} is put into C. If not, then q = q(2e) and ⟨q, x⟩ ∈ C iff y ∈ A. This procedure is the required truth–table reduction. □

3. Low_{2} results.

In this section we prove some results on low_{2} r. e. degrees. One natural question arising from the results of §2 is whether the low_{2} classes arising there are strictly low. For instance we know that all incomplete wtt–topped r. e. degrees are low_{2}. Are they in fact all low? Here we know the answer is no, since Downey and Jockusch [1987] showed that there exist incomplete 1–topped r. e. degrees, and all such degrees are low_{2}–low_{1}. Similarly, Lachlan [1968] showed that all coinfinite low_{2} r. e. sets have maximal supersets so that (2.3) is sharp in terms of the high/low classification scheme. Downey [1993] constructs a low_{2}–low_{1} array recursive degree and therefore (2.1) is tight too. The last of the results of §2 dealt with tt– bottomed degrees. Again, the result is sharp.

(3.1) Theorem. There exist low_{2}–low_{1} wtt– bottomed T –degrees containing r. e. sets of minimal tt–degree.

Proof sketch: Originally, we had a direct proof of this result, but subsequently discovered that one can modify known results to obtain the desired one. The construction of Downey–Slaman [1989] of a completely mitotic promptly simple contiguous degree can easily be combined with the construction of Downey–Jockusch [1987], Theorem (4.3) and Theorem (4.17), of a strongly contiguous strongly tt–bottomed r. e. degree. Let A be the set so constructed. Then by Downey–Slaman [1989, Theorem 2.1], A is low_{2}–low_{1}, since this theorem says no low set of promptly simple degree is completely mitotic. The result then follows by the following observation by Nies (personal communication).

(3.2) Lemma. (Nies) Suppose A is the strong tt–bottom of an r. e. T–degree. Then A has minimal r. e. tt–degree.

Proof: (Nies) Let D be the deficiency set of A. Then D ≤_{tt} A and A ≤_{T} D, hence D ≡_{tt} A. As D is simple and semirecursive, X ≤_{tt} D and X ≢_{T} ∅ implies D ≤_{T} X (Degtev [1978], see Odifreddi [ta, Proposition X.7.12]). Thus A ≡_{T} X and A ≡_{tt} X. So we see that A has minimal tt–degree. □

We now give some new and rather surprising characterisations of an r. e. set being low_{2} in terms of the structure of m and tt–degrees. The first result shows that every low_{2} r. e. set has a minimal cover in the r. e. tt–degrees. Together with Theorem 2.7, this theorem shows that the low_{2} r. e. tt–degrees are definable in the r. e. tt–degrees. We view this result as the highlight of the paper. The second result improves a claim of Downey and Jockusch [1987, Theorem 3.5]. They claimed that if c is r. e. and low_{1} then there is a 1–topped incomplete r. e. a ≥ c. Although the proof there is incorrect, we in fact show that the result is correct for every low_{2} r. e. c. The proof employs a more complicated version of the techniques used for the first result. As all 1–topped r. e. sets are low_{2}, it proves the definability of the low_{2} degrees in a language with two orderings, one for the Turing degrees and the other for either many–one or one–one degrees.

(3.3) Theorem. (i) If C is r. e. and low_{2}, then there exists an r. e. A such that the tt–degree of A is a minimal cover of the tt–degree of C.

(ii) Consequently, the jump class low_{2} is definable in the r. e. tt–degrees: a is low_{2} iff a has a minimal cover.

(iii) The same result holds for the tt–degrees below 0′ and the wtt–degrees below 0′.

Proof: (i) Let C be r. e. and given. We need to build A to meet the following requirements.

P_{e} : Φ_{e}(C) ≠ A

R_{e} : If Φ_{e} is a total tt–reduction, then Φ_{e}(A⊕C) ≤_{tt} C or A⊕C ≤_{tt} Φ_{e}(A⊕C)⊕C.

Here Φ_{e} is the e–th possible tt–reduction and has use φ_{e}. In this construction we modify the ideas of Kobzev [1979], Degtev [1973] and Fejer–Shore [1989]. At each stage s, let \{a_{0,s}, a_{1,s}, … \} list \overline{A}_{s} in order. We begin by discussing the method whereby we construct a minimal r. e. tt–degree when C = ∅.

Let ℓ(e, s) = max{z : (∀y < z)(Φ_{e,s}(A_{s} ⊕ C_{s}; y) ↓)}. The construction can either be performed by intersecting trees as in Fejer–Shore [1989] or can be thought of as an “η–maximal set” type construction where we build equivalence classes as in Odifreddi [1989, pp.302–318]. We choose the latter. Our construction will use the dump method. That is, if A_{s+1} ≠ A_{s} then, for some i, A_{s+1} = A_{s}^{i} where A_{s}^{i} = A_{s} ∪ {a_{j,s} : i ≤ j ≤ s}.

For a fixed e, the strategy is as follows. During the construction we dynamically build (finite) equivalence classes which we refer to as boxes. Initially B_{j,0} = {a_{j,0}} and we always let b_{j,s} = a_{d(j),s} denote the first element of B_{j,s}. At each stage s, B_{j,s} ∩ A_{s} = ∅. The primary rule of the construction is that at stage s, if any of B_{j,s} enters A_{s+1} then all of B_{j,s} enters. Finally, a box will have a state. In the simple construction — that is with C = ∅ — box B_{e} will have an e–state, a string of length e. This state will be used to encode the j ≤ e for which we have seen j–splittings. It will be defined formally below but the crucial fact will be the usual one for e–state arguments. For each e the e–state of box B_{e,s} is eventually constant and once the i–state of B_{i,s′} has reached its final value for i ≤ e, the box B_{e,s} itself is also constant. As we use its first element, b_{e,s}, as our witness for satisfying the Friedberg requirement P_{e} in the usual way, this fact will assure the success of P_{e}. More precisely, we wait for a stage s such that Φ_{e}(C_{s}(= ∅); b_{e,s}) = A_{s}(b_{e,s}) = 0. At such a stage, we would put b_{e,s} into A, winning the requirement forever. As b_{e,s} is eventually constant, the procedure satisfies P_{e}. Of course, in the real construction, C will later be able to change necessitating further attacks on P_{e}. The reader should, however, note that the important dynamic of the construction is achieving a stable follower b_{e,s} from a box B_{e,s} in the “correct” e–state, i.e., the one that correctly codes whether or not we get infinitely many j–splittings for each j ≤ e. In the full construction, this follower will need to be chosen so that our actions will be sufficiently C–correct to win by using it.

We now define the e–state of a box B_{i} for i ≥ e and describe how to increase it. The e–state σ(e, i, s) of B_{i,s} at s has value 1 at j ≤ e if there seems to be a j– splitting for B_{i,s} at z for some z < s, i. e., ∃z < sΦ_{j}(A_{s}⊕C; z)↓ ≠ Φ_{j}(A_{s}^{d(i)}⊕C; z)↓ at stage s and the use φ_{j}(z) is less than b_{i+1,s} (and so if B_{i,t} does not change then neither does A_{t} ↾ φ_{j}(z)). Otherwise, it has value 0 at j. Consider the simple case C = ∅. The requirement R_{e} attempts to maximize the e–states of boxes (in the usual lexicographic ordering). It finds the first j and k greater than e such that j < k but σ(e, j, s) < σ(e, k, s) and raises the e–state of B_{j} by amalgamating boxes B_{j−1}, …, B_{k−1}:

B_{i,s+1} = B_{i,s} i < j − 1

B_{j−1,s+1} = ⋃_{j−1≤i<k} B_{i,s}

B_{j+n,s+1} = B_{k+n,s} n ≥ 0

This action keeps the e–state of B_{i,s+1} the same as that of B_{i,s} for i < j but makes that of B_{j,s+1} be σ(e, k, s) > σ(e, j, s). (Of course, the e–state of a box may increase “on its own” as time goes by and more splittings are discovered. Such increases call for no additional action on our part.) The usual e–state arguments show that all boxes are finite in the limit and that almost all of them are in the same e–state. We call this the well–resided e–state. The crucial point here is that, once we have acted for each P_{i}, i ≤ e, for which we ever act (say by stage s_{0}) we change B_{i,s} (by making it larger) for i ≤ e only to increase its i–state and we never put B_{i,s} into A for i ≤ e. Suppose B_{i,s} and its i–state are constant for s ≥ s_{1} ≥ s_{0} and consider B_{e}. If at s ≥ s_{1} we have σ(e, j, s) = 1 for some j ≤ e, we have Φ_{j}(A_{s} ⊕ C; z) ↓≠ Φ_{j}(A_{s}^{d(e)} ⊗ C; z) ↓ and φ_{j}(z) < b_{e+1,s}. As we can only increase B_{e,t} for t ≥ s and no B_{i,t} ever enters A for i ≤ e, A_{t} ↾ φ_{j}(z) = A_{s} ↾ φ_{j}(z) for t > s. Of course b_{e,t} is also constant and so A_{t}^{d(e)} ↾ φ_{j}(z) = A_{s}^{d(e)} ↾ φ_{j}(z) for every t ≥ s as well. Thus the j–splitting for B_{e} at z can never disappear after s and so the e–state of B_{e,s} can never decrease after s_{1}. As usual, this means that B_{e,s} and its e–state are eventually constant for each e. These facts suffice to establish the theorem when C = ∅. To see this, we prove that the requirements R_{e} are satisfied. Let η be the well–resided (e + 1)–state. If η(e) = 1 we will prove that A ≤_{tt} Φ_{e}(A). If η(e) = 0 we will prove that ϕ_{e}(A) ≤_{tt} C = ∅. In either case we describe the required reductions for x larger than all elements of the n many final boxes which are not in the well–resided (e + 1)–state η. Suppose first that η(e) = 1. Find a stage s by which B_{i,s} have settled down for i < n and x is either in A or in a box B_{j,s} with state η. Suppose x ∈ B_{j,s}. Now x will later enter A if and only if B_{k,s} is put into A for some k, n ≤ k ≤ j. As η(e) = 1, there is for each k, n ≤ k ≤ j, a number z(k) such that Φ_{e,s}(A_{s}; z(k)) ≠ Φ_{e,s}(A_{s}^{d(k)}; z(k)). We can thus check for each such k in turn if B_{k,s} enters A by answering the appropriate question about Φ_{e}(A). Clearly this provides a tt–reduction for A from Φ_{e}(A).

If η(e) = 0 and Φ_{e} is a tt–reduction, we claim Φ_{e}(A) is recursive. To compute Φ_{e}(A; x) let n be as above and let s be a stage by which all B_{i}, i ≤ n, have settled down, Φ_{e,s}(A_{s}; x)↓ and all B_{j,s} are in state η for j ≥ n and b_{j,s} < φ_{e,s}(x). We claim Φ_{e,s}(A_{s}; x) = Φ_{e,t}(A_{t}; x) for all t ≥ s and so Φ_{e,s}(A; x) = Φ_{e}(A; x). If not, let t + 1 be the first counterexample, i.e., for some i ≥ n,

Φ_{e,t+1}(A_{t+1}; x) = Φ_{e,t}(A_{t}^{d(i)}; x) ≠ Φ_{e,s}(A_{s}; x) = Φ_{e,t}(A_{t}; x).

Of course a_{d(i),t} < φ_{e,t}(x). Thus we could raise the state of B_{n} at t to take value 1 at e, contrary to our choice of n and s.

(We note that this argument can be modified to make A ≤_{m} Φ_{e}(A) if Φ_{e}(A) is r. e. by the methods of Downey [1989].)

We now turn to the case with C low_{2}. We employ a tree construction and assume familiarity with such constructions as presented in Soare [1987, XIV]. Familarity with earlier low_{2} constructions as in Shore and Slaman [1990] would also be helpful. We will meet the requirements P_{e} : Φ_{e}(C) ≠ A via a Sacks coding strategy. The version α of P_{e} with the guess τ at the well resided e–state will attempt to code K up to the length of agreement with A. Let L(α, s) be the length of agreement function for P_{e}. The node α takes control of the boxes B_{i,s} with (the code for) α < i < L(α, s) which are not controlled by nodes of higher priority and are in state τ. (So, in particular, no action can be taken by nodes of lower priority to improve their j–state for j > e.) If one such i later enters K we put B_{i,s} into A. If Φ_{e} is a total truth–table reduction we must eventually produce a disagreement as K ≰_{T} C. If not, L(α, s) is eventually constant anyway. Thus α’s effect on nodes extending it is finitary. Note that if we move to the left of α, it loses its control over all boxes.

To be more precise, suppose by induction that α is on the leftmost path and that on the C–true α–stages (defined below) the set of boxes assigned to each node of higher priority than α is eventually constant and that, from some point on, no β < α ever acts to redefine any box. Moreover, assume also by induction that on the C–true α–stages almost all boxes eventually assigned to α are in state τ. If Φ_{e} is not a truth–table reduction, the length of agreement function is obviously eventually constant and so, therefore, is the set of boxes eventually controlled by α on the C–true α–stages. If Φ_{e} is a truth–table reduction, then any box B_{i,s} controlled by α at a sufficiently large C–true α–stage s is controlled by α at every later C–true α–stage and it is eventually fixed by construction and our induction hypothesis. If Φ_{e}(C) = A, α would then eventually control B_{i,s} for every i larger than some i_{0} at every C–true α–stage. Once so controlled, B_{i,s} will enter A only if some j ≤ i enters K. In this case, we could compute K from A ⊕ C and so from C for our desired contradiction. Thus Φ_{e}(C) ≠ A and once again the length of agreement is eventually constant. In any case, the set of boxes controlled by α is eventually constant and, from some point on, α does not act to redefine any boxes (by putting numbers into A) so each box is eventually fixed as well.

We can thus consider 0 to be the only outcome of α and make α 0 accessible whenever α is. Of course α 0 works on the next R requirement.

Thus the crucial point, for C ≠ ∅, is determining when a node η, such as α 0, trying to maximize the state of boxes at e for the sake of R_{e} should act by amalgamating boxes. (It has an assumption τ as to the well-resided (e − 1)–state.) The problem, of course, is that it may appear that σ(e − 1, j, s) = σ(e − 1, k, s) = τ and σ(e, j, s) < σ(e, k, s) but the computation Φ_{e}(A_{s} ⊕ C_{s}; z) ↓ ≠ Φ_{e}(A_{s}^{d(k)} ⊕ C_{s}; z) ↓ may be C–incorrect. Acting on the basis of such computations could result in infinitary action without stabilizing the (e + 1)–states. Our basic plan is to use low_{2}–ness in the fashion of Slaman and Shore [1990] to approximate the answers to the appropriate question of C′′ at node η:

Q(η) : ∀n∃^{∞}s (s is a C − true η − stage and there is a box B_{m}, m > n,

in state τ 1 via computations using only C ↾c(η, s)?

(c(η, s) is defined below and τ is η’s guess at the well–resided e–state.)

Notation: We approximate C as C_{s} = {c(t) | t < s} where c(s) is a 1–1 recursive enumeration of C. If η is accessible at s and was last accessible at r (= 0 if η has never been accessible before), then c(η, s) is min(C_{s} − C_{r}), the least number enumerated C since stage r. We say that a stage s is a C–true η–stage if η is accessible at s and C_{s} ↾c(η, s) = C ↾c(η, s). This procedure is a version of Lachlan’s “hat trick” (Soare [1987], p.131) done on a tree.

In the usual way, we use the recursion theorem to uniformly get an index for the C′′ question Q(η) and so, by the low_{2}–ness of C, a Δ_{3} index for the answer, i.e. we have an index a such that for every η, if the answer to our question is yes, then {a}^{∅′′}(η) = 1 and otherwise {a}^{∅′′}(η) = 0. The typical approximation procedure for Δ_{3} functions then gives us a recursive g such that for every η the second coordinate (π_{2}) of lim inf g(η, s) is {a}^{∅′′}(η). [As h(η) = {a}^{∅′′}(η) is a Δ_{3} function, we may choose recursive predicates R_{0} and R_{1} such that, for k = 0, 1, h(η) = k iff ∃x∀y∃zR_{k}(x, y, z, a, η). The idea is to define g(η, s) as the least ⟨x, k⟩ for which we have made progress at stage s towards seeing that ∀y∃zR_{k}(x, y, z, a, η). Formally we choose the least ⟨x, k⟩ such that either there is no r < s for which g(η, r) = ⟨x, k⟩ or u = μy(¬(∃z < s)R_{k}(x, y, z, a, η)) is larger than the corresponding number at the last t for which g(η, t) = ⟨x, k⟩ (that is, such that if t is the largest r less than s such that g(η, r) = ⟨x, k⟩ and v = μy(¬(∃z < t)R_{k}(x, y, z, a, η)), then u > v). It is clear that g(η, s) is always defined by the first alternative if not by the second. It is easy to see that our desired function can be taken to be g(η, s).] It is this function g(η, s) that we use to approximate the required answer to our C′′ questions.

Next we describe the outcomes of η which is working on R_{e}. As a first approximation, the outcome at stage s of the node η should, in essence, be the value ⟨x, k⟩ of g(η, s). Note first, that we must coordinate the approximations to g at successive nodes by the standard procedure that calculations at a node η work on the assumption that the only stages of the construction to be considered are those at which η is accessible. In terms of bookkeeping, one could try to simply consider g(η, t) where, at s, η has become accessible for the t–th time. The left to right ordering on these outcomes is the usual lexicographic ordering on pairs. A further coordination procedure, however, is also required.

Suppose η (with guess τ at the well resided e − 1–state) is accessible at stage s for the t^{th} time and was last accessible at r. If g(η, t) = ⟨y, k⟩, we assign a chip ⟨η, y, k, s⟩ to the corresponding outcome η ⟨y, k⟩ of η. These chips will be used (by assigning various boxes to them) to monitor the number of times and the priority with which the various successors of η are allowed to act either to preserve computations by keeping various boxes out of A or to code K by putting boxes into A. Let B_{j_{0}} be the last box controlled by a requirement of priority greater than η and B_{j_{1}}, …, B_{j_{n}} be the boxes not controlled by any requirement of higher priority than η which are in state τ 1 (all at stage s). Assign all the boxes in each of the following intervals of boxes (B_{j_{0}}, …, B_{j_{1}}), [B_{j_{1}}, …, B_{j_{2}}), …, [B_{j_{n−1}}, …, B_{j_{n}}) to a chip ⟨η, x, 1, v⟩, v ≤ s, in order of priority (lexicographic order on the chips). (Thus for example B_{i} is assigned to the first chip of the form ⟨η, x, 1, v⟩ which is assigned to η ⟨x, 1⟩ for j_{0} < i < j_{1}; for j_{i} ≤ i < j_{2}, B_{i} is assigned to the second such chip.) The outcomes ⟨η, x, 0, v⟩ do not expect any boxes in state τ 1 and so do not get any of the boxes in state τ 1 assigned to their chips. Instead, we simply assign the boxes B_{j_{n}+1}, B_{j_{n}+2}, … in order to the chips assigned to η ⟨x, 0⟩. These boxes are now protected with the priority of the chip ⟨η, x, k, v⟩ to which they are assigned against any action by requirements to the right. This protection remains in effect as long as the relevant C–computations are correct and no node β <_{L} η is accessible. It does not, however, interfere with the action of η ⟨x, 1⟩ or its successors. In particular, the boxes assigned to chips ⟨η, x, 1, v⟩ (actually, the ones resulting from the amalgamation and dumping action of η ⟨x, 1⟩ described below) are the ones available to nodes extending η ⟨x, 1⟩. Similarly, the ones assigned to chips ⟨η, x, 0, v⟩ can be passed on to nodes extending η ⟨x, 0⟩.

The determination of the accessible immediate successor of η depends primarily on the approximation procedure g(η, t). It must, however, be coordinated with the C–true η–stages as well. Let r be the last stage that appears to be a C–true η–stage, i.e., the largest r such that c(t) > c(η, r) for r < t ≤ s. We declare η ⟨x, k⟩ to be accessible where ⟨x, k⟩ is the lexicographically least value of g(η, u) with r ≤ u ≤ s. If k = 1 we amalgamate boxes B_{j_{i}}, …, B_{j_{i+1}−1} for the sequences assigned to chips ⟨η, x, k, v⟩; thereby making the e state of B_{j_{0}+i} be τ 1. (Note that if there are no C–changes and we never move left of η ⟨x, 1⟩, then the new boxes remain in state τ 1. Each of them, as a sequence of length one, will automatically be assigned to its own chip ⟨η, x, 1, w⟩ at the next η stage.) If at s′ > s the computation witnessing the high e–state is seen to be C–incorrect, we dump boxes B_{j_{i}+1}, …, B_{s′} into A. If k = 0, we take no action for η but protect the boxes assigned to its chips ⟨η, x, 0, v⟩ from any action by nodes to the right of η ⟨x, 0⟩ until some node to its left becomes accessible. (Again no actions by node α ⊇ η ⟨x, 0⟩ are restricted.)

In any case, we now act for η ⟨x, k⟩ which is assigned to some P_{j}. Our action at η ⟨x, k⟩ for P_{j} is to code K (up to the appropriate length of agreement) on the sequence of boxes handed down to η ⟨x, k⟩ by our actions for η. (These are the ones assigned to ⟨η, x, k, v⟩ chips.) As we have argued above, these actions will be finitary. The boxes received by η ⟨x, k⟩ which are larger than those used for coding by P_{j} are passed on to its immediate successor η ⟨x, k⟩ 0 on the priority tree for its use.

Note that if ⟨x, k⟩ is the leftmost value of g(η, s) taken on infinitely often, then η ⟨x, k⟩ is accessible at infinitely many C–true η–stages. (If no preceeding value is taken on for any s ≥ s_{0}, η is accessible at s_{0} and g(η, t) = ⟨x, k⟩ for some t > s_{0} then η ⟨x, k⟩ is accessible at the first C–true η–state t′ ≥ t.)

Assume η is on the true path. We analyze its action to see that we can maintain our inductive assumptions about the eventual effects of α. This will allow us to complete our proof. Let ⟨x, k⟩ be the leftmost value taken on infinitely often by g(η, s). The definition of accessibility guarantees that η ⟨x, k⟩ is accessible at infinitely many C–true η–stages and that, from some point s_{0} on, no node to its left gets a chip or becomes accessible. Thus no node to its left can act to redefine any boxes after stage s_{0}. By the assignment of sequences of boxes to chips in order, it is clear that the assignment to chips to the left of η ⟨x, k⟩ is eventually constant on the C–true η–stages.

Suppose first that k = 0 and so the answer to Q(η) is no. In this case, all sufficiently large boxes are in state τ 0 at all sufficiently large C–true η–stages and are eventually all assigned to ⟨η, x, 0, v⟩ chips by construction. This suffices to continue our induction.

Next suppose k = 1 and so the answer to Q(η) is yes. In this case, η ⟨x, 1⟩ gets infinitely many chips. Each of them eventually gets a sequence of boxes B_{j,s}, …, B_{k,s} assigned at C–true η–stages which are associated with C–correct computations. Each one also eventually gets to amalgamate such a sequence when η ⟨x, k⟩ is accessible at a C–true η–stage. Thus all sufficiently large boxes are eventually assigned to chips ⟨η, x, 1, v⟩ and wind up in state τ 1. (Remembers that if η ⟨x, k⟩ gets infinitely many chips then all boxes not assigned to chips belonging to higher priority nodes that are in e–state τ k will be eligible to be assigned to these chips belonging to η ⟨x, k⟩. If η ⟨x, k⟩ is on the true path then only finitely many boxes are assigned to chips belonging to nodes of higher priority and only finitely many are not eventually in e–state τ k. Thus almost all boxes will actually be assigned to chips of the form ⟨η, x, k, v⟩.) As η ⟨x, 1⟩ takes no action for a box once it and all its predecessors are in state τ 1, we once again have continued the inductive hypotheses.

It is now clear that every box B_{i,s} is eventually constant. (It is eventually assigned to some chip assigned to a node β on or to the left of the leftmost path. After that point, it can be changed only by nodes γ ≤ β. We have, however, shown that their outcomes are finitary.)

We can now argue that the node η on the leftmost path which is associated with R_{e} actually satisfies the requirement. Let η ⟨x, k⟩ be on the leftmost path and let s_{0} be such that all action by nodes γ < η ⟨x, k⟩ has ceased and such that there is a fixed assignment of boxes to such γ on all the C–true η–stages greater than s_{0}.

Suppose first that k = 0. We prove that Φ_{e}(A ⊕ C) ≤_{tt} C. As the answer to Q(η) is no, we may also assume that after s_{0} no more computations show up at C–true η–stages that would make the state of B_{n} be τ 1 for any n > some fixed n_{0}. Assume the B_{i,s} have reached their limits for i ≤ n_{0}. To compute Φ_{e}(A ⊕ C; x), find a stage s at which η ⟨x, 0⟩ is accessible, Φ_{e,s}(A_{s} ⊕ C_{s}; x) ↓ and such that every z < φ_{e,s}(x) not in a box permanently assigned to a chip belonging to some node of higher priority than η ⟨x, 0⟩ is in A or a box in state τ 0. We claim that Φ_{e}(A ⊕ C; x) = Φ_{e}(A_{s}^{d(n_{0})} ⊕ C; x) = Φ_{e}(A_{s} ⊕ C_{s}; x). If not, Φ_{e}(A ⊕ C; x) = Φ_{e}(A_{t} ⊕ C_{t}; x) for some C–true stage η–stage t but A_{t}^{d(n_{0})} = A_{s}^{d(n_{0})} on the use of this computation by our choice of n_{0} and s. In this case, we would have a computation at the C–true η–stage t showing that the state of B_{n_{0}} is τ 1 for a contradiction. This procedure gives a tt–reduction from C computing Φ_{e}(A ⊕ C) as required.

Finally, suppose k = 1, the answer to Q(η) is yes and ⟨x, 1⟩ is the leftmost outcome accessible infinitely often. In this case, we claim that A ≤_{tt} Φ_{e}(A⊕C)⊕C. To compute A(y), find a stage s by which all higher priority nodes have reached their final state; Φ_{e,s}(A⊕C; y)↓ and all numbers z < φ_{e,s}(y) not in boxes assigned to chips belonging to higher priority nodes are in A or a box in state τ 1 assigned to a chip belonging to η ⟨x, 1⟩. Now check each box in turn to see that the computation providing the witness for the high e state is C–correct. If not, then we know it, and all subsequent boxes < φ_{e,s}(y), will go into A. If it is C–correct, we ask Φ_{e}(A ⊕ C) which of the two associated computations gives the final answer and so determine if this block (and so all later ones < φ_{e,s}(y)) will go into A or not. Checking each box in this way using C ↾φ_{e,s}(y) and Φ_{e}(A ⊕ C) at the relevant witness points, we can determine A ↾ φ_{e,s}(y). This procedure provides the required truth table reduction and concludes the proof of (i).

Part (ii) follows immediately from (i) and Theorem 2.7. Standard Δ_{2}^{0} approximation techniques can be used to extend the result to the tt and wtt degrees below 0′ and so prove (iii). We omit the (many) technical details needed. □

We now know that the low_{2} r. e. tt–degrees are precisely those with minimal covers. One might guess that they are also the tt–degrees which are minimal covers. The following result shows that this is not the case.

(3.4) Theorem. There exists a low r. e. nonrecursive set A such that A is not a minimal cover in the r. e. tt–degrees.

Proof: We build A = ∪_{s}A_{s}, together with auxiliary r. e. sets Q_{e} to meet the following requirements:

P_{e} : \overline{A} ≠ W_{e}
N_{e} : (∃^{∞}s)(Φ_{e,s}(A_{s}; e) ↓) → (Φ_{e}(A; e) ↓)
R_{e} : Γ_{e}(A) = V_{e} ⇒ [(A ≤_{tt} V_{e}) or (Q_{e} ≤_{tt} A & (∀i)(R̂_{e,i}))],

where

R̂_{e,2i} : Δ_{i}(V_{e}) ≠ Q_{e}
R̂_{e,2i+1} : Δ_{i}(V_{e} ⊕ Q_{e}) ≠ A.

Here Δ_{i} and Γ_{e} list the partial tt–functionals with uses δ_{i} and γ_{e}, respectively, and ⟨V_{e}, Γ_{e}⟩ is a listing of all pairs consisting of an r. e. set and a partial tt–functional.

Once again, the construction will employ boxes and dumping. Let \overline{A}_{s} = \{a_{j,s} : j ∈ ω}. Let A_{s}^{i} = A_{s} ∪ {a_{j,s} : i ≤ j ≤ s}. We ensure that if A_{s+1} ≠ A_{s} then A_{s+1} = A_{s}^{i} for some i. Moreover, each node α in the construction will have at stage s, a division of \overline{A} into boxes B_{α,i,s} with first element b_{α,i,s} = a_{d(α,i,s)}. It may process these boxes by an amalgamation procedure and then hand them on to its successor nodes. In any case, each node α enforces the rule that if any element of B_{α,i,s} is put ito A by a node β ≥ α then all of B_{α,i,s} enters A. Let ℓ(e, s) = max{y : ∀x < y(Γ_{e,s}(A_{s}; x) = V_{e,s}(x))}. As usual, we regard Γ_{e,s}(A_{s}) as controlling V_{e,s} in the sense that once we have ℓ(e, s) > x we will not allow V_{e,s}(x) to change unless A_{s} changes on γ_{e,s}(x), the use of the computation.

A node α assigned to R_{e} checks for α–expansionary α–stages, i.e., ℓ(e, s) reaches a new maximum length of agreement on the α–stages. If s is not expansionary, α’s outcome is f and no nodes extending α f are assigned to any R̂_{e,j}. If s is expansionary, α first sees if it can kill R_{e} off once and for all. Thus it first asks if there is some “α–active” b_{α,j,s} such that for some q < ℓ(e, s), V_{e,s}(q) = 1 yet Γ_{e}(A_{s}^{d(α,j,s)}; q) = 0. If this is the case, we set A_{s+1} = A_{s}^{d(α,j,s)} and preserve A↾γ_{e}(q) with priority α. It also asks if there is a q such that V_{e,s}(q) = 0 and α–active b_{α,i,s} < b_{α,j,s} such that Γ_{e}(A_{s}^{d(α,i,s)}; q) = 0 but Γ_{e}(A_{s}^{d(α,j,s)}; q) = 1. In this case, we also let A_{s+1} = A_{s}^{d(α,j,s)} and preserve the current disagreement with priority α. Should q later enter V_{e} at t we can set A_{t+1} = A_{t}^{d(α,i,t)} and preserve a permanent diagonalization. (Note that, by our preservation procedure at s, d(α, i, s) = d(α, i, t) and so A_{t}^{d(α,i,t)} ↾ s = A_{s}^{d(α,i,s)} ↾ s. As γ_{e}(q) < s, our action produces the desired diagonalization.) In either of these two cases, we again have a finitary outcome for α that imposes finite restraint on A and requires no further work on R_{e}. (The “α-active” j (or b_{α,j,s}) are those for which it is still possible (with priority α) to set A_{s+1} = A_{s}^{d(α,j,s)} i.e., there is no restraint of higher priority on b_{α,j,s} and they are in the e–state expected by α.)

If none of the finitary wins are possible we attempt to make A ≤_{tt} V_{e} via an “e–state amalgamation of boxes” procedure that makes V_{e} emulate the outcome of A. We first claim that Γ_{e,s}(A_{s}^{d(α,i+1,s)}) ⊆ Γ_{e,s}(A_{s}^{d(α,i,s)}) for each α–active i. If not, there would be a q that could be put into Γ_{e}(A) by putting b_{α,i+1,s} into A but not by putting in b_{α,i,s}. If q ∈ V_{e,s}, we could force the first type of finite diagonalization for R_{e}. If q ∉ V_{e,s}, we could force the second. Next, note that if v ∈ Γ_{e,s}(A_{s}^{d(α,i,s)}) − Γ_{e,s}(A_{s}^{d(α,i+1,s)}) then v ∈ Γ_{e,s}(A_{s}^{d(α,j,s)}) for all α–active j < i. (Otherwise, we would again be able to get a finitary win of the second type.)

Now if Γ_{e,s}(A_{s}^{d(α,i,s)}) ⫌ Γ_{e,s}(A_{s}^{d(α,i+1,s)}), we let v(α, i, s) denote the least v in the former set but not the latter (if one exists). The key point is that, if there is such a number, then b_{α,i,s} ∈ A iff v(α, i, s) ∈ V_{e}. Our goal is to get such a number for each i and so make A ≤_{tt} V_{e}. To do this we amalgamate boxes B_{α,i,s} to increase their e–state. More precisely, we say the state of a box B_{α,i,s} at e is 1 if there is a number v(α, i, s) as desired and 0 otherwise. Assume that the boxes B_{α,i,s} for i > e are all in the same (e − 1)–state (α’s guess at the well resided one). If B_{α,i,s} is in the low e–state and some B_{α,j,s}, j > i, is in the high one, we amalgamate all the boxes B_{α,i,s}, …, B_{α,j,s} to produce our new box B_{α,i,s+1} which now enters the high e–state. (By definition v(α, j, s) ∈ Γ_{e,s}(A^{d(α,j,s)}) − Γ_{e,s}(A^{d(α,j+1,s)}). The amalgamation makes d(α, i + 1, s + 1) = d(α, j + 1, s) and so A^{d(α,i+1,s+1)} ↾ s = A^{d(α,j+1,s)} ↾ s, v(α, j, s) ∉ Γ_{s,s+1}(A^{d(α,i+1,s+1)}) and γ_{e}(v(α, j, s)) < s. Of course, we are still assuming that no finite win is available and so Γ_{e,s}(A_{s}^{d(α,k+1,s)}) ⊆ Γ_{e,s}(A^{d(α,k,s)} for each k with i ≤ k ≤ j. Thus Γ_{e,s}(A_{s}^{d(α,j,s)}) ⊆ Γ_{e,s}(A^{d(α,i,s)}). As our amalgamation keeps d(α, i, s) = d(α, i, s + 1), A^{d(α,i,s)} ↾ s = A^{d(α,i,s+1)} ↾ s and so v(α, j, s) ∈ Γ_{e,s+1}(A^{d(α,i,s+1)}) and is the required v(α, i, s + 1) witnessing that B_{α,i,s+1} in the high e–state.)

As usual the infinitary outcome that all boxes are eventually in the high e–state is the leftmost one on the tree of strategies. The outcome that almost all boxes are always in the low e–state is next and its action is finitary in nature. (The former may amalgamate boxes infinitely often, the later never does.) The truely finite outcomes producing permanent diagonalizations discussed above can be grouped as the rightmost outcome on the tree.

If α eventually gets every box B_{α,i,s} into the high e–state, A ≤_{tt} V_{e}: To see if x ∈ A (for x sufficiently large) wait until x is in A or in a box B_{α,i,s} in the high e–state. If x is not yet in A, x ∈ A iff v(α, i, s) ∈ V_{e} and no further action is needed for R_{e}. The last outcome to consider is that ℓ(e, s) → ∞, there are no finite wins for R_{e} and, for some i_{0}, the B_{α,i,s} boxes are all in the low e–state for i > i_{0} and α eventually stops acting at all. In this case, we must satisfy every R̂_{e,j} on the path extending α for the version Q_{α} of Q_{e} that is built below the outcome of α.

To satisfy R̂_{e,2i} at some node β ⊇ α we choose the first box B_{β,i,t} (i > |β|) not restrained by a node of higher priority. If the last element of this box is < t, we amalgamate enough B_{β} boxes into it to make its last element be x > t. We designate this x as β’s follower of R̂_{e,2i} and guarantee that x ∈ Q_{α} iff x ∈ A.

As long as ¬(Δ_{i,s}(V_{e,s}; x)↓ = 0), we keep x ∈ B_{β,i,s} out of A to meeet R̂_{e,2i}. If we ever get Δ_{i,s}(V_{e,s}; x) ↓= 0, at a β–stage s, we let A_{s+1} = A_{s}^{d(β,i,s)}. Of course, this puts x into Q_{α} by our previous guarantee. The general format of our construction guarantees that (if β is on the tru

e path and we are never to its left again) that for every t ≥ s if A_{t+1} ≠ A_{t} then A_{t+1} = A_{t}^{d(β,j,t)} for some j ≥ i. If such a change would cause a change in Γ_{e}(A) ↾ δ_{i,s}(x) then either we could have killed off R_{e} by a diagonalization at α or we could have increased the e–state of some box at α contrary to our assumptions that β is on the true path and that we are never again to its left. Thus Δ_{i}(V_{e}; x) = 0 ≠ Q_{α}(x) as required to meet R̂_{e,2i}.

The procedure for a β ⊇ α devoted to R̂_{e,2i+1} is similar albeit the argument is a bit more complicated. We again choose as a follower x the least b_{β,i,s} not restrained with higher priority. Now we declare that x ∉ Q_{α} and wait for Δ_{i,s}(V_{e,s} ⊕ Q_{α,s}; x) to converge.

Note that, if for no number y with x < y < δ_{i}(Γ_{e}(A) ⊕ Q_{α}; x)) have we declared that y ∈ Q_{α} iff y ∈ A (for the sake of some R̂_{e,2p}), then we can win R̂_{e,2i+1} immediately by setting A_{s+1} = A_{s}^{d(β,i,s)}, since this causes x to enter A with no change to Δ_{i}(Γ_{e}(A) ⊕ Q_{α}). The point here is again that Γ_{e}(A_{s}) and Γ_{e}(A_{s}^{d(β,i,s)}) must be identical since we are not able to diagonalize or raise states.

The more difficult case is that for some (least) number k > d(β, i, s) we have declared that a_{k,s} ∈ A iff a_{k,s} ∈ Q_{α}. By our choice of i, a_{k,s} is not controlled by any requirement of priority higher than β. So, the first thing β does is to see if it can meet R̂_{e,2i+1} by setting A_{s+1} = A_{s}^{d(β,i,s)}. That is, we see if Δ_{i,s}(Γ_{e,s}(A_{s}^{d(β,i,s)}) ⊕ Q_{α,s}^{i}; x) = 0. Here Q_{α,s}^{i} denotes what Q_{α,s+1} would be if we set A_{s+1} = A_{s}^{d(β,i,s)}. Should such a win exist, we set A_{s+1} = A_{s}^{d(β,i,s)}, and meet R̂_{e,2i+1} by x entering A. Of course, we now impose restraint of priority β to preserve the win. Suppose that no such win exists. Then we see if we can win by setting A_{s+1} = A_{s}^{d(β,j,s)} instead where j is least such that a_{k,s} ∈ B_{β,j,s}. That is, does Δ_{i}(Γ_{e}(A_{s}^{d(β,j,s)})⊕Q_{α,s}^{j}; x) = 1? Again, if such a win exists we take it. If neither of these are true then since Q_{α,s}^{i} = Q_{α,s}^{j}, it can only be that Γ_{e}(A_{s}^{d(β,i,s)}) ≠ Γ_{e}(A_{s}^{d(β,j,s)}) below δ_{i}(x). Once again, this would mean that we would have had a different outcome at α by diagonalization or state raising for a contradiction. Thus we can meet R̂_{e,2i+1}.

Finally, the requirements P_{e} and N_{e} are met in the usual way. A node σ acting for N_{e} just imposes restraint whenever Φ_{e,s}(A_{s}; e) converges at a σ–stage. A node τ acting for P_{e} chooses a follower x = b_{τ,i,s} not restrained with higher priority. If at a later τ–stage t, x ∈ W_{e,t}, we put B_{τ,i,s} (= B_{τ,i,t}) into A.

Note that all positive outcomes and all restraints are finitary so all the requirements (in particular the N_{e}) are eventually satisfied by the actions of nodes on the true path.

The last point to be verified is that if we do not get A ≤_{tt} V_{e} at the node α on the true path devoted to R_{e}, then the version Q_{α} of Q_{e} that we build below α is tt–reducible to A. Now the only way a number x can get into Q_{α} is for it to be attached to A’s action at x by some β ⊇ α is acting for R_{e,2i}. When this assignment is made we guaranteed that x > s. Thus it suffices to go to stage x + 1 and see if x has been attached to A. If not x ∉ Q_{α}. If so, x ∈ Q_{α} iff x ∈ A. □

(3.5) Theorem. (i) If c is low_{2} and r. e. then there exists an incomplete 1–topped r. e. degree a ≥ c.

(ii) Since all incomplete 1–topped degrees are low_{2} by Jockusch [1972] (Corollary 8 (i)), it follows that c is low_{2} iff c is bounded by an incomplete 1 − topped-r. e. degree.

(iii) Consequently, the class low_{2} is definable in the structure of r. e. sets with two degree orderings, ≤_{T} and ≤_{r} for r ∈ {1, m, tt, wtt}. (This uses the facts that every incomplete r. e. wtt-topped T -degree is low_{2} and that the set constructed above the given low_{2} degree is in fact above it in the 1-degrees. The first fact is an index set result proven exactly as for the 1–topped or m–topped r. e. degrees as {e | W_{e} ≤_{wtt} A} is Σ_{3} for any r. e. A.)

Proof: Let γ_{e} denote the e–th partial recursive function. We need to build A and an auxiliary r. e. set B in stages to meet the following requirements.

Q_{e} : ¬(B ≤_{m} A ⊕ C via γ_{e})
R_{e} : Φ_{e}(A ⊕ C) = W_{e} implies W_{e} ≤_{1} A.

Here (Φ_{e}, W_{e})_{e∈ω} is a listing of all pairs consisting of a (partial) Turing reduction and an r. e. set. We use the standard convention that Φ_{e}(A⊕C) controls W_{e} in the sense that once a computation halts and we have a length of agreement l(e, s) > x then we don’t allow W_{e,t}(x) to change for t > s unless some number below the use φ_{e}(x, s) enters either A or C.

We begin by briefly reviewing the construction of an m–topped degree (i.e. with C = ∅) from Downey and Jockusch [1987]. We will then discuss how to work above a given low C, and, finally, how to work above a low_{2} C.

The manner in which we meet the R_{e} is essentially positive. Suppose node σ is devoted to R_{e}. We let ℓ(σ, s) be the length of agreement between Φ_{e}(A ⊕ C) and W_{e} at σ–stage s. We also denote W_{e} by W_{σ} as usual. The idea is that, at the first σ–stage when l(σ, s) > x, if x ∉ W_{e,s} we define a coding marker f(σ, x) ∉ A_{s}, chosen as a fresh number. We then promise that f(σ, x) ∈ A iff x ∈ W_{e}. So if x enters W_{e}, we are committed to enumerating f(σ, x) into A. The outcome of σ is i (for infinitary) when ℓ(σ, s) reaches a new maximum and f (for finite) otherwise.

The action for a node τ devoted Q_{e} is as follows. We pick a follower z targeted for B and wait till γ_{e,s}(z) ↓. Then if γ_{e,s}(z) ∈ A_{s} already, we win by keeping z out of B. If γ_{e,s}(z) ∉ A_{s}, then we can win by adding z into B and keeping γ_{e,s}(z) out of A. The outcomes for τ are all finitary. Either we wait (w) for the follower z to be realized (γ_{e}(z) ↓) or we diagonalize (d) by putting z into B and preserving A.

(Note that another reasonable strategy is to put γ_{e,s}(z) into A and keep z out of B. The problem with this approach is that for some pair ⟨σ, q⟩ it may be that f(σ, q) = γ_{e,s}(z). So such a γ_{e,s}(z) is forbidden to enter A unless q enters W_{σ}. This means that the entry of γ_{e,s}(z) into A is more or less out of our control if we respect f’s wishes. Actually, the dual problem of being forced to keep some q out of W_{σ} will be encountered below. The difference is that we can hope to keep numbers out of W_{σ} via our control of A while we have no way to put them into W_{σ}.)

In the basic construction (no C), the other thing we need to do is to make A nonrecursive. The corresponding requirements acting, for example, at a node β add elements into A for diagonalization initiating a sequence of coding actions since some x entering A can allow W_{e,s} to change for many e. This action in turn puts many f(σ, y) into A. The principal task in any one–topped construction is to mesh the interaction of such codings with the satisfaction of the Q_{e}: We must know that, when we add z into B for β, all pending coding commitments (of higher priority) have ceased to act. (After all, f(σ, y) = γ_{e,s}(z) is entirely possible; if y enters W_{σ} after we put z into B, we are committed to putting f(σ, y) into A and hence γ_{e,s}(z) into A. Now we would have no contradiction since z ∈ B and γ_{e,s}(z) ∈ A).

We can, however, actively prevent such y from entering W_{σ} by preserving A on φ_{e}(y). We can do this simultaneously for all possible actions of higher priority R requirements (say at node α ⊆ β) with infinitary outcomes contained in β as long as all the higher prior ity Q requirements have ceased to act. (This is eventually guaranteed by the usual tree mechanisms.) The point is that, if α i ⊆ β, then we act for β only at a α–expansionary stages, s, when its length of agreement function is at a new maximum. Thus preserving A ↾ s will preserve W at every x with a coding marker already appointed. Of course, if α f ⊆ β we may eventually assume that no further action is taken for the sake of α.

We now turn to the case where C is low. Note that we now no longer need to make A nonrecursive. The principal difficulty will be to make A⊕C not 1–complete.

Now if C is low then C′ ≡_{T} ∅′. Hence, in a standard way via the recursion theorem, test sets, and the limit lemma, we can approximate answers to C′–questions about the construction recursively in ∅′. We always reconcile the answer given by the recursive approximation to any C′ question with the current apparent answer by continuing to run the enumeration of C and the recursive approximation until they agree. (We assume that the reader is familiar with this technique sometimes referred to as the “Robinson trick” (see Soare [1987, Ch XI]). We remind the reader that this typically involves a low set C and a reduction Δ(C). One asks if Δ_{s}(C_{s}; q), say, is correct by seeing if C is correct on the use of the computation δ = δ_{s}(q). To answer this question, one enumerates a canonical index u for {z : z ≤ δ & z ∉ C_{s}} into a “test set” V whose index i is given by the recursion theorem. Since C is low 0′ can tell if there is a u ∈ W_{i} = V such that D_{a} ∩ C = ∅. Thus we can approximate the answer as lim_{s} g(i, s) for some recursive g. After we enumerate u into V we reconcile any apparent inconsistencies by waiting for a stage t > s where either g(i, t) = 1 or the Δ_{s} computation becomes C–incorrect since C_{s}↾ δ ≠ C↾ δ. We will assume this procedure to be known and only refer to it informally in the discussion below.)

A requirement τ devoted to diagonalizing against the potential reduction γ_{τ} wants to get a stage s at which there is an x with γ_{τ} (x) ∉ A ⊕ C at which there are C–correct computations for all coding markers of priority σ such that σ i ⊂ τ (i for infinitary outcome) which are still on the board. If τ can get such stage, it can put x into B and preserve A (up to the stage) as before so as to win its requirement. (By preserving A, τ guarantees that γ_{τ} (x) will never have to be put into A.) Of course, if γ_{τ} (x) ∈ A ⊕ C we just keep x out of B for an easy win.

The problem is how to produce such a stage (if τ needs one, i.e. γ_{τ} (x) ∉ A ⊕ C for all the potential witnesses x). The solution is to ask the right questions (of the recursive approximation to C′).

When we hit the first coding node σ we first ask the oracle approximation if there is at least one stage s at which σ is accessible and we have C–correct computations for all current σ coding markers. If the answer is no, the outcome of σ is f (for finite win). In this case, we proceed as if Φ_{σ}(A ⊕ C) is not total or is not equal to W_{σ}, i.e. no action is necessary. In particular, no chips are issued to appoint new coding markers. (We will only appoint new coding markers when additional chips have been assigned to the node.) If the answer is yes, we see if the current answer, as judged by C_{s}, is that s is the first such stage. If so, the outcome is i and we issue a chip for the appointment of a new coding marker at a later stage. (Coding markers are appointed when there is a new length of agreement between Φ_{σ}(A⊕C) and W_{σ} and there is an available chip to use up for the appointment.) If s is not the first such stage (according to C_{s}), we ask (the oracle approximation) if there are at least two such stages in the construction. If the answer is no, the outcome of σ is f. If yes, we check if s now seems to be the second such stage. If so the outcome is i (and we issue a chip). If not, we ask if there are at least three such stages, etc. Eventually, we either get an outcome f or s seems to be the nth such stage and we get an outcome i.

If there is a question in this sequence whose final answer is no, we argue that no action is really needed for σ. Let n + 1 be the first such, i.e. there are n stages as described but not n+1 many such stages. Once we are beyond the n correct stages and the answers to the first n + 1 questions have reached a limit, no new chips can be issued and so eventually no new markers can be appointed. Thus there is never a stage at which there are C–correct computations for all the finitely many markers on the board. It follows that it cannot be the case that Φ_{σ}(A ⊕ C) = W_{σ} and the overall effect of σ is finite. The construction can easily live with this.

On the other hand, if every question has a final answer yes, then we have outcome i infinitely often at stages at which the computations are really C–correct. (Consider the first such s. It appears C–correct at stage s, of course, and we run the approximation until it gives the answer that there is such a stage.)

The next coding requirement α below σ i asks for stages at which all the current σ computations are C–correct and if, among such stages, there are n which are also C–correct on all the α markers. If we really have to worry about α, then there will be infinitely many stages at which α i is accessible and all the σ and α computations are C–correct.

Eventually we get to τ which is working on requirement Q_{τ}. If we have to worry about τ there will eventually be a stage at which τ is accessible, all the σ, α etc. computations are C–correct, and there is a witness x with γ_{τ} (x) ∉ C. At such a stage we can preserve A and win τ. (Of course, we are asking if there is such a stage from the recursive approximation. If it answers no we need do nothing for τ. If yes, we put x into B and try to preserve A (until C changes when we start again).)

At the end of every stage we put into A every pending coding marker (i.e. ones appointed to code the fact that “x is in W ” when x has in fact gone into W) for which we have a computation from A ⊕ C saying it is in W and which is not restrained by any requirement of higher priority.

We will now describe how to perform the construction above a \overline{low}_{2} r. e. set C. The idea is to replace the above series of questions by one: Are there infinitely many σ–stages where the current σ markers have C–correct computations. Note that this question is Π_{2}^{C} and hence Δ_{3} as C is low_{2}. We shall approximate the answers as in Shore–Slaman [1992] and the proof of Theorem 3.3. Our construction is more involved and technically more difficult as it has additional coordination problems.

We remark that coding markers will be issued not just for σ but for each positive outcome (of the Δ_{3} approximation) for σ when the outcome has a chip and seems correct. They will be cancelled when nodes to the left become accessible and put in only when the outcome with which they are associated are accessible. The crucial point in the construction is that a node associated with the diagonalization requirement for γ_{τ} needs a certain type of configuration to be able to win. We describe the required situation in the following definition.

(3.6)Definition. Let η be a node on the tree of outcomes. Then we say that s is η–closed at t if (∀z < s)∀σ, x, y{[(z is a σ ⟨x, 1⟩–marker for y) & (σ ⟨x, 1⟩ ⊆ η)] → y < ℓ(σ, t) & φ_{σ,t}(A_{t} ⊕ C_{t}; y) < s] & [(z is an η ⟨x, 1⟩-marker for y → y < ℓ(η, t) & φ_{η,t}(A_{t} ⊕ C_{t}; y) < s)]}. (The η ⟨x, 1⟩–markers relevant in this definition are the ones still defined when some immediate successor of η has been declared accessible. The computations are done with the oracles as they exist when η is declared accessible and ℓ is the length of agreement function appropriate to the requirement.)

We say that s is C–correct at t if C ↾s = C_{t} ↾s.

The idea here is that if τ is a diagonalization node for Q_{τ} and there are x < s < t such that, at t, τ is accessible; γ_{τ} (x) < s and is not in A; and s is τ–closed and C– correct, then we can win the τ requirement at t by putting x into B and preserving A↾s against all lower priority requirements. Thus this is the situation we are trying to produce.

We now describe the construction assuming familiarity with the methods used in Theorem 3.3 as the general format of this construction is the same.

Construction

As usual, whenever a node α becomes accessible, we initialize all nodes to its right by canceling all chips, markers and restraints associated with them. Suppose we are at stage t. We describe our actions based on the type of requirement assigned to the node that has just become accessible. Suppose σ = η ⟨y, j⟩ r is associated with the coding requirement for Φ_{σ}(A ⊕ C) = W_{σ}. (The “r” at the end of the sequence is the restraint imposed by the action associated with η ⟨y, j⟩.) The question whose answer we approximate in our Δ_{3} way at σ is

Q(σ) : ∀n∃s > n∃t > s[σ is accessible during stage t and, when some immediate successor of σ is declared accessible at t, s is σ–closed and C–correct].

At stage t, we assign a chip ⟨σ, x, k, t⟩ to the appropriate outcomes ⟨x, k⟩ of σ (as determined by our approximation to the answer to Q(σ)) and determine the accessible immediate successor of σ as in the construction for Theorem 3.3 and so, in particular, initialize all nodes to the right of this immediate successor. (Thus any outcome to the left of the true one gets only finitely many chips, appoints only finitely many markers and is accessible only finitely often. Moreover, if ⟨y, j⟩ is the true outcome, it is accessible infinitely often and indeed at infinitely many C–true σ–stages.) We next list the stages s_{1}, …, s_{n} which are σ ⟨x, 1⟩ closed (and surely appear C–correct as we can only use C_{t} to check) at t and assign them in order to the still current σ ⟨x, 1⟩ chips for each outcome ⟨x, 1⟩ of σ. At t, each σ ⟨x, k⟩ imposes restraint r(σ ⟨x, k⟩, t) equal to the largest s so assigned to any chip assigned to a node to its left. We also assign a new large number as a σ ⟨x, 1⟩ coding marker for each z less than both ℓ(σ, t) (the associated length of agreement) and the number of chips assigned to σ ⟨x, 1⟩ which does not yet have such a σ ⟨x, 1⟩ coding marker. If the accessible outcome for σ is ⟨x, 1⟩, we put into A all σ ⟨x, 1⟩ coding markers that are not restrained with priority at least that of σ ⟨x, 1⟩ whose corresponding number is now in W_{τ} and less than the current length of agreement for the associated functional. In any case, the outcome for the accessible immediate successor σ ⟨x, k⟩ of σ is σ ⟨x, k⟩ r(σ ⟨x, k⟩, t).

We now consider a node μ = σ ⟨z, j⟩ r associated with the diagonalization requirement that γ_{μ} does not reduce B to A that has just become accessible. The node μ wants a z such that γ_{μ,t}(z) ↓∉ A_{t} ⊕ C_{t} and s, t > z, γ_{u}(z) such that, at t, μ is accessible, s is μ-closed and C–correct. At such a stage t, μ would like to put z into B and preserve A↾s against all lower priority requirements for a win. We ask the question:

Q(μ) : ∀n∃z, s, t > n[(γ_{μ,t}(z) ↓∉ A_{t} ⊕ C_{t}) & (z, γ_{μ}(z) < s < t) and, when

μ is accessible during stage t, s is μ–closed and C–correct]

We approximate the answer to this question, assign chips to outcomes ⟨x, k⟩ and determine the accessible immediate successor for μ as before. Each chip assigned to a successor of μ wants to have assigned to it a number z which will be a potential diagonalization witness with certain properties as well as a stage s which will include the restraint it needs to impose to preserve the diagonalization. A chip assigned to ⟨x, k⟩ wants to be assigned, at a stage t when μ is accessible, a z ∈ ω^{(μ,x,k)} which is larger than each z′ assigned to any smaller chip belonging to ⟨x, k⟩ as well as an s > z, γ_{μ}(z) which, when μ is accessible at t, is μ-closed and C–correct. A chip for ⟨x, 1⟩, in addition, wants γ_{μ}(z)↓∉ A ⊕ C_{t}. We assign numbers z and s that satisfy the desires of the outcomes of μ to the chips assigned to all these outcomes in order of the priority of the chips as long as there are such numbers available. If ⟨x, 0⟩ is the accessible outcome of μ, we take no action for γ_{μ} and it imposes no restraint. Thus the next accessible node is just μ ⟨x, 0⟩ followed by 0. If ⟨x, 1⟩ is the accessible outcome of μ, we put into B any z assigned to one of its chips and restrain A ↾ s, with priority μ ⟨x, 1⟩ for the associated s unless there is a smaller z for which μ ⟨x, k⟩ is already preserving such a set up which also seems C–correct. The outcome for μ ⟨x, k⟩ is this restraint that it imposes.

When we reach a node of length t, we terminate stage t.

Verifications:

Let T be the true path in the priority tree, i. e. the leftmost nodes that are accessible infinitely often. We show that each requirement is satisfied by the action of the nodes on T assigned to it. First a preliminary lemma.

(3.7) Lemma. Suppose σ ∈ T is assigned to a coding requirement and no node to the left of σ ⟨x, k⟩ is accessible after stage t_{0}. If, at stage t > t_{0}, a σ ⟨x, k⟩ chip is assigned a number s which is actually C–correct then s remains σ ⟨x, k⟩ closed and C–correct until σ ⟨x, k⟩ is accessible.

Proof: By assumption C ↾s never changes. We claim A↾s also does not change. No node to the right of σ ⟨x, k⟩ can put any number < s into A because of the restraint imposed by the assignment of s to a σ ⟨x, k⟩ chip. No node to its left can put in any number without becoming accessible and so contradicting our hypothesis. Of course, no node extending σ ⟨x, k⟩ can put in any number without σ ⟨x, k⟩ first becoming accessible. If any node ρ with ρ ⟨w, 1⟩ ⊂ σ associated with a coding requirement wants to put a number z < s into A at some t it does so because it is a ρ ⟨w, 1⟩ marker for some y < s and y has entered W_{ρ} since s but z is not in A. In this case, the current length of agreement ℓ(ρ, t) is at most y since it was larger than y at s, neither A nor C has changed on the use since s but y has entered W_{ρ}. Thus we would not actually try to put z into A. □

(3.8) Lemma. i) If η ∈ T and η is not assigned a coding requirement then

∀n∃s >n∃t > s[at stage t, η is accessible and,

when it is accessible, s is η-closed and C–correct].

(⋆)

ii) If σ ∈ T is assigned a coding requirement R_{σ} then our actions for its true outcome satisfy R_{σ}. In particular, if the true outcome of σ is ⟨x, 0⟩ then Φ_{σ}(A⊕C) ≠ W_{σ}; if it is ⟨x, 1⟩ and Φ_{σ}(A ⊕ C) = W_{σ} then the σ ⟨x, 1⟩ coding markers supply a 1 − 1 reduction computing W_{σ} from A. Moreover, the restraint imposed by the true outcome σ ⟨x, k⟩ eventually attains its lim inf on almost all the C–true σ ⟨x, k⟩ stages and so it has a leftmost outcome r.

iii) If μ ∈ T is assigned a diagonalization requirement Q_{μ}, then our actions for its true outcome satisfy Q_{μ}. Moreover, the restraint imposed by its true outcome ⟨x, k⟩ is eventually constant on the μ ⟨x, k⟩ stages and so it has a leftmost outcome r.

Proof: We proceed by simultaneous induction along T by blocks (of length two) corresponding to nodes assigned to requirements and their outcomes We first consider a node σ ∈ T assigned to a coding requirement R_{σ} with true outcome ⟨x, k⟩. Let t_{0} be such that no node to the left of σ ⟨x, k⟩ ever gets a chip or is accessible after t_{0}. First, there are finitely many chips assigned to outcomes to the left of ⟨x, k⟩. By the Lemma above any number assigned to one of them at any sufficiently large C-true σ–stage remains assigned to it forever. Thus the set of number assigned to outcomes to the left of ⟨x, k⟩ is eventually constant on the C–true σ-stages and so on the subset of those stages which are also C–true σ ⟨x, k⟩ stages. Thus the restraint imposed by the true outcome σ ⟨x, 1⟩ eventually attains its lim inf on almost all the C–true σ ⟨x, 1⟩ stages and so it has a leftmost outcome r as required.

Of course, for σ itself, (i) is vacuously true. We show that R_{σ} is satisfied and that we can continue our induction to its immediate successor σ ⟨x, k⟩ on T (and so to the end of its block) by showing that

∀n∃s >n∃t > s[at stage t, σ ⟨x, k⟩ is accessible and, when it is accessible at t,

s is σ ⟨x, k⟩ –closed and C–correct].

Fix n and assume that, by t_{1} > t_{0}, outcome ⟨x, k⟩ has more than n many chips.

a) k = 0. By our induction assumption for (i), we may choose an s_{1} > t_{1} and t > s_{1} such that σ is accessible at t and s_{1} is η ⟨y, j⟩ closed and C–correct when ν langley, j⟩ is accessible at t where σ = η ⟨y, j⟩ r for some r. Now any s ≤ s_{1} which is η ⟨y, j⟩ closed at t is also C–correct. By our assumptions, there is at least one such s > n which is assigned to a σ ⟨x, 0⟩ chip since there are more than n chips and η ⟨y, j⟩ closed is the same as σ ⟨x, 0⟩ closed. If t′ ≥ t is the next stage at which σ ⟨x, 0⟩ is accessible, the above lemma guarantees that this s > n will still be σ ⟨x, 0⟩ closed and, of course, C–correct. Thus we have established (i) for σ ⟨x, 0⟩.

We now prove that R_{σ} is satisfied if k = 0.

Claim: Φ_{σ}(A ⊕ C) ≠ W_{σ}.

Proof (by contradiction). There is a fixed finite set of σ markers which are the only ones current when σ ⟨x, 0⟩ is accessible at all sufficiently large σ ⟨x, 0⟩ stages (as nodes to its left get only finitely many chips and so markers while ones to its right are canceled when it becomes accessible). If Φ_{σ}(A ⊕ C) = W_{σ}, then ℓ(σ, t) would eventually be greater than all the numbers which have σ markers at such stages and indeed via C–correct (and even A–correct) computations. Thus each sufficiently large number the additional requirements for s to be σ closed (and C–correct) over those for its predecessor η ⟨y, j⟩ will be satisfied at all sufficiently large σ ⟨x, 0⟩ stages. This contradicts the correctness of the answer to our question Q(σ) given by the approximation. □

b) k = 1. By the correctness of our approximation, there is an s > t_{1} > n and a t > s such that, when some σ ⟨z, j⟩ is accessible at t, s is σ closed and C–correct. Any such s is σ ⟨x, 1⟩ closed at the point during stage t at which σ is accessible since this actually imposes fewer demands as σ ⟨y, 1⟩ markers for y > x can be ignored and, by the choice of t_{0}, no outcome to the left of ⟨x, 1⟩ can be accessible at t and so no markers relevant to the definition of σ ⟨x, 1⟩–closed can be canceled after σ is accessible. Moreover, any such s′ less than s which appears C–correct is, of course, C–correct. As σ ⟨x, 1⟩ has more than n chips, one such s > n is assigned to one of its chips. By the lemma, it remains σ ⟨x, 1⟩ closed (and C–correct) until σ ⟨x, 1⟩ is accessible and so we have established (i) for σ ⟨x, 1⟩.

Finally, note that σ ⟨x, 1⟩ is accessible infinitely often at C–true σ ⟨x, 1⟩ stages at which the restraint imposed by nodes of higher priority are eventually constant by induction. Thus almost all its markers that are ever appointed succeed in coding W_{σ}. If Φ_{σ}(A⊕C) = W_{σ} then the length of agreement goes to infinity and so σ ⟨x, 1⟩ coding markers are appointed for every y and so R_{σ} is satisfied as required.

We now turn to the diagonalization requirements. There is nothing to prove for (i) for a node μ = σ ⟨z, j⟩ r associated with the diagonalization requirement that γ_{μ} does not reduce B to A or for its true successor, μ ⟨x, k⟩, as μ-closed and μ ⟨x, k⟩- closed are the same as σ ⟨z, j⟩–closed. We therefore prove (iii) for μ. Remember that, by induction, there are infinitely many s with stages t at which μ is accessible and s is μ–closed and C–correct.

a) k = 0. So the answer to Q(μ) is “no” and there is then a stage t_{0} after which no outcome to the left of ⟨x, 0⟩ is ever accessible or assigned a chip. Now no number z ∈ ω^{(μ,x,0)} is ever put into B by construction. Thus we satisfy the requirement Q_{μ} unless γ_{μ}(z) ↓∉ A ⊕ C for every z ∈ ω^{(μ,x,0)} so we assume this to be the case. The outcome ⟨x, 0⟩ gets infinitely many chips and, by construction and our assumption, each one is eventually assigned a μ–closed s and a number z which is never assigned to any chip for another outcome such that γ_{μ}(z)↓ ∉ A ⊕ C. By the induction hypothesis, there are then infinitely many s, t as required to make Q(μ) true for our contradiction. Thus if the true outcome is ⟨x, 0⟩ we satisfy the requirement associated with μ. Of course, the accessible outcome for μ ⟨x, k⟩ and the restraint it imposes is always 0.

b) k = 1. So the answer to Q(μ) is “yes” and there is then a stage t_{0} after which no outcome to the left of ⟨x, 0⟩ is ever accessible or assigned a chip. The outcome ⟨x, 0⟩ gets infinitely many chips and, by our case assumption and the rules of the construction, each one is eventually assigned, at a μ-stage t, a μ–closed C–correct s and a number z < s which is never assigned to any chip for another outcome such that γ_{μ}(z) ↓∉ A_{t} ⊕C_{t} & z, γ_{μ}(z) < s < t. Once such assignment is made after t_{0} we would put z into B and preserve A↾s unless we already have a smaller such z in B. In any case, as one is really C-correct at t, the smallest one that seems C-correct really is. We now restrain A↾s for the appropriate s with priority μ ⟨x, 1⟩. By our choice of t_{0} this restraint is never violated and so we satisfy Q_{μ} and from now on the outcome of μ ⟨x, 1⟩ and so the restraint it imposes is always s. □

References

[1973] Cooper, S. B., Minimal degrees and the jump operator, J. Symb. Logic 38, 249–271.

[1993] Cooper, S. B., Rigidity and definability in the noncomputable universe (to appear).

[1973] Degtev, A. N., tt– and m–degrees, Algebra and Logic 12, 78–89.

[1978] Degtev, A. N., Three theorems on tt–degrees, Algebra and Logic 17, 187–194.

[1993] Downey, R. G., Array nonrecursive sets and lattice embeddings of the diamond, Illinois J. Math. J. 37, 349–374.

[1989] Downey, R. G., Recursively enumerable m– and tt–degrees I: the quantity of m–degrees, J. Symb. Logic 54, no. 2, 553–567.

[1990] Downey, R. G., Lattice nonembeddings and initial segments of the recursively enumerable degrees, Ann. Pure and Appl. Logic 49, 97-119.

[1987] Downey, R. G. and C. Jockusch, Jr., T–degree, jump classes and strong reducibilities, Trans. Amer. Math. Soc. 301, 103–136.

[1990] Downey, R. G., C. Jockusch, and M. Stob, Array nonrecursive sets and multiple permitting arguments, in Recursion Theory Week (K. Ambos–Spies, G. Müller and G. Sacks, eds.), Springer–Verlag, Berlin, LNMS 1432, pp. 141–171.

[1995] Downey, R. G. and R. A. Shore, Lattice embeddings below nonlow_{2} recursively enumerable degrees, Israel J. Math. (to appear).

[1989] Downey, R.G. and T. Slaman, Completely mitotic recursively enumerable degrees, Ann. Pure and Appl. Logic 41, 119–152.

[1981] Epstein, R.L., R. Haas, and R. Kramer, Hierarchies of sets and degrees below 0′, in Logic Year 1979–1980 (M. Lerman, J. Schmerl, and R. Soare, eds.), LNMS 859, Springer– Verlag, Berlin, 32-48.

[1989] Fejer, P. J. and R. A. Shore, A direct construction of a minimal tt–degree, in Recursion Theory Week (K. Ambos–Spies, G. Müller and G. Sacks, eds.), Springer–Verlag, Berlin, LNMS 1432, pp. 187–204.

[1972] Jockusch, C. G. Jr., Degrees in which the recursive sets are uniformly recursive, Can. J. Math. 24, 1092–1099.

[1978] Jockusch, C.G. Jr. and D. Posner, Double jumps of minimal degrees, J. Symb. Logic 43, 715–724.

[1972] Jockusch, C.G. Jr. and R.I. Soare, Π_{1}^{0} classes and degrees of theories, Trans. Amer. Math. Soc. 173, 33–56.

[1979] Kobzev, G., On tt–degrees of r. e. T –degrees, Mathematics of USSR Sbornik 35, 1973– 180.

[1968] Lachlan, A., On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130, 1–37.

[1968a] Lachlan, A., Degrees of recursively enumerable sets which have no maximal supersets, J. Symb. Logic 38, 431–443.

[1975] Ladner, R. E., On the structure of polynomial–time reducibility, J.ACM 22, 155–171.

[1983] Lerman, M., Degrees of Unsolvability, Springer–Verlag, Berlin.

[1982] Maass, W., Recursively enumerable generic sets, J. Symb. Logic 47, 809–823.

[1966] Martin, D., Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logic. Grund. Math. 12, 295–310.

[1970] Martin, D. and M. Pour.–El, Axiomatizable theories with few axiomatizable extensions, J. Symb. Logic 35, 205–209.

[1980a] Nerode, A. and Shore, R. A., Second order logic and first order theories of reducibility orderings, in The Kleene Symposium (K. J. Barwise et al., eds.), North–Holland, Amsterdam, 181–200.

[1980b] Nerode, A. and Shore, R. A., Reducibility orderings: Theories, definability and automorphisms, Ann. Math. Logic 18, 61–89.

[ta] Nies, A. and Shore, R. A., Interpreting true arithmetic in the theory of the tt and wtt degrees below 0′, in preparation.

[1981] Odifreddi, P., Strong reduciblities, Bull. Amer. Math. Soc. 4, 37–86.

[1989] Odifreddi, P., Classical Recursion Theory, North–Holland, Amsterdam.

[ta] Odifreddi, P., Classical Recursion Theory, vol. 2, North–Holland, Amsterdam.

[1976] Shoenfield, J., Degrees of classes of r. e. sets, J. Symb. Logic 41, 695–696.

[1985] Shore, R. A., The structure of the degrees of unsolvability, in Recursion Theory, Proc. Symp. Pure Math. 42, (A. Nerode and R. A. Shore, eds.), AMS, Providence, RI, 33–51.

[1990] Shore, R.A. and T.A. Slaman, Working below a low_{2} recursively enumerable degree, Archive for Math. Logic 29, 201-211.

[1993] Shore, R.A. and T.A. Slaman, Working below a high recursively enumerable degree, J. Symb. Logic 58, 824–859.

[1996] Slaman, T. and Woodin, H., Definability in Degree Structures, in preparation.

[1987] Soare, R. I., Recursively Enumerable Sets and Degrees, Springer–Verlag, Berlin.

[1969] Yates, C. E. M., On the degrees of index sets II, Trans. AMS 135, 249–266.