JUMPS OF MINIMAL DEGREES BELOW 0′

Rodney G. Downey, Steffen Lempp, and Richard A. Shore

Abstract. We show that there is a degree a REA in and low over 0′ such that no minimal degree below 0′ jumps to a degree above a. We also show that every nonlow r.e. degree bounds a nonlow minimal degree.

Introduction.

An important and long-standing area of investigation in recursion theory has been the relationship between quantifier complexity of the definitions of sets in arithmetic as expressed by the jump operator and the basic notion of relative computability as expressed by the ordering of the (Turing) degrees. In this paper we are concerned with an aspect of the general problem of characterizing the range of the jump operator on various classes of degrees. The first such result was the completeness or jump inversion theorem of Friedberg [1957].

Theorem (Friedberg Jump Inversion). If c ≥ 0′ then there is an a such that a′ = c.

As a′ is obviously at least 0′ for every degree a, this result says that every “possible” degree c (i.e., every degree not ruled out on trivial grounds) is the jump of some degree a. A number of other important jump inversion theorems of this sort followed Friedberg’s. In particular Shoenfield [1959] and Sacks [1963] characterized the jumps of the degrees below 0′ and of the r.e. degrees, respectively, as all “possible” degrees:

Theorem (Shoenfield Jump Inversion). If c ≥ 0′ and c is r.e. in 0′ then there is a degree d ≤ 0′ such that d′ = c.

Theorem (Sacks Jump Inversion). If c ≥ 0′ and c is r.e. in 0′ then there is an r.e. degree d such that d′ = c.

Our concern in this paper is the problem of jump inversion into the minimal degrees below 0′. The general problem for the degrees as a whole was solved by Cooper [1973]:

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 03D25.

Key words and phrases. minimal degree, Turing jump, low degree.

Research partially supported by NSF Grants DMS-9100114 (Lempp), DMS-9344740 (Shore), a U.S.-New Zealand Binational Cooperative Research grant including NSF INT 90-20558 (Downey, Lempp and Shore), ARO through ACSyAm at MSI, Cornell University, DAAL-03-91-C-0027 (Downey and Shore), and IGC of Victoria University, Wellington (Downey).

Theorem (Cooper Jump Inversion). If c ≥ 0′ then there is a minimal degree m such that m′ = c.

The natural conjecture at this point would have been that the Shoenfield jump inversion theorem could be extended analogously, i.e., if c ≥ 0′ is r.e. in 0′ then there should be a minimal m ≤ 0′ with m′ = c. Cooper [1973], however, refuted this by showing that no high degree m below 0′ (i.e., no degree with m′ = 0′′) can be minimal. The only known positive result at the time was that there were minimal m < 0′ with m′ = 0′. (This follows from the existence of a minimal degree below any r.e. degree a (Yates [1970]) by taking a to be low (i.e., a′ = 0′).) Indeed, the minimal degrees d constructed in the proof of the Cooper jump inversion theorem all had the property that m′ = m∨0′ (m is in GL_{1} or generalized low_{1}). Answering a question from Yates [1974], Sasso [1974] proved that this is not always the case by constructing a minimal m < 0′ with m′ > 0′.

In the early 70’s Jockusch conjectured (see Sasso [1974, p.573], Yates [1974, p. 235]) that the jumps of minimal degrees m < 0′ are precisely the set of c ≥ 0′ with c r.e. in 0′ and low over 0′, i.e., c′ = 0′′. Jockusch and Posner [1978] eventually proved the (remarkable) half of this conjecture.

Theorem (Jockusch and Posner [1978]). Every minimal degree m is in GL_{2}, i.e., (m ∨ 0′)′ = m′′. In particular, every minimal m ≤ 0′ is low_{2}, i.e., m′′ = 0′′.

The other half of Jockusch’s conjecture, that the jumps of minimal degrees m ≤ 0′ include all those c ≥ 0′ r.e. in 0′ with c′ = 0′′, has remained an open problem.

In this paper we refute this attractive conjecture by exhibiting an entire upward cone of such degrees which contains no jump of a minimal degree below 0′:

Theorem 1.1. There is a degree a recursively enumerable in and above 0′ with a′ = 0′′ such that a is not recursive in the jump of any minimal degree below 0′.

A similar but (in terms of determining the range of the jump on the minimal degrees below 0′) somewhat weaker result has been independently (and slightly earlier) obtained by Cooper and Seetapun (personal communcation^{1}):

Theorem (Cooper and Seetapun). There is a degree a recursively enumerable in and above 0′ with a′ = 0′′ such that if d ≤ 0′ and a is r.e. in d then there is a 1-generic degree below d.

We have not seen Cooper and Seetapun’s proof but they have told us that it is a 0′′′-argument like the proof of Lachlan’s nonbounding theorem as presented in Soare [1987, Chapter XIV]. Our construction is of a considerably simpler type. Indeed, it is really a finite injury argument relative to K (as one might expect in building a low r.e. degree a relative to K). As we cannot actually deal with potential minimal degrees d < 0′ in a construction recursive in K, we use recursive approximation procedures for K and A which turn the construction into a 0′′-tree argument.

We also prove that the theorem fails if we try to replace upward cones by downward ones.

1Recently, Cooper has claimed a full characterization of this class of degrees as the class of what he calls the almost Δ_{2}-degrees.

Theorem 2.1. If D is any r.e. set with ∅′ <_{T} D′, then there is a set M of minimal degree with M ≤_{T} D and ∅′ <_{T} M′ ≤_{T} D′.

Corollary 2.3. If c > 0′ is r.e. in 0′, then there is a minimal degree m < 0′ such that 0′ < m′ ≤ c.

Thus the range of the jump operator on the minimal degrees below 0′ cannot be characterized simply in terms of the jump classes of degrees r.e. in and above 0′.

We finally include sketches of the proofs of two old unpublished related results by the third author concerning cone avoiding by the jumps of minimal degrees below 0′:

Theorem 3.1. If c is r.e. in and above 0′ and c′ = 0′′ then (uniformly in the information) there is a minimal degree a < 0′ with a′ ≰ c.

Theorem 3.2. There are minimal degrees a_{0}, a_{1} < 0′ such that a′_{0} ∪ a′_{1} = 0′′.

1. An upward cone with no jumps of minimal degrees.

In this section we will prove that there is a degree a r.e. in 0′ and low over K such that no minimal degree m < 0′ jumps above it.

Theorem 1.1. There is a degree a recursively enumerable in and above 0′ with a′ = 0′′ such that a is not recursive in the jump of any minimal degree below 0′.

We let K = {⟨x, y⟩ | φ_{x}(y)↓} be the complete r.e. set. Our plan is to define a Σ_{2}-set A via a recursive approximation so that the degree of A ⊕ K is the a of our theorem. There are two types of requirements that we must satisfy. The first is the standard lowness requirement relativized to K:

N : (A ⊕ K)′ ≡_{T} K′.

As usual, N is divided up into infinitely many requirements

N_{e} : preserve Φ_{e}(A ⊕ K; e).

As our construction will be recursive, we can only expect to succeed modulo the K-correctness of our computations (and, of course, the outcomes of requirements of higher priority).

The second type of requirements, P, deal with the jumps of minimal degrees below 0′. We can list all candidates, Δ, for minimal degrees below 0′ by taking a list of all partial recursive {0, 1}-valued functions Δ(x, s). If we let Δ(x) = lim_{s→∞} Δ(x, s), we have, by the limit lemma, a list which includes all sets recursive in K. One more application of the limit lemma tells us how to represent sets recursive in Δ′, the jump of Δ. They are all those of the form Γ = λy lim_{n→∞} Γ(Δ, y, n) for some partial recursive functional Γ of the appropriate form. Thus we can express the remaining conditions of the theorem by the requirements P_{Δ,Γ} as Δ(x, s) and Γ(Δ, y, x) range over the appropriate classes of partial recursive functionals:

P_{Δ,Γ}: If Δ and Γ are total functions and Γ = A then there is a Z such that 0 <_{T} Z <_{T} Δ.

We divide each requirement P_{Δ,Γ} into two infinite sequences of subrequirements

R_{Δ,Γ,Ψ} : Z ≠ Ψ
S_{Δ,Γ,Ψ} : Ψ(Z) ≠ Δ

where Ψ ranges over all partial recursive functionals (and Ψ is short for Ψ(∅)).

If the hypotheses of P_{Δ,Γ} hold, Δ and Γ are total and Γ = A, then our plan is to define a recursive functional Λ so that setting Λ(Δ) = Z satisfies R_{Δ,Γ,Ψ} and S_{Δ,Λ,Ψ} for each functional Ψ. For each subrequirement we will have a number y called the killing point which we will alternately put into and take out of A to try to force a win (We will explain the precise mechanics of this later. For now just note that the killing point for the version of a requirement at node α will be (the code of) α.) Roughly speaking, the plan for R = R_{Δ,Γ,Ψ} is as follows: We put y into A and wait for an n such that Γ(Δ, y, n) = 1. (If there is no such n, Γ ≠ A.) When we get such an n, we use it by choosing a follower x and setting Z(x) = 0 = Λ(Δ, x) by an axiom from Δ of length γ(y, n). We now wait for x to be realized, i.e., for Ψ(x) = 0. At this point, we remove y from A. If Δ changes on γ(y, n) we can redefine Λ(Δ, x) = Z(x) to be 1 and win R. If not we can put y back into A and try again for a new n and x. The idea is that if we never get a win (Z(x) ≠ Ψ(x)) we cycle through this scenario infinitely often each time getting an n with Γ(Δ, y, n) = 1 via a Δ-correct computation. As we remove y from A infinitely often, y ∉ A^{K}. As y ∉ A^{K} requires that lim_{n→∞} Γ(Δ, y, n) = 0, we have the desired failure of the hypotheses of P_{Δ,Γ}.

Note that if x ∈ ω^{[i]} and the i^{th} requirement is not an R_{Δ,Γ,Ψ} for any Ψ then Z(x) = 0 by a trivial axiom ⟨∅, x, 0⟩ which we put into Λ at stage 0.

