On isolating r.e. and isolated d-r.e. degrees

Marat Arslanov^{∗} Kazan University, Kazan, Russia

Steffen Lempp^{†} University of Wisconsin, Madison WI 53706-1388 USA

Richard A. Shore^{§} Cornell University, Ithaca NY 14853 USA

1. Introduction

The notion of a recursively enumerable (r.e.) set, i.e. a set of integers whose members can be effectively listed, is a fundamental one. Another way of approaching this definition is via an approximating function {A_{s}}_{s∈ω} to the set A in the following sense: We begin by guessing x ∉ A at stage 0 (i.e. A_{0}(x) = 0); when x later enters A at a stage s + 1, we change our approximation from A_{s}(x) = 0 to A_{s+1}(x) = 1. Note that this approximation (for fixed) x may change at most once as s increases, namely when x enters A. An obvious variation on this definition is to allow more than one change: A set A is 2r.e. (or d-r.e.) if for each x, A_{s}(x) change at most twice as s increases. This is equivalent to requiring the set A to be the difference of two r.e. sets A_{1} − A_{2}. (Similarly, one can define n-r.e. sets by allowing at most n changes for each x.)

The notion of d-r.e. and n-r.e. sets goes back to Putnam [1965] and Gold [1965] and was investigated (and generalized) by Ershov [1968a, b, 1970]. Cooper showed that even in the Turing degrees, the notions of r.e. and dr.e. differ:

∗Partially supported by Russia Foundation of Fundamental Investigations Grant 93-011-16004 and a Fulbright Fellowship held at Cornell University and the University of Wisconsin.

†Partially supported by NSF Grant DMS-9100114.

§Partially supported by NSF Grant DMS-9204308 and ARO through MSI, Cornell University, DAAL-03-C-0027.

Theorem 1.1. (Cooper [1971]) There is a properly d-r.e. degree, i.e. a Turing degree containing a d-r.e. but no r.e. set.

In the eighties, various structural differences between the r.e. and the dr.e. degrees were exhibited by Arslanov [1985], Downey [1989], and others. The most striking difference is probably the following result which stands in contrast with the well-known Sacks Density Theorem for the r.e. degrees:

Theorem 1.2. (Cooper, Harrington, Lachlan, Lempp, Soare [1991]) There is a maximal incomplete d-r.e. degree below 0′; thus the d-r.e. degrees are not densely ordered.

The distribution of r.e. degrees within the structure of the d-r.e. degrees has also been investigated, starting with Lachlan’s observation (unpublished) that any noncomputable d-r.e. degree bounds a noncomputable r.e. degree.

Cooper and Yi [1995] defined the notion of an isolated d-r.e. degree d as a Turing degree such that the r.e. degrees strictly below d contain a greatest r.e. degree a, say. (a is then said to isolate d.) They established the following results about this notion:

Theorem 1.3. (Cooper, Yi [1995]) (i) There exists an isolated d-r.e. degree. (ii) There exists a non-isolated properly d-r.e. degree. (iii) Given any r.e. degree a and d-r.e. degree d > a, there is a d-r.e. degree

e between a and d.

They raise the question of whether the phenomena in (i) and (ii) above occur densely relative to the r.e. degrees (i.e. whether we can find such degrees between any two comparable r.e. degrees), and whether every noncomputable incomplete r.e. degree isolates some d-r.e. degree. LaForte answered the first of these questions positively:

Theorem 1.4. (LaForte [1995]) Given any two comparable r.e. degrees v < u, there exists an isolated d-r.e. degree d between them.

(Ding and Qian [1995] independently obtained a partial answer to the above by showing that there is an isolated d-r.e. degree below any noncomputable r.e. degree.)

We answer the other two questions in the present paper:

Theorem 2.1. Given any two comparable r.e. degrees v < u, there exists a non-isolated d-r.e. degree d between them.

Before stating the answer to the last question, we state the following proposition, connecting d-r.e. and REA in a degrees:

Proposition 3.1. If d > a is d-r.e. (or n-r.e. for any n ∈ ω) then there is a c ≤ d which is r.e. in a and strictly above a. So, in particular, if a isolates d then a isolates c.

The following is then a negative answer to the last question of Cooper and Yi mentioned above: Theorem 3.2. There is a noncomputable r.e. degree a which isolates no degree REA in it.

We extend this result by showing that the non-isolating degrees are downward dense in the r.e. degrees and that they occur in any jump class:

Theorem 3.7. For every noncomputable r.e. degree c, there is a noncomputable r.e. degree a ≤ c which isolates no degree REA in it.

Theorem 3.8. If c is REA in 0′ then there is a noncomputable r.e. degree a with a′ = c which isolates no degree REA in it.

We close with another result relating the d-r.e. degrees to the notion of relative enumerability.

Theorem 4.2. Given r.e. degrees v < u, there is a d-r.e. degree d between them which is not r.e. in v.

We generally follow the notation of Soare [1987]. Familiarity with the proof of the weak density result of Cooper, Lempp, Watson [1989] is frequently assumed throughout the paper.

2. Non-isolated d-r.e. degrees

In this section we show that between any two r.e. degrees there is a properly d-r.e. degree which is not isolated by any r.e. degree. The proof of this theorem uses an infinite injury argument and is essentially the same as in Cooper, Lempp, Watson [1989] where, given r.e. sets U >_{T} V, a d-r.e. set C of properly d-r.e. degree such that U >_{T} C >_{T} V is constructed.

Theorem 2.1. Given r.e. sets U >_{T} V there is a d-r.e. set C of properly d-r.e. degree such that U >_{T} C >_{T} V, and, for any r.e. set B, if B <_{T} C then B <_{T} W <_{T} C for some r.e. set W.

Proof. We construct r.e. sets A_{1}, A_{2} ≤_{T} U. If A = A_{1}−A_{2} then C = V ⊕A will be the desired set. To ensure that V ⊕ A is not of r.e. degree we satisfy for every e the requirement

R_{e} : A ≠ Θ_{e}^{W_{e}} ∨ W_{e} ≠ Φ_{e}^{V ⊕A}.

To ensure that the degree of V ⊕ A is not isolated we satisfy for every e the requirement

S_{e} : W_{e} = Ψ_{e}^{V ⊕A} ⇒ (∃ r.e. U_{e} ≤_{T} V ⊕ A)(∀ i)(U_{e} ≠ Ω_{i}^{W_{e}}).

