Lattice Embeddings below a Nonlow_{2} Recursively Enumerable Degree^{∗}

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

Richard A. Shore Mathematics Department Cornell University Ithaca NY 14853 USA

September 9, 1997

∗Research partially supported by NSF Grants DMS-9204308, DMS-93-44740, a US-NZ binational grant NSF 90-20558, the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell University Contract DAAL03-91-C-0027 and the IGC of Victoria University.

Abstract

We introduce techniques that allow us to embed below an arbitary nonlow_{2} recursively enumerable degree any lattice currently known to be embedable into the recursively enumerable degrees.

1 Introduction

One of the most basic and important questions concerning the structure of the upper semilattice R of recursively enumerable degrees is the embedding question: what (finite) lattices can be embedded as lattices into R? This question has a long and rich history. After the proof of the density theorem by Sacks [31], Shoenfield [32] made a conjecture, one consequence of which would be that no lattice embeddings into R were possible. Lachlan [21] and Yates [40] independently refuted Shoenfield’s conjecture by proving that the 4 element boolean algebra could be embedded into R (even preserving 0). Using a little lattice representation theory, this result was subsequently extended by Lachlan-Lerman-Thomason [38], [36] who proved that all countable distributive lattices could be embedded (preserving 0) into R. This last result pushed the Lachlan-Yates techniques to the limit since any embedding using their “minimal pair” method was, by necessity, distributive.

Lachlan [22] introduced some far more complex techniques which allowed one to embed the basic nondistributive lattices M_{5} and N_{5} of Figure 1

All of these successes tended to support the hypothesis that all lattices could be embedded into R. Lerman, however, suggested that the lattice S_{8} of Figure 1 could not be embedded (see Lerman [29]).

Lerman’s intuition turned out to be quite sharp: Lachlan and Soare [24] proved that in fact S_{8} is not embeddable into R. These embedding/ nonembedding results have been pushed quite a bit, the current state of affairs can be found in Ambos-Spies and Lerman [4], [5], where sufficient conditions are given for both embedability and nonembedability.

Figure 1: Basic Nondistributive Lattices Figure 2: A Nonembeddable Lattice

Another direction in lattice embedding questions was to look at fragments of R. Lachlan [23] proved that the diamond lattice could not be embedded into every initial segment of R preserving 0. On the other hand, Slaman [35] proved that the diamond lattice could be embedded into all nontrivial intervals of R, and again this result was extended to countable distributive lattices by Downey [10] and Ambos-Spies, Lempp and Soare. But here there is a difference from R. While N_{5} can be embedded into all nontrivial intervals (Ambos-Spies in [2], [11]), M_{5} cannot be embedded into all nontrivial initial segments Downey [11]. In fact, Cholak and Downey [6] have proven that if a < b then there is a c with a < c < b such that M_{5} cannot be embedded into [a, c]. Similar work has been done on embeddings preserving 1 (see Ambos-Spies, Decheng, Fejer [1]).

The present paper grew from an attempt to understand how the Turing jump operator relates to lattice embeddings. In particular, we look at the nonlow_{2} recursively enumerable degrees. Recall that a degree a is called low_{2} if a′′ = 0′′. For the global degrees, it is known (Fejer [18]) that any finite lattice can be embedded below a nonlow_{2} (in fact non-GL_{2}) degree. Also for strong reducibilities, it is known that “low_{2}-ness” has strong reflections in the degree structures. For instance, Downey and Shore [14] proved that an r.e. tt-degree a is low_{2} iff a has a minimal cover in the r.e. tt-degrees, and hence the low_{2} r.e. tt-degrees are definable in the r.e. tt-degrees.

In the present paper we introduce a new technique that enables one to embed lattices into the recursively enumerable degrees below an arbitrary recursively enumerable nonlow_{2} degree. We believe that the technique is sufficiently flexible to enable one to embed, below an arbitrary nonlow_{2} degree, any lattice currently known to be embeddable into R. We conjecture that

(1.1) If L is embeddable into R then L is embeddable below any nonlow_{2} recursively enumerable degree.

We remark that we cannot add “preserving 0” to (1.1) since it is known that there is a high_{2} r.e. degree not bounding a minimal pair (Downey-Lempp-Shore [12]).

In this paper we will prove (1.1) for the lattice M_{5}. We remark that M_{5} occupies a central role in all major embedding conjectures. This is because a_{1},a_{2},a_{3} in M_{5} form what is called, following Downey [11], a critical triple. That is, a_{1}∪a_{2} = a_{2}∪a_{3} and a_{1}∩a_{3} ≤a_{2}. For instance, it is conjectured that L is embeddable into all nontrivial intervals iff L contains no critical triples (Downey [11]). A similar conjecture has been made concerning the embedding conjecture. (Namely L is embeddable into R iff L has no pair “infing into a critical triple”).

The point about critical triples is that they seem to need the complex “continuous tracing” technique of Lachlan [22] and this interferes with both permitting and the delicate minimal pair machinery (which is why S_{8} is not embeddable). However, the intuition is that if b is “sufficiently high” then b will provide enough permissions. Indeed it is relatively easy to see that if b is high then one can embed M_{5} below b preserving 0 via Lerman’s pinball method. (This result is proved in another style in Weinstein [39]. Another approach to high permitting can be found in Shore-Slaman [34]). Our main construction proves that two jumps is enough. If b is nonlow_{2} then M_{5} is embeddable into [0, b].

We remark that while we have not checked that all the lattices of Ambos-Spies and Lerman [5] are embeddable via our technique, the method is sufficiently generic to seem to apply to those lattices, and M_{5} is only used as a representative example.

One might have hoped to generate a definition of low_{2} via our result, particularly in view of our results for tt-degrees [15]. It might seem reasonable to suggest that if a < b and b “sufficiently high over a”one should be able to embed a critical triple in [a, b]. However we have not even be able to prove that if a is low then one can embed 1-3-1 above a. In Cholak-Downey-Shore [7]) in fact it is shown that such an embedding cannot be done uniformly, and furthermore there is a low_{2} recursively enumerable degree a for which one cannot embed a critical triple either above or below a. Incidentally this result establishes that our result is the best posible in terms of the jump operator: one jump is not enough to embed 1-3-1 below a degree. [This can also be proven by combining the nonbounding construction of [11] with the construction form [15] of a promptly simple completely mitotic r.e. degree.]

The organization of the paper is as follows. In §2 we review the Lerman-Style [28] pinball embedding of M_{5} along the lines of Stob [37]. In §3 we prove how to incorporate “nonlow_{2}-permitting” to get the argument below an arbitrary nonlow_{2} degree.

Notation is standard and follows Soare [36]. We let all computations etc. be bounded by s at stage s and A[x] = {y|y ≤ x & y ∈ A}.

2 Embedding M_{5}

In this section we prove Lachlan’s result [22] that M_{5} is embeddable into R. We follow Lerman’s pinball [28] approach, along the lines of some old notes of Stob [37]. We present this (a) as an aid for the more complex arguments to follow, and (b) because there is no presentation of a pinball proof of Lachlan’s result in the literature, and we think there should be, as the proof clearly demonstrates the power of the technique.