The basic plan for satisfying S = S_{Δ,Γ,Ψ} is similar. We begin by putting y into A and waiting for an n such that Γ(Δ, y, n) = 1 that we can use. We also want a Ψ-computation of the Δ use from Z, Ψ(Z)↾γ(y, n) = Δ↾γ(y, n). At this point, we remove y from A. If we get a Δ change on γ(y, n) we would hope to be able to restore Z↾ψγ(y, n) to its previous value for a diagonalization Ψ(Z)↾γ(y, n) ≠ Δ↾γ(y, n). If we cannot do this, we return y to A and try again for a new n with Γ(Δ, y, n) = 1 and Ψ(Z) = Δ↾ γ(y, n). We will have to argue that we can be prevented from eventually restoring Z to one of these older desired values only if there are infinitely many n with Δ-correct computations Γ(Δ, y, n) = 1. As y ∉ A we will again have contradicted the hypotheses of P_{Δ,Γ}.

The general structure of our argument is actually that of a finite injury argument (modulo the approximations to K). Although this may seem surprisingly simple, we are after all constructing (relative to K) a low r.e. set. General considerations as in Soare [5] then suggest that our argument should be a finite injury one (over K). As the actual construction must be recursive, our approximation procedure produces a standard tree structure for it.

We begin by listing all the requirements N_{e}, R_{Δ,Γ,Ψ} and S_{Δ,Γ,Ψ} in an ω-list Q_{i}. As usual, the tree structure will consist of sequences α of outcomes of the requirements Q_{i}, i < |α|. Such a node α will be devoted to requirement Q_{|α|}. We say that α is associated with P_{Δ,Γ} if Q_{|α|} is R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ} for some Ψ. The possible outcomes of a requirement R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ} are 0 and 1 depending on whether it believes y ∉ A or y ∈ A, respectively. A requirement N_{e} can have any element of ω as its outcome. It will be the use of Φ_{e}(A^{K} ⊕ K; e) if it is believed to converge and 0 otherwise. To specify the actions and outcomes of the requirements more precisely we need to fix various approximation procedures.

Approximations: We have already fixed K as the complete r. e. set. We also fix some recursive one-one enumeration k(s) of K. As usual, K_{s} = {k(t) | t < s}. We approximate Δ in the obvious way: Δ_{s}(x) = Δ(x, s). We follow the convention of adding an s in brackets at the end of an expression to denote that we are using the s^{th} stage approximation to each set or functional in the expression. Thus K(x)[] and Δ(x)[s] mean K_{s}(x) and Δ_{s}(x). More interestingly, Γ(Δ, y, n) = 1[s] means that Γ_{s}(Δ_{s}, y, n)↓ = 1. (To compute the functional Γ for s steps.) If we wish to denote the state of affairs at substage i of stage s we append “[s, i]” to the relevant expression. We also adopt the standard conventions that small Greek letters such as γ(y, n) indicate the use of the functional denoted by the corresponding capital Greek letters Γ(Δ, y, n) and that uses are nondecreasing in both the input and stage of the approximation.

For each Δ and Γ we will enumerate axioms into a functional Λ_{Δ,Γ} = Λ to define Z = Λ(Δ). We can take the axioms to be of the form ⟨σ, x, j⟩ where σ is a binary string and, for j = 0, 1, Λ(Δ; x) = j ⇔ ∃σ(⟨σ, x, j⟩ ∈ Λ & σ ⊆ Δ). This defines the obvious approximations to Z : Z_{s}(x) = j ⇔ ∃σ(⟨σ, x, j⟩ ∈ Λ_{s} & σ ⊆ Δ_{s}). Of course, we must make sure that axioms are enumerated so that Λ is consistent and that Λ(Δ) is total if Δ and Γ satisfy the hypotheses of P_{Δ,Γ}.

The last approximation is the one to the Σ_{2} set A that we are constructing. We begin with A = ∅ at stage 0. At various times during the construction we may put a number y into A or take it out. Our approximations to, or beliefs about, A at any point in the construction are the obvious ones: We believe that A(x) = 1 if the last action we took was to put x into A and A(x) = 0 otherwise. Our final Σ_{2} set A is defined by A(x) = 1 ⇔ there is a point in the construction at which we put x into A and then never take it out. We can now describe our construction.

The construction: We begin each stage s of the construction by declaring the empty sequence ∅ to be accessible. Stage s will now have s substages each of which starts with some node α being accessible. If α is the node accessible at the beginning of substage i, we remove β from A for every β to the right of α. If permitted, we may now act for requirement Q_{i}. In any case, we declare α q to be accessible for some q ∈ ω. If i < s, we proceed to substage i + 1. If i + 1 = s, we finish stage s and move on to stage s + 1. Our actions at substage i depend on the form of the requirement Q_{i}.

Q_{i} = N_{e}: Let r be the last α-stage, i.e., one at which α was accessible (0 if this is the first α-stage). Let k(α, s) be the least number enumerated in K since stage r, i.e., k(α, s) = min(K_{s} − K_{r}). We say that there is an α-believable computation of Φ_{e}(A ⊕ K; e)↓ if Φ_{e}(A ⊕ K↾k(α, s); e)↓ [s, i]. If there is such a computation with use u we declare α u to be accessible. If not, we declare α 0 to be accessible.

If Q_{i} is of the form R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ}, the killing point for α is α itself, i.e., the natural number coding the sequence α. The dependence of α’s actions on higher priority requirements in terms of its enumerating axioms in Λ is expressed in terms of its dependency set , D(α, s) = {⟨β, m⟩ | β ≤ α ∧ β is associated with P_{Δ,Γ} and has used m at some point prior to substage |α| of stage s}.

We begin substage i by having α impose a global wait for Γ(Δ, β, m) to be convergent for every ⟨β, m⟩ ∈ D(α, s), i.e., no node γ ≥ α associated with P_{Δ,Γ} can act at any stage t ≥ s unless Γ(Δ, β, m)↓ [t] for all ⟨β, m⟩ ∈ D(α, s). If this condition is not met, we proceed directly to the terminal step (5) below of substage i. Otherwise, our actions depend on whether Q_{i} is R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ}.

Q_{i} = R_{Δ,Γ,Ψ}: Step 1. If there is a marker x such that α is satisfied by x, i.e., Z(x)↓ = 1 and Ψ(x)↓ = 0 then we proceed to step 4 below. If not, we see if we can satisfy α via some marked x, i.e., we see if there is a marked x not controlled by any β < α such that Z(x)↑. In this case we set Z(x) = 1 by enumerating an axiom ⟨Δ_{s}↾ m, x, 1⟩ into Λ where m is the maximum of the length of any previous axiom for x in Λ and u(α, s) = max{γ(β, m)[s] | ⟨β, m⟩ ∈ D(α, s)}. (Note that all such γ(β, m) are defined by our global wait requirements.) If so, go to step 4. Otherwise, let d be the number of times α has been taken out of A and proceed to step 2.

Step 2. If α is not in A, put α into A and impose a global wait for an n > d, with Γ(Δ, α, n)↓ = 1, i.e., no action can be taken for any β ≥ α associated with P_{Δ,Γ} at any stage t ≥ s unless there is an n > d with Γ(Δ, α, n)↓ = 1[t] until α is removed from A. If at any t ≥ s we act for a requirement β on the basis of such a computation Γ(Δ, α, n) = 1, we say that α uses n at t. If this global wait condition is satisfied, we proceed to step 3. Otherwise, we go to step 5.

Step 3. If there is an unrealized follower x of α we proceed to step 4. If there is a realized follower x of α which is associated with a number n > d and Γ(Δ, α, n) = 1[s] then we mark x, remove α from A and proceed to step 4. If there is no such x but there is an m > d not used by α such that Γ(Δ, α, m) = 1[s] let n be the least such. We now use n by associating it with a follower x ∈ ω^{[i]} of α which is larger than any number mentioned so far. We set Z(x) = 0 by an axiom of length

u(α, s) = max ({γ(β, m)[s] | ⟨β, m⟩ ∈ D(α, s)} ∪ {γ(α, n)[s]}).

We say that x is realized at t ≥ s if Ψ_{t}(x) = 0, otherwise it is unrealized. In any case, we now go to step 4.

Step 4. We have α take control of every x < s, x ∈ ω^{[i]} which is not currently controlled by any β < α. (Of course, if δ > α had control of x before, it no longer does.) If x ∈ ω^{[i]} is now controlled by some δ ≤ α (which is necessarily associated with P_{Δ,Γ}), δ first took control of x at t ≤ s and Z(x) is now undefined (i.e., σ ⊈ Δ_{s} for every ⟨σ, x, j⟩ now in Λ), we redefine Z(x) to be its value at the last δ-stage (0 if there is none) via an axiom of length the maximum of that of any axiom previously defining Z(x) and u(δ, t, s) where u(δ, t, s) = max{γ(β, m)[s] | ⟨β, m⟩ ∈ D′(δ, t)} and D′(δ, t) = {⟨β, m⟩ | β ≤ δ ∧ β is associated with the same P_{Δ,Γ} as δ ∧ β has used n at some point prior to the end of substage |δ| of stage t}. We now go to step 5.

Step 5. If α is now in A, we let α 1 be accessible. Otherwise, we let α 0 be accessible. This ends substage i of stage s.

Q_{i} : S_{Δ,Γ,Ψ}: Step 1. If α is satisfied, i.e., there is an x controlled by α such that Ψ(Z; x)↓ ≠ Δ(x)[s], we go to step 4. Otherwise, we see if we can satisfy α, i.e., there is an n marked for α at some r < s such that, for every x < ψ(γ(α, n))[r, i], Z(x)[s, i] is either undefined or equal to Z(x)[r, i]. If so, α takes control of every x < ψ(γ(α, n))[r, i] with x ∈ ω^{[i]} such that Q_{i} is associated with P_{Δ,Γ} (no others can ever even appear to be in Z.) not controlled by some β < α. (Of course, no β > α controls any such x from now on.) For each such x, we redefine Z(x) to be Z(x)[r, i] by an axiom of length u(α, s). (The relevant γ(β, n) are all defined by our global wait requirements. Moreover, our procedures for redefining Z(x) (in Steps 4) guarantee that Z(x)↓ [s, i] for all x controlled by some β < α.) We now go to step 4. If we cannot satisfy α, we let d be the number of times α has been removed from A and proceed to step 2.