Here {(W_{e}, Θ_{e}, Φ_{e}, Ψ_{e}, Ω_{e})}_{e∈ω} is some enumeration of all possible fivetuples of r.e. sets W and partial recursive functionals Θ, Φ, Ψ and Ω.

Since we handle the requirements {R_{e}}_{e∈ω} in the same way as in Cooper, Lempp, Watson [1989] we will consider here only the requirements {S_{e}}_{e∈ω}. In satisfying S_{e} we shall construct a r.e. set U_{e} with the intention that if W_{e} = Ψ_{e}^{V ⊕A} then U_{e} ≠ Ω_{i}^{W_{e}} for all i and U_{e} ≤_{T} V ⊕ A through a modified permitting argument. We break S_{e} up into subrequirements S_{e,i}:

S_{e,i} : W_{e} = Ψ_{e}^{V ⊕A} ⇒ U_{e} ≠ Ω_{i}^{W_{e}}.

Basic module. Let us first consider requirements S_{e,i} without the claim that A ≤_{T} U and in the absence of any V -changes. (This is just the proof that there is a non-isolated d-r.e. degree.) The strategy proceeds as follows:

(1) Choose an unused candidate x for S_{e,i} greater than any number mentioned in the construction thus far.

(2) Wait for a stage s such that

Ω_{i,s}^{W_{e,s}}(x) ↓= 0,

and for some least u such that

W_{e,s} ω_{i,s}(x) = Ψ_{e,s}^{(V ⊕A)_{s} u} ω_{i,s}(x).

(If this never happens then x is a witness to the success of S_{e,i}).

(3) Protect A u from other strategies from now on.

(4) Put x into U_{e} and A.

(5) Wait for a stage s′ such that

Ω_{i,s′}^{W_{e,s′}}(x) ↓= 1,

and for some least u′ such that

W_{e,s′} ω_{i,s′}(x) = Ψ_{e,s′}^{(V ⊕A)_{s′} u′} ω_{i,s′}(x).

(If this never happens then again x is a witness to the success of S_{e,i}. If it does happen then the change in Ω_{i}^{W_{e}}(x) between stages s and s′ can only be brought about by a change in W_{e} ω_{i,s}(x), which is irreversible since W_{e} is a r.e. set.)

(6) Remove x from A and protect A u′ from other strategies from now on.

(Now x is a permanent witness to the success of S_{e,i} because

Ψ_{e}^{V ⊕A} ω_{i,s}(x) = Ψ_{e,s}^{(V ⊕A)_{s}} ω_{i,s}(x) = W_{e,s} ω_{i,s}(x) ≠ W_{e} ω_{i,s}(x).)

We see that the S_{e,i}-strategy in isolation and without the claims A ≤_{T} U and V ≤_{T} A is essentially the same as the R_{e}-strategy under similar assumptions. (Note that since we have refuted the overall hypothesis of S_{e} we no longer need to maintain the reduction U_{e} ≤_{T} A.) It allows us to meet all requirements {S_{e,i}}_{e,i∈ω} and {R_{e}}_{e∈ω} together in the same way as in the similar theorem from Cooper, Lempp, Watson [1989].

As in Cooper, Lempp, Watson [1989], we handle the condition V ≤_{T} A by imposing “indirect” restraints to protect V, threatening U ≤_{T} V via a functional Γ. We make infinitely many attempts to satisfy S_{e,i} as above by an ω-sequence of “cycles”, each cycle k proceeding as above with its own witness and with the following step inserted after step 3:

(3\frac{1}{2}) Set Γ_{e}^{V} (k) = U_{s}(k) with use γ(k) = u, start cycle k + 1 simultaneously, wait for U(k) to change, then stop cycles k′ > k and proceed.

Finally, we ensure that A ≤_{T} U through a permitting argument. So x has to be permitted to enter A by U at step (4) and to leave A at step (6). The former permission is already given by the U(k)-change, the latter we build into the strategy as in Cooper, Lempp, Watson [1989].

Now the basic module for the S_{e,i}-strategy repeats the module for the R_{e}-strategy from Cooper, Lempp, Watson [1989]. It consists of an (ω × ω)- sequence of cycles (j, k), j, k ∈ ω. Cycle (0, 0) starts first, and each cycle (j, k) can start cycles (j, k+1) or (j+1, 0) and stop, or cancel, cycles (j′, k′) > (j, k) (in the lexicographical ordering). Each cycle (j, k) can define Γ_{j}^{V} (k) and Δ^{V} (j).

A cycle (j, k) now proceeds as follows:

(1) Choose an unused candidate x such that x − 1 is greater than any number mentioned thus far in the construction.

(2) Wait for a stage s_{1} such that

Ω_{i,s_{1}}^{W_{e,s_{1}}}(x) ↓= 0,

6 M. M. Arslanov, S. Lempp, R. A. Shore

and for some least u such that

W_{e,s_{1}} ω_{i,s_{1}}(x) = Ψ_{e,s_{1}}^{(V ⊕A)_{s_{1}} u} ω_{i,s_{1}}(x).

(3) Protect A u from other strategies from now on.

(4) Set Γ_{j}^{V} (k) = U_{s_{1}}(k) with use γ_{j}(k) = u, and start cycle (j, k + 1) to run simultaneously.

(5) Wait for V u or U(k) to change.

If V u changes first then cancel cycles (j′, k′) > (j, k), drop the A-protection of cycle (j, k) to 0, and go back to step (2). If U(k) changes first then stop cycles (j′, k′) > (j, k) and proceed to step (6).

(6) Put x into A and U_{e}.

(7) Wait for a stage s_{2} such that

Ω_{i,s_{2}}^{W_{e,s_{2}}}(x) ↓= 1,

and for some least u′ such that

W_{e,s_{2}} ω_{i,s_{2}}(x) = Ψ_{e,s_{2}}^{(V ⊕A)_{s_{2}} u′} ω_{i,s_{2}}(x).

(8) Protect A u′ from other strategies from now on.

(9) Set Δ^{V} (j) = U_{s_{2}}(j) with use δ(j) = u′ and start cycle (j + 1, 0) simultaneously.

(10) Wait for V u′ or U(j) to change.