(2.1)Theorem (Lachlan [22]). There exist non zero r.e. degrees a_{1}, a_{1}, and a_{3} such that a_{0} ∪ a_{1} = a_{1}∪ a_{2} = a_{2}∪a_{3} and, for all i ≠ j, a_{1}∩a_{j} = 0. Proof. (Stob[37], after Lerman [28]) We construct r.e. sets A_{i} with deg(A_{i}) =a_{i} to realize the required properties.

We use the pinball machine of Figure 2.

In addition to the procedures to produce the desired ordering of the degrees that we discuss below, we must meet the following requirements:

P_{e,i} : Φ_{e} ≠ A_{i} (i ∈ {0, 1, 2}, e ∈ ω). N_{e,i,j} : Φ_{e}(A_{i}) = Φ_{e}(A_{j}) = f total implies f recursive (i, j ∈ {0, 1, 2}, i ≠ j, e ∈ ω.)

Figure 3: The Pinball Machine 7

We associate hole H_{⟨e,i⟩} with P_{e,i} and gate G_{<e,i,j>} with N_{e,i,j}. As usual there will be various auxiliary functions:

ℓ(e, i, j, s) = max{x: ∀y < x[Φ_{e,s}(A_{i,s}; y) = Φ_{e,s}(A_{j,s}; y)}. mℓ(e, i, j, s) = max{0, ℓ(e, i, j, t): t < s}.

In general the motion of a ball is down. Balls may be follower balls (which are emitted from holes), or trace balls. A follower can have many traces. We denote follower balls by x = x_{e,n}^{i}. This notation indicates that x is targeted for A_{i} for the sake of requirement P_{e,i} and is our n^{th} attempt at satisfying P_{e,i}. Otherwise, a ball is of the form t_{e,i,m}^{j}(x) which indicates it is targeted for A_{j} and is the m^{th} trace of the trace entourage: (2.3) x_{e,n}^{i}, t_{e,i,1}^{j_{1}}, t_{e,i,2}^{j_{2}}, ..., t_{e,i,m}^{j_{m}}

When the meaning is clear, we shall drop some of the subscripts. Note that since for all i ≠ j ≠ k, we must guarantee that

(2.4) A_{i} ≤_{T} A_{j} ⊕ A_{k},

We are committed to coding A_{i} into A_{j} ⊕ A_{k}. This is what the traces are used for. The underlying idea is that if y enters the set A_{i} for which it is targeted, then y is either a trace or a follower. We promise that either y enters A_{i} by stage y + 1, or y will have a trace. If y is targeted for A_{i} then y’s trace will be targeted for A_{j} or A_{k}. Thus in the entourage (2.3), if p < q then t_{q} must enter its target set before, or at the same stage as t_{q}. If t_{q} enters then either t_{q−1} also enters, or t_{q−1} gets a new trace at the next stage. In this way we work to insure (2.4).

The priority of a ball is the same as that of the follower in its entourage. The priority of a follower is a pair consisting of first the requirement it follows, and second the order of appointment so that x_{n} has higher priority than x_{m} if n < m. (The priority ordering is the lexicographic ordering of pairs.) Finally, the surface of the machine is defined to be the section not including the pockets, and the track is the section of the surface not including corrals or holes.

The key observation of Lachlan was that a requirement N_{e,i,j} is only concerned with entry of elements into both A_{i} and A_{j} between expansionary stages (we assume that the reader is familiar with the minimal pair technique as in Soare [36]). How could that happen? Thinking of the N_{e,i,j}’s as gates, this happens whenever a pair (or more) of balls y^{i} and y^{j} attempt to simultaneously pass a gate. Now one of these (y^{j}, say) is a trace of the other. The idea is to allow y^{j} to enter A_{j} first and then hold y^{i} at the gate G_{e,i,j} until we can retarget by appointing a trace y^{k} in place of y^{j}. Then the new pair y^{i}, y^{k} can pass together at the next N_{e,i,j}-expansionary stage.

Surprisingly, this local action is enough to allow one to embed M_{5}. We now turn to some details.

At stage s + 1 we say a ball y requires attention if (2.5) y is the least ball at gate G_{e,i,j} and ℓ(e, i, j, s) > mℓ(e, i, j, s), or (2.6) y is the least ball above hole H_{e,i} and Φ_{e,s}(y) = 0.

We say that P_{e,i} requires attention if some ball associated with P_{e,i} requires attention, or P_{e,i} is not met and there is no ball above hole H_{e,i}.

. Construction, Stage s

Step 1 Find the highest priority requirement, and then, if relevant the highest priority ball that requires attention. Cancel all lower priority balls on the surface of the machine. Adopt the appropriate case below. Case 1 (2.5) holds: Action Allow y and all its descendents via tracehood (i. e. all later (= larger) balls in the same entourage as y) to drop to the first unoccupied gate G_{p} (if such a gate exists). Then put all of these balls except the largest one into corral C_{p}, and put the largest (=last) one (which will be the most recently appointed descendent) at gate G_{p}. If no such gate exists, put all the balls of this set into their respective target sets. In this case, if y is a follower, declare that P_{e,i} is met and cancel all balls associated with P_{e,i}. Otherwise we claim that (2.7) If y is a trace, it is the trace of some ball z in a corral C_{t} and, furthermore, G_{t} is empty.

Given (2.7), remove z from C_{t} and put it at gate G_{t}.

Case 2 (2.6) holds: Action Allow y and all its descendents to drop from the hole H_{e,i} and along the chute to the track, and then proceed as in Case 1. Case 3 P_{e,i} has no ball above H_{e,i}: Action Appoint a new fresh number (x = ⟨e, i, s⟩, say) and place it above hole H_{e,i}. Label x by x_{e,n}^{i} where n = 0 if P_{e,i} has no uncancelled followers and n is the number of uncancelled followers previously assigned otherwise.

Step 2 (Trace appointment) At the end of step 1 give a trace to each number on the surface currently without a trace. Use some large fresh number. Traces are given according to the following rule. If y is targeted for A_{j} and y needs a trace then we claim that (2.8) y is either at a hole H_{e,p} or y is at a gate G_{e,p,q}.

Furthermore we claim (2.9) if y is at a gate or a hole, then y will either be alone, or a member of a j, k-stream at the gate or hole. A j, k-stream is a collection of balls, each related to the next by tracehood with y at the end, each alternatively targeted for A_{j} then A_{k}.

Thus a (1, 2) - stream would, for example, look like

t_{n}^{1}, t_{n+1}^{2}, t_{n+2}^{1}, ....., t_{n+m}^{j} = y.

If y is a member of such a j, k-stream, target y’s new trace for A_{k}. Otherwise, if y has no trace and y is at a gate G_{e,p,q}, target y’s trace for k ≠ p, q and k ≠ j, and if j ≠ p, q then pick k = p. Finally, if y has no trace and is at a hole H_{e,p} target y’s trace for any k ≠ j (since y will be a follower targeted for A_{j}). (2.10) Claim: If a gate or hole has a i, j-stream at the end of step 1, then it has an i, j-stream at the end of step 2.

End of construction

The following Lemma is easily established by induction.

(2.11) Lemma (i) All the claims (2.7)-(2.10) made in the construction hold at each stage s.

(ii) At any stage s if x, y_{1}, ...., y_{n} is an entourage of balls (with y_{1} a trace of x, and y_{j+1} a trace of y_{j}) which is on the surface at stage s, then either all of x, y_{1}, ...., y_{n} are in a hole, or there exist i_{1} < i_{2} < ... < i_{k} and j_{1} > j_{2} > ... > j_{k} such that

the balls in {x, y_{q}: q < i_{1}} are in corral C_{j_{1}},

the balls in {y_{q}: i_{1} ≤ q < i_{2}} are in corral C_{j_{2}},

...............

the balls in {y_{q}: i_{k−2} ≤ q < i_{k−1}} are in corral C_{j_{k−1}}, and the balls in {y_{q}: i_{k−1} ≤ q ≤ i_{k}} are at gate G_{j_{k−1}}.

(2.12) Lemma Only finitely many balls associated with a given follower receive attention. Proof There is nothing to prove unless the ball leaves the hole. Suppose x, y_{1}, ...., y_{n} leave H_{e,i}. Now either they enter their respective target sets (done) or they get placed in a corral C_{e_{1}}, associated with a gate G_{e_{1}} with the last y_{n}, placed at gate G_{e_{1}}. Note that no more balls associated with x receive attention unless y_{n} moves from gate G_{e_{1}}. Now there are two possibilities. The first is that y_{n} actually enters its target set at some stage s_{n}, at which point, by (2.11) we know that x, y_{1}, ..., y_{n−1} will be the only balls associated with x currently on the surface, and that y_{n−1} will be placed at G_{e_{1}}. We can then argue a fortiori for y_{n−1} in place of y_{n}. The other possibility is that y_{n} does not enter its target set. But this means that either it never leaves G_{e_{1}} (done) or it gets cancelled (cancelling x) or it gets stuck at a gate G_{e_{2}} or corral C_{e_{2}} for some e_{2} but with e_{2} < e_{1}. Repeating this reasoning at e_{2} and using the fact that e_{2} < e_{1} we see that the process must stop. If y_{n} is never cancelled some descendent of y_{n}, or y_{n} itself, must get stuck forever at a gate G_{e_{f}} for some e_{f} ≤ e_{2}, and when this ball gets to G_{e_{f}}, all balls associated with x will cease receiving attention.

(2.13) Lemma. If a gate G_{q} has permanent residents, these permanent residents are an i, j-stream of a single ball y (for some i, j, y), and, in particular, all have the same priority. Proof When a ball moves it cancels all lower priority balls. Balls only stop at unoccupied gates.

(2.14) Lemma. All the P_{e,i} receive attention at most finitely often and are met. Proof. By induction: Assume the lemma for all P_{q} with q < ⟨e, i⟩. Let s_{0} be the least stage by which all balls currently associated with P_{q} are in their final positions, and P_{q} does not receive attention after stage s_{0}. [So all that can happen is that various entourages get longer, but no balls move.]

Assume P_{e,i} fails to be met, arguing by the minimality of s_{0}, we can suppose that P_{e,i} has no uncancelled followers at stage s_{0}, but is given one above hole H_{e,i} at stage s_{0} + 1. Since such a follower x_{0} is uncancellable (assuming P_{e,i} fails to be met), since x_{0} fails to succeed in meeting P_{e,i}, it must get stuck permanently at a gate G_{q} or at a corral C_{q} for some q < ⟨e, i⟩. If it gets stuck at a corral, it must be because some descendent of x gets stuck at a gate G_{q} for some q′ ≤ q. Thus x’s failure to meet P_{e,i} causes (2.15) a gate G_{q} for some q < ⟨e, i⟩ to be permanently occupied by either x or a descendent of x.

Note that after the stage s_{1} when the relevant gate first gets its permanent resident associated with x, no ball associated with x ever again moves. (They are all in corrals waiting for this permanent resident to move.) It follows that no follower appointed to P_{e,i} after stage s_{1} can be cancelled by the x-entourage. One sees that the first follower x_{1} appointed to P_{e,i} after s_{1} must have a statement analogous to (2.15) applying to it or one of its descendents at some gate G_{q′}. But since G_{q} is occupied and balls don’t stop at occupied gates, we see that q′ ≠ q. But now it is clear that since there are only ⟨e, i⟩ many gates below H_{e,i} some follower of P_{e,i} must succeed.

(2.16) Lemma. All the N_{e,i,j} are met. Proof. For an induction, suppose s_{0} is a stage by which all the P_{q} for q < ⟨e, i, j⟩ have ceased acting, in the sense that P_{q} never again receives attention. Suppose that Φ_{e}(A_{i}) = Φ_{e}(A_{j}) = f total. We show how to compute f(x) recursively. First, let s_{1} > s_{0} be a stage such that, for all gates G_{q} with q < ⟨e, i, j⟩, if G_{q} has any permanent residents, it has one by stage s_{1}. Now, given x, to compute f(x) find a stage s = s(x) > s_{1} such that (2.17) (i) ℓ(e, i, j, s) > x (ii) For all q ≤ ⟨e, i, j⟩ if G_{q} has any residents at all, it has permanent residents.

Note that, from the assumption that Φ_{e}(A_{i}) = Φ_{e}(A_{j}), (i) must occur cofinitely often. We can compute s(x) recursively from the parameters s_{1} and the least permanent residents of the relevant gates below G_{e,i,j}, provided that we argue that (2.17) (ii) occurs infinitely often. To see this last claim, suppose t > s_{1}. We claim that (2.17) (ii) will occur for some stage u > t. If (2.17) (ii) does not hold at stage t, then there must be some ball at or below gate G_{e,i,j} that is not a permanent resident. The highest priority such ball must either enter its target set, or get cancelled. If the former, then at that stage (2.17) (ii) must hold (its movement cancels lower priority balls); if the latter, then at the stage it is cancelled either (2.17) (ii) holds, or a ball of higher priority that is not a permanent resident of any gate or corral must be below G_{e,i,j}. But now we can apply a similar argument to the new ball and again appeal to the wellordering of the priority ordering. Thus (2.17) (ii) holds.

Now the argument is straightforward. At stage s we have (2.18) Φ_{e,s}(A_{i,s}; x) = Φ_{e,s}(A_{j,s}; x).

We claim the following. (2.19) For all stages t ≥ s, one of the following holds.

Φ_{e,t}(A_{i,t}; x) = Φ_{e,s}(A_{i,s}; x), or
Φ_{e,t}(A_{j,t}; x) = Φ_{e,s}(A_{j,s}; x).

And so furthermore both of the statements of (2.19) will hold at stages where ℓ(e, i, j, s) > mℓ(e, i, j, s), i.e. when the gate opens.

Suppose that (2.19) fails. Let w be the first stage after s at which it fails. Some number must enter A_{i} or A_{j} at stage w, say the smallest such number is y and it enters A_{j}. Consider the stage v ≤ w at which y passed gate G_{e,i,j}. If the gate G_{e,i,j} had been occupied at v, it would have been occupied by some ball z of higher priority than y which reached the gate at a stage u < v. By the leastness of w, (2.19) held at u. All balls of lower priority than z were cancelled at stage u and as z is still at the gate at stage v (when y went by) and indeed still there at stage w (since otherwise y would have been canceled), no ball of higher priority has moved since stage u. As all numbers appointed after stage u (including y) are large (and so larger than the Φ_{e} use at u), no numbers less than the use of the computation verifying (2.19) at u have entered either set by the end of stage w and so (2.19) would hold then contrary to our assumption. On the other hand, if G_{e,i,j} was empty when y reached it, y stopped at the gate and when it passed Φ_{e,v}(A_{i,v}; x) = Φ_{e,v}(A_{j,v}; x) = Φ_{e,s}(A_{i,s}; x). Now when y (which is targeted for A_{j}) passes G_{e,i,j} it is a member of a j, k-stream and so only numbers targeted for A_{j} or A_{k} pass the gate but none targeted for A_{i}. All balls of lower priority are cancelled at v, none of higher priority have moved by w, and all appointed in between are larger than the Φ_{e} use from A_{i} at v. Thus, no changed has occurred in A_{i} on this use from stage v to the end of stage w and so Φ_{e,w}(A_{i,w}; x) = Φ_{e,s}(A_{i,s}; x) as required for the desired contradiction.

(2.20) Lemma A_{i} ≤_{T} A_{j} ⊕ A_{k} for i ≠ j ≠ k. Proof To decide if x ∈ A_{i} go to stage x + 1. If x ∉ A_{i,x+1} and x is not currently a trace or a follower targeted for A_{i}, x ∉ A_{i}. If x is a follower or a trace then as x is alive at stage x + 1 it has a trace t_{1} targeted for one of A_{j} or A_{k} if t_{1} ∉ A_{j} and t_{1} ∉ A_{k} then x ∉ A_{i}. However, if t_{1} enters its target set, then either x enters at the same stage, or it has been in a corral C_{e_{1}}, is placed at gate G_{e_{1}} and gains a new trace t_{2}. If t_{2} enters its target set then x will actually move to a new gate G_{e_{2}} with e_{2} < e_{1}. It follows that only finitely many traces can be appointed for x as traces are only changed if the previous trace enters its target set, and hence A_{i} ≤_{T} A_{j} ⊕ A_{k}.

(2.21) Comment. The above proof is transparently amenable to high permitting in the same way as, say, the minimal pair. As in Cooper [8], we use upper and lower gates to add “e-dominant permission” for leaving gates. (See Cooper [8] or Soare [36], page 222, Ex 2.15 for further details) The point here is that high permission = “almost all” permission. That is, as a corollary to the construction we see that below any high r.e. degree one can embed M_{5} preserving 0. (This result was proved in Weinstein [39] by a somewhat different construction. See also Shore-Slaman [34] for another approach to high permitting.) This leads one to conjecture the following.

High Embedding Conjecture: If L is embeddable into R (preserving 0), then L is embeddable below an arbitrary high r.e. degree (preserving 0).

Of course the results of the present paper support our other conjecture: Nonlow_{2} Embedding Conjecture If L is embeddable into R then L is embeddable below an arbitary nonlow_{2} r.e. degree.

3 The Main Result

(3.1) Theorem. Suppose that B is a nonlow_{2} r.e. set of degree b, then there exists an embedding of M_{5} into the degrees below b.

The main additional ingredients to the construction of §2 are (i)the use of “nonlow_{2}” permitting to enable the construction to work below b and (ii) the addition of a set C for the 0 of the M_{5} allowing us to “shorten” our tracing procedure when waiting for permission from B.

The key to “nonlow_{2}” permitting is the following: (3.2) a degree b is nonlow_{2} iff for every function h ≤_{T} ∅′ there is a function g recursive in b such that g is not dominated by h.

In the study of the global degrees, or even those below 0′, (3.2) is used 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” within which one should search for witnesses to satisfy the relevant requirements. Due to the specific nature of the requirements in question, it will be the case that h ≤_{T} ∅′. The idea is to then use g to b-recursively bound searches and make the construction an oracle one recursive in b. By the way h and g are constructed, (∃^{∞}s)(g(s) > h(s)), so we can guarantee, with a priority argument, that all requirements get met.

In [14], the authors introduced techniques to “fully approximate” the above method so as to allow it to work in the r.e. degrees. Specifically, the natural idea is to approximate h and g via the limit lemma. Now we are given an r.e. set B and a “witness” function h ≤_{T} ∅′. We use a recursive approximation h(x, s) to h such that h(x) = lim_{s} h(x, s) and view g as Γ(B). Thus Γ_{s}(B_{s}: x) admits a suitable approximation g(x, s) with lim_{s} g(x, s) = g(x). As we observed in [14], the serious obstacle we must overcome is that, not only must the construction be recursive in B, but additionally the sets constructed must be recursively enumerable.

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 B, 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 ∈ B_{s+1} − B_{s}) and z < g(x, s). (iii)If g(x, s + 1) ≠ g(x, s) then g(x, s + 1) > h(x, s + 1). (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.

In our specific construction, h will be generated by considering the witnesses for the “Friedberg” type requirements, together with the nature of the permissions needed for the relevant balls to move down the machine. We will code all such behavior into h.

Turning now to the construction at hand, we must build A_{0}, A_{1}, A_{2}, C all recursive in B such that, for i ≠ j ≠ k, A_{i} ≤_{T} A_{j} ⊕ A_{k} ⊕ C and to meet the new requirements

P_{e,i} : Φ_{e}(C) ≠ A_{i}
N_{e,i,j} : Φ_{e}(A_{i} ⊕ C) = Φ_{e}(A_{j} ⊕ C) = f total implies f ≤_{T} C.

Here the degrees of C, Â_{i} = A_{i} ⊕ C and Â_{0} ⊕ Â_{1} ⊕ Â_{2} form the embedding of M_{5} below b. The construction is almost the same as the one for embedding M_{5} given in the previous section. Of course, there are the obvious changes caused by having C in the oracles. In particular the definitions of the length of agreement functions ℓ, mℓ use A_{i} ⊕ C in place of A_{i} (for i = 0, 1, 2). In addition, we add a “permitting bin” to the machine. When, in the previous construction, any sequence of balls (all part of the entourage of a single follower x) would be allowed to fall through the gates and enter their respective target sets, we now put them into the permitting bin and add a trace targeted to C to the end of the sequence and wait for permission from B in the form of a change of g(n, t) where n is the “permitting number” assigned to x. While we are awaiting a permission, the rest of the elements of x’s entourage sit at their current places in the corrals and no action is taken for them. When permitted in this way, we will put all the balls in this sequence into their target sets and resume our previous activity for the last ball of the entourage still on the surface of the machine. (It will roll out onto the gate for its corral which will necessarily be unoccupied: If it had been occupied by a ball of lower priority the ball would be cancelled when we put the numbers into their target sets. If it is occupied by a ball of higher priority which arrived at the gate after these balls then they would have been cancelled along with the ones now in the permitting bin. If the higher priority ball was at the gate when our ball passed, no elements of its entourage stopped in the corral.

Formally, modulo the definition of h (and therefore with g unspecified), the construction runs as follows:

At stage s + 1 we say a ball y requires attention if one of the following pertains. (3.8) For some n, y is the least number in the permitting bin with permitting number n and g(n, s + 1) ≠ g(n, s). (3.9) y is the least ball at gate G_{e,i,,j} and ℓ(e, i, j, s) > mℓ(e, i, j, s). (3.10) y is a follower of P_{e,i} at hole H_{e,i} and Φ_{e,s}(C_{s}; y) = A_{i,s}(y) = 0.

We say that the requirement P_{e,i} requires attention at s if either some ball y associated with P_{e,i} requires attention, or (3.11) P_{e,i} is not currently met and P_{e,i} has no follower at hole H_{e,i}.

Construction, stage s Step 1 Find the highest priority requirement P_{e,i}, then the highest priority ball y (if relevant) that requires attention. Cancel all lower priority balls on the surface. Adopt the appropriate procedure of the ones listed below. Case 1 (3.8) holds: Put all balls with permitting number n that are now in the permitting bin into their target sets. If this meets the requirement (i. e. a follower of P_{e,i} is put into its target set A_{i}) do nothing else. Otherwise, find the corral C_{d} containing the ball x for which y is the trace. Put the ball at gate G_{d}. (We here are claiming that the analog of (2.7), call it (2.7′) that the ball x of which y is a trace is in some coral C_{d} and that G_{d} is empty.) Case 2 (3.9) holds. Allow y and all its descendents via tracehood (i. e. all later (= larger) balls in the same entourage as y) to drop down to the first unoccupied gate G_{p} (if such a gate exists). Then put all of these balls except the largest one into corral C_{p}, and put the largest (=last) one (which will be the most recently appointed descendent) at gate G_{p}. If no such gate exists, put all the balls of this set into the permitting bin and attach a trace t^{C} targeted for C to the last ball in this set. Case 3 (3.10) holds. Release the balls in H_{e,i} from the hole and let them enter the chute. Now proceed as in (3.9). Case 4 (3.11) holds. Suppose there are n as yet uncancelled followers of P_{e,i}. Appoint a large fresh follower x = x_{e,n}^{i} at hole H_{e,i} and let x’s permitting number be n + 1. Step 2 At the end of step 1, give a new large trace z to each ball y on the surface which does not have a trace and is not targeted for C, as in §2. The trace z has the same permitting number as y. End of Construction

As in §2 the reader can easily see that (2.7′)-(2.10), and (2.13) still hold, and that (2.11)(ii) holds with the adjustment that {y_{q}: i_{k−1} ≤ q ≤ i_{k}} can be either at gate G_{j_{k−1}} or in the permitting bin. However, the proof of (2.14) now needs the definition of g(n, s) which depends on the as yet unspecified definition of h(x, s). Before we can verify the remainder of the construction, we need to describe the required function h.

(3.12) Definition of h (Multiply inductive permitting).

We will define a family of functions h_{k} uniformly recursive in 0′ so that for each requirement P_{e,i}, there will be some k (that will depend on the stage s_{e,i} after which no action is taken for any requirement of higher priority and by which each gate of higher priority with permanent residents already has one) such that if g is not dominated by h_{k} then we will satisfy P_{e,i}. (When we say that a family of functions (or sets) F is uniformly recursive in 0′ we mean that there is a set A recursive in 0′ such that F = {{e}^{0′}| e ∈ A}.) The actual single function ĥ recursive in 0′ that we need will then be any one dominating all the h_{k}. To motivate the definition of this family of functions consider the permissions that would be needed to satisfy a requirement P_{e,i} with only one gate G below it by its first follower x_{e,1}^{i} appointed at a stage after all action for higher priority positive requirements has ceased and such that if G has a permanent resident it already has one.

Suppose x_{e,1}^{i} is realized at stage s and its entourage at the beginning of stage s is (3.13) t_{1,1}, ..., t_{1,m} with m < s.

If G is now occupied, we put the entire entourage with a trace t_{m+1}^{C} at the end targeted for C into the permitting bin. In this case, we need only one permission via a change in g(1, t) after s to satisfy P_{e,i}. Otherwise, t_{1,m} is put at G and the rest of the entourage is placed in G’s corral. We now wait for a stage s_{1} at which G opens. At that time we put the final segment of the entourage beginning with t_{m} into the permitting bin with a trace t^{C} added to the end. We then would need g(1, t) to change once after s to allow t_{1,m} to t^{C} to enter their target sets. Should this occur, we would take t_{1,m−1} out of the corral and place it at gate G where it would begin to acquire a sequence of traces continuing its entourage. At the stage at which the gate G reopens t_{1,m−1}, together with the later elements of its entourage (including a new trace targeted for C at the end), enters the permitting bin. We would then need another permission to allow t_{1,m−1} to enter its target set and continue the procedure. Thus in all we would need at most s many permissions from g(1, t) if they came at the required times.

Our plan is to define an appropriate function h in our family so that the definition of h(1) forces enough changes at the required times in g(1, t) (assuming g(1) > h(1)). If we could define the recursive approximation to h(1) along with the construction, we could increase it every time we wanted a permission. When we get the permission, we then wait until we want another one, say at t, to again increase h(1). As we would make h(1) larger than t at t, the nature of our approximation to g (property (v)) would force g(1, v) to change after t as required. Such a definition of h seems to need the recursion theorem. However, as explained in Downey and Shore [14], we cannot simultaneously define h with the construction and still get to use a g recursive in B as required. Thus we must define a family of functions in advance which will include all possible ones desired in the construction. We do this in two stages. The first step is to define a family of functions so that for requirement P_{e,i} there is a function f_{e,i}(n) in the family that bounds the number of changes needed to satisfy the requirement via (some version of) its n^{th} follower x_{e,n}^{i}. The second phase of our definition will circumvent the apparent need for the recursion theorem by defining a family of auxiliary r.e. sets so that for each e, i there will be a member of the family V_{e,i} so that at most f_{e,i}(n) many numbers are enumerated in its n^{th} column, V_{e,i}^{[n]}. We will then let h_{e,i}(n) be the last stage at which a number is enumerated in V_{e,i}^{[n]}. The V_{e,i} that we need is the one that gets an element enumerated in its n^{th} column when we need a change in g(n, t) to make progress on the current version of P_{e,i}’s n^{th} witness x_{e,n}^{i}. As enumerating such a number at a stage v forces h_{e,i}(n) to be bigger than v, and g(n, t) can become larger than v only at stages larger than v, we would have to get the desired change at a stage when we could use it (i. e. after stage v). The fact that we have a family f_{e,i} of functions uniformly calculable in 0′ bounding the number of times this can happen allows us to make the required functions h_{e,i} uniformly recursive in 0′.

To define the first family of functions, let us return to the example of a requirement P_{e,i} and a stage u = s_{e,i} after all action for higher priority positive requirements has ceased that has only one gate G below it which already has a permanent resident if it ever gets one. We want to define a class of functions uniformly recursive in 0′ which will include one f_{e,i,u} = f such that f(n) bounds the number of times we need permission to satisfy P_{e,i} by a version of the n^{th} follower x_{e,n}^{i} appointed after stage u. We describe these functions in terms of a bound on the number of times a recursive approximation f(n, s) to f(n) changes. Of course, we must arrange that the family of functions so described is uniformly recursive in 0′. Now as we described above, the first witness x_{e,1}^{i} appointed at s > u is never cancelled and, once realized at s_{1}, can act though any of its descendants at most s_{1} many times. Thus the approximation f(1, s) changes at most once. A version of the second witness x_{e,2}^{i} can act in the same way but can be cancelled (along with all its descendants) when we act for x_{e,1}^{i} or one of its descendants. Thus the value of f(2, s) can change f(1) many times. Similarly, the value of f(n + 1, s) can change f(n) many times. Thus we can specify a family of functions F which are uniformly recursive in 0′ and include one f such that f(n) bounds the number of times we might have to act for any number appointed as x_{e,n}^{i} or its any of its descendants: F = {f| f(0) = 1 ∧ (∃ recursive f(n, s)) (∀n > 0)(lim f(n, s) = f(n) ∧

|{s|f(n + 1, s) ≠ f(n + 1, s + 1)| ≤ f(n))}

It is clear that given any partial recursive function ϕ we can recursively in 0′ calculate, for each n ≥ 0 in turn, f(n) = lim ϕ(n, s) and then verify that ϕ(n + 1, s) does not change more than f(n) many times. As long as ϕ does not fail the test in terms of the number of times it changes, we successively calculate the values of f(n). If ϕ ever fails by changing too often or being undefined, we declare f to be constant from that n onward. Thus, we may compute a family of representatives of F uniformly recursively in 0′. (We remark that it is clear that we can go effectively in 0′ from an index for ϕ as a partial recursive function to an index of f as a function recursive in 0′. The situation for G below is the same.)

Consider next a requirement P_{e,i} with two gates G_{2}, G_{1} below it. Once again, the first witness x_{e,1}^{i} appointed after all requirements of higher priority have ceased acting (and the gates have their permanent residents) is never cancelled. It can be realized at a stage s_{1} when it and its entourage of at most s_{1} many element falls down to G_{2} (if unoccupied, the worst case scenario). One element may sit at the gate while the others are put into the corral. While sitting at the gate G_{2} a descendant of x_{e,1}^{i} gets its own entourage of traces. This trace appointment procedure stops when the gate opens say at s_{1,1} The descendant of x_{e,1}^{i} and the later part of its entourage (of size at most s_{1,1}) fall down to the next gate G_{1} (again, if unoccupied). There they are faced with the same situation as a ball and its entourage arriving from the hole with only G_{1} below it. In other words, each member of the entourage in turn rolls out to the gate and waits for it to open (at which point it is put into the permitting bin together with the latter part of the entourage ending with a trace targeted for C). Later followers x_{e,n}^{i} of P_{e,i} may follow the same route except that they (and all their descendants) may be cancelled each time action is taken for some x_{e,m}^{i} for m < n or one of its descendants). Thus to measure the number of changes, f(n), needed for x_{e,n}^{i}, we calculate in terms of a recursive approximation f(n, s) as follows:

f(1, s) changes (from 1 to s_{1}) when x_{e,1}^{i} is realized at s_{1}. Thereafter, it may change s_{1} many times.

f(2, s) can go through the same changing procedure as did f(1, s) each time f(1, t) changes.

f(n, s) can go through the same procedure as f(1, s) each time f(i, t) changes for any i < n. We thus see that there is a function g ∈ F such that f(n) = g(2n). Similarly, if there are m many gates below P_{e,i} , f(1) changes once at s_{1} when realized and then s_{1} many times at G_{m} for each of which it may change again at G_{m−1} etc. In general, then a function f(n) bounding the number of actions needed for a P_{e,i} with m gates below it can be given by f(n) = g(mn) for some g ∈ F. We therefore define our first family of functions G as follows:

G = {g|∃f ∈ F∃m∀n(g(n) = f(mn)}.

As (a set of representatives for) F is uniformly recursive in 0′, it is easy to see that so is (one for) G.

For the next step, we define a class V of r.e. sets which for each requirement P_{e,i} will include one W that enumerates a number into its n^{th} column W^{[n]} whenever a descendant of some x_{e,n}^{i} needs permission to enter A_{i}.

V = {W_{i}|(∃g ∈ G)(∀n)(|W_{i}^{[n]}| ≤ g(n)}.

Once again, it is easy to construct a family of representatives of V which is uniformly recursive in 0′. Again, when we say that V, which happens to be a family of r.e. sets, is uniformly recursive in 0′, we mean, as above, that there is a set A recursive in 0′ such that V = {{e}^{0′}| e ∈ A} and each W ∈ V is r.e. but not that we can find an r.e. index for it uniformly in 0′. (Again we try each W_{i} and each g ∈ G and when the pair fails the test we switch to the empty set. This gives us a set recursive in 0′ which is r.e. but not, uniformly, its index as an r.e. set.)) We can then define our final family of functions which are again uniformly recursive in 0′:

H = {h|(∃W ∈ V)(∀n)(h(n) is the last stage at which

a number is enumerated in W^{[n]})}.

Note that for H we again use guesses at the r.e. index i for each W ∈ V and when one fails we make the corresponding h constant.

Our required function ĥ can now be taken to be any function recursive in 0′ which dominates every function in H. We then choose a g recursive in B which is not dominated by ĥ to use in the construction described above. We can now argue that the required lemmas are correct.

(3.13) Lemma. Each requirement P_{e,i} (including the balls associated with it) receives attention at most finitely often and is met.

Proof By induction, we may assume that there is a stage u such that no requirement of higher priority (or ball associated with it) requires attention after stage u. We may also assume that all gates of higher priority that have a permanent resident have one by stage u. As in the basic construction (2.14) no ball associated with P_{e,i} can be hereafter be permanently stuck at any gate. Some of them may, however, be stuck in the permitting bin forever. We assume by induction that the action for descendants of any follower labelled x_{e,k}^{i} k < m are finite. Consider then the history of a follower x_{e,m}^{i} after a stage s by which all action for descendants of followers x_{e,i} for k < m have stopped. Once a follower x_{e,m}^{i} is appointed after s, it is never cancelled. If x_{e,m}^{i} is never realized, no further action is taken for P_{e,i} which is then satisfied. Otherwise, it is realized. Note that when realized all lower priority balls are cancelled and all later ones appointed are larger than the C use of the realizing computation. No ball of higher priority ever enters C (or any other set) by assumption. Thus once realized after s, the associated C computation Φ_{e,i}(C; x_{e,m}^{i}) = 0 is correct forever. Now, the follower x_{e,m}^{i} either eventually enters A_{i} and so satisfies P_{e,i} (causing all action for P_{e,i} to cease) or it or one of its descendants is permanently stuck in the permitting bin. We must show that not every x_{e,m}^{i} can have a descendant stuck in the permitting bin.

By our choice of g there is an m > u such that g(m) > h(m) where h ∈ H is the function associated with the r. e. set W which gets a number enumerated in its j^{th} column whenever a ball in the entourage of a follower x_{e,j}^{i} enters the permitting bin. Our analysis above of how often this can happen and the definitions of F, G, V and H guarantee that there is such a function h ∈ H. We now claim that every time a descendant of some follower x_{e,m}^{i} enters the permitting bin, it is later permitted and so enters its target set. This clearly suffices. If some descendant y of a follower x_{e,m}^{i} enters the permitting bin at t then an element is enumerated in W^{[m]} at t. Thus h(m) > t.

As g(m) > h(m), g(m) > t. By convention (v) on our recursive approximations to g, there is a v > t such that g(m, v) ≠ g(m, v +1). Our construction then guarantees that y would then be put into A_{i} as required.

(3.14) Lemma. All the N_{e,i,j} are met, i. e. Φ_{e}(A_{i} ⊕ C) = Φ_{e}(A_{j} ⊕ C) = f total implies f ≤_{T} C.

Proof The argument is very like that for (2.16) with some changes to take into account the new set C being constructed at the bottom of the lattice. Let s_{0} be a stage after which no ball associated with any requirement of higher priority than N_{e,i,j} ever receives attention. Suppose that Φ_{e}(A_{i} ⊕ C) = Φ_{e}(A_{j} ⊕ C) = f total. We show how to compute f(x) recursively. First, let s_{1} > s_{0} be a stage such that, for all gates G_{q} of higher priority than N_{e,i,j} (i. e. with q < ⟨e, i, j⟩), if G_{q} has any permanent residents, it has one by stage s_{1}. Now, given x, to compute f(x) find a stage s = s(x) > s_{1} such that

(i) ℓ(e, i, j, s) > x (ii) For all q ≤ ⟨e, i, j⟩ if G_{q} has any residents at all, it has permanent residents. (iii) Every ball in the permitting bin at s which is less than the use of either computation at x, ϕ_{e,s+1}(A_{i} ⊕ C; x) and ϕ_{e,s+1}(A_{j} ⊕ C; x), remains there forever.

Note that any ball y in the permitting bin has a sequence of traces ending with one t^{C} targeted for C. The entire sequence of elements enter their respective target sets simultaneously and so y leaves the permitting bin (necessarily to enter its target set) iff t^{C} ∈ C. Thus, given the parameters s_{1} and the least permanent residents of the relevant gates below G_{e,i,j}, we can determine recursively in C if a stage s satisfies the required conditions. We must now argue that, for each x, (i)-(iii) are simultaneously satisfied some stage s and that the procedure described correctly computes f(x).

For the first claim, note that, as Φ_{e}(A_{i} ⊕ C) = Φ_{e}(A_{j} ⊕ C), we may assume that ℓ(e, i, j, s) > x and (iii) holds for every s > s_{2} for some s_{2} > s_{1}. If (ii) does not hold at some stage t > s_{2}, then there must be some ball y < ϕ_{e,t}(A_{i} ⊕ C; x) or ϕ_{e,t}(A_{j} ⊕ C; x) at or below gate G_{e,i,j} (perhaps in the permitting bin) that is not a permanent resident. The highest priority such ball must either enter its target set, or get cancelled. If the former, then at that stage (i)-(iii) must hold (its movement cancels lower priority balls none of higher priority could pass G_{e,i,j} without cancelling y); if the latter, then at the stage it is cancelled either (ii) holds, or a ball of higher priority then y that is not a permanent resident of any gate or corral must be below G_{e,i,j}. But now we can apply a similar argument to the new ball and eventually appeal to the well-ordering of the priority ordering to see that this process must terminate at a stage at which (i)-(iii) hold.

Now we must argue that at any stage z satisfying (i)-(iii), Φ_{e}(A_{i} ⊕ C; x) = Φ_{e}(A_{j} ⊕ C; x) = f(x). At stage z we have Φ_{e,z}(A_{i,z} ⊕ C_{z}; x) = Φ_{e,z}(A_{j,z} ⊕ C_{z}; x) and C is correct on the associated uses (ϕ_{e,z}(A_{i}⊕C_{z}; x) and ϕ_{e,z}(A_{j,z} ⊕C_{z}; x)) as any trace targeted for C is always in the permitting bin and any appointed later will be larger than this use.

We claim the following. (*) For all stages t ≥ z, one of the following holds.

Φ_{e,t}(A_{i,t}; x) = Φ_{e,s}(A_{i,t}; x) and C is correct on ϕ_{e,t}(A_{i,t} ⊕ C_{t}; x)

Φ_{e,t}(A_{j,t}; x) = Φ_{e,s}(A_{j,t}; x) and C is correct on ϕ_{e,t}(A_{j} ⊕ C; x)

Suppose that (*) fails. Let w be the first stage after z at which it fails. Some number must enter A_{i} or A_{j} at stage w, say the smallest such number is y and it enters A_{j}. (The smallest number going into some set at any stage cannot enter C by construction.) Consider the stage v ≤ w at which y passed gate G_{e,i,j}. If the gate G_{e,i,j} had been occupied at v, it would have been occupied by some ball q of higher priority than y which reached the gate at a stage u < v. By the leastness of w, (*) held at u. All balls of lower priority than q were cancelled at stage u and, as q is still at the gate at stage v (when y went by) and indeed still there at stage w (since otherwise y would have been canceled), no ball of higher priority has moved since stage u. As all numbers appointed after stage u (including y) are large (and so larger than the Φ_{e} use at u), no numbers less than the use of the computation verifying (*) at u have entered any set by the end of stage w and so (*) would hold then contrary to our assumption. On the other hand, if G_{e,i,j} was empty when y reached it, y stopped at the gate and when it passed Φ_{e,v}(A_{i,v} ⊕ C_{v}; x) = Φ_{e,v}(A_{j,v} ⊕ C_{v}; x) = Φ_{e,s}(A_{i,s} ⊕C_{s}; x). Now when y (which is targeted for A_{j}) passes G_{e,i,j} it is a member of a j, k-stream and so only numbers targeted for A_{j} or A_{k} pass the gate but none targeted for A_{i}. All balls of lower priority are cancelled at v, none of higher priority have moved by w, and all appointed in between are larger than the Φ_{e} use from A_{i} at v. Thus, no change has occurred in A_{i} on this use from stage v to the end of stage w. Moreover, even if it was the A_{j} side of the computation that was C-correct at v, that guarantees C-correctness up to y while the cancellation procedure at v guarantees that no traces of lower priority targeted for C are left between y and ϕ_{e,v}(A_{i,v} ⊕ C_{v}; x). We claim that there are also none of higher priority in this interval. Suppose there were one r. If r had been appointed before y then y would be bigger than r contrary to hypothesis. On the other hand, if y was appointed before r then it would be cancelled when r is appointed and so never enter A_{j}. Thus at w we would satisfy (*) via the Φ(A_{i}⊕C; x) computation for the desired contradiction.

(3.15) Lemma. A_{i} ≤_{T} A_{j} ⊕ A_{k} ⊕ C for i ≠ j ≠ k.

Proof The proof is the same as for (2.20) except that the trace t may also be targeted for C and we must check if t ∈ C as well. (This case arises only when x is in the permitting bin in which case it enters its target set only if t enters C and if so at the same stage.)

(3.16) Lemma. The sets constructed C, A_{i} are all recursive in B. Proof A number y is enumerated in a set at a stage s only it

is a descendant of some follower x_{e,i} (possibly the follower itself), necessarily with y > m, and it is permitted by a change g(m, s) ≠ g(m, s+1). As g(m, t) is nondecreasing and its final value is recursive in B, we can, recursively in B, clearly find a stage after which this cannot happen and so after which y cannot be enumerated.

Remark Note that the construction only needs that b contains a function g that is not dominated by ĥ. Note that given any particular function k ≤_{T} ∅′, it is easy to construct a degree d which is low and contains a function q not dominated by k. Thus it seems that attempts to characterize nonlow_{2} by pure “multiple permitting” would seem to need a range of properties in some sense we do not as yet understand. Of course nonlow_{2} really is characterized by its domination properties of functions recursive in ∅′. The difficulty is in finding reflections of this domination in elementary properties of the structure of the r.e. degrees.

References

[1] K. Ambos-Spies, D. Decheng, and P. Fejer, Embedding lattices preserving 1 below a nonzero recursively enumerable Turing degree, in Logical Methods, (ed. J. Crossley, et. al.) Birkhauser, Boston, (1994) 92-129.

[2] K. Ambos-Spies and P. Fejer, Degree theoretical splitting properties of recursively enumerable sets, J. Symbolic Logic, 53 (1988) 1110-1137.

[3] K. Ambos-Spies, C. Jockusch, R. Soare and R. Shore, An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. Soc. 281 (1984), 109-128.

[4] K. Ambos-Spies and M. Lerman, Lattice embeddings into the recursively enumerable degrees, J. Symbolic Logic, 51 (1986) 257-272.

[5] K. Ambos-Spies and M. Lerman, Lattice embeddings into the recursively enumerable degrees II, J. Symbolic Logic, 54 (1990) 735-760.

[6] P. Cholak and R. Downey, Lattice nonembeddings and intervals in the recursively enumerable degrees, Annals Pure and Applied Logic, 61 (1993) 195-222.

[7] P. Cholak, R. Downey and R. Shore, Lattice nonembeddings and the Low_{2} recursively enumerable degrees, in preparation.

[8] S. Cooper, Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic 39 (1974) 655-660.

[9] R. Downey, Notes on the 0′′′ priority method with special attention to density results, in Recursion Theory Week (ed. K. Ambos-Spies, G. Müller, G. Sacks) Lecture notes in Mathematics, 1432 Springer-Verlag (1990) 114-140.

[10] R. Downey, Array nonrecursive sets and lattice embeddings of the diamond, Illinois J. Math, 37 (1993) 349-374.

[11] R. Downey, Lattice nonembeddings and initial segments of the recursively enumerable degrees, Annals Pure and applied Logic, 49 (1990) 97-119.

[12] R. Downey, S. Lempp, and R. Shore, Highness and bounding minimal pairs, Math. Logic Quarterly, 39 (1993) 475-491.

[13] R. Downey, C. Jockusch and M. Stob, Array nonrecursive sets and multiple permitting arguments, in Recursion Theory Week (ed. K. Ambos-Spies, G. Müller, G. Sacks) Lecture Notes in Mathematics, Vol. 1432, Springer-Verlag (1990) 141-174.

[14] R. Downey and R. Shore, Degree theoretical definitions of low_{2} recursively enumerable sets, submitted.

[15] R. Downey and T. Slaman, Completely mitotic r.e. degrees, Annals Pure and Applied Logic, 41 (1989) 119-152.

[16] R. Downey and M. Stob, Structural interactions of the recursively enumerable W- and T-degrees, Annals Pure and Applied Logic 31 (1986) 205-236.

[17] R. Downey and M. Stob, Splitting theorem in recursion theory, Annals Pure and Applied Logic, 65 (1993) 1-106.

[18] P. Fejer, Embedding lattices with top preserved below non-GL_{2} degrees, Z. Math. Logik Grundlagen d. Math, 35 (1989) 3-14.

[19] M. Ingrassia, P-genericity for Recursively Enumerable Sets, Thesis, University of Illinois at Urbana (1981).

[20] C. Jockusch and R. Soare, Degrees of members of Π_{1}^{0} classes, Pacific J. Math. 40 (1972) 605-616.

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

[22] A. Lachlan, Embedding nondistributive lattices in the recursively enumerable degrees, in Conference in Mathematical Logic, London 1970 (ed. W. Hodges) Lecture notes in mathematics, 255, Springer-Verlag, New York (1972) 149-177.

[23] A. Lachlan, Bounding minimal pairs, J. Symbolic Logic, 44 (1979) 626-642.

[24] A Lachlan and R. Soare, Not every finite lattice is embeddable in the recursively enumerable degrees, Advances in Math, 37 (1980) 78-82.

[25] R. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic, 38 (1973) 199-211.

[26] R. Ladner, A completely mitotic nonrecursive recursively enumerable degree, Trans. Amer. Math. Soc., 184 (1973) 479-507.

[27] R. Ladner and L. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Annals Mathematical Logic, 8 (1975) 429-448.

[28] M. Lerman, Admissible ordinals and priority arguments, in Cambridge Summer School in Mathematical Logic (A. Mathias and H. Rogers (eds.)) Lecture notes in Math. 337, Springer-Verlag, New York (1973) 311-344.

[29] M. Lerman, The embedding problem for the recursively enumerable degrees, in Recursion Theory (ed. A. Nerode and R. Shore), American Math. Soc., Providence, R. I., U. S. A., (1995) 13-20.

[30] D. Martin and M. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic, 35 (1970) 205-209.

[31] G. Sacks, The recursively enumerable degrees are dense, Annals of Math. (2) 80 (1963), 211-231.

[32] J. Shoenfield, Application of model theory to degrees of unsolvability, in Symposium on the Theory of Models (J. Addison, L. Henkin, A. Tarski, (eds.)), North-Holland, Amsterdam (1965) 359-363.

[33] R. Shore and T. Slaman, Working below a low_{2} recursively enumerable degree, Arch. Math. Logic, 29 (1990) 201-211.

[34] R. Shore and T. Slaman, Working below a high recursively enumerable degree, J. Symbolic Logic, 58 (1993) 824-859.

[35] T. Slaman, The density of infima in the recursively enumerable degrees, Annals Pure and Applied Logic, 52 (1991) 155-179.

[36] R. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, New York, 1987.

[37] M. Stob, Embedding M_{5} (New Seminar Version), unpublished handwritten notes, 1977.

[38] S. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971) 273-280.

[39] S. Weinstein, Ph. D. Thesis, University of California, Berkeley (1988).

[40] C. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966) 159-168.