Step 2. If α is not in A, put α into A and impose a global wait for an n > d with Γ(Δ, α, n) = 1. If this condition is now satisfied we go to step 3. Otherwise we go to step 5.

Step 3. If there is an n marked for α such that Ψ(Z; x) is undefined for some x < γ(α, n)[s], go to step 4. If not and there is an unmarked n > d such that Γ_{1}(Δ, α, n) = 1[s] and Ψ(z)↾ γ(y, n) = Δ↾ γ(α, n)[s, i] then α uses and marks the least such n. We remove α from A and proceed to step 4.

Step 4. If x is controlled by some β ≤ α and Z(x)↑ [s, i], we redefine Z(x) as we did for R_{Δ,Γ,Ψ}.

Step 5. If α is now in A, α 1 is accessible. Otherwise, α 0 is accessible. This ends substage i of stage s.

End of Construction.

We must now verify that the construction defines a set A which satisfies all the requirements N and P_{Δ,Γ}. We begin by showing that there is a leftmost path f on the tree T of nodes α which are ever accessible and that (A ⊕ K)′ is determined by the outcome along f. Remember that an infinite path f on T is the leftmost path on T if ∀α ⊂ f (α is the leftmost node on level |α| of T which is accessible infinitely often).

Lemma 1.2. There is a leftmost path f on T and the outcomes along f are the true ones:

i) If Q_{i} is R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ} and α = f↾i, then α ∈ A ⇔ f(α) = 1.

ii) If Q_{i} = N_{e}, then Φ_{e}(A ⊕ K; e)↓ ⇔ f(i) = 1.

Proof. We proceed by induction on the length of α ⊂ f. Clearly α = ∅ is the leftmost sequence of length 0 accessible infinitely often. Suppose by induction that |α| = i and α is the leftmost node of length i accessible infinitely often. Let s_{0} be such that no node β <_{L} α is accessible at any s ≥ s_{0}.

i) If Q_{i} is R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ} and α is accessible at s, then α 1 is accessible if α is in A and α 0 is accessible otherwise. As α ∈ A iff it is in A from some point on, α A(α) is clearly the leftmost immediate successor of α which is accessible infinitely often.

ii) Q_{i} = N_{e}: We say an α-stage s is K-true if K_{s}↾ k(α, s) = K↾ k(α, s). There are clearly infinitely many such stages. The outcomes of α at such stages are what really matter.

Sublemma 1.2.1. If there is a K-true α-stage s_{1} ≥ s_{0} at which there is an αbelievable computation of Φ_{e}(A⊕K; e) with use u, then this computation is A⊕Kcorrect, i.e., (A ⊕ K)↾ u = (A ⊗ K)↾ u[s, i] and α u is accessible at every α-stage s ≥ s_{1}.

Proof. First note that α’s beliefs about A(β) for β < u and β ⊅ α are correct and return to their correct state at every α-stage s ≥ s_{1}. For β <_{L} α, this holds by our choice of s_{0}. For β >_{L} α, it holds by our removing β from A at the beginning of substage i of every α-stage. For β ⊂ α, it holds by induction. On the other hand, as long as α u is accessible, we cannot change A(β) for any β <_{L} α u. As K_{s}↾ u never changes by the definitions of a K-true α-stage and α-believability, we see that the current computation at s is α-believable at every α-stage. Of course, any β ⊇ α v for v ≥ u is itself bigger than u and so irrelevant. Thus A(β) is never changed at s ≥ s_{1} for β < u and β ⊃ α and so the computation is A ⊕ K correct as well. □

Note that we have now proved that α has a leftmost successor which is accessible infinitely often: If the hypotheses of Sublemma 1.2.1 hold then α u is accessible at all sufficiently large α-stages. If not, α 0 is accessible at every K-true α-stage. Thus there is a leftmost path f on Γ whose outcomes for nodes R_{Δ,Γ,Ψ} and S_{Δ,Γ,Ψ} are correct, i.e., (i) holds. We conclude the verification of Lemma 1.2 by establishing the following:

Sublemma 1.2.2. If Φ_{e}(A ⊕ K; e)↓ with use u, then α u is accessible at all sufficiently large α-stages.

Proof. The proof of Sublemma 1.2.1 shows that it suffices to prove that the correct computation is α-believable at some α-stage s ≥ s_{0} by which K_{s} ↾ uK ↾ u and k(α, s) > u. It also shows that α’s beliefs are correct at all such stages for all β ⊅ α. Let δ ⊂ f be of length u and suppose that δ is accessible at s_{1} ≥ s_{0}. By our results so far, ((i) holds), we know that A↾u[s_{1}, s_{1}] = A↾u. If s is the first α-stage after s_{1}, then no changes have been made on A(β) for β < α and so A↾u[s, i] = A↾u and the true computation of Φ_{e}(A ⊕ K; e)↓ is α-believable as required. □

Corollary 1.3. (A ⊕ K)′ ≡ K′.

Proof. Clearly K′ ≤ (A ⊕ K)′. It thus suffices to show that we can compute (A ⊕ K)′ from K′. Now, by Lemma 1.2, there is a leftmost path f on T. By definition, f ≤ K′. As the Lemma also shows that Φ_{e}(A⊕K; e)↓ ⇔ f(i) = 1 where Q_{i} = N_{e} we have the desired reduction. □

We now wish to show that the requirements P_{Δ,Γ} are met. If the hypotheses of P_{Δ,Γ} fail then there is nothing to prove. Note, however, that in any case no subrequirement of P_{Δ,Γ} has an effect on any α on the true path f which is associated with any other P_{Δ′,Γ′} (at least not after a stage after which no node to the left of α is ever accessible). Suppose, therefore, that the hypotheses of P_{Δ,Γ} are met. We prove by induction along f that the outcome of α ⊂ f associated with P_{Δ,Γ} satisfy the subrequirements of P_{Δ,Γ}. We must also show that Λ(Δ) = Z is total.

Lemma 1.4. Suppose the hypotheses of P_{Δ,Γ} are met and α ⊂ f is associated with P_{Δ,Γ}.

i) If Q_{|α|} = R_{Δ,Γ,Ψ} then there is a stage t_{0} such that at every s ≥ t_{0} either (as defined in Step 1) α is already satisfied or we satisfy α at s or α has an unrealized follower.

ii) If Q_{|α|} = S_{Δ,Γ,Ψ} then there is a stage t_{0} such that at every s ≥ t_{0} either (as defined in Step 1) α is already satisfied or we satisfy α at s or there is an n marked for α and an x < γ(α, n)[s] such that Ψ(Z; x) is undefined.

Proof. We suppose that the hypotheses of P_{Δ,Γ} are met and proceed by induction on α ⊂ f. First, note that (i) and (ii) imply that from some point on no action is taken for α except possibly in step 4 to redefine Z(x) for those x which α controls. More specifically, no more numbers are used or marked or followers appointed by α; Z(x) is not changed from its last value by α for any x; and no more global waits are imposed by α. All global waits for Γ(Δ, α, n)↓ are eventually met by the hypotheses of P_{Δ,Γ}. Any global wait for any n with Γ(Δ, α, n)↓ = 1 imposed in step 2 is permanent only if α is never removed from A (and so α ∈ A). Thus, by the hypotheses of P_{Δ,Γ}, any such condition is also eventually permanently met. Of course if β <_{L} α, then β is accessible only finitely often and the same conditions eventually hold for β as well. Suppose, therefore, that s_{0} is a stage after which no β <_{L} α is ever accessible but all these conditions always hold for β < α.

We divide the proof into cases according to whether α ∈ A or not.

α ∈ A: In this case, there is a stage s_{1} ≥ s_{0} after which α is never removed from A. Let d be the number of times α is removed from A. By the hypotheses of P_{Δ,Γ}, there is eventually a permanent current computation of Γ(Δ, α, n_{0}) = 1 for some n_{0} > d, s_{1}, say by s_{2} ≥ s_{1}. Similarly, for any finite set F we must eventually have Γ(Δ, α, n)↓ for every n ∈ F. Thus α must be accessible infinitely often at stages s ≥ s_{2} when all global wait conditions are satisfied.

It is now clear that if the conclusions of the Lemma do not hold then we will eventually associate some follower x with n_{0} and later mark it (if Q_{|α|} = R_{Δ,Γ,Ψ}) or use and mark n_{0} (if Q_{|α|} = S_{Δ,Γ,Ψ}). In either case, we would remove α from A for the desired contradiction.

α ∉ A: When α is accessible after s_{0} and not in A and all global wait conditions are met, we can be prevented from putting α into A only by satisfying α. Thus we may assume that we put α into A and remove it infinitely often. By the hypotheses of P_{Δ,Γ}, there must be an n_{0} such that Γ(Δ, α, n) = 0 for every n ≥ n_{0}. Consider now the n_{0}^{th} time we put α into A, say at stage s_{1} ≥ s_{0}. We impose a global wait for an n ≥ n_{0} such that Γ(Δ, α, n) = 1. Note that we can now act for α (and so define Z(x) for any new x at an s ≥ s_{1} for Q_{|α|} = R_{Δ,Γ,Ψ}) only when we either have α satisfied or an n ≥ n_{0} with Γ(Δ, α, n) = 1 which we have used.

We now assume that Q_{|α|} = R_{Δ,Γ,Ψ} and prove (i). As we remove α from A infinitely often, we must eventually appoint and then mark an x ≥ n_{0} at stages s_{3} ≥ s_{2} ≥ s_{1}, respectively. By our induction hypotheses and choice of s_{0}, α retains control of x and so Z(x) is, for all sufficiently large α-stages s, defined by axioms of length u(δ, t, s) (plus a constant) for a fixed t. By our hypotheses in P_{Δ,Γ}, lim_{s→∞} u(δ, t, s) exists and Δ is eventually constant on all the relevant uses. If α is not already satisfied, we can be prevented from satisfying α by defining Z(x) = 1 at such a point only by there being some axiom σ defining Z(x) = 0 which was put into Δ at some stage since x was appointed and is now Δ-correct. As we have noted, any such axiom contains the information needed to either satisfy α via some other x or to give a computation Γ(Δ, α, n) = 1 for some n ≥ n_{0}. As this correct Δ-information is, in fact, correct, we have the desired contradiction.