If V u′ changes first then cancel cycles (j′, k′) ≥ (j + 1, 0), drop the A-protection of cycle (j, k) to u, and go back to step (7). If U(j) changes first then stop cycles (j′, k′) ≥ (j+1, 0) and proceed to step (11).

(11) Remove x from A.

(12) Wait for V u ≠ V_{s_{1}} u.

(13) Reset Γ_{j}^{V} (k) = U(k), put x + 1 into A, cancel cycles (j′, k′) > (j, k), start cycle (j, k + 1), and halt cycle (j, k).

Whenever a cycle (j, k) is started, any previous version of it has been cancelled and its functionals have become undefined through V -changes and, therefore, Γ_{j} and Δ are defined consistently.

The basic module has four possible outcomes similar to those of the basic module of the R_{e}-strategy.

(A) There is a stage s after which no cycle acts. Then some cycle (j_{0}, k_{0}) eventually waits at step 2, 7 or 12 forever. Thus we win requirement S_{e,i} through the cycle (j_{0}, k_{0}).

(B) Some cycle (j_{0}, k_{0}) acts infinitely often but no cycle < (j_{0}, k_{0}) does so. Then it goes from step 5 to step 2, or from step 10 to step 7, infinitely often. Thus Ψ_{e} or Ω_{e} is partial. Notice that the overall restraint of all cycles has finite liminf.

(C) There is a (least) j_{0} such that every cycle (j_{0}, k), k ∈ ω, eventually waits at step 5 or 13 forever. (“Row j_{0} acts infinitely”.) This means that U ≤_{T} V via Γ_{j_{0}} contrary to hypothesis.

(D) For every j there is a cycle (j, k_{j}) that eventually waits at step 10 forever. (“Every row acts finitely”). This means that U ≤_{T} V via Δ contrary to hypothesis.

The verification now proceeds as in Cooper, Lempp, Watson [1989], and we leave the details to the reader, except for the following item: When we remove x from A, we also lose the U_{e}-permission for x (which must, of course, remain in U_{e}). But note that the win on S_{e} is global (and so U_{e} is no longer needed) unless V u changes later. In that case, however, x+1 is enumerated into A, and so V ⊕ A can recognize this. □

3. Nonisolating r.e. degrees

Following Cooper and Yi [1995] we say that a r.e. degree a isolates the degree d > a if, for every r.e. b ≤ d, we have b ≤ a. Cooper and Yi ask (Q 4.3) if every r.e. degree a isolates some d-r.e. degree d. In this section we supply a strong negative answer to this question. Our basic construction shows (Theorem 3.2) that there is a noncomputable r.e. degree a which does not isolate any d which is REA in it. The answer to Q 4.3 then follows immediately from the next proposition.

Proposition 3.1. If d > a is d-r.e. (or n-r. e. for any n ∈ ω) and a is r.e. then there is a degree c ≤ d which is r.e. in a and strictly above it. So, in particular, if a isolates d then a isolates c.

Proof. By Jockusch and Shore [1984], d is 2-REA, i.e. there is a r.e. degree e such that d is REA in e. Now if e ≤ a then d itself is REA in a and so the degree c required in the Proposition. If not, then a < e ∨ a ≤ d and so e ∨ a is the degree c required by the Proposition. (Essentially the same argument now works for d n-r.e. by induction on n.) The assertion about a isolating c follows by definition.

We also supply two variations on this basic construction that show that the degrees a not isolating any d which is REA in a are widely distributed in the r.e. degrees. Theorem 3.7 shows that such degrees exist below every nonrecursive r.e. c and Theorem 3.8 shows that they exist in every jump class, i.e. for every c REA in 0′ there is such a r.e. degree a with a′ = c.

We begin with the basic construction.

Theorem 3.2. There is a nonrecursive r.e. set A such that its degree a isolates no degree REA in it, i. e. ∀e(A <_{T} W_{e}^{A} → ∃B(B is r.e. & B ≤_{T} W_{e}^{A} & B ≰_{T} A)).

There are two types of basic requirements:

P_{e} : Φ_{e} ≠ A (for each partial recursive function Φ_{e}).

N_{e} : A <_{T} W_{e}^{A} → B_{e} ≤ W_{e}^{A} & B_{e} ≰ A (for each e we construct an appropriate r.e. set B_{e}).

The requirements N_{e} are divided up into subrequirements:

N_{e,i} : Φ_{i}^{A} ≠ B_{e} (for each partial recursive functional Φ_{i}).

We order the requirements P_{e}, N_{e,i} in an ω type list ⟨R_{n}⟩. The procedures for satisfying the individual requirements are fairly standard. We will diagonalize against Φ_{e} by putting some witness x into A at a stage s to satisfy P_{e} when Φ_{e}(x) = 0[s]. For N_{e,i} we will wait until some x ∈ ω^{[⟨e,i⟩]} with Φ_{i}(A; x) = 0[s] is permitted by W_{e}^{A} at s and then put x into B_{e}. To implement the permitting we first approximate W_{e}^{A} in the usual way: x ∈ W_{e}^{A} [s] iff Φ_{e}(A; x) ↓ [s]. We then say that x is permitted by W_{e}^{A} at s if it looks as if some y < x is in W_{e}^{A} at s but it does not, at s, look as if it was in at s − 1 by an A-correct computation, i.e.

∃y < x{y ∈ W_{e}^{A}[s] & (y ∉ W_{e}^{A}[s − 1] ∨ ∃z < φ_{e}(y, s − 1)[z ∈ A_{s} − A_{s−1}])}.

The restraint necessary to preserve the A-use relevant to this computation will be imposed automatically by our procedure for choosing potential witnesses for the P_{e}. We now present the formal construction and verifications.

Construction:

At stage s we find the first requirement R_{n} in our list such that one of the following two cases holds:

1) R_{n} = P_{e}; there is no z such that Φ_{e}(z) = 0 [s] and z ∈ A; Φ_{e}(x) = 0 [s] for the least x ∈ ω^{[e]} which is larger than any stage at which we have acted for any requirement of higher priority than P_{e}. We call this x the current potential witness for P_{e}.

2) R_{n} = N_{e,i}; there is no z such that Φ_{i}(A; z) = 0 [s] and z ∈ B_{e}; there is a least x ∈ ω^{[⟨e,i⟩]} larger than any stage at which we have acted for any requirement of higher priority than N_{e,i} such that Φ_{i}(A; x) = 0 [s] and larger than any current potential witness for any higher priority P -requirement; and x is permitted by W_{e}^{A} at s.

