Domination, forcing, array nonrecursiveness and relative recursive enumerability

Mingzhong Cai Department of Mathematics Cornell University Ithaca NY 14853

Richard A. Shore^{∗} Department of Mathematics Cornell University Ithaca NY 14853

March 31, 2009

Abstract

We present some abstract theorems showing how domination properties equivalent to not being GL_{2} or array recursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of several old results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang and Yu [2009] that every degree above any not in GL_{2} is recursively enumerable in a 1-generic degree strictly below it. Our major new result is that every array nonrecursive degree is r.e. in some degree strictly below it. Our analysis of array nonrecursiveness and construction of generic sequences below ANR degrees also reveal a new level of uniformity in these types of results.

1 Introduction

The motivations for the work presented here were twofold. The first was the similarity between certain constructions of degrees below a nonzero recursively enumerable one and the analogous ones for degrees that are not in GL_{2} or ANR (array nonrecursive). (A Turing degree a is in GL_{2} if a′′ = (a ∨ 0′)′. An equivalent condition is that for every function g ≤_{T} a ∨ 0′, there is an f ≤_{T} a which is not dominated by g, i.e. ∃^{∞}x(g(x) < f(x)) (see Lerman [1983, IV.3.4]). The degree a is ANR if, for every function g ≤_{wtt} 0′, there is an f ≤_{T} a which is not dominated by g (Downey, Jockusch and Stob [1996], hereafter [DJS]). In particular, there are theorems from Shore [1981, Lemma 4.2] and Shore [2007, Theorem 4.1] about coding sets which are Σ_{3}^{A} below a for A ∈ a when a is either r.e. and nonrecursive or ANR. These results played crucial roles in the proofs, respectively, that the theory of D(≤ 0′), the degrees below 0′, is recursively isomorphic to that of true (first order) arithmetic and that the Turing jump operator is directly definable in any jump ideal containing 0^{(ω)}, the degree of the truth set of (first order) arithmetic. Both theorems were proved by fairly complicated but in some ways similar constructions. The first used what is called r.e. permitting and the second ANR permitting. Both, like many constructions below r.e. ANR or \overline{GL_{2}} degrees, depend on domination properties of the given degree to carry out a type of forcing argument (meeting various dense sets) in a type of priority construction.

∗Partially supported by NSF Grant DMS-0554855 and John Templeton Foundation Grant 13408.

Thus it seemed that these and other results could be simplified by proving that ANR (and so a fortiori \overline{GL_{2}}) degrees are relatively recursively enumerable, RRE, i.e. recursively enumerable in some degree strictly below them. Moreover, it seemed desirable to formulate a general theorem about meeting classes of dense sets for specified notions of forcing based on the relevant domination properties characterizing these two classes of degrees that would unify the various constructions exploiting these properties.

The second motivation for this work was the paper of Ambos-Spies, Ding, Wang and Yu [2009], hereafter [ASDWY]. They proved the following:

Theorem 1.1. ([ASDWY, Theorem 1.5]) Every a ∈ \overline{GL_{2}} is RRE and, in fact,every b above any a ∈ \overline{GL_{2}} is r.e. in some 1-generic degree c < b.

[ASDWY] then raised a number of interesting questions asking for characterizations of the degrees a such that every b ≥ a is RRE and the relation between being RRE and (the apparently stronger) property of being r.e. in a strictly smaller 1-generic degree. (A set G is 1-generic if for every r.e. set of binary strings S there is a binary string σ ⊂ G such that either σ ∈ S or (∀τ ⊇ σ)(τ ∉ S). A degree is 1-generic if it contains a 1-generic set.)

We present in §2 a analysis of the domination properties characterizing array nonrecursiveness that provide a good definition for a relativized version of the notion. The analysis also proves that ANR degrees satisfy a stronger domination property with greater uniformity than previously established. This property is closer to that characterizing \overline{GL_{2}} and allows us to give a single proof of a general theorem about meeting dense sets recursively in either \overline{GL_{2}} or ANR degrees. Even in the \overline{GL_{2}} case our Theorem 2.8 is more general than the ones in the literature that typically deal only with Cohen forcing. In particular, it allows for notions of forcing that are recursive in the given \overline{GL_{2}} or ANR degree and so are directly applicable to results that, for example, involve statements about coding the given set. It thus applies directly to results about cupping (join) properties and jump inversion. It also includes notions of forcing whose conditions are objects such as finite trees which are more complicated than binary strings. The proof we provide is also simpler than the standard ones in that we eliminate the usual procedure of, given the current string σ (an initial segment of our eventual generic G), appointing a string τ ⊃ σ as a target (to satisfy some density requirement) and moving toward τ one step at a time while at every step checking to see if some target for a higher priority requirement has been located. While this procedure makes sense for binary strings, it is hard to see what to make of it in more general settings when the forcing conditions are more complicated. Instead, we provide a method that, at every step, attempts to satisfy the highest possible requirement not currently satisfied. These attempts eventually succeed for each requirement. We then present a couple of illustrative applications for old results (at times extended from \overline{GL_{2}} to ANR) that are proven by ad hoc arguments in the literature. Ones for ANR degrees are presented in §3 as is the new result (Theorem 3.2) that ANR degrees are RRE and some strengthenings. This supplies the result needed to unify those of Shore [1981] and [2007] as described above.

In §4, we provide direct proofs of weaker natural variants, as well as the full result, of Theorem 1.1 for \overline{GL_{2}} degrees. To be more precise, we note that the proof of Theorem 1.1 in [ASDWY, Theorem 1.5], while very ingenious and clever, is quite indirect and nonuniform. It proceeds by first establishing that any a ≤ 0′ which is not L_{2} (i.e. a′′ > 0′′) is RRE. This argument relies on results of Harizanov [1998] to convert the problem into one of finding an infinite ascending or descending chain in a linear order constructed from a and then on (a modification of) one of Hirschfeldt and Shore [2007] to (nonuniformly) produce such a chain that is low and even 1-generic. [ASDWY] then use a modification of a result of Jockusch and Posner [1978] (proved below for ANR degrees as Theorem 3.1) and one of Yu [2006] as well as the Robinson Jump Interpolation Theorem [1971] and another result of Jockusch and Posner [1978] to reduce the general case to a relativization of the one for degrees below 0′ not in L_{2}. In contrast, our proof that even ANR degrees are RRE is uniform in a witness that the given degree is ANR as defined and explained in Definition 2.4, Proposition 2.5 and Theorem 3.2. In Theorem 4.1 we extend a more elaborate coding strategy introduced in Definition 3.5 that provides a 1-generic c in which the given \overline{GL_{2}} degree is RRE. We close our treatment of \overline{GL_{2}} degrees by using a notion of forcing in which conditions are finite trees to give a direct proof (Theorem 4.4) of the full version of Theorem 1.1 that is uniform relative to choice of a function witnessing the specific instance of the degree being in \overline{GL_{2}} required by the construction.

Theorems 3.2 and 1.1 also raise the natural question of whether the former can be strengthened along the lines of the latter by making the given ANR degree r.e. in a 1-generic below it. Rather surprisingly, the answer is no as will be shown in Cai [2010]:

Theorem 1.2. (Cai [2010]) There is an ANR degree a which is not r.e. in any 1-generic g < a.

This contrasts with the observation in Proposition 4.1 of [ASDWY] that every RRE degree is r.e. in some 1-generic (not necessarily below it) and answers Question 4.2 of [ASDWY].

Even more surprisingly, Cai [2010] shows the property that every b ≥ a is RRE characterizes the ANR degrees and answers Questions 4.3 and 4.4 of [ASDWY]:

Theorem 1.3. (Cai [2010]) If a ∉ ANR then there is a b ≥ a which is not RRE.

Corollary 1.4. (Cai [2010]) A degree a is ANR if and only if every b ≥ a is RRE.

2 Domination and Forcing

In this section we begin by analyzing the definition of array nonrecursiveness. We have in mind two goals. One (motivated in part by Theorem 3.4 and Question 2.7) is to develop the correct relativized version. The other is to strengthen the known domination properties for these functions and degrees. The strengthenings will be make the notion seem more similar to the domination characterization of \overline{GL_{2}} degrees. They will also provide a stronger general theorem about meeting dense sets to construct generic sequences for a larger class of collections of dense sets than had been previously handled. Indeed, they will provide a common construction of generic sequences for both ANR and \overline{GL_{2}} degrees.

Recall that the basic domination theoretic definition of array nonrecursiveness as given originally in [DJS] is for degrees:

Definition 2.1. A degree a is ANR if for every function g ≤_{wtt} K there is an f ≤_{T} a such that f is not dominated by g, i.e. ∃^{∞}x(f(x) > g(x)).

What then should be the correct relativized definition that a is array nonrecursive relative to b? We should at least have b ≤ a. One might first try also requiring that for some (or perhaps any) B ∈ b and any g ≤_{wtt} B′ there is an f ≤_{T} a not dominated by g. This, however, would not be sufficient to relativize the usual results about ANR degrees to the realm above b. (In fact, it is not hard to see that there is a single function recursive in 0′ which dominates every g wtt below any set X.) Another possibility might be to include all functions f computable from B′ with use bounded by a function recursive in A. This too is insufficient. One needs to allow unbounded access to B. Along these lines a stronger version would be that for any g computable from B ⊕ B′ such that the use from B′ is bounded by a function recursive in B there is an f ≤_{T} a not dominated by g. Other variations also seem plausible. A simpler route is provided by an alternate characterization of ANR degrees from [DJS] that depends (in the unrelativized case) on only a single function g, the modulus of K:

Notation 2.2. We let m be the least modulus function of K, i.e. m(x) is the least s ≥ x such that K_{s} ↾ x = K ↾ x where K_{s} is the standard enumeration of K = 0′. Note that m is nondecreasing. Similarly we let m_{h} (or m_{A}) be the least modulus function for the standard enumeration of h′ (A′) relative to h (A). (We view sets as represented by their characteristic functions.)

Proposition 2.3. ([DJS]) A degree a is ANR if and only if there is a function f ≤_{T} a which is not dominated by m.

We propose to turn this Proposition into a definition which relativizes in an obvious way.

Definition 2.4. A function f is ANR if it is not dominated by m. It is ANR relative to h if h ≤_{T} f and f is not dominated by m_{h}. A degree a is ANR relative to one b, ANR(b), if there is an f ∈ a and an h ∈ b such that f is ANR relative to h, ANR(h).

Note that when b = 0 this definition agrees with the standard one for a being ANR by Proposition 2.3 and the general observation that if there is a g ≤_{T} X not dominated by a function h then there is an f ≡_{T} X which is also not dominated by h: Let f(n) = 2g(n) + X(n). We now provide a domination property characterizing being ANR(h) stronger than the ones previously presented in the literature even in the unrelativized case. It also shows that our (seemingly weak) definition in the relativized case is even stronger than all the proposals above. It also makes ANR seem much more similar to \overline{GL_{2}}. Recall that a ∈ \overline{GL_{2}} if for every function g ≤_{T} a ∨ 0′, there is an f ≤_{T} a which is not dominated by g. Our proposition similarly says that if f is ANR and g = Θ(f ⊕ 0′) with 0′ use bounded by a function r ≤_{T} f (not just a recursive function or even one recursive in h in the relativized version) then there is a k ≤_{T} f which is not dominated by g. We state and prove the relativized version by substituting an arbitrary h′ for 0′ and also make the uniformities explicit.

Proposition 2.5. If f is ANR(h) and g = Θ(f ⊕ h′) with h′ use bounded by a function r ≤_{T} f then there is a k ≤_{T} f which is not dominated by g. Moreover k can be found uniformly in f in the sense that there is a recursive function s(e, i, j) such that if Θ = Φ_{e}, r = Φ_{i}(f) and h = Φ_{j}(f) then Φ_{s(e,i,j)}(f) will serve as the required k.

Proof. Without loss of generality or uniformity we may assume that f, g and r are increasing. We define the required k ≤_{T} f as follows: To compute k(n) compute Θ_{fr(m)}(f ⊕ (h′)_{fr(m)}; n) (i.e. compute fr(m) many steps in the standard enumeration of h′ from h and then, using this set as the second component of the oracle (and f for the first), compute Θ at n for fr(m) many steps for each m > n in turn until the computation converges and then add 1 to get the value of k(n). (This procedure must converge as Θ(f ⊕ h′; n) converges.) Now as m_{h} does not dominate f, there are infinitely many n such that there is a j ∈ [r(n), r(n + 1)) with f(j) > m_{h}(j). For such n we have fr(n+1) > f(j) > m_{h}(j) ≥ m_{h}r(n). Thus (h′)_{fr(m)} ↾ r(n) = (h′) ↾ r(n) for every m > n. So the computation of Θ(f ⊕h′; n) is, step by step, the same as that of Θ(f ⊕(h′)_{fr(m)}; n) for each m > n as all the oracles agree on the actual use of the true computation. So eventually we get an m > n such that Θ_{fr(m)}(f ⊕ (h′)_{fr(m)}; n) ↓ and the output must be Θ(f ⊕ h′; n). Thus for these n, k(n) = g(n) + 1 > g(n) as required. The uniformity of the definition of k from f and the functions of the hypotheses is clear. (Noting that we can uniformly, in f and the reduction of h to f, compute the standard enumeration of h′ from h.)

Corollary 2.6. A degree a is ANR(b) if and only if for every h ∈ b there is a k ∈ a such that k is ANR(h).

Proof. The only if direction is immediate from Definition 2.4. The other direction follows easily from the Proposition since given one h ∈ b with f ∈ a which is ANR(h), the modulus function of any ĥ ≡_{T} h is given by a function of the type specified in the hypotheses of the Proposition and so the function k ≤_{T} f provided by the Proposition is not dominated by mĥ and as noted above we may as well take k ≡_{T} f. It is then the required ANR(ĥ) function.

Iterating the notion of relative array recursiveness also provides some interesting questions. (A degree a is array recursive relative to b if it is not ANR(b).)

Question 2.7. If 0 = a_{0}< a_{1} < a_{2} < ⋯ < a_{n} is a sequence of degrees such that a_{i+1} is array recursive relative to a_{i} for each i, what can be said about a_{n}? If, for example, one could prove that a_{n} ∈ GL_{2} then one could show that no \overline{GL_{2}} degree is the top of a finite maximal chain of degrees and so answer this question from Lerman [1983, p. 87] who shows that the top of any such maximal chain below 0′ must be in L_{2}. Even showing that a_{n} ∉ GH_{1} would provide interesting information.

We next present a basic and somewhat simplified view of relatively effective notions of forcing. A notion of forcing, P is simply a partial order q ≤_{P} p, q extends p, on a set P of forcing conditions with greatest element 1. We view the elements of P as being (coded by) natural numbers equipped, of course, with their usual natural order ≤ as well. For convenience we let the natural number 1 be the greatest element of P. P is A-recursive (or a-recursive) if the set P and relation ≤_{P} are recursive in A (∈ a). (In general, one also has a forcing language L and a forcing relation ⊩ that need to be defined and analyzed but for the constructions of this paper they will be obvious and actually unneeded.) If C is a collection of dense subsets D_{n} of P (i.e. (∀p ∈ P)(∃q ≤_{P} p)(q ∈ D_{n})) then a sequence ⟨p_{i}⟩ of conditions is C-generic if it is nested, i.e. ∀i(p_{i} ≤_{P} p_{i+1}) and it meets each D_{n}, i.e. ∀n∃i(p_{i} ∈ D_{n}). (We work in terms of generic sequences in place of filters as it is the sequences that we actually construct and going from them to the filter they generate while usually a recursive operation is not always so without some assumptions on the partial order P.)

The standard example is Cohen forcing where the elements of P are binary strings and σ ≤_{P} τ ⇔ τ ⊇ σ. This is the primary recursive notion of forcing and while it is, in some sense, universal it is will be helpful to consider others that are A (a)-recursive for specified sets (degrees) A (a).

The basic fact about degrees a ∈ \overline{GL_{2}} being able to construct generic sequences (for Cohen forcing) is Lemma 6 of Jockusch and Posner [1978] stating that if C = ⟨D_{n}⟩ is a sequence of dense sets (in 2^{<ω}) uniformly recursive in A ⊕ 0′ for any A ∈ a then there is a C-generic sequence recursive in a. (In fact, as [DJS] point out, it is easy to see that this condition also implies (and so is equivalent to) a ∈ \overline{GL_{2}}.) We wish to generalize this result to arbitrary notions of forcing that are a-recursive. We give a construction more direct than the original and usual one in that at each step we move (if at all) directly to the condition that seems to get into the first D_{n} that our sequence does not yet seem to have met rather searching for a “best possible” target then moving towards it step by step and perhaps changing our mind before reaching it. Also note that the idea of moving toward a condition p step by step that makes natural sense when the conditions are binary sequences does not make any obvious sense when they are arbitrary numbers under an arbitrary order relation.

We also give a single argument that works (under the appropriate assumptions) for both \overline{GL_{2}} and ANR degrees. For a ∈ \overline{GL_{2}} the natural formulation of the necessary condition on the sequence ⟨D_{n}⟩ of dense sets that we want to meet is that it is uniformly recursive in A ⊕ 0′. What we actually want to use in the construction is a procedure witnessing this density requirement, i.e. a function d(x, y) recursive in A ⊕ 0′ such that ∀p ∈ P ∀n(d(p, n) ≤_{P} p & d(p, n) ∈ D_{n}). In this setting, the existence of the desired function d always follows from, and is usually equivalent to, the density of the D_{n} and their being uniformly recursive in A ⊕ 0′. This is no longer the case when we move from \overline{GL_{2}} degrees to ANR ones and so from Turing reducibility to wtt reducibility. (For example, one cannot get the required d ≤_{wtt} A ⊕ 0′ from the assumption that the D_{n} are dense and uniformly wtt reducible to A ⊕ 0′ as its definition requires an unbounded search.) Thus to handle ANR degrees we would naturally turn to the function witnessing density as is done for Cohen forcing in [DJS]. To give a single proof for both classes of degrees we use it for the \overline{GL_{2}} case as well. Note that, by Proposition 2.5,we can actually get by with a weaker hypothesis in the ANR case than might be expected that is closer to that for \overline{GL_{2}}. For notational convenience we state and prove the unrelativized versions of the theorem but, given the definitions and results above, relativization (to \overline{GL_{2}}(b) and ANR(b)) is routine.

Theorem 2.8. Suppose P is an A-recursive notion of forcing, C = ⟨D_{n}⟩ a sequence of sets dense in P and there is a d(x, y) = Ψ(A ⊕ K; x, y) witnessing their density, i.e. ∀p ∈ P ∀n(d(p, n) ≤_{P} p & d(p, n) ∈ D_{n}).

(i) If A ∈ \overline{GL_{2}} then there is a C-generic sequence recursive in A.

(ii) If A ∈ ANR and the use from K in the computation of Ψ(A ⊕ K; x, y) is bounded by a function r̂ ≤_{T} A, then there is also a C-generic sequence recursive in A.

In both cases the sequence ⟨p_{s}⟩ constructed is C-generic because ∀n∃s(p_{s+1} = d(p_{s}, n)). Moreover, in the ANR case the generic sequence is uniformly computable from any ANR f ∈ a (as a function of the indices of Ψ and of r̂ relative to f).

Proof. Let r̂(x, y) be a function that bounds the K use in the computation of Ψ(A ⊕ K; x, y). Without loss of generality we may assume that r̂(x, y) is increasing in both x and y. In case (i) we may clearly take r̂ ≤_{T} A ⊕ K and in case (ii) we may take r̂ ≤_{T} A by hypothesis. Next note that the nondecreasing function mr̂(s, s) in case (i) is recursive in A ⊕ 0′ and in case (ii) satisfies the hypotheses of Proposition 2.5, i.e. it is computable from A ⊕ K and its K use is bounded by a function (r̂(s, s)) recursive in A. Finally note that the maximum of the running times of Ψ(A ⊕ K; x, y) for x, y ≤ s is also is such a function in each case. (We run Ψ on each input and then output the sum of the number of steps needed to converge.) Finally, we let r be the maximum of these three functions so it too is of the desired form. We now have, by the basic characterization of \overline{GL_{2}} degrees or Proposition 2.5, an increasing function g ≤_{T} A not dominated by r. We use g to construct the desired generic sequence p_{s} by recursion.

We begin with p_{1} = 1. At step s + 1 we have (by induction) a nested sequence ⟨p_{i}|i ≤ s⟩ with p_{i} ≤ s. We calculate K_{g(s+1)} and see if there are any changes on the use from K in a computation based on which some D_{m} was previous declared satisfied. If so we now declare it unsatisfied. Suppose n is the least m < s + 1 such that D_{m} is not now declared satisfied. (There must be one as we declare at most one m to be satisfied at every stage and none at stage 1.) We compute Ψ_{g(s+1)}(A ⊕ K_{g(s+1)}; p_{s}, n). If the computation does not converge or gives an output q such that q > s + 1 or q ≰_{P} p_{s} we end the stage and set p_{s+1} = p_{s}. Otherwise, we end the stage, declare D_{n} to be satisfied on the basis of this computation of the output q and set p_{s+1} = q.

We now verify that the sequence constructed is C-generic and indeed ∀n∃s(p_{s+1} = d(p_{s}, n)). Clearly if we ever declare D_{n} to be satisfied (and define p_{s+1} accordingly) and it never becomes unsatisfied again then p_{s+1} = d(p_{s}, n). Moreover, if we ever declare D_{n} to be satisfied (and define p_{s+1} accordingly) and it remains satisfied at a point of the construction at which we have enumerated K correctly up to r(p_{s}, n), then by definition p_{s+1} = d(p_{s}, n) and D_{n} is never declared unsatisfied again. We now show that this happens.

Suppose all D_{m} for m < n have been declared satisfied by s_{0} and are never declared unsatisfied again. Let s+1 ≥ s_{0} be least such that g(s+1) ≥ r(s+1). If D_{n} was declared satisfied at some t + 1 ≤ s on the basis of some computation of Ψ_{g(t+1)}(A ⊕ K_{g(t+1)}; p_{t}, n) and there is no change in K on the use of this computation by stage g(s + 1) then the computation is correct, p_{t+1} = Ψ(A ⊕ K; p_{t}, n) ∈ D_{n} and D_{n} is never declared unsatisfied again. (The point here is that by our choice of s, g(s + 1) > mr̂(s + 1, s + 1) ≥ mr̂(p_{t}, n) and so K_{g(s)} ↾ r̂(p_{t}, n) = K ↾ r̂(p_{t}, n).) Otherwise, D_{n} is unsatisfied at s and the least such. By construction we compute Ψ_{g(s+1)}(A ⊕ K_{g(s+1)}; p_{s}, n). The definition of r along with our choice of g and s guarantee that this computation converges and is correct and so unless d(p_{s}, n) > s + 1 we declare D_{n} satisfied, set p_{s+1} = d(p_{s}, n) and D_{n} is never declared unsatisfied again. If d(p_{s}, n) > s + 1, we set p_{s+1} = p_{s} and, as D_{n} remains unsatisfied and the computations already found do not change, we continue to do this until we reach a stage v + 1 ≥ d(p_{s}, n) at which point p_{v} = p_{s} and we set p_{v+1} = d(p_{v}, n) declare D_{n} satisfied and it is never unsatisfied again.

The uniformity required in the ANR case is immediate from Proposition 2.5 and our construction.

The uniformity provided in the ANR case of this Theorem carries over to most constructions of degrees recursive in a given ANR one. We describe them explicitly in a number of results below. One classic example is the result of DJS that every ANR degree bounds a 1-generic degree. Our construction shows that there is a single e such that, for every ANR function f, Φ_{e}(f) is 1-generic (see also Proposition 3.8). (An equivalent but suggestive reformulation of this fact is the assertion that {G| G is 1-generic} is Medvedev reducible to {f| f is ANR}.)

3 ANR degrees are RRE

In this section we give a number of applications of the basic Theorem 2.8 for ANR degrees including the result that they are RRE. We begin by extending a theorem of Jockusch and Posner [1978] from \overline{GL_{2}} to ANR. Even for the \overline{GL_{2}} case, it does not fall under the usual paradigm since it makes demands on coding that require a notion of forcing that is a-recursive but not recursive.

Theorem 3.1. If a ∈ ANR and c ≥ a ∨ 0′ and is r.e. in a, then there is a g ≤ a s.t. g′ = c.

Proof. First fix an A ∈ a and an A-recursive enumeration ⟨C_{s}⟩ of C. The conditions in our notion of forcing P are binary strings σ but extension is defined to reflect the given enumeration of C. We let F (σ) = {e|Φ_{e}^{σ}(e) ↓}. (We employ the usual conventions so that, for example, the computation of Φ_{e}^{τ}(x) requires at least x many steps to converge and runs only for |τ| many steps so F is a recursive function and its values are finite sets.)

If τ ⊇ σ (and so F (τ) ⊇ F (σ)) and for any e ≤ min({|σ|} ∪ (F (τ) − F (σ))), and for any ⟨e, s⟩ ∈ [|σ|, |τ|), τ(⟨e, s⟩) = C_{|σ|}(e) we say that τ ≤_{P} σ. We make this into the required partial order by taking the transitive closure of this relation which is still, of course, recursive in A. The intuition (as in the Shoenfield [1959] jump theorem) is that, whenever we try to extend a string, we want to make sure that some (eventually growing) initial segment of columns respect the enumeration of C in sense that τ(⟨e, s⟩) = C_{|σ|}(e).

Define our sequence C of sets as follows:

D_{n,j} = {σ : |σ| > j & [Φ_{n}^{σ}(n) ↓ or ∀τ ⊃ σ[Φ_{n}^{τ}(n) ↑ or

∃s∃e < min({|σ|} ∪ (F (τ) − F (σ)))(⟨e, s⟩ ∈ [|σ|, |τ|) & τ(⟨e, s⟩) ≠ C_{|σ|}(e))]]}.

We calculate the required witness function d(σ, ⟨n, j⟩) for the D_{n,j} as follows: Given any σ, n and j we may as well assume (by, recursively in A, taking a long enough extension ρ with ρ(⟨e, s⟩) = C_{|σ|}(e) for every ⟨e, s⟩ > |σ|, ⟨e, s⟩ ≤ j ) that |σ| > j. Now check whether Φ_{n}^{σ}(n) ↓, if so then set d(σ ⟨n, j⟩) = σ ∈ D_{n,j} and we are done. If not, then use A to get all the values of C_{|σ|}(e) for e ≤ |σ|. Ask (K) whether we can find an extension τ of σ with the property that for all e ≤ min({|σ|} ∪ (F (τ) − F (σ))) and all s such that ⟨e, s⟩ ∈ [|σ|, |τ|), we have τ(⟨e, s⟩) = C_{|σ|}(e), and Φ_{n}^{τ}(n) ↓, if so we let d(σ, ⟨n, j⟩) be the first such τ (found in a standard ordering of computations). It is immediate that d(σ, ⟨n, j⟩) ≤_{P} σ and τ ∈ D_{n,j}. Otherwise, we let d(σ, ⟨n, j⟩) = σ ∈ D_{n,j}.

As we determined C_{σ} recursively in A, the K use for the question asked is clearly bounded by a function recursive in A. Thus, by Theorem 2.8(ii), we have a C-generic sequence ⟨σ_{i}⟩ recursive in A. We let G = ∪{σ_{p_{i}}} ≤_{T} A.

First, we claim that C ≤_{T} G′ and, in particular, C(n) = lim G(n, s) for every n. Given n, there is obviously a j such that for every e ≤ n, e ∈ G′ ⇔ Φ_{e}^{σ_{j}}(e) ↓ and C_{|σ_{j}|}(n) = C(n). By the definition of our forcing notion, G(n, t) = C_{|τ|}(n) = C(n) for t ≥ |τ| as required.

To see that G′ ≤_{T} C, assume we have determined G′ ↾ n and want to decide if n ∈ G′. Recursively in A ∨ 0′ ≤_{T} C find j and k large enough so that C ↾ n = C_{j} ↾ n, σ_{k+1} = d(σ_{k}, ⟨n, j⟩) and G′ ↾ n = F (σ_{k+1}) ↾ n. (It is clear, first, that there are such j and k and then that they can be recognized recursively in A ∨ 0′ which computes both the sequence σ_{i} and d.) It is now clear from the definition of D_{n,j} and our notion of forcing that n ∈ G′ ⇔ Φ_{n}^{σ_{k}}(n) ↓.

We now apply our general theorem to an A-recursive notion of forcing chosen to produce relative recursive enumerability.

Theorem 3.2. If a ∈ ANR then a is RRE. Indeed, there are e and i such that, for every ANR function f, Φ_{e}(f) <_{T} f and W_{i}^{Φ_{e}(f)} ≡_{T} f.

Proof. Suppose f ∈ a is ANR. Uniformly take an A ≡_{T} f (say its graph). We use an A-recursive notion of forcing P with conditions p = ⟨p_{0}, p_{1}, p_{2}⟩, p_{i} ∈ 2^{<ω} such that

1. |p_{0}| = |p_{1}|, p_{0}(d_{n}) = A(n − 1), p_{1}(d_{n}) = 1 − A(n − 1) where d_{n} is n^{th} place where p_{0}, p_{1} differ and

2. ∀e < |p_{0} ⊕ p_{1}|(e ∈ p_{0} ⊕ p_{1} ⇔ ∃x(⟨e, x⟩ ∈ p_{2})).

Extension in the notion of forcing is defined by

q ≤_{P} p ⇔ q_{i} ⊇ p_{i} and ¬∃x (⟨e, x⟩ ∈ q_{2} − p_{2} & p_{0} ⊕ p_{1}(e) = 0) .

Membership in P and ≤_{P} are clearly recursive in A.

Our plan is to define a class C of sets D_{n} with witness functions d(p, n) recursive in A ⊕ K with K use actually recursively bounded. Theorem 2.8(ii) then supplies a C-generic sequence ⟨p_{s}⟩ ≤_{T} A from which we can define the required G ≤_{T} A in which a is r.e. If p_{s} = ⟨p_{s,0}, p_{s,1}, p_{s,2}⟩ we let G_{i} = ∪{p_{s,i}|s ∈ ℕ} for i = 0, 1, 2 so G_{i} ≤_{T} A. Then, if we can force G_{0} and G_{1} to differ at infinitely many places, G_{0} ⊕ G_{1} ≡_{T} A. On the other hand, the definition of the notion of forcing obviously makes G_{0} ⊕ G_{1} r.e. in G_{2}. Thus a will be r.e. in g = deg(G_{2}). We will have other requirements that make g < a as well.

We begin with the dense sets that provide the differences we need:

D_{2n} = {p ∈ P : p_{0}, p_{1} differ at at least n points}.

We define the required function d(r, 2n) by recursion on n. Given r and n+1, we suppose we have calculated d(r, 2n) = p = ⟨p_{0}, p_{1}, p_{2}⟩ ∈ D_{2n} with p ≤_{P} r. If p ∉ D_{2n+2}, we need to compute a q = ⟨q_{0}, q_{1}, q_{2}⟩ ∈ D_{2n+2} with q ≤_{P} p. Let q_{0} = p_{0}ˆ A(n), q_{1} = p_{1}ˆ (1 − A(n)). Choose i ∈ {0, 1} such that q_{i}(|p_{0}|) = 1. Define q_{2} ⊇ p_{2} by choosing x large and setting q_{2}(⟨2|p_{0}| + i, x⟩) = 1 and q_{2}(z) = 0 for all z ∉ dom(p_{2}) and less than ⟨2|p_{0}| + i, x⟩. Now q = ⟨q_{0}, q_{1}, q_{2}⟩ satisfies the requirements to be a condition in P. It obviously extends p and is in D_{2n+2}. This computation is clearly recursive in A.

We must now add dense sets to guarantee that A ≰_{T} G_{2}. A direct route is to let

D_{2n+1} = {p ∈ P : ∃x(Φ_{n}^{p_{2}}(x) ↓≠ A(x))or∀(σ_{0}, σ_{1} ⊇ p_{2})[∃x(Φ_{n}^{σ_{0}}(x) ↓≠ Φ_{n}^{σ_{1}}(x)) ↓⇒
(∃i ∈ {0, 1})(∃ ⟨e, x⟩)(e < |p_{0} ⊕ p_{1}| & σ_{i}(⟨e, x⟩) = 1 ≠ (p_{0} ⊕ p_{1})(e)]}.

Of course, the first alternative guarantees that Φ_{n}^{G_{2}} ≠ A while the second that Φ_{n}^{G_{2}}, if total, is recursive by our definition of extension in the notion of forcing. We compute the required function d(q, 2n + 1) as follows. Given q we ask one question of K determined recursively in q: Are there extensions σ_{0}, σ_{1} of q_{2} that would show that q does not satisfy the second disjunct in the definition of D_{2n+1}. If not, let d(q, 2n+1) = q which is already in D_{2n+1}. If so, we find the first such pair (appearing in a recursive search) and ask A which σ_{i} gives an answer different from A(x). We now need a condition r = d(q, 2n + 1) extending q with third coordinate r_{2} extending σ_{i}. For each ⟨e, x⟩ with e ≥ |q_{1} ⊕ q_{2}|) and σ_{i}(⟨e, x⟩) = 1 we define r_{j}(z) = 1 for both j ∈ {0, 1} for the z that makes (r_{0} ⊕r_{1})(e) = 1 and otherwise we let r_{j}(u) = 0 for all other u less than the largest element put into either r_{0} or r_{1} by the previous procedure. We now extend σ_{i} to the desired r_{2} by putting in ⟨k, y⟩ for a large y for all those k ≥ |q_{1}| put into r_{0} ⊕ r_{1} for which there is no ⟨k, w⟩ in σ_{i}. Otherwise we extend σ_{i} by 0 up to the largest element put in by this procedure. It is clear that this produces a condition r as required. (No points of difference between r_{0} and r_{1} are created that were not already present in q.)

We now apply Theorem 2.8 to get a C-generic sequence ⟨p_{s}⟩ ≤_{T} A. As promised, we let G_{i} = ∪{p_{s,i}|s ∈ ℕ} for i = 0, 1, 2 and, as described above, A ≡_{T} G_{0} ⊕ G_{1} which is r.e. in G_{2}. In addition, the conditions in D_{2n+1} guarantee (as above) that Φ_{n}^{G_{2}} ≠ A as well. The uniformity assertions follow immediately from those in Theorem 2.8 and our construction.

We now point out some additional information about G_{2} that can be extracted from this construction.

Proposition 3.3. For the G_{2} constructed in the proof of Theorem 3.2 such that the given A ∈ ANR is r.e. in and strictly above G_{2} we also have G′_{2} ≡_{T} A ⊕ 0′ and so if A ∈ \overline{GL_{2}} then A is also \overline{GL_{2}}(G_{2}), i.e. (A ⊕ G2^{′})′ <_{T} A′′.

Proof. We first claim that G′_{2} ≤_{T} A ∨ 0′. To see if e ∈ G′_{2}, recursively compute an n such that Φ_{n}^{τ}(x) = τ(x) if Φ_{e}^{τ}(e) ↓ and is divergent otherwise. Now, recursively in A ⊕ 0′ find an s such that p_{s+1} = d(p_{s}, 2n + 1). If p_{s+1} is in D_{2n+1} because of the first clause of the definition then Φ_{n}^{p_{s+1,2}}(x) ↓ for some x and so e ∈ G′_{2}. Otherwise we claim e ∉ G2^{′}. Suppose for the sake of a contradiction that, for some t, Φ_{e}^{p_{t,2}}(e) ↓. It is now easy to get extensions of p_{t,2} that show that p_{s+1} does not satisfy the second clause of the definition of D_{n} for the desired contradiction. Simply choose y > 2|p_{s,0}|, |p_{t,2}| and extend p_{t,2} by 0 up to ⟨y, 0⟩ and then with i = 0, 1 at ⟨y, 0⟩ to get the required σ_{i}. On the other hand, as a is r.e. in G_{2}, A ⊕ 0′ ≤_{T} G′_{2} and G′_{2} ≡_{T} A ⊕ 0′ as desired. If a ∈ \overline{GL_{2}}, a′′ > (a ∨ 0′)′ and so a′′ > (a ∨ g′_{2})′ as required.

A reasonable question now would be to ask for an analogous result for ANR degrees to that given in this Proposition for \overline{GL_{2}} based on our Definition 2.4 of relative array nonrecursiveness.

Theorem 3.4. If a is ANR then there is a g relative to which a is both r.e. and ANR.

Proof. We replace the sets D_{2n+1} of the proof of Theorem 3.2 with new ones (also called D_{2n+1}) that force a maximal number of convergences of Φ_{n}^{G_{2}}(m). We here directly specify the (calculation procedure for the) associated density functions d(p, 2n + 1): We ask 2^{p} many questions of K. For each subset F of {i|i < p} we ask if there is a σ ⊇ p_{2} “adding no new numbers” (i.e. ¬∃ ⟨e, x⟩ (e < |p_{0} ⊕ p_{1}| & σ(⟨e, x⟩) = 1 ≠ (p_{0} ⊕ p_{2})(⟨e, x⟩)) that makes Φ_{n}^{σ}(m) ↓ for every m ∈ F. We take a maximal such F and find the first extension σ > p witnessing the convergences for m ∈ F. We then get an extension q of p with third coordinate extending σ as before. Note that by the usual coding of binary sequences and triples, q > p as well. By induction then if g(m) is the mth stage s at which we have p_{s+1} = d(p_{s}, 2n + 1) for some n, p_{g(m)} > m. Note that this procedure also satisfies the hypotheses of Theorem 2.8(ii). The D_{2n+1} are declared satisfied and unsatisfied as before but note that they become unsatisfied when we discover that the F associated with the extension used was not maximal (this is, after all, part of the computation on which we based the calculation of d). By the proof of Theorem 2.8, there are infinitely many m such that the D_{2n+1} declared satisfied at g(m) is never declared unsatisfied. So in particular for such m, for every e < m with e ∈ G′_{2}, Φ_{e}^{p_{g(m)+1,2}}(e) ↓. Thus if we now define h(m) as the stage in the standard enumeration of G′_{2} at which all the numbers e such that Φ_{e}^{p_{g(m)+1,2}}(e) ↓ have been enumerated in G′_{2}, then, for each of these infinitely many m, h(m) will be at least as large as the modulus function for G′_{2} (relative to G_{2}) at m.

In the next section we will improve Theorem 3.2 when a ∈ \overline{GL_{2}} by making the degree witnessing that a is RRE 1-generic. Here we present another extension to ANR of a result result from [ASDWY] about \overline{GL_{2}} both as an illustration of our general methodology as well as an introduction of the coding techniques that will be exploited in the next section.

Definition 3.5. For any set G, we define a relationship as(e, G) = σ, the number e is assigned to (the string) σ to hold when σ is the shortest τ ⊂ G such that Φ_{e}^{τ}(e) ↓. If as(e, G) = σ, we define the weak order of e along G, wo(e, G), recursively as one more than the weak order of e′ along G where e′ is the unique x < e such, for some τ ⊂ σ, as(x, G) = τ and for no e′′ < x and ρ with τ ⊂ ρ ⊂ σ is as(e′′, G) = ρ. If there is no such x, then wo(e, G) = 0. We define as(e, ρ) = σ and the weak order of e along ρ similarly for strings ρ.

Intuitively we first assign numbers to strings along G, and then for any e assigned to σ, we search downward from σ for the first e′ < e assigned. The weak order of e is then the weak order of e′ plus 1.

Remark 3.6. Without loss of generality we may clearly choose our master list of computations so that for any τ there is at most one e such that Φ_{e}^{τ}(e) ↓ but Φ_{e}^{τ^{−}}(e) ↑. So along any G each node is assigned at most one number.

Notation 3.7. For any string σ, we let σ^{−} be the initial segment of σ gotten by removing the last number in σ. If there is a set G (string τ) that is clear from the context such that σ ⊂ G (τ), σ^{+} will denote σˆ G(|σ|) (σˆ τ(|σ|)).

Proposition 3.8. ([ASDWY]) If a ∈ ANR then there is an 1-generic degree g recursive in a such that g′ = a ∨ 0′. Indeed, there is an e such that, if f is ANR, then Φ_{e}^{f} is 1generic and Φ_{e}(f)′ ≡_{T} f ⊕ 0′ (and this equivalence is also given uniformly).

Proof. We again being with uniformly choosing an A ≡_{T} f. Our forcing conditions are binary strings. Membership of ρ in P is defined recursively: if σ ⊊ ρ is the longest initial segment of ρ such that as(e, ρ) = σ for any e then we require that σ^{+}(|σ|) = A(wo(e, ρ)); moreover, if τ is the longest initial segment of σ such that as(e′, ρ) = τ for some e′ < e then τ^{+} is also (recursively required to be) in P. (By default, for the base case, if no number is assigned to any σ ⊂ τ, then τ ∈ P.) Thus P is clearly recursive in A. The order σ ≤_{P} τ for our notion of forcing is the usual extension relation on strings, σ ⊇ τ.

Our dense sets will be:

D_{n} = {σ ∈ P|Φ_{n}^{σ}(n) ↓ or (∀τ ⊃ σ)(Φ_{n}^{τ^{−}}(n) ↓ or Φ_{n}^{τ}(n) ↑ or (∀i)(τˆ i ∉ P))}.

Now we define an appropriate function d(p, n) witnessing the density of the D_{n}. Consider any ρ ∈ P. (If ρ ∉ P, we let d(ρ, n) = 1 for any n.) In order to find σ ≤_{P} ρ in D_{n}, we first check whether Φ_{n}^{ρ}(n) ↓, if so we are done, if not then ask whether there is σ ⊃ ρ such that Φ_{n}^{σ}(n) ↓, Φ_{n}^{σ^{−}}(n) ↑ and σˆ A(wo(n, σ)) ∈ P. If so, σˆ A(wo(n, q)) ∈ D_{n} and σˆ A(wo(n, q) ≤_{P} ρ. If not, ρ ∈ D_{n}. The second question only requires A ↾ n to determine the question it asks of K. The rest of the procedure is recursive in A and so d satisfies the hypotheses of Theorem 2.8(ii).

Theorem 2.8(ii) now provides a sequence ⟨σ_{i}⟩ ≤_{T} A meeting all the D_{n}. Our desired G is ∪σ_{i}. So G ≤_{T} A. To see that G is 1-generic, we need to check that for any e there is a node σ ⊂ G which forces e ∈ G′ or e ∉ G′. Note that there is an i such that σ_{i} decides if e′ ∈ G′ for every e′ < e (by induction) and σ_{i+1} ∈ D_{e} (by the genericity of the sequence and the closure of the D_{n} under extension in P). Of course, if Φ_{e}^{σ_{i+1}}(e) ↓ we are done. Otherwise, we claim that σ_{i+1} forces e ∉ G′. If not, then we can find the first τ ⊃ σ_{i} such that Φ_{e}^{τ}(e) ↓, take a one-bit extension of τ by coding in A(wo(e, τ)), then this τ^{+} ∈ P because all e′ < e in G′ are forced in by strings shorter than σ_{i}. This contradicts the fact that σ_{i+1} ∈ D_{n}.

Now we have G′ ≤_{T} G ∨ 0′ ≤_{T} A ∨ 0′ and it remains to show that A ≤_{T} G′. We say some pair (e, τ) has true weak order n = wo(e, τ), if no string extending τ can have an assignment e′ with weak order n, i.e., any e′ assigned after τ is greater than e. For such a pair (e, τ), we must have τ^{+}(|τ|) = A(wo(e, τ)) = A(n). Finally, for every n we can use G′ to find the unique pair (e, τ) with true weak order n, so A ≤_{T} G′.

As usual the desired uniformities are immediate from those of Theorem 2.8(ii) and our construction.

4 \overline{GL_{2}} degrees

Theorem 3.2 provides a procedure that, given any ANR degree a, produces a g < a in which a is r.e. We now show how to make g 1-generic if a ∈ \overline{GL_{2}} much more directly than is done in [ASDWY].

Theorem 4.1. If a ∈ \overline{GL_{2}}, then it is r.e. in and above a 1-generic degree.

Proof. Given a finite string σ, we define the rank of σ (rk(σ)) as the maximum weak order along σ.

Define a notion of forcing P consisting of all p = ⟨p_{0}, p_{1}, p_{2}⟩, p_{0}, p_{1}, p_{2} ∈ 2^{<ω} such that:

1. p_{0} and p_{1} are of the same length and if m is the nth position at which they differ, p_{0}(m) = 1 − p_{1}(m) = A(n − 1).

2. For n < |p_{0} ⊕ p_{1}|, n ∈ p_{0} ⊕ p_{1} if and only if there exists σ ⊊ p_{2} and an e assigned to σ with weak order n and p_{2}(|σ|) = 1 (i.e. σ^{+}(|σ|) = 1).

3. 2|p_{0}| = rk(p_{2}).

Let q ≤_{P} p if q_{i} ⊃ p_{i} for each i. Clearly this notion of forcing is A-recursive. Intuitively, if we get ⟨A_{0}, A_{1}, G⟩ from a sufficiently generic sequence (recursive in A), then A ≡_{T} A_{0} ⊕ A_{1} which is r.e. in (and above) G. To determine whether n ∈ A_{0} ⊕ A_{1}, one simply runs through G checking whether there is a node with weak order n and a 1 coded right after that. We also want to guarantee the 1-genericity of G.

Given p ∈ P, we say τ ⊃ p_{2} respects p if there is no (n, σ) such that n < |p_{0} ⊕ p_{1}|, n ∉ p_{0} ⊕ p_{1}, σ is between p_{2} and τ with some number e assigned to it and of weak order n and τ(|σ|) = 1. So if τ does not respect p, then we cannot extend p to a condition q with q_{2} extending τ because any such extension would violate clause (2) in the definition of our notion of forcing. Conversely, the following holds:

Lemma 4.2. If p ∈ P, rk(p_{2}) > n, Φ_{n}^{p_{2}}(n) ↑, τ ⊃ p_{2} respects p and n is assigned to τ, then there exists a q ≤_{P} p such that q_{2} ⊃ τ and so one can be found recursively in A.

Proof. We first try to extend p_{0} and p_{1}. If we use τ and blindly follow the dictates of clause (2) of our definition of P to extend p_{0}, p_{1}, we might violate clause (1). However, it is easy to see that we can fix this by extending τ by putting 1’s after some nodes with certain weak order between rk(p_{2}) and rk(τ). Notice that wo(n, τ) ≤ n and rk(p_{2}) > n, and those weak orders that need adjustments are > n, so we can extend τ and wait for those weak orders to appear, then code in 1’s after some of them so that we meet the requirements of clause (1).

Define dense sets:

D_{n} = {p : Φ_{n}^{p_{2}}(n) ↓ or ∀τ ⊃ p_{2}(Φ_{n}^{τ}(n) ↑)}.

These D_{n} will guarantee that G = ∪_{i}{p_{i,2}} is 1-generic. We need to find witnesses to density recursively in A ⊕ 0′.

Given p, assume Φ_{n}^{p_{2}}(n) ↑ and rk(p_{2}) > n (as we can always extend a string respectfully). We first ask whether there is a τ extending p_{2} which makes Φ_{n}^{τ}(n) ↓ and respects p. If so we find the first such τ and notice that n is assigned to τ. Then by Lemma 4.2 we can find q ∈ D_{n} extending p. If not, we claim that we can find q ≤_{P} p with q ∈ D_{n} and Φ_{n}^{q_{2}}(n) ↑, i.e. q forces n ∉ G′.

Next we ask (0′) whether there is a τ extending p_{2} which makes Φ_{n}^{τ}(n) ↓. If not then p is already in D_{n}. If so, find the first one τ_{1}, then, by the negative answer to our first question, we know that τ_{1} does not respect p. Find the first initial segment η_{1} of τ which does not respect p, i.e., η_{1}^{−} is assigned a number with weak order < rk(p_{2}), η_{1}(|η_{1}| − 1) = 1 but the definition of η_{1} respecting τ would require it to be 0. Then put ξ_{1} = η_{1}^{−} ∗ 0, that is, we change the last bit to respect p.

Note that φ_{n}^{ξ_{1}}(n) ↑ because ξ_{1} respects p. Now ask (0′) whether ξ_{1} forces n ∉ G′. If so, then we are done by (a slight variation of) Lemma 4.2. If not, we repeat this process: find τ_{2} ⊃ ξ_{1} which makes Φ_{n}^{τ_{2}}(n) ↓, then find the first initial segment of τ_{2} which does not respect p, change the last bit and get a ξ_{2} which respects p.

We can continue this process but at each repetition we need some new extension assigned a number with weak order < rk(p_{2}). Therefore this process cannot continue forever, i.e. we will eventually stop and get a ξ_{i} which respects p and which forces n ∉ G′. Finally use Lemma 4.2 to get q ≤_{P} p, q_{2} ⊃ ξ_{i} and q ∈ D_{n}.

To make sure that A_{0} and A_{1} have infinitely many points of differences we add another sequence of dense sets:

D_{n}^{∗} = {p : p_{0}, p_{1} differ at at least n positions}

This is similar to the last part of Lemma 4.2: for any p, one has to be careful extending p_{2} while still satisfying clauses (1) and (2) and yet adding a point of difference. Since we don’t have any other requirements, this process is easy and recursive in A.

Our final step is to prove that if a ∈\overline{GL_{2}} then every b ≥ a is r.e. in a 1-generic strictly below it. We prove a seemingly quite different proposition from which this result will easily follow.

Proposition 4.3. Every a ∈ \overline{GL_{2}} computes an infinite binary tree T in 2^{<ω} such that for any path C ∈ [T], C is 1-generic, C does not compute a and a is r.e. in C (but not necessarily above C).

Proof. We now also arrange our master list of computations so that there is no τ of even length such that Φ_{e}^{τ}(e) ↓ but Φ_{e}^{τ^{−}}(e) ↑. Thus no string of even length is assigned a number.

We say a string τ is A-admissible if there exist p_{0}, p_{1} s.t. ⟨p_{0}, p_{1}, τ⟩ is a forcing condition in the sense of the previous construction. Note that p_{0} and p_{1} are uniquely determined by τ. We will denote them by p_{0}(τ) and p_{1}(τ), respectively.

We say τ respects σ if τ respects ⟨p_{0}(σ), p_{1}(σ), σ⟩ as in the previous construction. Now we define a new notion of forcing: P consists of finite binary trees such that

every leaf is A-admissible. We let q ≤_{P} p if q is a binary tree extending p, and each leaf of q respects the corresponding leaf in p it extends.

We define dense sets:

D_{n} = {p : for every leaf σ of p, Φ_{n}^{σ}(n) ↓ or ∀τ ⊃ σ(Φ_{n}^{τ}(n) ↑)}.

D_{n}^{∗} = {p : for every leaf σ of p, p_{0}(σ) and p_{1}(σ) differ at at least n positions}

These two types of dense sets are handled in the same way as in the previous construction. For every leaf, after we find an extension satisfying the conditions in D_{n} (or D_{n}^{∗}), we can assume that it has even length and extend it by 0 and 1 to split it into two leaves. This preserves A-admissibility since no number is assigned to nodes of even length.

Next, we want to make sure that no path C can compute A. Define additional dense sets as follows:

E_{n} = {p : for every leaf σ of p, [∃xΦ_{n}^{σ}(x) ↓≠ A(x)
or ∃x∀τ ⊃ σ(τ respects σ ⇒ Φ_{n}^{τ}(x) ↑)]}

Now given σ, a leaf of p, we first fix a recursive list of strictly increasing indices n_{0} < n_{1} < ... < n_{i} < ... such that if Φ_{n}^{τ}(i) ↓ then for any τ′ ⊃ τ which is large enough to allow for the spacing required by the conditions we imposed on our master list of computations, Φ_{n_{i}}^{τ′}(n_{i}) ↓, and conversely Φ_{n_{i}}^{τ′}(n_{i}) ↑ if no τ ⊂ τ′ makes Φ_{n}^{τ}(i) ↓.

Let σ_{i} = σ ∗ 0^{j} where j is the least such that rk(σ ∗ 0^{j}) > n_{i} and rk(σ ∗ 0^{j}) is even. Using 0′ and A we go through the σ_{i} asking whether:

∀τ ⊃ σ_{i}(τ respects σ_{i} ⇒ Φ_{n}^{τ}(i) ↑)

If we ever get a“yes” answer for some σ_{i}, we output this σ_{i} (note that σ_{i} is always A-admissible and respects σ). If we get a “no” answer for σ_{i}, we then find the first such τ_{i} ⊃ σ_{i} which respects σ_{i} and which makes Φ_{n}^{τ_{i}}(i) ↓. If Φ_{n}^{τ_{i}}(i) = A(i) we proceed to i + 1. If Φ_{n}^{τ_{i}}(i) ≠ A(i), then extend τ_{i} to η_{i} = τ_{i} ∗ 0^{k} for the first k such that η_{i} is assigned the number n_{i}. Now this η_{i} respects σ_{i} and by Lemma 4.2 we can find an extension η of η_{i} which is A-admissible, and then output η.

Now we prove that we always halt in this process: Suppose not, then for any σ_{i} we would always get a “yes” answer and could find the first τ_{i} ⊃ σ_{i} which respects σ_{i} and Φ_{n}^{τ_{i}}(i) = A(i). That would make A recursive.

Finally we get extensions of all leaves of p and then branch each them into two in the same way as in our analysis of D_{n} and D_{n}^{∗}. Now E_{n} forces that, for each path C, either Φ_{n}^{C} is not total, or it is not A.

Theorem 4.4. If a ∈ \overline{GL_{2}} and b > a, then b is r.e. in and strictly above a 1-generic c. Moreover, a C ∈ c can be found uniformly effectively in any B ∈ b from an index for an A ∈ a as a set recursive in B and an index for a function (recursive in A and hence B) not dominated by a particular effectively determined function recursive A ⊕ 0′.

Proof. Let T be the tree recursive in A constructed in the above Proposition. Given B ≥_{T} A, we let C be the path in the tree gotten by following B, i.e., C = T (B). It is easy to see that B ≡_{T} A ⊕ C, so B is r.e. in and above C which is, of course, 1-generic. Moreover, since A ≰_{T} C, C is strictly below B.

As for the uniformity assertions, we explain what we mean by describing the procedure. We are given B and an index computing A from B. From this information we can effectively find indices (from A ⊕ 0′) for the density functions for the sets D_{n}, D_{n}^{∗} and E_{n} and then for the associated function r (from A ⊕ 0′) used in the proof of Theorem 2.8. The noneffective step is now to produce an index for the function g ≤_{T} A which is not dominated by r. Given that index for g, the rest of the construction in the proof of Theorem 2.8 proceeds effectively in A and provides the generic sequence ⟨p_{i}⟩ for our construction here and an index for it from A. Going from the sequence to the corresponding tree T and then to the path C = T (B) is then also uniformly effective in B.

5 Bibliography

Ambos-Spies, K., Ding, D., Wang, W. and Yu, L. [2009], Bounding non-GL_{2} and R.E.A., Journal of Symbolic Logic, to appear.

Cai, M. [2010], Array nonrecursiveness and relative recursive enumerability, to appear. Downey, R. G., Jockusch, C. G. jr. and Stob, M. [1990], Array nonrecursive sets

and multiple permitting arguments, in Recursion Theory Week, K. Ambos-Spies, G. H. Müller and G. E. Sacks eds., Springer-Verlag, Berlin, 141-174.

Harizanov, V. [1998], Turing degrees of certain isomorphic images of computable relations, Ann. Pure and Applied Logic 93, 103-113.

Hirschfeldt, D. and Shore, R. A. [2007], Combinatorial Principles Weaker than Ramsey’s Theorem for Pairs, Journal of Symbolic Logic 72, 171-206.

Jockusch, C. G. jr. and Posner, D. B. [1978], Double jumps of minimal degrees, Journal of Symbolic Logic 43, 715-724.

Lerman, M. [1983], Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

Robinson, R. W. [1971], Jump restricted interpolation in the recursively enumerable degrees, Annals of Mathematics (2) 93, 586-596.

Shoenfield, J. R. [1959], On degrees of unsolvability, Annals of Mathematics (2) 69, 644-53.

Shore, R. A. [1981], The theory of the degrees below 0′, Journal of the London Mathematical Society 24 (1981), 1-14.

Shore, R. A. [2007], Direct and local definitions of the Turing jump, Journal of Mathematical Logic 7, 229-262.

Yu, L. [2006], Lowness for genericity, Archive for Math. Logic 45, 233-238.