Finally, we assume that Q_{|α|} = S_{Δ,Γ,Ψ} and prove (ii). Consider the numbers x controlled by some δ < α at s_{1}. For each such x, Z(x) is defined by an axiom of length u(δ, t, s) (plus a constant) for a fixed t. By our hypotheses on P_{Δ,Γ}, we may choose a stage s_{2} ≥ s_{1} after which u(δ, t, s) is fixed as is Δ↾ u(δ, t, s) for each such x. As we remove α from A infinitely often, there is a stage s_{3} ≥ s_{2} at which we mark some n > n_{0}. By our choice of n_{0}, Γ(Δ, α, n) = 0. Once Δ↾ γ(α, n) has reached its correct value, we can be prevented from satisfying α (if it is not yet satisfied) only by there being an axiom σ defining some Z(x) inappropriately. By our assumptions, σ was put into Λ at a stage at which we had α satisfied or an n ≥ n_{0} with Γ(Δ, α, n) = 1 and this information was included in σ. Thus this information (about Δ) must be correct and we would either have α satisfied or have a correct computation Γ(Δ, α, n) = 1 for n > n_{0} for the desired contradiction. □

Lemma 1.5. If the hypotheses of P_{Δ,Γ} are met then Λ(Δ) = Z (for the associated functional Λ) is well defined and total.

Proof. As we only add a new axiom ⟨σ, x, j⟩ for x to Λ when all previous ones are incorrect (σ ⊈ Λ) and any new axiom is always at least as long as any previous one, Λ is consistent. Consider now any number x. If x ∉ ω^{[i]} for some i such that Q_{i} is an R_{Δ,Λ,Ψ}, Z(x) is set to be 0 by a trivial axiom. Suppose x ∈ ω^{[i]}, Q_{i} = R_{Δ,Γ,Ψ} and α ⊂ f is of length i. It is clear from the construction that α eventually takes control of x if it is not controlled by a higher priority requirement. As the priority ordering is well ordered, there is a highest priority β such that β ever controls x. Suppose β first takes control of x at t. It then controls x at every stage s ≥ t. Z(x), if undefined, is redefined when α is accessible at s via an axiom of length u(δ, t, s). Our assumptions on P_{Δ,Γ} guarantee that lim_{s→∞} u(δ, t, s) exists and so Z(x) is eventually defined by a fixed (necessarily Δ-correct) axiom. □

Lemma 1.6. If the hypotheses of P_{Δ,Γ} are met then Z = Λ(Δ) meets every subrequirement Q_{i} of the form R_{Δ,Γ,Ψ} or S_{Δ,Γ,Ψ} and so 0 <_{T} Z <_{T} Δ.

Proof. Let α be the initial segment of f of length i and let t_{0} be as in the conclusions of Lemma 1.4.

i) Q_{i} = R_{Δ,Γ,Ψ}: No new followers are ever appointed after t_{0}. If one of them, x, is unrealized then Ψ(x) ≠ 0 but Z(x) = 0 as we can never change the value of Z(x) once it is defined. Thus Ψ ≠ Z as required. Otherwise, there is a t_{1} ≥ t_{0} by which all the followers are realized. At every α-stage s ≥ t_{1}, α must be satisfied, i.e., Z(x)↓ = 1[s] and Ψ(x) = 0[s] for some follower x of α. As Z(x) is eventually constant by Lemma 1.4, Ψ(x) ≠ Z(x) for one of these x’s. Again Ψ ≠ Z as required.

ii) Q_{i} = S_{Δ,Γ,Ψ}: No numbers n are marked for α after t_{0}. By our hypotheses on P_{Δ,Γ}, γ(α, n)[s] is eventually constant for all n maked for α. If Ψ(Z; x) is not defined for some x < γ(α, n) for a marked n, then Ψ(Z) ≠ Δ. Otherwise, α is satisfied at every sufficiently large α-stage by Ψ(Z; x) ≠ Δ(x) for some x < γ(α, n) for one of the marked n. As Δ(x) and Ψ(Z; x) eventually stabilize for each such x, there is some x such that Ψ(Z; x)↓ ≠ Δ(x) as required. □

2. Jumps of minimal degrees in downward cones.

Theorem 2.1 Let D be any r.e. set with D′ >_{T} ∅′. Then there exists a set M of minimal degree with M ≤_{T} D and ∅′ <_{T} M′ ≤_{T} D′.

Proof. We will construct M ≤_{T} D by a full approximation construction along the lines of, for instance, Lerman [1983], Epstein [1975] and Yates [1970] with M = lim_{s} M_{s}. At each stage s, we shall construct nested sequences of recursive trees T_{α,s} ⊇ … ⊇ T_{λ,s} for certain paths α on the stage s priority tree. At stage s, if |σ| ≤ s, |β| ≥ e, and σ is on T_{β,s} then σ will have a j-state for some j ≤ e. Such a state is a string of length j + 1 that codes guesses as to the “arena” in which σ must live. (We will be assuming that the reader has at least nodding acquaintance, if not familiarity, with the full approximation technique. In particular, the notion of state will be somewhat similar to the usual notion of e-state, in the sense that it will characterize whether the node at hand is locally e-splitting. The notion of state will also need to encode additional Π_{2} behaviour, namely the behaviour of diagonalization requirements of stronger priority as they affect the trees we search to decide if splittings exist. Because of this nonstandard notion of state, in the full construction we shall replace “state” by “guess” to avoid confusion. However, in the discussion of the basic modules we will stick to state since the need for more elaborate notions only becomes apparent when we look at interaction between the requirements.) We will meet the minimality requirements below, for all partial recursive functionals Δ_{e}.

N_{e} : Φ_{e}(M) total ⇒ [(M ≤_{T} Φ_{e}(M)) ∨ (∅ ≡_{T} Φ_{e}(M))]

Additionally, we need to ensure that ∅′(= K) cannot compute the jump of M. In fact, we build a set V which is r.e. in M, and satisfy the following requirements.

R_{e} : Δ_{e}(K) ≠ V.

Let Q = K^{D} denote the standard enumeration of D′ so that K_{s}^{D_{s}} = Q_{s} = {e : {e}_{s}^{D_{s}}(e) ↓ & e ≤ s}. We briefly remind the reader of the manner by which one satisfies the N_{e}. We assume that the reader is familiar with, for instance, the Sacks [1961] construction of a minimal degree below 0′. However, our construction will be a full approximation one as follows. As with all known minimal degree constructions, in a full approximation argument, one tries to get M on either an e-splitting (partial recursive) tree or a tree with no e-splittings. For simplicity in the following discussion we will drop some of the tree notation and pretend that we are only constructing a nested sequence T_{0,s} ⊆ ...T_{s,s} and are working to maximise e-states on T_{e,s}. In the perfect set version à la Spector [1956] and Shoenfield [1971], one does this using recursive total trees, and uses 0′′ as an oracle to achieve this in one step. In the present construction, one can only work locally. With no permitting around, this simply corresponds to waiting till one sees extensions τ_{1}, τ_{2} of some node τ which are e-splitting at stage s. Clearly we need τ_{1} and τ_{2} on tree T_{e,s}, τ_{1} and τ_{2} having the same (e − 1)-state as τ, and τ_{i} ⊆ M_{s} for some i. If we see such τ_{1} and τ_{2} we can raise τ’s state to the high e-state ν 1, assuming it was in the low e-state ν 0. [We reserve ν for states; α, β, and γ for nodes on the priority tree (and sometimes states); μ, σ, τ, λ for strings; and φ and δ for uses corresponding to Φ and Δ, respectively.] So the idea is to slowly build the trees T_{e,s} as subtrees of T_{e−1,s} so that lim_{s} T_{e,s} is achieved stringwise. At each stage s, this enables us to define a string, M_{s}, of length s, the leftmost common path on T_{0,s}, … T_{s,s} of length s. By the way we define e-states and by construction, lim_{s} M_{s}(x) = M(x) will exist for all x. One can argue that M has minimal degree as in Sacks [3], except that in a full approximation argument we use e-states as follows. Let ν i (i = 0 or 1) be the well-resided e-state. By well-resided, we mean that for almost all σ on lim_{s} T_{e,s}, if σ is an initial segment of M, then σ has state ν i. If this state is ν 1 then we simply go to some σ ⊂ M on T_{e} such that all τ ⊇ σ on T_{e} have final e-state ν 1. From this parameter, as in the Sacks construction, we know that we can inductively generate M from the tree of extensions on T_{e} that achieve state ν 1 and Φ_{e}(M). Similarly, if i = 0, then there are no e-splittings on the “well-resided tree”, so any computation Φ_{e,s}(M_{s}; x) with M_{s} of the correct e-state must agree with Φ_{e}(M). [Minimality will then follow by the fact that we meet the R_{e} and hence M ≢_{T} ∅.]

We remark that in the present construction, the above is not quite correct, since we will construct at each stage s a path α_{s} (through the priority tree) that “looks correct”, and M_{s} will lie on the trees T_{γ,s} for γ ⊆ α_{s} where α_{s} denotes the path of length s that looks correct at stage s. As we see, this means that the trees are actually determined also by the actions of the jump requirements. The idea, however, is essentially the same.

Keeping M ≤_{T} D in the above construction entails adding r.e. permitting. For this theorem, we are able to use simple permitting. That is, we ensure that

D_{s}[x] = D[x] implies M_{s}[x] = M[x],
where E[x] = {z | z ∈ E & z ≤ x}.