If there is no such n, we go on to stage s + 1. Otherwise, we now act for requirement R_{n} according to which of the above two cases applies:

1) If R_{n} = P_{e} then we put x into A.

2) If R_{n} = N_{e,i} we put x into B_{e}.

Verifications:

Lemma 3.3. We act for each requirement only finitely often.

Proof. We proceed by induction through the priority ordering. Suppose we never act for any R_{m} with m < n after stage s. If R_{n} = P_{e} and we act for this requirement at t > s by putting x into A then it is clear that we never act for it again as Φ_{e}(x) = 0 [t] and x ∈ A [t + 1]. If R_{n} = N_{e,i} and we act for this requirement at t > s by putting x into B_{e}, we never put any number less than t into A at any later stage since no P_{j} of lower priority can do so by construction and none of higher priority can act by our choice of s. Thus, by the usual conventions that the Φ_{i} use at t is at most t, no number less than the use φ_{i}(x, t) can ever enter A after t. In particular, Φ_{i}(A; x) [t] = Φ_{i}(A; x) [t′] = 0 and x ∈ B_{e} for every t′ > t. So we never act again for N_{e,i}. □

Lemma 3.4. Each requirement P_{e} is satisfied, i. e. Φ_{e} ≠ A.

Proof. Let s be the last stage at which we act for a requirement of higher priority than P_{e} and let x be the least element of ω^{[e]} larger than s. If we ever act for P_{e} after s we have Φ_{e}(x) = 0 and we put x into A to satisfy P_{e}. If we never act for P_{e} after s, then either there is some other z such that Φ_{e}(z) = 0 and z ∈ A or x ∉ A and ¬(Φ_{e}(x) = 0). In either case Φ_{e} ≠ A as required. □

Lemma 3.5. If A <_{T} W_{e}^{A} then we satisfy each requirement N_{e,i}, i. e. Φ_{i}^{A} ≠ B_{e} for each i.

Proof. Consider any requirement N_{e,i} and let s be a stage after which we never act for any requirement of higher priority than N_{e,i}. If we ever act for N_{e,i} at a stage t > s by putting some x into B_{e} then the argument for Lemma 3.3 shows that Φ_{i}(A; x) = 0 and so Φ_{i}^{A} ≠ B_{e} as required. If we never act for N_{e,i} after stage s then x ∉ B_{e} for each x ∈ ω^{[⟨e,i⟩]} which is larger than some fixed s′ > s. Unless Φ_{i}(A; x) = 0 for each such x, we have also shown that Φ_{i}^{A} ≠ B_{e}.

If neither of these situations satisfying N_{e,i} occurs, we show that W_{e}^{A} ≤_{T} A for a contradiction. To compute W_{e}^{A}(x) for x > s′, then find a z ∈ ω^{[e]} such that z > x and a stage t > z such that Φ_{i}(A; z) = 0 [t] by an A-correct computation, i. e. A φ_{i}(z, t) = A_{t} φ_{i}(z, t). We claim that x ∉ W_{e}^{A} unless x ∈ W_{e}^{A}[t] by an A-correct computation, i. e. Φ_{e}(A; x)↓ [t] and A φ_{e}(x, t) = A_{t} φ_{e}(x, t). Of course, if x ∈ W_{e}^{A}[t] by an A-correct computation, then x ∈ W_{e}^{A}. On the other hand, if x ∈ W_{e}^{A} but not by an A-correct computation at t, then there must be a v > t (the first stage at which we have the A-correct computation of Φ_{e}(A; x)) at which W_{e}^{A} would permit z and so we would act for N_{e,i} at v by putting z into B_{e} contrary to our assumption. □

Lemma 3.6. B_{e} ≤_{T} W_{e}^{A} ⊕ A.

Proof. To determine if x ∈ ω^{[⟨e,i⟩]} is in B_{e}, wait until a stage s such that A x = A_{s} x and, for every y < x such that y ∈ W_{e}^{A}, y ∈ W_{e}^{A}[s] by an A-correct computation. We claim that if x ∉ B_{e,s} then x ∉ B_{e}. The only way x can enter B_{e} at some t > s is by our acting for N_{e,i} at t and so, in particular, by W_{e}^{A} permitting x at t. Thus some y < x is in W_{e}^{A[}[t] that was not previously (and so not at s) in W_{e}^{A} by an A-correct computation. By construction, no requirement of lower priority than N_{e,i} can injure the computation of Φ_{e}(A; y)[t]. On the other hand, the current potential witnesses for P_{j} of higher priority than N_{e,i} must all be less than x by construction.

Thus none of them can enter A by our choice of s. If any of these potential witnesses changes at a later stage v > t (because of some action by a yet higher priority N_{k,l} requirement), it must change to a number grater than v > t > φ_{e}(y, t) and so also cannot injure the computation putting y into W_{e}^{A}. Thus y ∈ W_{e}^{A} but is not in W_{e}^{A} by an A-correct computation at s for the desired contradiction. □

We may combine this last construction with r.e. permitting to construct the desired A below any given nonrecursive r.e. set C.

Theorem 3.7. For every nonrecursive r.e. set C there is a nonrecursive r.e. set A <_{T} C such that ∀e(A <_{T} W_{e}^{A} → ∃B(B is r.e. & B ≤_{T} W_{e}^{A} & B ≰_{T} A)).

Proof. We adjust the previous construction by possibly appointing many current potential witnesses for each requirement P_{e}. More specifically, if there is no z such that Φ_{e}(z) = 0 [s] and z ∈ A and Φ_{e}(y) = 0 [s] for every current potential witness for P_{e} at s, then we act for P_{e} by appointing as a potential witness the least x ∈ ω^{[e]} which is larger than any stage at which we have acted for any requirement of higher priority than P_{e} and larger than every current potential witness. We cancel this potential witness at any later stage at which we act for some requirement of higher priority than P_{e}. If there is now a potential witness x with Φ_{e}(x) = 0 which is permitted by C (i.e. some y < x enters C at s) then we act for P_{e} by putting x into A. Otherwise, the construction is the same as before. The verifications now follow the usual pattern of a permitting argument. Assuming we never act for any requirement of higher priority than P_{e} after stage s, we use the nonrecursiveness of C to show that we act only finitely often for P_{e} and eventually satisfy it. (If we act infinitely often without putting a number into A (necessarily by appointing more and more potential witnesses) then we calculate C by noting that once Φ_{e}(x) = 0 at a stage t > s for some potential witness x, we can never later have a number y < x enumerated in C.) The other verifications now proceed as before. □

Finally we show that there is a nonrecursive r.e. set A in every jump class which does not isolate any set D which is REA in A and so (by Proposition 3.1) not any d-r.e. degree above it either.

Theorem 3.8. If C is REA in ∅′ then there is a nonrecursive r.e. set A such that A′ ≡_{T} C and ∀e(A <_{T} W_{e}^{A} → ∃B(B is r.e. & B ≤_{T} W_{e}^{A} & B ≰_{T} A)).

We follow the usual proof of the Sacks jump theorem by starting with an r.e. D such that x ∈ C implies D^{[x]} = {y|y < n} for some n and x ∉ C implies D^{[x]} = ω. Moreover, for technical convenience we assume that if a number z is enumerated in D^{[e]} at stage s then z < s and every x < s which is in ω^{[e]} and not already in D^{[e]} is enumerated in D^{[e]} at s. We will make A a thick subset of D, i. e. for every x, A^{[x]} ⊆ D^{[x]} and D^{[x]} − A^{[x]} is finite. As usual this guarantees that C ≤_{T} A′. We now use a typical tree construction to satisfy the following requirements:

P_{e} : A^{[e]} ⊆ D^{[e]} and D^{[e]} − A^{[e]} is finite.

N_{e,i} : Φ_{i}^{A} ≠ B_{e} (for each e we construct a r.e. set B_{e} satisfying N_{e,i} for each partial recursive functional Φ_{i} if A <_{T} W_{e}^{A}).

Our priority tree is constructed as usual given that we assign nodes on level 2e to P_{e} and their possible outcomes are, in left to right order, i < 0 < 1 < … < n < … while ones on level 2⟨e, i⟩ + 1 area assigned to N_{e,i} and their possible outcomes are w < 0 < 1 < … < s < . . .. (The intended meaning of the outcomes for P_{e} are i : D^{[e]} = ω and n : n is the last stage at which a number is enumerated in D^{[e]} (and so the first number not in D^{[e]}). The intended meaning of the outcomes for N_{e,i} are w : we are waiting for a chance to diagonalize and s ∈ ω : we succeed in diagonalizing by putting some x into B_{e} for which Φ_{i}(A; x) = 0 at stage s. The nodes α assigned to requirements N_{e,i} may impose restraint r(α, s) at stage s. We define R (α, s) the restraint imposed at s on a requirement α assigned to a requirement P_{e} as max{r(β, s)|β < α}.

Construction:

At each stage s we define a sequence of length s of accessible nodes and act accordingly. We begin with ∅, the root of our priority tree, as the first accessible node at each stage s. Suppose a node α of length less than s has just been declared accessible. If P_{e} is assigned to α then we see if there has been a number enumerated in D^{[e]} since the last stage at which α was accessible (since stage 0 if this is the first stage at which α is accessible). If so, then the outcome of P_{e} is i; we declare αˆ i to be accessible; and we put every x > R(α, s) which is in D_{s}^{[e]} into A. If not, we declare αˆ n to be accessible where n is the last stage at which some number was enumerated in D^{[e]}. If α is assigned to N_{e,i} and we have acted for α at some previous stage t, then the outcome of α is t and we declare αˆ t to be accessible. Otherwise, the outcome of α is w and αˆ w is accessible. When we reach a node β of length s we see if there is any node α for which we have not yet acted which has previously been accessible (but is not necessarily accessible now) and is assigned to a requirement N_{e.i} and any x ∈ ω^{[α]} satisfying the following conditions:

(1) x is larger than the first stage u′ > u at which α was accessible where u is the last stage at which any β <_{L} α has been accessible.

(2) x is smaller than the last stage at which α was accessible.

(3) x is permitted by W_{e}^{A} at s.

(4) Φ_{i}(A; x) = 0 [s] via an α-believable computation. (We say that the computation Φ_{i}(A; x) = 0 is α-believable at s if ∀z∀k( z ∈ ω^{[k]} & α(k) = i & z > R(α k, s) & z < φ_{i}(x, s) → z ∈ A_{s}).)

If there is such an α, we act for the highest priority one by putting the smallest such x into B_{e} and set r(α, s) = s. If not, we go on to stage s + 1.

Verifications:

As each node that is accessible infinitely often clearly has a leftmost immediate successor which is accessible infinitely often, there is a path T P in the priority tree consisting of the leftmost nodes which are accessible infinitely often.

Lemma 3.9. If α ∈ T P and α is first accessible at s then no β <_{L} α is ever accessible at t > s. Moreover, there is a stage t ≥ s after which we never act for any β < α assigned to a requirement N_{e,i}. Thus if α is assigned to some P_{e} then R (α, v) is constant for v ≥ t.

Proof. Proceeding by induction along T P the first claim is obvious from the definition of when the various outcomes of each node are accessible. As we can act at most once for each β assigned to a requirement N_{e,i}, the other assertions are also immediate. □

Lemma 3.10. Suppose α ∈ T P is assigned to requirement P_{e} and s is the first stage at which α is accessible and t ≥ s is the first stage after which we never act for any β < α assigned to a requirement N_{e,i} (such a stage exists by Lemma 3.9). If D^{[e]} = ω then αˆ i ∈ T P and for all x ∈ ω^{[e]}, x ∈ A^{[e]} iff x > R(α, t) ∨ x ∈ D_{t}^{[e]}. Otherwise, D^{[e]} is finite and if n is the last stage at which some number is enumerated in D^{[e]} then αˆ n ∈ T P and no number is put into A^{[e]} after the first stage at which αˆ n is accessible.

Proof. Suppose D^{[e]} = ω. It is immediate from the definition of the accessible successor of α that αˆ i ∈ T P. Now, R(α, t) = R(α, v) for every v > t by our choice of s and Lemma 3.9. Thus if x < R(α, t) and x ∉ D_{t}^{[e]} then x ∉ A^{[e]} by construction. On the other hand, if x > R(α, t) then there is a stage v > t after x has entered D^{[e]} at which αˆ i is accessible. By construction, we put x into A^{[e]} at v.

If D^{[e]} is finite and n is the last stage at which a number is enumerated in D^{[e]} then it is clear from the definition of the accessible successor of α that αˆ n ∈ T P and from the construction and Lemma 3.9 that no number is put into A^{[e]} after the first stage at which αˆ n is accessible. □

Lemma 3.11. If α ∈ T P is assigned to N_{e,i} and we act for α at s by putting x into B_{e}, then Φ_{i}(A; x) = 0.

Proof. By construction, α has been accessible before stage s or we could not act for it. Thus by Lemma 3.9 no node to the left of α can ever be accessible again. In particular, no action for a node β <_{L} α can put any number into A after stage s. No node of lower priority can put any number less than φ_{i}(x, s) < s into A after stage s as we set r(α, s) = s and never change it. Finally, we claim no node β ⊂ α will ever put a number less than φ_{i}(x, s) into A after stage s. If β ⊂ α and βˆ n ⊆ α for some n, then β puts no numbers at all into A after s by Lemma 3.10. On the other hand, if βˆ i ⊆ α, then note that R(β, t) is nondecreasing in t and so we will not put in any number less than R(β, s) for β after s while all others that it might ever put into A less than φ_{i}(x, s) are already in A by the definition of Φ_{i}(A; x)[s] being α-believable. □

Lemma 3.12. We satisfy N_{e}, i.e. if A <_{T} W_{e}^{A} then Φ_{i}^{A} ≠ B_{e} for each i.

Proof. Suppose A <_{T} W_{e}^{A} and consider the node α ∈ T P assigned to N_{e,i}. If we ever act for α by putting some x ∈ ω^{[α]} into B_{e} then, by Lemma 3.11, Φ_{i}(A; x) = 0 ≠ B_{e}(x) as required. If we never act for α then B_{e} ∩ ω^{[α]} = ∅ by construction. In this case, if, contrary to the conclusion of our Lemma, Φ_{i}^{A} = B_{e} then Φ_{i}(A; x) = 0 for every sufficiently large x ∈ ω^{[α]}. Let s be the first stage at which α is accessible. We now argue exactly as in Lemma 3.5 with α replacing e that W_{e}^{A} ≤_{T} A for the desired contradiction. □

Lemma 3.13. For every e, B_{e} ≤_{T} W_{e}^{A} ⊕ A.

Proof. To determine if x ∈ ω^{[α]} with α assigned to N_{e,i} is in B_{e} assume we have already calculated B_{e} x and all numbers in B_{e} x have already been enumerated in B_{e} by stage u > x. Now choose a w such that for every e in the domain of α there is a z ∈ ω^{[e]} with w > z > u and wait until a stage s > w such that A w = A_{s} w and, for every y < x such that y ∈ W_{e}^{A}, y ∈ W_{e}^{A}[s] by an A-correct computation. We claim that if x ∉ B_{e,s} then x ∉ B_{e}. First, note that if any node β <_{L} α has been accessible since stage x then x cannot later enter B_{e} by condition (1) on our choice of x. Moreover, until such a β becomes accessible, no number greater than x can be put into any B_{j} for any β <_{L} α by condition (2) on our choice of x. Thus, by our choice of u, the restraints imposed by such β remain constant after stage u and are less than u until some such β becomes accessible. Now, the only way x can enter B_{e} at some t > s is by our acting for α at t and so, in particular, by W_{e}^{A} permitting x at t. Thus some y < x is in W_{e}^{A[}[t] that was not previously (and so not at s) in W_{e}^{A} by an A-correct computation. By construction no requirement of lower priority than α can injure the computation of Φ_{e}(A; y)[t] after t. On the other hand, no action for a node β ⊂ α or β <_{L} α can injure the computation without our moving to the left of α or already having first moved to its left. Suppose then that we move to the left of α at some v > t. This can happen only when some α e is accessible at v and some has been enumerated in D^{[e]} since stage n where α(e) = n ∈ ω. When this happens, we must enumerate all numbers in ω^{[e]} which are less than v into A^{[e]} unless they are below R(α e, v). Our previous remarks, however, show that R(α e, v) < u and so some number z ∈ ω^{[e]} with w > z > u is enumerated into A at v contradicting our choice of s. Thus φ_{e}(y, t) would never be injured contradicting our choice of s once again. □

Lemma 3.14. A′ ≡_{T} C.

Proof. By Lemma 3.10, A is a thick subset of D and so C ≤_{T} A′. We claim that T P ≤_{T} C and that A′ ≤_{T} T P. We first recursively calculate T P from C. Suppose we have α ∈ T P and want to find the immediate successor of α on T P. If α is assigned to some N_{e,i} then αˆ w ∈ T P unless there is a stage s at which we act for α. In this case, αˆ s ∈ T P. Of course, ∅′ can tell if there is such a stage and ∅′ ≤_{T} C. If α is assigned to some P_{e} then αˆ i ∈ T P if D^{[e]} is infinite and otherwise αˆ n ∈ T P where n is the last stage at which a number is enumerated in D^{[e]}. As D^{[e]} is infinite if and only if e ∉ C, C can tell which case applies and so (using ∅′ again in the second case) find the correct immediate successor of α on T P.

Now, we calculate A′ from T P. We begin with a fixed e such that A <_{T} W_{e}^{A}. To determine if j ∈ A′ find an i such that, for every z, Φ_{i}(A; z) = 0 iff Φ_{j}(A; j) ↓. It is now clear from the proof of Lemma 3.12 that j ∈ A′ iff αˆ w ∉ T P for the node α ∈ T P assigned to N_{e,i}. □

Proof (of Theorem 3.8). If C ≡_{T} ∅′ then Theorem 3.7 provides the required A. Otherwise, our last construction supplies the desired set by Lemmas 3.12, 3.13 and 3.14. □

4. D-r.e. degrees and REA degrees

Theorem 4.1. Let v be a r.e. degree such that 0′ > v. Then there is a d-r.e. degree d > v which is not r.e. in v.

Proof. Let K ∈ 0′ and V ∈ v be fixed r.e. sets. We will construct a d-r.e. set A so that D = V ⊕ A does not have degree r.e. in v.

To satisfy the last property we meet the following requirements for all e,

R_{e} : A ≠ Φ_{e}^{W_{e}^{V}} ∨ W_{e}^{V} ≠ Ψ_{e}^{V ⊕A},

where {(W_{e}^{V} , Φ_{e}, Ψ_{e})}_{e∈ω} is some enumeration of all possible triples consisting of sets W^{V} r.e. in V and partial recursive functionals Φ and Ψ.

We use a common convention (see, for example, Rogers [1967]) that W_{e}^{V} enumerates an element x by listing in W_{e} a quadruple ⟨x, 1, u, v⟩ with D_{u} ⊆ V and D_{v} ⊆ V̄.

Obviously, if for some finite set X ⊂ ω, X ⊆ W_{e}^{V} then there is a stage s such that for all t ≥ s we have X ⊆ W_{e,t}^{V_{t}}. (Note here that we denote by X ⊆ W_{e}^{V} that X is a subset and not necessarily a substring.) Besides, if for some s and a (least) number θ, X ⊆ W_{e,s}^{V_{s}}, and

∀x(x ∈ X → ⟨x, 1, u, v⟩ ∈ W_{e,s} ∧ (D_{u} ⊂ V_{s} θ ∧ D_{v} ⊂ V̄_{s} θ)),

then X ⊈ W_{e}^{V} implies V θ ≠ V_{s} θ. We call θ the X-use for W_{e,s}^{V_{s}}.

In satisfying R_{e} we shall construct functionals Γ_{j}(j ∈ ω) and Δ with the intention that if R_{e} fails then K ≤_{T} V via some Γ_{j}, or Δ, contrary to our hypothesis.

Basic module. As usual, we will choose a sequence of candidates (one for each “cycle” of the strategy), one of which will witness the failure of one or both of the statements:

1. A = Φ_{e}^{W_{e}^{V}} ,

2. W_{e}^{V} = Ψ_{e}^{V ⊕A.}

This will be sufficient for R_{e} to succeed. We make infinitely many attempts to satisfy R_{e} by an ω × ω-sequence of

“cycles”, where each cycle (j, k) proceeds as follows:

(1) Choose an unused candidate x_{j,k} greater than any number mentioned thus far in the construction.

(2) Wait for a stage s at which for some n, Ψ_{e,s}^{V_{s}⊕A_{s}} n is defined, and for X ⊆ {0, …, n}, X n = Ψ_{e,s}^{V_{s}⊕A_{s}} n,

X ⊆ W_{e,s}^{V_{s}}

(with X-use θ), and

A(x_{j,k}) = Φ_{e}^{X n}(x_{j,k}).

(It is easy to see that if this never happens then x_{j,k} is a witness to the success of R_{e}.)

(3) Protect A ψ_{e,s}φ_{e,s}(x_{j,k}) from other strategies from now on.

(4) Set Γ_{j}^{V} (k) = K_{s}(k) with use γ_{j}(k) = max{θ, ψ_{e,s}φ_{e,s}(x_{j,k})}, and start cycle (j, k + 1) to run simultaneously with cycle (j, k).

(5) Wait for K(k) to change (at a stage s′, say).

(If there is a V ψ_{e}φ_{e}(x_{j,k})-change between stages s and s′, we kill the cycles (j′, k′) > (j, k), drop the A-protection of this cycle (j, k) to 0, and go back to step (2). If there is a V θ-change between stages s and s′, but there is no V ψ_{e}φ_{e}(x_{j,k})-change, we kill the cycles (j′, k′) > (j, k), and go back to step (2). In both cases, the parts of the functionals Γ_{j}, Δ defined by cycles (j′, k′) > (j, k) become undefined by the V -change.

(6) Stop cycles (j′, k′) > (j, k) and put x_{j,k} into A.

(7) Wait for a stage s′′ at which, for some n′, Ψ_{e,s′′}^{(V ⊕A)_{s′′}} n′ is defined, and for X′ ⊆ {0, …, n′}, X′ n′ = Ψ_{e,s′′}^{(V ⊕A)_{s′′}} n′,

a)X ⊂_{≠} X′,

b)X′ ⊆ W_{e,s′′}^{V_{s′′}}

with X′-use θ′, and

c)A(x_{j,k}) = Φ_{e}^{X′ n′} (x_{j,k}).

(Note that if this never happens then x_{j,k} is again a witness to the success of R_{e}. Indeed, if b) and c) never happen then obviously either A(x_{j,k}) ≠ Φ_{e}^{W_{e}^{V}} (x_{j,k}) or W_{e}^{V} ≠ Ψ_{e}^{V ⊕A}. If b) and c) do happen with some X′, but X ⊈ X′, then while enumerating V we must have seen some V ψ_{e,s′′}φ_{e,s}(x_{j,k})-change or a V θ-change and would go back to step 2, otherwise we would win R_{e} by x_{j,k}: we have X n′ ⊂_{≠} W_{e}^{V} n′ and