Such permitting really causes no problems with the e-state machinery. Remember, we seek e-splittings τ_{1}, τ_{2} extending τ such that M_{s} ⊃ τ_{1} or M_{s} ⊃ τ_{2}. Without loss of generality, suppose M_{s} ⊃ τ_{1}. Then all that the minimality machinery requests is that we refine the tree to either cause M ⊃ τ_{1} or M ⊃ τ_{2} should M ⊃ τ. The point is that we can ensure this refinement while keeping M_{s} ⊃ τ_{1}. It follows that if Φ_{e}(M) is total then either Φ_{e}(M) ≡_{T} M or Φ_{e}(M) ≡_{T} ∅.

What becomes more difficult is to ensure that M is nonlow by meeting the R_{e}. Now we are only able to diagonalize against an “α-correct” version of V when permitted by D.

Thus, we now turn to the satisfaction of the jump requirements, keeping M′ >_{T} ∅′. To meet these requirements, the reader should recall that the plan is to build a set V which is Σ_{1}^{M} making sure that Δ_{e}(K) ≠ V. Let ℓ(e, s) = max{x : (∀y < x)[Δ_{e,s}(K_{s}; y) = V_{s}(y)]}. Of course, V is built by enumerating axioms relative to M. We meet these R_{e} requirements via a Sacks encoding type strategy, only here we desire to encode Q = K^{D} into V via axioms about M. The idea is to try to encode more and more of Q into more and more of V so that if Δ_{e}(K) = V, then K will be able to compute Q, since K will be able to ascertain if a coding location c(i, s) for i ∈ Q is final, for a contradiction.

So the idea is that when ℓ(e, s) > c(i − 1, s) we choose a coding location c(i, s) for coding whether “i ∈ Q”. For simplicity we will not worry about the interaction with the state machinery, but consider only the basic module. The idea in the basic module is to pick some number d(i, s) (intuitively the (lower bound on the) use of c(i, s)) so that the following four conditions are satisfied.

(i) There exists σ on T_{e,s} with σ = T_{e,s}(τ), say, so that one of T_{e,s}(τ 0) or T_{e,s}(τ 1) is an initial segment of M_{s}. Without loss of generality, assume this to be T_{e,s}(τ 0).

(ii) |σ| = d(i, s).

(iii) i ∈ K_{s}^{D_{s}} = Q_{s} and u({i}_{s}^{D_{s}}(i)) < d(i, s).

(iv) d(i, s) > t where t is the greatest stage, if any where d(i, t) was previously

defined. If such a number exists, we declare that d(i, s) is the axiom location for “c(i, s) ∈

V at s”. We enumerate an axiom saying that

if T_{e,s}(τ 0) ⊂ M then c(i, s) ∈ V.

Also R_{e} will assert control of the construction in the sense that it will constrain M to travel through T_{e,s}(τ 0) while the conditions above are maintained.

The key idea is that if i leaves Q (i.e. i ∈ Q_{s} − Q_{s_{1}} for some least s_{1} > s) it must be that D_{s}[u({i}_{s}^{D_{s}}(i))] ≠ D_{s_{1}}[u({i}_{s}^{D_{s}}(i))]. Hence, in particular, D permits below d(i, s) by (iii) above. Therefore by (i) and (ii), we can cause M to now extend T_{e,s}(τ 1) [instead of T_{e,s}(τ 0)], since we are D-permitted to do so. In such a case we will abandon T_{e,s}(τ 0) forever. [This abandonment makes it necessary to ensure that some strings are set aside for other lower priority requirements, but this causes no special problems. See the remarks below.]

Now d(i, s_{1}) becomes undefined (and hence the parameter d(i, −) will need to be redefined to a new number) and c(i, s) = c(i, s_{1}) leaves V_{s_{1}}. The next axiom location for c(i, s), if any, will be chosen so that the relevant analogues of (i)-(iv) all hold. Note that if the cycle recurs infinitely often then c(i, s) ∉ V and i ∉ Q.

The only problem that occurs with the cycle for i outlined above is the following. The cycle could cause unbounded constraint on M because Δ_{e}(K) may not be total, but could have unbounded use for some c = c(i, s). Imagine δ_{e,s}(c) → ∞. As with the density theorem for the r.e. degrees, we might define coding locations c(i′, s) for all i′ > i and eventually this might cause M to be recursive, although Δ_{e}(K; c) ↑, since lim sup ℓ(e, s) = ∞. To overcome this familiar problem, when we pick a coding location c(i, s) for i at stage s if the Δ_{e}(K_{s}; c) ↓ computation is later seen to have incorrect K-use we cancel c(i′, s) for all i′ > i and pick c(i′, t) anew later (where c(i′, t) > s) (we call this kicking). For all such c(i′, s), we also declare d(i′, s) to be undefined; we do not cancel the corresponding T_{e,s}(τ 0) or T_{e,s}(τ 1) but release them to the construction.

The conclusion that Δ_{e}(K) ≠ V remains correct since using δ_{e,s} and K_{s}, K can still decide if a coding location is final.

Finally, in the full construction, we will need to deal with various versions of the R_{e} and N_{e} above working in a “tree of strategies” type of setting. Coding locations with the wrong guesses will need to be initialized and kicked as above. An R_{e} requirement at node α which is guessing that ν is the well-resided “e” guess (note “guess” not “state”) will need to wait till it sees σ’s and τ’s of guess ν before it enumerates an axiom involving an axiom location d(α, i, s) for the coding location c(α, i, s). The reader should note that the trickiest part of the construction is to get the correct environment within which each R_{e} operates. Here, not only do we need to guess the lim inf of the length of agreement associated with R_{e−1}, but the exact behavior of the various markers associated with this lim inf. We now turn to the formal details.

Remarks. As we mentioned above, the reader should note that a single c(α, i, s) has the potential of killing all of the tree T_{α} save for one branch (making M recursive) if we are not careful. If i ∉ Q but i is in Q_{s} infinitely often, then the R_{e} cycle could be repeated infinitely often for the sake of i. As above the action of the R_{e} is to kill T_{α}(σ j) and if we then killed one extension of T_{α}(σ (1 − j)) and so forth, one could kill all but one path on the tree. This is fine from R_{e}’s point of view, but has the potential for making M recursive. To ensure that this problem is avoided we shall use various control devices to guarantee that there will be enough available branches for the relevant requirements when we play the appropriate outcome of R_{e}. This is a little messy but is the point of the control functions count(α, s) and maxcount(α, s), and the freezing machinery. The idea is that suppose we wish to play an outcome o of α, as its guess has just looked correct. At this stage we acknowledge that we want a supply of strings available to the nodes guessing α o when we pass α o. We will not allow α, or any guesses extending α o, to assign any strings until we see count(α o, s) exceed a previous bound maxcount(α o, s), or we unfreeze the node because we see many strings of the appropriate guess. We increment count(α o, s) each time we visit α and would like to play α o. In this way, when we actually get to play α o we have many strings to assign to nodes guessing α o.

The priority tree. We generate the priority tree P T by induction first on length and then on the lexicographic ordering generated by the ordering < that we define on outcomes. We also denote this lexicographic ordering on nodes by <. It is the usual priority ordering. The left-to-right ordering α <_{L} β is defined as usual by α < β and α ⊈ β. On any path ρ a requirement is assigned to a node σ ⊂ ρ as follows. Assign N_{0} to λ, the empty string. We write e(λ) = 0 and req(λ) = N_{0}. λ will have outcomes 0 and 1, meaning that λ 0 = 0 and λ 1 = 1 are on P T. The idea here is that the outcome 1 corresponds to M lying upon a 0-splitting tree and we set 1 < 0. To each of λ’s outcomes we now assign a version of R_{0} so that req(0) = req(1) = R_{0}, and e(0) = e(1) = 0.

Each version of R_{0} will sit atop an infinite tree of outcomes of R_{0}, the R_{0} tree, coding the precise behavior of the coding locations, axiom locations and K-uses. At the top level will be the node σ with the c(0)-outcomes of R_{0}. Namely, σ will have outcomes (in < order)

⟨0, u⟩, ⟨0, ∞⟩, ⟨0, d⟩, ⟨0, f⟩.

The intended meaning of these outcomes is as follows: ⟨0, u⟩: c(σ, 0) (= lim_{s} c(σ, 0, s)) has unbounded Δ_{0}(K) -use (“u” for “unbounded”). ⟨0, ∞⟩: This corresponds to no win via c(σ, 0), but we change d(σ, 0, s) infinitely

often. In essence, this entails Δ_{0}(K; c(σ, 0)) = 0 and cycling through ⟨0, d⟩ infinitely often.

⟨0, d⟩: c(σ, 0) witnesses a win by a disagreement (“d” for “disagreement”). ⟨0, f⟩: No win via c(σ, 0) and we only change d(σ, 0, s) finitely often (“f” for “fi-

nite”).

Remark. The reader should note that the outcomes ⟨0, ∞⟩ and ⟨0, f⟩ do not code a win for σ but do code the behavior of σ’s action with respect to c(σ, 0). The idea is that we will continue to try to satisfy R_{0} at each of these outcomes generating an R_{0} tree as described below.

In general to define the R_{0} tree below σ suppose we have defined τ to be in this tree. If τ is of the form μ ⟨i, u⟩ or μ ⟨i, d⟩, then τ represents a win for R_{0} and we would assign N_{1} to τ. If τ is of the form μ ⟨i, ∞⟩ or μ ⟨i, f⟩, then we again assign R_{0} to τ and give it outcomes ⟨i + 1, u⟩, …, ⟨i + 1, f⟩. (See Diagram 1.)

For the full priority tree we assign N_{e} and R_{e} in order as above with e in place of 0 for the highest priority requirement not yet (completely) assigned. Note that the presence of R_{e} trees means that there exist paths P on P T whose nodes are only assigned to finitely many requirements. For such a path, almost all of the nodes will be assigned to a fixed R_{e} and will be of the form μ ⟨i, ∞⟩ or μ ⟨i, f⟩. We will need to argue that none of these paths is the true path of the construction, and hence all requirements get their chance to be met.

Parameters and Terminology for the Construction.

c(α, i, s) : The coding marker associated with “ i ∈ D′ ” at guess α at stage s. c(α, i, s) is targeted for V. We attempt to code D′ into V via these markers.