Ψ_{e}^{V ⊕A} n′ = X′ n′, therefore Ψ_{e}^{V ⊕A} n′ ≠ W_{e}^{V} n′). Notice also that if we now remove x_{j,k} from A, we would have (in the absence of a V θ′-change or V ψ_{e}ϕ_{e}(x_{j,k})-change)

Ψ_{e}^{V ⊕A} φ_{e}(x_{j,k}) = Ψ_{e,s}^{(V ⊕A)_{s}} φ_{e}(x_{j,k}) = X φ_{e}(x_{j,k}) ⊂_{≠} X′ φ_{e}(x_{j,k}).

So if X′ φ_{e}(x_{j,k}) ⊆ W_{e}^{V} φ_{e}(x_{j,k}) then this is enough for the success of R_{e}. But, unfortunately, W_{e}^{V} is reversible through a V θ′-change (even if V θ does not change) and we may again have X φ_{e}(x_{j,k}) = W_{e}^{V} φ_{e}(x_{j,k}).

To avoid this difficulty we will use these changes of V θ′ to threaten K ≤_{T} V via a new functional Δ.

(8) Set

Δ^{V} (j) = K(j)

with use δ(j) = max{θ′, ψ_{e,s′′}(φ_{e,s′′}(x_{j,k}))}, and start cycle (j + 1, 0) to run simultaneously.

(9) Wait for K(j) to change (at stage s^{∗}, say).

(10) Stop all cycles (j′, k′) ≥ (j + 1, 0), remove the number x_{j,k} from A, and preserve A ψ_{e,s^{∗}}φ_{e,s^{∗}}(x_{j,k}).

(11) Wait for a V δ(j)-change.

(12) Drop the A-protection of this cycle to 0, set

K(j) = Δ^{V} (j)

with a new use δ(j), stop cycle (j, k), cancel all cycles > (j, k), and start cycle (j + 1, 0).

Whenever some cycle sees a V δ(j)-change between stages s′′ and s^{∗}, it will kill the cycles (j′, k′) > (j, k), make their functionals (including Δ^{V}) undefined, and go back to step 7.

If some cycle sees a V ψ_{e,s}φ_{e,s}(x_{j,k})-change between stages s and s^{∗}, it will again kill the cycles (j′, k′) > (j, k), make their functionals and Δ^{V} (j) undefined, and go back to step 2.

Note that if a cycle (j, k) sees a V δ(j)-change between stages s′′ and s^{∗} but there is no V ψ_{e,s}φ_{e,s}(x_{j,k})-change after stage s then it goes back to step 7 and proceeds. If later the cycle again comes to step 8 it redefines Δ^{V} (j) (with the same j) with a new use δ(j). So in this case (when there is no V ψ_{e,s}φ_{e,s}(x_{j,k})-change), other cycles (j′, k′) ≠ (j, k) cannot define Δ^{V} (j).