d(α, i, s) : The current axiom location for “c(α, i, s) in V at stage s.”

count(α, s) : A control function at guess α used to ensure that when we play an N_{e}-node α then there are many unused strings available for guesses below α.

maxcount(α, s) : The reference control function that count(α, s) must exceed before we can play α.

α-freezing : While a node α is waiting to see enough strings to make it seem reasonable to play outcome o then we will say that the node is frozen with outcome o.

req(α) : The requirement assigned to α.

e(α) : The index of the requirement req(α).

j(α) : The j for which α is used to code “c(α, j, s) ∈ V.”

ℓ(e(α), s) = max{x : ∀y < x(Δ_{e,s}(K_{s}; y) = V_{s}(y)))}.

The most complex requirements are the higher level Sacks coding requirements, the R_{e}. The reader should think of their action as that of an automaton.

Construction, stage s + 1:

In substages we shall generate a guess (i.e. a node on the tree) α_{s+1} that looks correct, and a collection of trees T_{γ,s+1}(for γ ⊆ α_{s+1} and req(γ) of the form N_{e}). For convenience, let T_{λ,0} = 2^{<ω}. Initially, let all μ on T_{γ,0} have e-guess λ. We proceed in substages t ≤ s + 1. We will append a superscript t to a parameter to indicate its guess at the end of substage t. (At substage 0, the initial value of a parameter will be its value at the end of stage s). We also suppose that we are told that s + 1 is an α-stage (α = α_{s+1}^{t}) at the end of each substage t (α = λ initially).

Our action will be to determine how to modify trees, guesses, etc., and to define the outcome of α_{s+1}^{t}. Our actions will be determined by s, t, and req(α). We will assume that if req(α) = R_{e}, we are at the top of an R_{e} tree. We often use the phrase “initialize α.” This follows standard usage, and means cancelling α’s followers, etc. Furthermore, if β <_{L} α initializes α (β is visited at s + 1, say) then we let T_{α,s+1} be the full subtree of T_{β,s+1} extending M_{s+1} above T_{β,s+1}(τ)) with |τ| = s + 1 and M_{s+1} ⊃ T_{β,s+1}, with all guesses becoming initialized. Finally setting a value for α_{s+1} ends a stage.

Convention. We will also adopt the following convention that saves on terminology. During the construction we can visit nodes ν in one of two ways. One way is to visit them at substage t of stage s such that for all ν′ ⊆ ν we also visited ν′ at the same stage. The other possibility is that we did not visit some ν′ ⊆ ν during stage s but jumped directly to ν because although ν′ was not accessible, there was a permitted action at ν. In the latter case, we adopt the convention that visiting ν either ends the stage or we visit some ν̂ ⊃ ν via a permitted action. As we shall see when we act in this way we do not appoint markers etc. but merely modify trees.

Definition 2.2. We say that α (on P T) has a permitted action at substage t of stage s + 1 if, for some j,

(i) c = c^{t}(α, j, s + 1) is defined, (ii) c ∈ V_{α,s+1}^{t}, and (iii) j ∉ Q_{s+1} (i.e. {j}^{D}(j)[s + 1] ↑).

Substage t: Let α be the node eligible to act at substage t.

Case 1: req(α) is N_{e}.

Subcase 1: There exist τ, τ_{0}, τ_{1} such that τ, τ_{0}, and τ_{1} are on T_{α,s+1}^{t} with τ = T_{α,s+1}^{t}(η), τ_{1} = T_{α,s+1}^{t}(η_{1}), τ_{2} = T_{α,s+1}^{t}(η_{2}), and

(i) τ_{0} and τ_{1} e-split τ, (ii) τ_{0} <_{L} τ_{1}, (iii) τ_{0} ⊆ M_{s} or τ_{1} ⊆ M_{s}, (iv) τ, τ_{0}, τ_{1} had e-guess α 0 at the beginning of substage t,

(v) |η_{0}|, |η_{1}| > maxcount(α 1, s) (the last stage at which α genuinely had outcome 1), and

(vi) τ is the shortest such string.

Action: For ρ ⊅ η, let T_{α,s+1}^{t+1}(ρ) = T_{α,s+1}^{t}(ρ). For ρ ⊃ η and i < 2, define T_{α,s+1}^{t+1} via

T_{α,s+1}^{t+1}(η i σ) = T_{α,s+1}^{t}(η_{i} σ).

Raise the e-guess of τ to α 1. All else remains the same.

Set count(α 1, s + 1) = count(α 1, s) + 1. There are three subcases.

Subcase 1a: count(α 1, s + 1) < maxcount(α 1, s) and there exists a β ⊇ α 1 with a permitted action.

Action: Set α_{s+1}^{t+1} = β and declare s + 1 to be an α γ-stage for all α γ ⊆ β. [For all γ with α 1 ⊆ α γ ⫋ β, however, s + 1 not a genuine α γ-stage. A stage is a genuine η-stage if we actually visit η at one of its substages.]

Subcase 1b: count(α 1, s + 1) < maxcount(α 1, s) but Subcase 1a fails to apply.

Action: Set α_{s+1} = α 0 and declare s + 1 to be an α 0-stage. [This ends the stage. Recall that a low count indicates we have not yet seen enough potential strings in the good guess.]

Subcase 1c: count(α 1, s + 1) ≥ maxcount(α 1, s).

Action: Set maxcount(α 1, s+1) = s+1 and reset count(α 1, s+1) = 0. Declare s + 1 to be an α 1-stage and set α_{s+1}^{t+1} = α 1.

Subcase 2: Subcase 1 does not hold, but there exists a permitted action at some β ⊇ α 1.

Action: For the highest priority such β (that is, the lexicographically least) let α_{s+1}^{t+1} be β and declare s + 1 to be an α γ-stage for all α γ ⊆ β. [For all γ with α 1 ⊆ α γ ⫋ β, however, s + 1 is not a genuine α γ-stage]. Otherwise nothing changes.

Subcase 3: Otherwise.

Action: Nothing changes. Set α_{s+1}^{t+1} = α 0. Declare s + 1 to be an α 0-stage. Case 2: req(α) is R_{e}. We begin with the case that α is the top of an R_{e}-tree. We

continue to consider R_{e} until we play either an outcome ⟨j, d⟩ or ⟨j, u⟩ for some j. We consider the j in order, beginning with j = 0. Suppose j = 0 or we have already considered j − 1 and are considering j. We can assume that we have inductively generated a string α γ(j) so that α γ(j) ⊆ α_{s+1} and for all j′ < j, there exist η, k with α η ⟨j′, k⟩ ⊆ α γ(j) and k ∈ {∞, f}. [For j = 0; γ(j) = λ.] Finally, we let T_{η,s+1}^{t} = T_{α,s+1}^{t} for all η extending α which are devoted to R_{e} below α, i.e. they all use the same tree.

Pick the first subcase that applies and perform the action indicated. Here let s_{0} be the last genuine α γ(j)-stage at (the beginning of) which α γ(j) was not frozen.

Subcase 1: c = c^{t}(α, j, s + 1) is undefined.

Action: Pick a large fresh number c = c^{t+1}(α, j, s + 1) and set α_{s+1} = α_{s+1}^{t+1} = α γ(j).

Subcase 2: α has a permitted action at substage t of stage s + 1.

Action: Let d = |T_{α,s+1}^{t}(τ i)| be the use of “c ∈ V_{α,s+1}^{t}” (where T_{α,s+1}^{t}(τ i) ⊂ M_{s+1}^{t}); abandon the part of T_{α,s+1}^{t} above T_{α,s+1}^{t}(τ i) by setting