The module has the following possible outcomes:

(A) There is a stage s after which no cycle acts. Then some cycle (j_{0}, k_{0}) eventually waits at step (2), (7) or (11) forever. It means that we were successful in satisfying R_{e} through the cycle (j_{0}, k_{0}).

(B) Some (least) cycle (j_{0}, k_{0}) acts infinitely often. Then it goes from step (5) to step (2), or from step (9) to step (7) or (2) infinitely often. Thus Φ_{e} or Ψ_{e} is partial. Notice that the overall restraint of all cycles has finite liminf.

(C) Every cycle acts only finitely often but there are infinitely many cycles (j_{0}, k) (for some least j_{0}) which collectively act infinitely often. Then Γ_{j_{0}}^{V} = K, contrary to hypothesis.

(D) Otherwise. Then, for each j, the last time some cycle (j, k) acts, it defines Δ^{V} (j) permanently and correctly, so Δ^{V} = K, contrary to hypothesis.

The explicit construction and the remaining parts of the proof are now essentially the same as in Cooper, Lempp and Watson [1989] with only obvious changes. So we will not give them here.

Moreover, adding to the construction a permitting argument in exactly the same way as in Cooper, Lempp, Watson [1989], we can prove the following theorem.

Theorem 4.2. Let u and v be r.e. degrees such that v < u. Then there is a d-r.e. degree d such that v < d < u and d is not r.e. in v.

5. Bibliography

Arslanov, M. M. [1985], Structural properties of the degrees below 0′, Sov. Math. Dokl. N.S. 283 no. 2, 270-273.

Arslanov, M. M. [1988], On the upper semilattice of Turing degrees below 0′, Sov. Math. 7, 27-33.

Arslanov, M. M. [1990], On the structure of degrees below 0′, in Recursion Theory Week, K. Ambos-Spies, G. H. Müller and G. E. Sacks eds., LNMS 1432, Springer-Verlag, Berlin, 1990, 23-32.

Arslanov, M. M., Lempp, S. and Shore, R. A. [1995], Interpolating dr.e. and REA degrees between r.e. degrees, to appear.

Cooper, S. B. [1971], Degrees of Unsolvability , Ph. D. Thesis, Leicester University, Leicester, England.

Cooper, S. B. [1990], The jump is definable in the structure of the degrees of unsolvability, Bull. Am. Math. Soc. (NS) 23, 151-158.

Cooper, S. B. [1991], The density of the low_{2} n-r.e. degrees, Arch. Math. Logic 31, 19-24.

Cooper, S. B. [1992], A splitting theorem for the n-r.e. degrees, Proc. Am. Math. Soc. 115, 461-471.

Cooper, S. B. [1993], Definability and global degree theory, in Logic Colloquium ’90, J. Oikkonen and J. Väänänen eds., Lecture Notes in Logic 2, Springer-Verlag, Berlin, 25-45.

Cooper, S. B. [1994], Rigidity and definability in the noncomputable universe, in Proceedings of the 9th International Congress of Logic, Methodology and Philosophy of Science, D. Prawitz, B. Skyrms and D. Westerstahl eds., North-Holland, Amsterdam, 1994, 209-236.

Cooper, S. B., Harrington, L., Lachlan, A. H., Lempp, S. and Soare, R. I. [1991], The d-r.e. degrees are not dense, Ann. Pure and Applied Logic 55, 125-151.

Cooper, S. B., Lempp, S. and Watson, P. [1989], Weak density and cupping in the d-r.e. degrees, Israel J. Math. 67, 137-152.

Cooper, S. B. and Yi, X. [1995], Isolated d-r.e. degrees, to appear.

Ding, D. and Qian, L. [1995], An r.e. degree not isolating any d-r.e. degree, to appear.

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

Ershov, Y. [1968a] On a hierarchy of sets I, Algebra i Logika 7 no. 1, 47-73. Ershov, Y. [1968b] On a hierarchy of sets II, Algebra i Logika 7 no. 4,

15-47.

Ershov, Y. [1970] On a hierarchy of sets III, Algebra i Logika 9 no. 1, 34-51.

Gold, E. M. [1965], Limiting recursion, J. Symb. Logic 30, 28-48.

Ishmukhametov, Sh. T. [1985], On differences of recursively enumerable sets, Izv. Vyssh. Uchebn. Zaved. Mat. 279, 3-12.

Kaddah, D. [1993], Infima in the d-r.e. degrees, Ann. Pure and Applied Logic 62, 207-263.

LaForte, G. [1995], Phenomena in the n-r.e. and n-REA degrees, Ph. D. Thesis, University of Michigan.

Putnam, H. [1965], Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Logic 30, 49-57.

Sacks, G. E. [1963], On the degrees less than 0′, Ann. Math. (2) 77, 211-231.

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

Shore, R. A. [1982], On Homogeneity and Definability in the First Order Theory of the Turing Degrees, J. Symb. Logic, 47, 8-16.

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

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

Soare, R. I. and Stob, M. [1982], Relative recursive enumerability, in Proc. Herbrand Symposium, Logic Colloquium 1981, J. Stern, ed., North-Holland, Amsterdam, 299-324.