T_{α,s+1}^{t+1}(η) = \{ \begin{matrix}T_{α,s+1}^{t}(η), & if η ⊉ τ \\ T_{α,s+1}^{t}(τ (1 − i) η_{0}), & if η ⊇ τ, say η = τ η_{0} \end{matrix}

(and so c ∉ V_{α,s+1}^{t+1}); let M_{s+1}^{t+1} be a path through T_{α,s+1}^{t+1} extending T_{α,s+1}^{t+1}(τ (1−i)); declare α γ(j) frozen with outcome u (if α γ(j) was already frozen with outcome u or if Δ_{e}^{K} ↾ (c + 1) was not defined at any time since stage s_{0}) or with outcome ∞ (otherwise); and set α_{s+1}^{t+1} = α γ(j) ⟨j, u⟩ or α γ(j) ⟨j, ∞⟩, respectively.

Subcase 3: α γ(j) is frozen (with outcome o since stage s_{0}, say).

Action: Check if there are at least s_{0} many strings τ such that

(i) τ is on T_{α,s+1}^{t}, say τ = T_{α,s+1}^{t}(ν), (ii) τ ⊂ M_{s+1}^{t}, (iii) the e(η)-guess of T_{α,s+1}^{t}(ν i) is α(e(η)) for all N-strategies η ⊂ α and all i < 2, and (iv) |(T_{α,s+1}^{t})^{−1}(τ)| > s_{0}.

If so then declare α γ(j) no longer frozen, and let α γ(j) have outcome o. If furthermore

(v) α γ(j) was frozen with outcome ∞, and (vi) c ∉ V_{α,s+1}^{t} and j ∈ Q_{s+1} (i.e. {j}^{D}(j)[s + 1] ↓), then enumerate c into V_{α,s+1}^{t+1} with use T_{α,s+1}^{t}(ν i) where τ is the longest string satisfying (i)-(iv) not used by a strategy ⊂ α γ(j) for V -enumeration and T_{α,s+1}^{t}(ν i) ⊂ M_{s+1}^{t}.

Otherwise, i.e. if (i)-(iv) fail, α γ(j) remains frozen with outcome o. In either case, we set α_{s+1}^{t+1} = α γ(j) ⟨j, o⟩.

Subcase 4: Δ_{e}^{K} ↾ (c + 1) has not always been defined since stage s_{0}. Action: Declare α γ(j) frozen with outcome u and set α_{s+1}^{t+1} = α γ(j) ⟨j, u⟩. Subcase 5: Q(j) has changed since stage s_{0}, i.e. there are stages s_{1}, s_{2} ∈

[s_{0}, s + 1] such that exactly one of {j}^{D}(j)[s_{1}] ↓ and {j}^{D}(j)[s_{2}] ↓ holds. Action: Declare α γ(j) frozen with outcome ∞ and set α_{s+1}^{t+1} = α γ(j) ⟨j, ∞⟩. Subcase 6: j ∈ Q_{s+1} and c ∉ V_{α,s+1}^{t}. Action: Declare α γ(j) frozen with outcome ∞ and set α_{s+1}^{t+1} = α γ(j) ⟨j, ∞⟩.

Subcase 7: Δ_{e}^{K} ↾ (c + 1) = V_{α} ↾ (c + 1) has not always held since stage s_{0}. Action: Declare α γ(j) frozen with outcome d and set α_{s+1}^{t+1} = α γ(j) ⟨j, d⟩. Subcase 8: Otherwise. Action: Let α γ(j) have outcome f and set α_{s+1}^{t+1} = α γ(j) ⟨j, f⟩. This completes the action of α γ(j). We now initialize all strategies ξ >_{L} α_{s+1}^{t+1}

and check if

(i) α γ(j) is now frozen and there is a strategy β <_{L} α_{s+1}^{t+1} or ⊇ α_{s+1}^{t+1} with a permitted action (as defined in Subcase 2 above), or (ii) there is a strategy β <_{L} α_{s+1}^{t+1} with a permitted action.

If so then let the highest-priority such β act next. Otherwise, let α_{s+1}^{t+1} act at the next substage (if α γ(j) is not frozen now and Subcase 1 above did not apply) or end the stage (otherwise).

End of construction.

Verification. The reader should note that M ≤_{T} D because we always maintain the simple

permitting invariant : M_{s}[x] = M[x] if D_{s}[x] = D[x]. [While we might refine the underlying trees, we only change M due to a permitted action.] Let T P denote the true path.

We need to argue that for all α ⊆ T P, the following hold:

(i) lim_{s} T_{α,s} = T_{α} exists stringwise. (ii) Let α = α^{−}a. If req(α^{−}) = N_{e}, then for almost all σ on T_{α} with σ ⊆ M

the e(α^{−})-guess of σ agrees with α. (iii) If α ⊆ T P then there are infinitely many α-stages and α is only initialized

finitely often. (iv) If req(α) = R_{e} then there are at most finitely many α′ on T P with req(α′) =

R_{e} and R_{e} is met by some such α′. Furthermore, if req(α) = req(α′) then for all η with α ⊆ η ⊆ α′, req(η) = R_{e}.

(v) Let α be the shortest string on T P with req(α) = R_{e} and let τ be any such string. Let τ a ⊂ T P. Then a is of the form ⟨j, ⟩, and lim_{s} c(α, j, s) = c(α, j) exists. Furthermore the following hold:

(va) If a = ⟨j, u⟩ then the K-use of Δ_{e}(K; c(α, j)) is unbounded.

(vb) If a = ⟨j, ∞⟩ then Δ_{e}(K; c(α, j)) = 0 and j ∉ Q, c(α, j) ∉ V, and d(α, j, s)

tends to infinity as s does. (vc) If a = ⟨j, d⟩ then Δ_{e}(K; c(α, j)) ≠ V (c(j)) and d(α, j, s) is only reset finitely

often. (vd) If a = ⟨j, f⟩, then Δ_{e}(K; c(α, j)) is defined, equals V (c(j)) and d(α, j, s) is

reset only finitely often.

These are all fairly straightforward and are verified by simultaneous induction. Let α ⊆ T P and let s_{0} be a stage such that we are never again to the left of α, and α is not initialized after s_{0}.

We begin with (i). If req(α) is R_{e}, then α is devoted to some subrequirement attempting to produce a disagreement at some j in the R_{e} tree below some σ. Note that all the α′ in this tree work on the same T_{σ}. Now α only modifies trees in Subcase 2, where it deletes nodes, and redefines the tree. But whenever we do this we pick ν at the end of Subcase 3 much longer the next time. From this and the induction hypothesis it follows that lim_{s} T_{α,s} = lim_{s} T_{σ,s} exists stringwise. In the case that req(α) = N_{e}, we see that (i) follows immediately for α since we were permitting, and only raise guesses.

To see that (ii) holds, after stage s_{0}, we know that α^{−} and α will not be initialized, and that req(α^{−}) = N_{e}. If α = α^{−}1, then we only get to play α when we see a new splitting (Case 1, Subcase 1), or there is a permitted action at some β ⊇ α. In either case, the only places we will change M_{s} will be on trees T_{γ} for γ ⊇ α, and by induction, these will only involve strings of e guess α. Note that the same can be said of the case α = α^{−} 0 since we will not be to the left of α again.

Turning to (iii), we can suppose that there are infinitely many α^{−}-stages and all of the above holds for α^{−}. If req(α^{−}) = N_{e}, then we know α = α^{−} 0 or α = α^{−} 1. In the former case, after some stage we will set a new count which is never exceeded. (Otherwise, we would move left of α.) This means that T_{α,s} is never again reset and all the nodes on it are of guess ⊆ α^{−} 0. Since (iii) holds for nodes ⊆ α^{−}, it follows that α^{−} is given arbitrarily large numbers of strings of guess α^{−}. These strings constitute an infinite collection with guess α^{−} 0 = α. The case α = α^{−} 1, is similar, only there we know that infinitely often we see further strings with guess α^{−}. We only need to argue that infinitely often count(α^{−}, s + 1) is exceeded.

We remark that the same argument works for req(α^{−}) = R_{e} via the freezing machinery in place of the count machinery. Thus a node is frozen and waits in Subcase 3. The result now follows from (ii) and the induction hypothesis applied to α^{−}.

To establish (iv) and (v) we argue exactly as in the basic module. The trees T_{α} for α ⊆ T P are not initialized after a certain stage s_{0}. Let α be the top of an R_{e} tree with α ⊆ T P. All its nodes β ⊃ α are devoted to R_{e} and T_{α}. Now the key point is that for nodes in the R_{e}-tree of the form α γ(j) = α^{j}, if d = d(j, α, s) is defined, then whenever j leaves Q at stage s + 1 we will be able to cancel d via Subcase 2 as there will be a permitted action at α^{j} and hence s will either be a genuine α^{j}-stage, or s will be a β-stage for some β to the left of, or below α^{j}. In the latter case we will have picked d after we visited β and hence β’s action will also move M_{s} from extending the string corresponding to d at α^{j}. The remaining details are to do a routine case by case analysis of the subcases to show that our construction mirrors the basic module, with the additional freezing delay put in to ensure that β ⊃ α have enough strings to work with. These details are by and large straightforward, and should probably be apparent now to the reader, but we supply some as examples. First note that (va) holds since we only play the outcome ⟨j, u⟩ when the K use of Δ_{e}(K; c(α, j)) has been seen to increase. Since τ ⟨j, u⟩ ⊂ T P, we know that c(α, j) reaches a limit and hence the fact that the use increases infinitely often implies that for the final c(α, j) the use is unbounded. Similarly for (vb), we must have that Δ_{e}(K; c(α, j)) equals 0. As with the basic module, each time we unfreeze τ we will get to assign d(α, j, s) corresponding to the same c(α, j), and after this j will later leave Q, and hence (vb) follows since then the Δ_{e} use has finite limit but {j}_{s}^{D}(j) ↑ by divergence. The other two cases are similar. Finally, to see that (iv) holds, suppose that it fails. Then below α the only nodes on the true path are ones of the form τ a with e(τ) = e = e(α), and a ∈ {∞, f}. We claim that K can compute Q. To see this once α will never again be initialized, any c(α, j, s) once defined will be fixed unless the K-use of c(α, i, s) changes for some i < j. We know that all such uses reach a limit so for each j, some incarnation of c(α, j, s) is eventually fixed. Furthermore, note that since K can figure out if the use at c is final, K can figure out if an incarnation of c(α, j) is the final one. By induction, and the argument above we see that (vb) or (vd) applies to all nodes on the true path above α. We can therefore apply the argument of the basic module, and conclude that j ∈ Q iff c(α, j) ∈ V.

The argument that M is minimal is totally routine. To see that all the N_{e} are met, pick ρ on T P devoted to N_{e}, and look at its outcomes. First, since ρ is only initialized finitely often, for almost all strings on T_{ρ}, ρ will be able to raise guesses at will. Because of this the standard argument will work. We leave the details to the reader. □

We now immediately have the desired corollary showing that the range of the jump operator on the minimal degrees below 0′ cannot be characterized simply in terms of the jump classes of degrees r.e. in and above 0′.

Corollary 2.3. If c > 0′ is r.e. in 0′, then there is a minimal degree m < 0′ such that 0′ < m′ ≤ c.

3. Some related results on minimal degrees.

We now sketch the proof of two related results on jumps of minimal degrees below 0′. We assume familiarity with the standard oracle construction of a minimal degree below 0′ introduced by Shoenfield [1966] as in Lerman [1983, IX.2] (whose notation we adopt below) and the diagonalization method introduced by Sasso [1974] using what Lerman [1983, V.3] calls narrow trees to construct a minimal degree a < 0′ with 0′ < a′ as in Lerman [1983, V.3 and IX.2.11]. We also assume familiarity with the standard method of recursively approximating the answer to a Σ_{1}^{B} question for low B originally introduced in Robinson [1971] as in Soare [1987, XI.3]. We use this method relativized to 0′.

Theorem 3.1. If c is r.e. in and above 0′ and c′ = 0′′ then (uniformly in the information) there is a minimal degree a < 0′ with a′ ≰ c.

Proof (Sketch). We replace the nonrecursiveness requirements in the oracle construction of a minimal degree a < 0′ by ones to guarantee that Φ_{i}(C) ≠ A′. At each stage s of the standard construction we would have a sequence of partial recursive trees T_{0,s}, …, T_{n_{s},s} such that T_{i+1,s} is either Ext(T_{i,s}, σ), the full subtree of T_{i,s} above σ, for some σ or Sp(T_{i,s}, i), the (partial recursive) i-splitting subtree of T_{i,s}. Instead, we now have a sequence in which T_{2i+1,s} is either a full subtree of T_{2i,s} or Nar(Ext(T_{2i,s}, σ)), the narrow subtree of some full subtree of T_{2i,s}. (The narrow subtree of T is the tree which eliminates the right hand branches above all nodes at odd levels of T. Nar(T)(σ) = T (σ ⊕ 0^{n}) where n = lh(σ).) Moreover, T_{2i+2,s} is either a full subtree of T_{2i+1,s} or the i-splitting subtree of T_{2i+1,s}.

It is easy to see that we can recursively in (the index for) T_{2i,s} calculate an x such that if A is on T_{2i,s} then x ∉ A′ iff A is on T_{2i+1,s}, the narrow subtree of T_{2i,s}. If, at stage s of our construction, we see that Φ_{i}(C; x)[s] = 0 then we would like to let T_{2i+1,s+1} be some full subtree of T_{2i,s} which forces A off T_{2i+1,s} such as Ext(T_{2i+1,s}, 01). The problem is that, as the construction is recursive in 0′ and C is only r.e. in 0′, this computation may prove false. We use the low oracle approximation procedure to prevent us from acting infinitely often for this requirement.

At stage s we first redefine the trees T_{0,s}, …, T_{n_{s},s} as in the standard construction (to attempt to satisfy the minimality condition). We then see if there is a 2i < n_{s} for which we do not think we have satisfied the requirement Φ_{i}(C) ≠ A′; Φ_{i}(C; x) = 0[s] where x is calculated from T_{2i,s} as above; and our oracle approximation procedure says that there is a stage with these properties at which the C computation is actually correct. (If the approximation says “no” we speed up our enumeration of C and the approximation until either we no longer have Φ_{i}(C; x) = 0 or the approximation says “yes.”) If so, we let T_{2i+1,s+1} be a full subtree of T_{2i,s} (= T_{2i,s+1}) which forces A off T_{2i+1,s}. (As usual, n_{s+1} = 2i + 1.) If not, we make no additional changes in the trees to get the other T_{i,s+1}.

The only new element of the verification is the analysis of the effects of moving off the narrow subtrees. The lowness of C over 0′ (and the recursion theorem relative to K) guarantees that our K-recursive approximation is correct and so we act only finitely often to satisfy the requirement Φ_{i}(C) ≠ A′ and we eventually C-correctly satisfy it. As this action is finite, the argument that the trees T_{i,s} are eventually constant and the minimality requirements are satisfied proceeds as usual. □

A nonuniform version of the above result also follows from the following.

Theorem 3.2. There are minimal degrees a_{0}, a_{1} < 0′ such that a′_{0} ∪ a′_{1} = 0′′.

Proof (Sketch). Simultaneously build two sets A_{0}, A_{1} of minimal degree as above but use the narrow subtrees in each construction to code the final result of the other in an interleaved way as in Simpson [1975]. Suppose the sequences of trees for A_{0} and A_{1} at stage s are ⟨T_{0,s}^{0}, …, T_{n,s}^{0}⟩ and ⟨T_{0,s}^{1}, …, T_{n_{s},s}^{1}⟩, respectively, and α_{j,s} = T_{i}^{j}(σ_{i,j}, s) for j = 0, 1. We will also use the narrow subtrees to code ∅′′ into A′_{0} ∨ A′_{1} in place of diagonalization. At each stage s of our construction we will have, for j = 0, 1, a sequence of (partial recursive) trees ⟨T_{0,s}^{j}, …, T_{n_{s},s}^{j}⟩ and an initial segment α_{j,s} of A_{j} with strings σ_{i,j,s}, i ≤ n_{s}, such that T_{i,s}^{j}(σ_{i,j,s}) = α_{j,s}. In particular, σ_{n_{s},j,s} = ∅. T_{0,s}^{j} = id for every s while, for k ≥ 0, T_{2k+j+1,s}^{j} will be either the k–splitting subtree of T_{2k+j,s}^{j} or a full subtree of T_{2k+j,s}^{j}. Alternating with these trees, we will have ones T_{2k+j+2,s}^{j} (k ≥ 0) which will be narrow subtrees of some full subtree of T_{2k+j+1,s}^{j}.

At stage s, we first find the least k such that T_{2k+j+1}^{j} is not defined at α_{2k+j+1,s}∗ 01, (j = 0, 1). If there is an i < k enumerated in ∅′′ at s, we record this fact by forcing A_{1} off the narrow subtree of T_{2i,s}^{1}. We let n_{s+1} = 2i + 1 and T_{2i+1,s+1}^{1} = Nar(Ext(T_{2i}^{1}, α_{2i,1,s} ∗ 01)). No other trees are changed.

If no i < k is enumerated in ∅′′ at stage s and 2k+j +1 ≤ n_{s}, we let n_{s+1} = 2k+ j + 1 and set T_{n_{s+1},s+1}^{j} = Ext(T_{2k+j,s}^{j}, τ) where T_{2k+j,s}^{j}(τ) = T_{2k+j+1}^{j}(α_{2k+j+1} ∗ 0) and T_{n_{s+1},s+1}^{1−j} = Ext(T_{2k+j,s}^{1−j}, α_{2k+j,s} ∗ 01). All trees with smaller indices remain as at stage s. In this case, we satisfy the kth minimality requirement for A^{j} as there are no k–splittings on T_{2k+j,s+1}^{j} above α_{j,s+1}. We also record the fact in A^{1−j} that we switched from a k–splitting subtree by forcing α_{1−j,s+1} off the narrow subtree of T_{2k+j,s+1}^{1−j}.

If no i < k is enumerated and 2k + j + 1 = n_{s} + 1 we extend our sequences of trees by setting n_{s+1} = n_{s} + 1 and

T_{n_{s}+1}^{j} = Nar(T_{n_{s}}^{j})
T_{n_{s}+1}^{1−j} = Sp(T_{n,s}^{1−j}, k).

Clearly the number of times a tree T_{i,s}^{j} is changed is finite and so we can argue as usual that the A_{j} are of minimal degrees. We claim that we can compute ∅′′ and recover the sequence (of indices for) T_{i}^{j} = lim T_{i,s}^{j} from A′_{0} ⊕ A′_{1}. Suppose we have T_{0}^{0}, …, T_{2i}^{0} and T_{s}^{1}, …, T_{2i}^{1} and have computed ∅′′ ↾ i and a stage s_{2i} by which all of these have settled down. We ask A′_{1} if A_{1} is on Nar(T_{2i}^{1}). If so, i ∉ ∅′′, T_{2i+1}^{0} = Sp(T_{2i}^{0}), T_{2i+1}^{1} = Nar(T_{2i}^{1}) and all have settled down by s_{2i+1} = s_{2i}. If not, we wait for a stage s at which we forced A_{1} off Nar(T_{2i}^{1}). At stage s, we set T_{2i+1,s}^{1} = Nar(Ext(T_{2i}^{1}, τ)) for some τ (possibly ∅). We again ask A′_{1} if A_{1} is on T_{2i+1,s}^{1}. If so, T_{2i+1}^{j} has reached its limit for j = 0, 1 as has ∅′′(i). If not, we find s′ > s at which we force A_{1} off T_{2i+1,s}^{1}. As we can do this at most twice, we then have T_{2i+1,s′}^{j} = T_{2i+1}^{j} and ∅′′(i) = ∅′′_{s′}(i). We can now find T_{2i+2}^{j} by asking of A′_{0} if A_{0} is on Nar(T_{2i+1}^{0}). If so, T_{2i+2}^{j} are already fixed and if not they become fixed when we force A_{0} off Nar(T_{2i+1}^{0}). □

References

Cooper, S. B., Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973), 249–271. Epstein, R. L., Minimal degrees of unsolvability and the full approximation construction, Memoirs

AMS 162 (1975). Friedberg, R. M., A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22

(1957), 159–160. Jockusch, C. G. Jr. and Posner, D. B., Double jumps of minimal degrees, J. Symbolic Logic 43

(1978), 715–724.

Lerman, M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983. Posner, D. B., A survey of non-r.e. degrees ≤ 0′, Recursion Theory: Its Generalizations and

Applications (Proc. Logic Colloquium 1979, Leeds, August 1979) (F. R. Drake and S. S. Wainer, eds.), London Math. Soc. LNS 45, Cambridge University Press, Cambridge, England, 1980.

Robinson, R.W., Interpolation and embedding in the recursively enumerable degrees, Ann. of Math

(2) 93 (1971), 586–596. Sacks, G. E., A minimal degree below 0′, Bull. AMS (N.S.) 67 (1961), 416–419.

, Recursive enumerability and the jump operator, Trans. AMS 108 (1963), 223–239.

, On the degrees less than 0′, Ann. Math. (2) 77 (1963), 211–231. Sasso, L., A minimal degree not realizing the least possible jump, J. Symbolic Logic 34 (1974),

571–573. Shoenfield, J. R., On degrees of unsolvability, Ann. Math. (2) 69 (1959), 644–653.

, A theorem on minimal degrees, J. Symbolic Logic 31 (1966), 539–544.

, Degrees of Unsolvability, Math. Studies 2, North-Holland, Amsterdam, 1971. Simpson, S.G., Minimal covers and hyperdegrees, Trans. AMS 209 (1975), 45-64. Soare, R. I., Recursively Enumerable Sets, Springer-Verlag, Berlin, 1987. Spector, C., On degrees of recursive unsolvability, Ann. Math. (2) 64 (1956), 581-592. Yates, C. E. M., Initial segments of the degrees of unsolvability, Part II: Minimal degrees, J.

Symbolic Logic 35 (1970), 243–266.

, Prioric games and minimal degrees below 0′, Fund. Math. 82 (1974), 217–237.

Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand; Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA; Department of Mathematics, Cornell University, Ithaca, NY 14853-7901, USA

E-mail address: downey@math.vuw.ac.nz; lempp@math.wisc.edu; shore@math.cornell.edu