Generalized High Degrees have the Complementation Property

Noam Greenberg, Antonio Montalbán and Richard A. Shore^{∗} Department of Mathematics Cornell University Ithaca NY 14853

July 22, 2004

Abstract

We show that if d ∈ GH_{1} then D(≤ d) has the complementation property, i.e. for all a < d there is some b < d such that a ∧ b = 0 and a ∨ b = d.

1 Introduction

A major theme in the investigation of the structure of the Turing degrees, (D, ≤_{T}), has been the relationship between the order theoretic properties of a degree and its complexity of definition in arithmetic as expressed by the Turing jump operator which embodies a single step in the hierarchy of quantification. For example, there is a long history of results showing that 0′ has many special order theoretic properties. To cite just a few: every countable partial order can be embedded below 0′ (Kleene and Post [KP54]); there are minimal degrees below 0′ (Sacks [Sac61]); 0′ cups to every degree above it (and so has the cupping property)(Friedberg [Fri57]); every degree below 0′ joins up to 0′ (and so has the join property)(Robinson [Rob72], Posner and Robinson [PR81]).

It was often hoped that some such property would distinguish either 0′ or some class of degrees closely related to it. For degrees below 0′, the notion of being close to 0′ (or 0 at the other end) was also measured by the jump operator via the high/low hierarchy: for d ≤_{T} 0′, d ∈ H_{n} ⇔ d^{(n)} = 0^{(n+1)} and d ∈ L_{n} ⇔ d^{(n)} = 0^{(n)}. The questions then became at which levels of this hierarchy do the various properties of 0′ appear. The corresponding results for the above properties for d ≤_{T} 0′ are as follows: every countable partial order can be embedded below every d ∉ L_{2}; there are minimal degrees below every d ∈ H_{1}; every d ∉ L_{2} cups to every degree above it; every degree below d joins up to d for d ∈ H_{1}. (Except for the last, these results are all known to be sharp in terms of the high/low hierarchy. The sharpness of the first follows from the existence of a minimal degree a ∈ L_{2} − L_{1}: There is a minimal a < 0′ not in L_{1} by Sasso [Sas74] and it is in L_{2} by Jockusch and Posner [JP78]. This minimal degree is easily seen to be weakly recursive in the sense of Ishmukhametov [Ish99] and then, by that work, has a strong minimal cover b, i.e. {0, a, b} is an initial segment of the degrees. This proves the sharpness of the third fact. The existence of such an initial segment with b also below 0′ follows by Lerman’s methods as outlined in [Ler83, XII.5.8]. The sharpness of the second is by Lerman [Ler86].) The techniques used to prove all these positive results are tied up with approximation methods, rates of growth conditions and domination properties. Thus they are of independent interest for relating degree theoretic properties of functions with such conditions.

∗All the authors were partially supported by NSF Grant DMS-0100035.

In the setting of the degrees as a whole the analogous measure of the strength of a degree in terms of its jumps is the generalized high/low hierarchy: d ∈ GH_{n} ⇔ d^{(n)} = (d ∨ 0′)^{(n)} and d ∈ GL_{n} ⇔ d^{(n)} = (d ∨ 0′)^{(n−1)} . (We take GL_{0} = {0}.) All of the results mentioned above for d ≤_{T} 0′, for example, are true for all degrees as long as we use the generalized hierarchy. (Jockusch and Posner [JP78]; (Cooper [Coo73]) for H_{1} and Jockusch [Joc77] for GH_{1}; Jockusch and Posner [JP78]; Posner [Pos77].) Once again approximations, rates of growth and domination properties play prominent roles in the constructions.

It was often hoped that these investigations would lead to a definition of 0′ in D or of some of the classes in the appropriate hierarchy in D or D(≤ 0′). In fact, the jump operator has been defined in D by entirely different methods involving coding models of arithmetic and other arguments by Shore and Slaman [SS99] as have all of the high/low classes in D(≤ 0′) with the exception of L_{1} by Nies, Shore and Slaman [NSS98]. The dream of a natural definition for any of these classes based on such order theoretic properties, however, still persists and can only be realized by investigations such as these. Moreover, the analysis of the relations between rates of growth and domination principles and the ordering of degrees remains intriguing on its own.

In this paper we consider the complementation property for degrees d: for every a < d there is a b < d such that a ∨ b = d and a ∧ b = 0. The primary result here is that 0′ has the complementation property. This result has a long history. R. W. Robinson [Rob72, cf. [PR81]] showed that every a ∈ L_{2} has a complement in D(≤ 0′); Posner [Pos77], that every a ∈ H_{1} has one and Epstein [Eps75], that every r.e. a has one. Finally, Posner [Pos81] showed that every a ∉ L_{2} has a complement in D(≤ 0′) and so 0′ has the complementation property. By a further argument using relativization and an additional division into cases along with some known results, Posner also showed that every d ∈ GH_{0}, i.e. d ≥ 0′, also has the complementation property. At the end of that paper, he posed four questions:

1. Is there a uniform proof of the complementation property for 0′ (i.e. eliminate the split into cases and provide a single procedure that generates a complement for any nonrecursive a < 0′)?

2. Does every nonrecursive a < 0′ have a 1-generic complement?

3. Does every nonrecursive a < 0′ have a complement of minimal degree?

4. Does every d ∈ GH_{1} have the complementation property?

Slaman and Steel [SS89] answered questions 1 and 2 simultaneously by providing a uniform proof that every nonrecursive a < 0′ has a 1-generic complement. Seetapun and Slaman circulated a sketch of a proposed affirmative answer to the third question around 1992 and that sketch has recently been extended and made into a proof by Lewis ([Lew03]). There have been several partial and related results about the fourth question. Epstein [Eps81], for example, showed that if a < h are r.e. and h ∈ H_{1} then a has a complement in D(≤ h). In this paper we supply a full affirmative answer:

Theorem 1.1. Every degree d ∈ GH_{1} has the complementation property, i.e. for every a < d there is a b < d such that a ∨ b = d and a ∧ b = 0.

Like the original proof that 0′ has the complementation property, our proof of this theorem is nonuniform. Rather than two case (a ∈ L_{2} and a ∉ L_{2}) we here have three separate cases, depending on the “distance” between a and d. The three cases are:

1. a ∈ GL_{2}.

2. a ∉ GL_{2}, but there is some function recursive in d which is not dominated by any function recursive in a.

3. Every function recursive in d is dominated by some function recursive in a.

Note that as defined these three cases are disjoint. The point is that if a ∈ GL_{2} then d′ = (d ∨ 0′)′ ≥ (a ∨ 0′)′ = a′′ and so there is a function recursive in d which dominates every function recursive in a. They are also each nonempty. For (2) just take d′ ≥ a′′. For (3) choose a ≥ 0′ and d any degree above a which is hyperimmune free with respect to a such as is given by relativizing either Miller and Martin [MM68] or the standard construction of a Spector minimal degree using total recursive binary trees to a. (The point here is that the usual forcing argument, even if only attempting to force minimality, decides totality of every ϕ_{e}^{A}. Thus, if ϕ_{e}^{A} is total, A lies on a recursive binary tree T every path through which makes ϕ_{e} total. So, for every n there is a level s of the tree such that ϕ_{e}^{T (σ)} ↓ for every σ at level s. This guarantees that ϕ_{e}^{A} is dominated by the recursive function which, given n, finds such an s and then outputs the maximum value of ϕ_{e}^{T (σ)} for σ on level s.) We should also note, however, that the proof we give for case (1) only needs d′ ≥ a′′ and so would cover some pairs in cases (2) as well. The constructions of a complement for a in D(≤ d) in each of the three cases are quite distinct. We describe the intuitions and the motivations for each now and provide the precise constructions and verifications in the following sections.

Case 1: The existence of a complement for a below d in this case was already proved in his thesis by Posner [Pos77]. Like the proof that L_{2} degrees have complements in D(≤ 0′) in Posner and Robinson [PR81] that proof was indirect (see [Ler83, IV.15]) and based on a nonuniform proof of the join theorem for GH_{1} (see [Ler83, IV.9]). It was also explicitly left open even in [Ler83] if the degree providing the join could be made GL_{1}. This was answered by Lerman [Ler85] but again nonuniformly. We supply a uniform proof for this sharper version of the join theorem for GH_{1} which we then modify to get this case of the complementation theorem.

The basic idea of our proof of the join theorem for d ∈ GH_{1} is, given A <_{T} D ∈ d, to build a 1-generic set B in a construction recursive in D (so that B <_{T} D) that codes D and to have the choices we make at each stage depend on A, so that the construction itself (and hence D) can be recovered from A ⊕ B. It combines the key idea of Jockusch and Shore’s [JS84] proof of the Posner-Robinson join theorem for 0′ with Jockusch’s [Joc77] use of the recursion theorem with degrees in GH_{1}. This approach is maintained for the proof of the first case of the complementation theorem, except that to ensure that A ∧ B ≡_{T} 0 we look for splits instead of strings forcing the jump. Since we are now looking for two strings rather than one, the coding is a little more complicated. Also, once we have found a split, we need the convergence of a functional with oracle A to let us know which string of the split we should take to diagonalize. This presents the problem that D cannot necessarily know if such a convergence will ever appear. However, by our case assumption, D can approximate whether a given functional with oracle A produces a total function (which is the only case we worry about). Thus, if we keep attacking some requirement, we will eventually believe the correct outcome and act appropriately.

Case 2: In this case, a is no longer in GL_{2}, hence d cannot approximate questions regarding totality. However, as was noted by Jockusch and Posner [JP78] (using Martin’s [Mar66] characterization of the domination properties of H_{1}), this loss is offset by a’s ability to approximate bounds for searches conducted by 0′: for every function f ≤_{T} 0′ (even a ∨ 0′) there is a function g ≤_{T} a, not dominated by f.

We would like to imitate a construction of complements below 0′, and as in the previous case, we use the fact that d being generalized high enables us to approximate constructions which are naturally recursive in 0′. However, another special aspect of 0′ is that it is recursively enumerable . Dominating the modulus (computation) function for a recursively enumerable (even Δ_{2}) set enables us to compute the set itself. In other words, there is a function d ≤_{T} 0′ which isn’t dominated by any function of lesser degree. In the standard constructions, this property is used to bound searches for facts which are r.e. in a. As this seems to be an essential element of all such constructions, we simply assume (this is the second case) that we are given a function d ≤_{T} d which isn’t dominated by any function recursive in a, and carry out the construction (with the necessary modifications, of course). Given such a function we can adapt the uniform construction of complements below 0′ of [SS89] to our second case. If such a function does not exist, we find ourselves in the third case for which a completely different approach seems to be required.

Case 3: The key observation which enables us to construct complements in the third case is the following. Suppose that an A falling under the third case is given, and we manage to construct some B ≤_{T} D such that A ∧ B ≡_{T} 0 and such that D ≤_{T} (A ⊕ B)′. In this case we must have D ≡_{T} A ⊕ B; if not, then we have

A ⊕ B <_{T} D ≤_{T} (A ⊕ B)′,

in other words, D ∈ Δ_{2}(A ⊕ B) but is not Δ_{1}(A ⊕ B), which implies (see [Ler83, III.5.9]) that the computation function for D (as a set which is Δ_{2}(A ⊕ B)) is not dominated by any function recursive in A⊕B, so also not by any function recursive in A. This contradicts the assumption that we are in case (3).

To construct B as required, we simply construct a set B of minimal degree, satisfying the requirement D ≤_{T} (A⊕B)′. Since we can assume that D ≰_{T} A′ (by the same argument as above), we cannot have B ≤_{T} A. Since B is minimal, we get A ∧ B ≡_{T} 0.

Now there is a mysterious aspect of our construction. We construct a set B without reference to the set A, and then use the assumed domination property of A to get our result. This implies that any B so constructed is automatically a complement for every A falling under the third case.

To accomplish this, we need to construct a B which will have properties which are fairly independent of the construction. We begin with a more controlled version of the construction of a minimal degree below a d ∈ GH_{1} and then modify it to code in D in a way that can be recovered from B and any function g dominating a search function used in the construction. The case assumption for A will guarantee that there is such a function recursive in A.

We begin with the standard method of constructing (a Spector) minimal degree by forcing with perfect trees. One constructs a sequence of recursive perfect trees, each tree succeeded by a splitting subtree or an extension (full) subtree, forcing either that B ≤_{T} Φ(B) or that Φ(B) is recursive, respectively (of course, if total). To prove Sacks’ [Sac61] result that there is a minimal degree below 0′, one introduces a priority argument version of this basic construction and uses partial recursive trees to get a minimal degree below 0′. The idea is to define the successor subtree as the splitting subtree, until we find an initial segment of the set we are building which does not split on our current tree, and then switch (permanently modulo action by higher priority requirements) to an extension (full) subtree.

The generalization of this technique to working below an arbitrary GH_{1} degree was introduced by Jockusch in [Joc77] where he proved that below every GH_{1} degree there is a minimal degree. Since, in this case, we do not have the power of 0′ to find whether a certain string splits on a tree or not, we keep looking for splits in hope of eventually finding one. The power of GH_{1}, together with the recursion theorem, allows us, as in the previous cases, to guess, eventually correctly, whether such a search will be successful. We use this guess to determine what kind of tree the successor will be. Since we may guess incorrectly for some time, we may switch back and forth between splitting and extension (full) subtrees, but only finitely many times, and so we maintain the finite injury character of the construction.

In such a construction, the limit tree in a given place in the sequence of final trees is determined not only by the set B we construct and the question whether it splits or not on the previous tree, but also on the time during the construction at which we finally made the correct guess - this is because that stage determines what the stem of the tree will be. The primary difference between our construction and Jockusch’s is that we eliminate this dependency by making the stem of the tree independent of the stage and dependent only on B and on the previous tree. As we shall see, this change allows us to recover the final list of trees from (B ⊕ g)′, where g is any function dominating the search in the construction for splits when needed or a notification from our D recursive approximation to the (D ∨ 0′)′ question as to whether there is a initial segment of B above which there are no splits. We will finally use the fact that A falls under the third case to see that such a g can be obtained from A.

Our solution to the complementation problem for GH_{1} obviously leaves several natural open questions. Can the complements be taken to be either always 1-generic or always minimal? Is there a uniform procedure for computing a complement from D and A = {e}^{D} for 0 <_{T} A <_{T} D ∈ GH_{1}?

Finally, before beginning the specific cases, we provide some general definitions. We fix a set D ∈ d and a set A ∈ a (later we may specify sets with particular properties). We construct a set B whose degree will be a’s complement. The requirements we need to satisfy are:

• C: D is coded in B so that D ≤_{T} A ⊕ B.

• Z_{Φ}: If Φ(A) = Φ(B) is total, then it is recursive.

(Here Φ varies over Turing functionals; we identify a functional, and the requirement associated with it, with its index.) We think of a Turing functional as a recursive function Φ : 2^{<ω} → 2^{<ω} which is extendable continuously to a function Φ : 2^{ω} → 2^{≤ω}. If q ∈ 2^{<ω} and n ∈ dom Φ(q) we sometimes write Φ(q; n) ↓ and write Φ(q; n) = Φ(q)(n).

We fix an implicit recursive bijection ω ↔ ω^{<ω}. We let, for n <ω,

⟨(n)_{0}, (n)_{1}, …, (n)_{ℓ(n)−1}⟩

be the sequence associated with n.

In this paper, tree means a function tree, that is a partial function T : 2^{<ω} → 2^{<ω} which preserves order and nonorder and whose domain is closed under initial segments.

Suppose that Φ is a functional. A Φ-split is a pair of strings q_{0}, q_{1} such that Φ(q_{0}) ⊥ Φ(q_{1}), i.e. for some n, Φ(q_{0}; n) ↓≠ Φ(q_{1}; n) ↓. If (q_{0}, q_{1}) is a Φ-split, then we let n_{Φ}(q_{0}, q_{1}) be the least n witnessing this fact.

A split (q_{0}, q_{1}) extends p if both q_{0} and q_{1} extend p. If there is some Φ-split extending p, we say that p Φ-splits . If p Φ-splits, then we let (q_{Φ}^{0}(p), q_{Φ}^{1}(p)) be the least split extending p, and let n_{Φ}(p) = n_{Φ}(q_{Φ}^{0}(p), q_{Φ}^{1}(p)).

We say that a function f : ω → ω dominates the function g : ω → ω (and write g <_{∗} f) if for all but finitely many n, g(n) < f(n).

We use ⊂ to denote containment whether proper or not.

2 Case One

We begin with a uniform proof of the join property (via a 1-generic) for d ∈ GH_{1} that we then modify to produce a complement when A falls under Case 1.

Theorem 2.1. If 0 <_{T} A <_{T} D ∈ GH_{1} then there is a uniform procedure producing a 1-generic B such that A ∨ B ≡_{T} D.

Proof. In addition to the coding the requirement C, we here have just those for 1genericity:

• N_{Φ}: Φ(B) ↓ or (∃n)(∀q ⊇ B ↾ n)(Φ(q) ↑).

(Here we diverge from the usage described above and assume that the Turing functionals Φ take no input).

Without loss of generality (or uniformity), we may assume that A is the set of (natural number) codes for the initial segments of a set Ã of the same degree. The set B will be constructed as an increasing union of strings ⟨β_{s}⟩. However, for the sake of the applicability of the recursion theorem, we also present B as a finer union of initial segments ⟨p_{t}⟩_{t<ω}. The construction is recursive in D, hence the complexity of the question

∃t (p_{t} has no extension q such that Φ(q) ↓) ?

is (D ∨ 0′)′ ≡_{T} D′. Thus its answer can be approximated recursively in D. By the recursion theorem, we assume that we have a function G ≤_{T} D such that the limit lim_{s} G(Φ, s) is the answer to the question. At stage s of the construction we proceed as follows:

Let p_{1} = β_{1} = ⟨⟩. We are given β_{s} = p_{t} for some t and we work for requirement N_{Φ} for Φ = (s)_{0}.

At substage k of stage s, we let p_{t+k} = p_{t}^{⌢}0^{k}. We find the least r_{0} > t + k such that either G(Φ, r_{0}) = yes or a q extending p_{t+k} with Φ(q) ↓ is found after r_{0} many steps (this search halts, for if there is no such q, then p_{t+k} is a witness to lim G(Φ, r) = yes).

Now if we didn’t find a q as requested, we let l be the least element of A greater than k (of course A is infinite), and let β_{s+1} = p_{t+k+1} = p_{t}^{⌢}0^{l}^{⌢}1^{⌢}D(s).

Otherwise, we take the least q ⊃ p_{t+k} such that Φ(q) ↓ and such that for some l, p_{t}^{⌢}0^{l}^{⌢}1 ⊂ q (the string we find can always be extended to such a string). If l ∈ A then we do nothing and move to the next substage. Otherwise, we let β_{s+1} = p_{t+k+1} =q^{⌢}D(s).

To verify that this construction produces the desired B, we first need to show that there is no final stage s, in other words, that at every stage we eventually define β_{s+1} and move to the next stage. Assume the opposite holds and that s is the last stage. Thus at every substage k of s, we find the least q extending β_{s}^{⌢}0^{k} containing at least one additional 1 such that Φ(q) ↓ and this q extends β_{s}^{⌢}0^{l⌢}1 for some l ∈ A. Thus we can recursively enumerate infinitely such l and so an infinite subset of A. As this would compute A recursively we have the desired contradiction.

To see that B is 1-generic consider any Φ. Find a stage s late enough such that the guess for N_{Φ} is correct at stage s and (s)_{0} = Φ. If G(Φ) = yes then there is an initial segment of B with no extension q such that Φ(q) ↓. If not, then we defined β_{s+1} such that Φ(β_{s+1}) ↓.

Finally to see that D ≤_{T} A ⊕ B it is clearly enough to show that ⟨β_{s}⟩ ≤_{T} A ⊕ B: Given β_{s}, we find the k such that β_{s}^{⌢}0^{k}^{⌢}1 ⊂ B. If k ∈ A then |β_{s+1}| = |β_{s}| + k + 2. Otherwise, we can recursively find the least q extending β_{s}^{⌢}0^{k}^{⌢}1 such that Φ(q) ↓. In this case |β_{s+1}| = |q| + 1.

We now turn to case 1 of the complementation theorem.

2.1 Construction

The situation is as in the proof of the join theorem above except that we have requirements Z_{Φ} in place of N_{Φ} and so our function G approximates the answer to the question

∃t (p_{t} does not Φ-split ) ?

Also, A′′ ≤_{T} D′ so we can approximate Tot(A) recursively in D: we have a function T ≤_{T} D such that for all functionals Φ, lim_{s} T (Φ, s) = total if Φ(A) is total, and lim_{s} T (Φ, s) = nottotal otherwise.

Construction of B. Let p_{1} = β_{1} = ⟨⟩. At stage s, we are given β_{s} = p_{t} for some t and we work for requirement Z_{Φ} for Φ = (s)_{0}.

At substage k of stage s, we let p_{t+k} = p_{t}^{⌢}0^{k}. We find the least r_{0} > s + k such that either G(Φ, r_{0}) = yes or a Φ-split extending p_{t+k} is found (the least one) after r_{0} many steps (this search halts, for if there is no such split, then p_{t+k} is a witness to lim G(Φ, r) = yes). In the latter case, we find the least r_{1} > r_{0} such that either T (Φ, r_{1}) = not total or Φ(A; n_{Φ}(p_{t+k})) ↓ [r_{1}] (again, the search halts because no convergence witnesses lim T (Φ, r) = not total).

Now if we didn’t find a split, or didn’t find convergence, we let l be the least element of A greater than k (of course A is infinite), and let β_{s+1} = p_{t+k+1} = p_{t}^{⌢}0^{l}^{⌢}1^{⌢}D(s).

Otherwise, we know which element of the split q is the one which gives the wrong answer about Φ(A; n_{Φ}(p_{t+k})); we may assume it extends some p_{t}^{⌢}0^{l}^{⌢}1 for some l ≥ k. If l ∈ A then we do nothing and move to the next substage. Otherwise, we let β_{s+1} = p_{t+k+1} = q′^{⌢}D(s), where q′ is the least string ⊆ q and extending p_{t}^{⌢}0^{l}^{⌢}1 such that Φ(q′) ⊥ Φ(A). ♢

2.2 Verifications

We first need to show that there is no final stage s, in other words, that at every stage we eventually define β_{s+1} and move to the next stage. Assume the opposite holds and that s is the last stage. Thus at every substage k of s, the least Φ-split (q_{k}^{0}, q_{k}^{1}) extending β_{s}^{⌢}0^{k} is found, and we know that at least one of q_{k}^{0}, q_{k}^{1} extends β_{s}^{⌢}0^{l}1 for some l ∈ A.

Thus, we can recursively enumerate infinitely many pairs (i_{k}, j_{k}) (where both coordinates get larger and larger; i_{k}, j_{k} ≥ k) such that at least one of i_{k}, j_{k} is in A.

Now we can compute A and get a contradiction. Recall that the elements of A are codes for initial segments of Ã. Let σ_{k} be the string coded by i_{k} and τ_{k} the string coded by j_{k}.

Now there are two cases. Suppose that for all σ ⊂ Ã there is some k such that σ ⊂ σ_{k}, τ_{k}. Then we can compute Ã by enumerating

{σ_{k} ∩ τ_{k} : k < ω}.

Otherwise, there is some σ^{∗} ⊂ Ã and some k^{∗} such that for all k > k^{∗}, σ^{∗} is extended by exactly one of σ_{k}, τ_{k}, and this one has to be an initial segment of Ã. In this case we can compute Ã by enumerating

{σ_{k} : k > k^{∗}, σ^{∗} ⊂ σ_{k}} ∪ {τ_{k} : k > k^{∗}, σ^{∗} ⊂ τ_{k}}.

Lemma 2.2. A ∧ B ≡_{T} 0.

Proof. Fix Φ such that Φ(A) is total. Find a stage s late enough such that the guesses for T (Φ) and G(Φ) are correct at stage s and (s)_{0} = Φ. If G(Φ) = yes then Φ(B), if total, is recursive. If not, then we must have diagonalized at stage s, so that Φ(A) ≠ Φ(B).

Lemma 2.3. ⟨β_{s}⟩ ≤_{T} A ⊕ B.

Proof. Given β_{s}, we find the k such that β_{s}^{⌢}0^{k}^{⌢}1 ⊂ B. If k ∈ A then |β_{s+1}| = |β_{s}|+k +2. Otherwise, from A we can find the q such that β_{s+1} = q^{⌢}D(s).

Corollary 2.4. D ≤_{T} A ⊕ B.

3 Case Two

The construction takes place on a tree T; B will be a branch on this tree. In Slaman and Steel’s construction, a requirement Z_{Φ} strives to find a Φ-split on T, and tries to let B extend that part of the split which gives the wrong answer about Φ(A). Since about Tot(A) we know naught, the strategy is to find such a split and then prevent weaker requirements from extending B beyond this split, until Z_{Φ} makes up its mind (due to a convergence of Φ(A)) or decides to give up. In the original construction, the requirement gives up at the next stage it receives attention, at which it is either guaranteed a string which doesn’t split on T (a negative win), or it is presented with a new split unto which its fortunes are now entrusted.

It is the domination property of d which is used to show that each requirement cannot be foiled for ever.

The first difficulty we come across is that in the construction of the tree, we wish to find out whether a certain node can be extended by some split. Instead of asking 0′, we construct the tree (ignoring the coding requirement for a while) recursively in A by looking, at level s, for splits, for g(s) many steps, where g ≤_{T} A is a function not dominated by some fixed f̃ ≤ 0′ which bounds the search needed to find all splits which exist. Thus in many levels devoted to some Z_{Φ}, the requirement falsely believes that no splits exist (and thus that it needs no action to succeed); but the domination properties of g ensure that, if there are infinitely many splits, splits will be found infinitely often, giving the requirement ample breathing space to act.

These changes create two new difficulties. As described earlier, a requirement Z_{Φ} imposes its will on weaker requirements (which threaten to extend B beyond a split, while Z_{Φ} is still waiting for convergence of Φ(A)). This restraint is built into the construction of the tree, and is only imposed (for each split) for a single stage only, since at the next stage Z_{Φ} looks ahead to find either a new split or no splits, in which case it is satisfied anyway. In our case, Z_{Φ} does not know how long it needs to wait, thus restraints need to be made explicit. Fairness is maintained by observing that at the “true stages” (those stages at which g > f, meaning that the answers for the question “is there a split?” are correct) all unnecessary restraints are dropped.

However, each requirement needs to determine for itself whether to pursue positive satisfaction (by waiting for the next split) or to give up and let B extend a node beyond which no splits are found yet, hoping that indeed no splits will appear later. It turns out that D is sufficiently strong to enable Z_{Φ} to guess which course to take (using the recursion theorem, of course). This solves this second problem.

We now give the details of the construction. For simplicity, we adopt a modular approach and ignore the coding requirement C for now, and later describe how to modify the construction to satisfy this requirement.

3.1 Construction of the Tree

We first define the function f which bounds the search for splits. Let

f_{0}(s) = max{⟨q_{Φ}^{0}(p), q_{Φ}^{1}(p)⟩ : p ∈ 2^{≤s}, Φ ≤ sp Φ-splits}.

Next, define f by recursion: f(0) = f_{0}(0); f(s + 1) = f_{0}(f(s) + 1). Finally, let f̃(s) = f(⟨s, s⟩). Observe that f̃ is recursive in 0′.

To level k of the tree we attach requirement Z_{Φ} = (k)_{0}. k is called a Φ-level.

We find some g ≤_{T} A, not dominated by f̃. We use g to define our tree T. T (⟨⟩) = ⟨⟩. If T (σ) is defined and equals p, and |σ| is a Φ-level, then we look for a Φ-split extending p which appears before stage g(s). If one is found, then we define T (σ^{⌢}i) = q_{Φ}^{i}(p). Otherwise, we let T (σ^{⌢}0) = p^{⌢}0 and leave T (σ^{⌢}1) undefined.

We say that a string p is a node if it is in range T. We let

L(k) = {T (σ) : |σ| = k},

and also write level(p) = k for all p ∈ L(k).

It is easily verified that T is Δ_{1}(A) (so not only is T partial recursive in A but also dom T is recursive in A). We are also interested in verifying how closely this tree reflects the truth (about existence of splits).

Lemma 3.1. For all k and p ∈ L(k), |p| < f(k).

Proof. This is true by induction; the inductive step holds because the elements of the k + 1^{st} level are least splits (or immediate successors) of strings of level k, and f bounds all such splits.

Definition. A level k is called Φ-true if it is a Φ-level, and g(k) > f(k).

Thus if k is a Φ-true level then for all p ∈ L(k), if there is no Φ-split on T extending p then indeed there is no such split at all.

Lemma 3.2. For every Φ there are infinitely many Φ-true levels.

Proof. We know that there are infinitely many n ≥ Φ such that g(n) ≥ f̃(n). For each such n, if we let k = ⟨Φ, n⟩, then

g(k) = g(⟨Φ, n⟩) ≥ g(n) ≥ f(⟨n, n⟩) ≥ f(⟨Φ, n⟩) = f(k).

3.2 The Construction

We now describe the construction of a set B <_{T} D such that A ∧ B ≡_{T} 0. We construct B as the union of an increasing sequence of initial segments ⟨β_{s}⟩ which are on T.

At stage s, each requirement Z_{Φ} may impose a restraint r(Φ)[s]. This is a level k of the tree (beyond the level of β_{s}), and the aim of the restraint is to prevent weaker requirements from extending β_{s+1} beyond the k^{th} level of T. If a stronger requirement Z_{Ψ} extends β_{s+1} beyond the k^{th} level of T then we say that it injures Z_{Φ}. We let

R(Φ)[s] = min ({r(Ψ)[s] : Ψ < Φr(Ψ)[s]↓} ∪ {s}) .

This is the restraint imposed on requirement Z_{Φ} at stage s. Thus at s, Z_{Φ} is prohibited from defining β_{s+1} beyond the R(Φ)^{th} level of T.

There are various states in which a requirement Z_{Φ} may find itself at a Φ-stage s. It may be positively satisfied at s if we have already forced that Φ(B) ⊥ Φ(A), i.e. for some n we have

Φ(A; n) ↓≠ Φ(B; n) ↓ [s].

If Z_{Φ} is positively satisfied at some stage then it is satisfied until the end of time and doesn’t need to act ever again.

We wish to describe when Z_{Φ} is satisfied negatively. As explained above, this requirement will feel satisfied if it can make B extend some node p which doesn’t Φ-split. Now without the power of 0′, this kind of satisfaction may be temporary, for the requirement may place its bets on some such p only to discover later some Φ-split extending p.

To make its decision whether to believe some negative satisfaction (or keep searching for splits), at various stages Z_{Φ} will put some strings on a “testing list” ℓ_{Φ} (which can be thought of as a partial function defined by Z_{Φ} during the construction). This will be the list of strings that Z_{Φ} will test, to see if they may provide negative satisfaction.

We thus say that Z_{Φ} is negatively satisfied at s if no Φ-splits extending the last element put on ℓ_{Φ} are found in g(s) many steps.

[We note, that if Z_{Φ} is negatively satisfied at a true stage s, then this satisfaction is correct and permanent; at true stages we find all possible splits above nodes on levels ≤ s on the tree.]

Now to decide whether it should even attempt to believe that negative satisfaction could come from some node p, Z_{Φ} will try to find an answer to the question

Is there some node p which is put on ℓ_{Φ} and doesn’t split?

This question can be answered by (D ⊕ 0′)′ ≡_{T} D′. So, by the recursion theorem and the limit lemma, there is a function G ≤_{T} D, that we can use during the construction, which approximates the answer (i.e. lim_{s} G(Φ, s) = yes if the answer to the question is yes, and lim_{s} G(Φ, s) = no otherwise.)

Let

L(k, p) = {T (σ) : |σ| = k and T(σ) ⊇ p},

this is the collection of nodes of the k^{th} level of T which extend p. At stage s, let L(k, s) = L(k, β_{s}).

We say that p = T (σ) splits on T if both T (σ^{⌢}0) and T (σ^{⌢}1) are defined, i.e. if a relevant split exists and was discovered by step g(|σ|) and put on T.

Construction of B, with oracle D. At stage 0, we let β_{1} = ⟨⟩, we set the lists ℓ_{Φ} to be empty, and let r(Φ) be undefined for all Φ.

If Φ is initialized (at any stage), then r(Φ) is removed.

Stage s: Suppose that s is a Φ-stage.

If Z_{Φ} believes it is satisfied (positively or negatively), then we skip this stage; r(Φ) is not defined.

Otherwise, Z_{Φ} may attempt to act, starting ambitiously.

Positive action

If Z_{Φ} can legally extend β_{s} to be permanently satisfied, it does so. Namely, if there is some p on T, extending β_{s}, on a level below R(Φ)[s], such that for some n we have Φ(p; n) ≠ Φ(A; n)[d(s)] then Z_{Φ} lets β_{s+1} = p. r(Φ) is removed (as the requirement is satisfied). [d is the function recursive in D, not dominated by any function recursive in A.]

Negative attempts

Otherwise, we look for some p of level beneath R(Φ)[s] (but which extends β_{s}) which is not yet on ℓ_{Φ} and which is not yet seen to Φ-split. If such a p exists, we add the first one to ℓ_{Φ}. We now perform a test to see if we believe p can be a witness for negative success: we find the least t > s such that either G(Φ, t) = yes, or some Φ-split extending p is found by stage t. This search has to halt since if there is no split to be found, then p is a witness to the limit of G(Φ, t) being yes. If a Φ-split was found then we may try with a new node p (until we run out). Otherwise, Z_{Φ} sets β_{s+1} = p, and removes r(Φ).

If we run out of p’s without acting, the requirement does nothing at this stage, but we calculate Restraint

If r(Φ) is not defined, then it is set to be level(β_{s}). Otherwise, if there is some Φ-level k such that r(Φ) < k ≤ R(Φ)[s] and such that every p ∈ L(k, s) splits on T, then we update r(Φ) to be the maximal such k. If there is no such k, then r(Φ) is left unaltered.

Whenever Z_{Φ} acts and extends β_{s}, it initializes all weaker requirements. ♢

3.3 Verifications

Since this is an oracle construction, we have B ≤_{T} D. We first check that the construction is fair.

Lemma 3.3. Every requirement is initialized only finitely many times, and eventually stops acting itself.

Proof. Since initialization occurs only by action of a stronger requirement, we assume by induction that after ŝ, no requirement stronger than Z_{Φ} acts again and so Z_{Φ} is never initialized again.

If at any time Z_{Φ} acts positively, then its satisfaction is permanent and it will never act again. We now consider what happens to Z_{Φ} after stage ŝ.

Infinite negative action is also impossible. For either lim G(Φ, s) = no, in which case after some stage we will never believe some string is a likely candidate for negative satisfaction; or lim G(Φ, s) = yes, by virtue of a witness p which was put on ℓ_{Φ}; when we put p on the list, we performed the test and acted for p (because it really doesn’t split); and negative satisfaction is permanent from then on (no splits are ever discovered, and no new strings are put on the list).

We digress to prove that the requirements succeed if they act.

Lemma 3.4. If Z_{Φ} ever acts positively, then it is met.

Proof. Because then Φ(A) ≠ Φ(B).

Lemma 3.5. If Z_{Φ} is eventually permanently satisfied negatively by some p then it is met.

Proof. We have some p ⊂ B such that no Φ-splits extend p. Then Φ(B), if total, is recursive.

Now if a requirement is not eventually satisfied as in the last two lemmas, then there is a last stage at which the requirement acts, necessarily a negative action. Since this does not lead to permanent satisfaction, at some later stage the last action taken is discovered to be insufficient (a split is discovered, extending the last element of ℓ_{Φ}); after that stage, since the requirement never acts again, it also never believes it is satisfied. In this case we say that Z is eventually unsatisfied.

We let s^{∗}(Φ) be the least Φ-stage after which neither Z_{Φ} nor any stronger requirement ever acts again, and after which Z_{Φ} is either permanently satisfied or eventually unsatisfied.

A requirement may also disturb weaker requirements by imposing restraint, so to check fairness, we need to verify that this restraint is not too prohibitive. If a requirement is permanently satisfied (positively or negatively) then it stops imposing any restraint.

Otherwise we have

Lemma 3.6. Suppose that Z_{Φ} is not eventually satisfied. Then at s^{∗}(Φ), r(Φ) is defined; thereafter it is never removed and cannot decrease. For all s ≥ s^{∗}(Φ), level(β_{s}) ≤ r(Φ)[s].

Proof. The first part is because Z_{Φ} is never initialized again, or acts again. The second follows because weaker requirements respect r(Φ).

We need to examine what happens to the restraint if a certain requirement is eventually unsatisfied. For this we use the true levels.

Lemma 3.7. Suppose that Z_{Φ} is eventually unsatisfied, k > s^{∗}(Φ) is a Φ-true level and that s > k is a Φ-stage such that level(β_{s}) ≤ k ≤ R(Φ)[s]. Then at s, r(Φ) is increased to at least k.

Proof. If not, then we must have some p ∈ L(k, s) which does not split on T. But k is a true stage; thus p doesn’t split, and Z_{Φ} would act negatively at stage s.

We get

Lemma 3.8. lim_{s} R(Φ)[s] = ∞.

Proof. Assume (by induction) that lim R(Φ)[s] = ∞. Suppose, for contradiction, that lim r(Φ, s) = r is finite. We can choose some Φ-true level k > r and wait for a later Φstage s > s^{∗}(Φ) such that R(Φ)[s] > k. level(β_{s}) ≤ r < k; then we must have r(Φ)[s] ≥ k, contradiction.

Lemma 3.9. lim_{s} |β_{s}| = ∞.

Proof. There are infinitely many Φ such that, for all X, Φ(X) = ⟨⟩, so there are no Φ-splits. For all these Φ, Z_{Φ} will act negatively the first time it receives attention. Therefore, β_{s} is extended infinitely often.

All that is left is to verify that Z_{Φ} is met, even if it is eventually unsatisfied.

Lemma 3.10. If Z_{Φ} is eventually unsatisfied, then Φ(A) is not total.

Proof. Suppose otherwise, and let h(n) be the stage at which Φ(A; n) ↓; h ≤_{T} A. We show that h dominates d for a contradiction.

Let s_{1}, s_{2}, ... be the stages, after s^{∗}(Φ), when r(Φ)[s] is increased. Let r_{i} = r(Φ)[s_{i}], and let p_{i} be the element of the r_{i}^{th} level of T which is an initial segment of B. Since p_{i} ∈ L(r_{i}, s_{i}) (β_{s_{i}} ⊂ B), by the instructions of the construction, we must have that p_{i} splits on T. We let n_{i} be the splitting point, i.e. n_{i} = n_{Φ}(p_{i}).

We claim that for all i < ω, h(n_{i}) ≥ d(n_{i+1}). At stage s_{i+1}, Z_{Φ} did not act positively. However, the Φ-split of p_{i} was still available for Z_{Φ} to pick for positive satisfaction; the restraint until s_{i+1} was r_{i} and r_{i} ≤ R(Φ, s_{i}) ≤ R(Φ, s_{i+1}) (the latter inequality holds because after s_{i} no requirement stronger than Z_{Φ} acts). This implies that Φ(A; n_{i}) ↑ [d(s_{i+1})], in other words,

d(s_{i+1}) < h(n_{i}).

Of course, n_{i} < s_{i} so d(n_{i+1}) < d(s_{i+1}) < h(n_{i}).

Both h and d are increasing functions, so the last inequality implies that h dominates d: for every n > n_{1}, there exits i such that n_{i} < n ≤ n_{i+1}. Then

d(n) ≤ d(n_{i+1}) < h(n_{i}) ≤ h(n).

3.4 Coding D into B

In this section we show how to modify the construction to satisfy the coding requirement C; this will ensure that indeed B is a complement for A below D.

To do this, we specify an infinite, recursive set of levels on f (say all k such that (k)_{0} = 0) which will be devoted to C (by the padding lemma this does not disturb the previous construction). Let ⟨n_{i}⟩_{i<ω} be an increasing enumeration of this set. We define a tree T_{D} ⊂ T (as functions) by removing all nodes extending T (σ^{⌢}(1 − D(i))) for σ ∈ 2^{n_{i}}. Namely,

T_{D} = T ↾ {σ : ∀n_{i} < dom σ : σ(n_{i}) = D(i)}.

Lemma 3.11. T_{D} ≤_{T} D and for every X ∈ [T_{D}], D ≤_{T} X ⊕ A.

Proof. To find whether i ∈ D, A can find (on T) the unique σ on level n_{i} + 1 such that T (σ) ⊂ X. Since X ∈ [T_{D}] we have σ(n_{i}) = D(i).

Thus all we need to do is repeat the previous construction, using T_{D} instead of T. This can be done because the construction is recursive in D; the construction follows through verbatim.

4 Case Three

4.1 A minimal degree below D

We first give our version of the construction of a minimal degree below D. As in Sacks’s and Jockusch’s constructions, we will construct a sequence of partial recursive trees ⟨T_{k}⟩ and an increasing sequence of strings β_{s} whose union B is a path on all of the trees. Later we will show how to modify this construction so that D can be recovered from ⟨T_{k}⟩. Now we just build B such that ⟨T_{k}⟩ ≤_{T} (A ⊕ B)′.

We follow Lerman’s [Ler83] definitions of splitting subtrees. If T is a tree and Φ is a functional, then a Φ-splitting subtree of T is a subtree S such that for all p ∈ dom T, T (p^{⌢}0) and T (p^{⌢}1), if defined, are a Φ-split. The canonical splitting subtree above a node T (p) (denoted S = Sp(T, Φ, p)) is defined by induction, letting the stem be T (p); given S(q) on T, S(q^{⌢}0), S(q^{⌢}1) is defined to be the least Φ-split on T extending S(q), and undefined if none is found.

We say that X ∈ [T] Φ-splits on T if for all σ ⊂ X, there is a Φ-split on T extending σ.

The requirement to be satisfied is

M_{Φ} If BΦ-splits on every tree T_{k} then it lies on a Φ-splitting tree.

Associating requirements with numbers as usual, the strategy to satisfy k = M_{Φ} is to let T_{k+1} = T_{k} if B does not Φ-split on T_{k}, and Sp(T_{k}, Φ, p) for some p otherwise. We make p depend on B directly, by letting p be the shortest string such that B ∈ Sp(T_{k}, Φ, p).

As usual, the construction will have approximations T_{k}[s] to T_{k} and an increasing sequence ⟨β_{s}⟩ of strings whose union is B. During each stage of the construction the trees T_{k}[s] are enumerated a certain number of steps to find splits above β_{s}. We will make sure that once T_{k} has stabilized, if B splits on T_{k} then at every s there is a split found on T_{k} extending β_{s}. Thus from the construction we can calculate a function f which bounds the search needed to find splits on the trees. Namely, we have a function f ≤_{T} D such that for all k = M_{Φ}, if B Φ-splits on T_{k} then for almost all n, a Φ-split extending B ↾ n will be found on T_{k} after enumerating the tree for f(n) many steps.

[We note that it is not necessary to assume that dom β_{s} ≥ s to get such a function; to calculate f(n) we can simply wait for a stage at which dom β_{s} > n. This will be helpful in the full construction we give at the end].

First, we would like to ensure that the above conditions on the construction indeed produce the desired result. Suppose, then, that B, ⟨T_{k}⟩ and f are given as described.

Lemma 4.1. B has minimal Turing degree.

Proof. See [Ler83, V.2.6]

Suppose that g is a function which dominates f.

Lemma 4.2. ⟨T_{k}⟩ ≤_{T} (B ⊕ g)′.

Proof. Take k = M_{Φ}. Suppose we have already determined what T_{k} is. First, we wish to find out what kind of tree T_{k+1} is, which is the same as finding whether B Φ-splits on T_{k} or not.

We first ask (B ⊕ g)′ if there is some n such that after running T_{k} for g(n) many steps, no Φ-splits above B ↾ n on T_{k} are found. If not, B splits on T_{k}. If there is such an n, then a search (recursive in B ⊕ g) can find the least one n_{0}. We now ask 0′ (which is below (B ⊕ g)′) if there are any Φ-splits extending B ↾ n_{0} on T_{k}. If not, then B does not split on T_{k}. If such a split exists, we repeat the process, asking if there is some n_{1} > n_{0} such that after g(n_{1}) many steps no Φ-split extending B ↾ n_{1} is found on T, and if one exists, we find it and ask 0′, etc. This process must stop. For if B doesn’t split on T_{k} then eventually we find some n such that there are no Φ-splits on T_{k} extending B ↾ n (and of course none before g(n).) If B does split on T_{K}, then the properties of f ensure that eventually, a Φ split extending B ↾ n is always found before step f(n), hence g(n).

Now if B doesn’t Φ-split on T_{k} then T_{k+1} = T_{k}. Otherwise, we need to find the least q such that B ∈ [Sp(T_{k}, Φ, q)]; We then know that T_{k+1} = Sp(T_{k}, Φ, q).

Suppose that T_{k}(q) ⊂ B. Consider the following process: Let T = Sp(T_{k}, Φ, q). T (⟨⟩) = T_{k}(q) ⊂ B. Since every initial segment of B splits on T_{k}, both T (0) and T (1) are defined. We find them. If neither are initial segments of B, then the process halts. Otherwise, pick the one (say T (0)) such that T (0) ⊂ B. By the same reasoning, both T (01) and T (11) are defined, etc.

We see that this process is recursive in B. Thus B′ can tell us whether it eventually terminates or not. However, a quick inspection shows that the process terminates iff B ∉ [T]. Thus

{r : B ∈ [Sp(T_{k}, Φ, q)]}

is recursive in B′ ≤ (B ⊕ g)′. We can thus inductively (on q such that T_{k}(q) ⊂ B) ask whether q is an element of the above set (this search is recursive in B ⊕ B′ ≡_{T} B′). Eventually we will find the least one which is the desired q.

Now recall that we had a set A, falling under the third case, which excludes the second case. This means that for every function f recursive in D, there is some g recursive in A which dominates f. Thus we can go back and write A in each place we wrote g to get ⟨T_{k}⟩ ≤_{T} (A ⊕ B)′.

4.2 Construction I

The construction which yields the B, ⟨T_{k}⟩ and f with the desired properties is not difficult, and in fact differs only slightly from Jockusch’s construction. We describe it now.

We construct a sequence β_{s}.

By the recursion theorem, we have a function G(T, Φ, s) ≤_{T} D such that for all (partial recursive function) trees T and Turing functionals Φ, lim_{s} G(T, Φ, s) is the answer to the question

Is there some t such that β_{t} is on T, and above β_{t} there are no Φ-splits on T?

At stage 0, we let k(0) = 0, T_{0}[0] = id, β_{0} = ⟨⟩ and f(0) = 0.

At stage s+1, we are given a sequence of trees T_{0}[s], …, T_{k(s)}[s] (each T_{k+1}[s] is either equal to T_{k}[s] or is a splitting subtree of T_{k}[s]), and β_{s} which is on every T_{k}[s].

Using G we can define a function H, which tells us how far a requirement has to search until its guess (about whether B splits or not) has evidence in reality. Namely, if k = M_{Φ}, then H(k, s) is defined to be the least stage t > s such that either G(T_{k}[s], Φ, t) = yes, or a Φ-split extending β_{s} is found on T_{k}[s]. By the properties of G, we know that such a t must exist. We also let F (k, s) = split if a Φ-split above β_{s} is found on T_{k}[s] at stage H(k, s); otherwise we let F (k, s) = no split. Thus F gives us k’s guess about whether B Φ-splits on T_{k}[s]. There is a discrepancy between reality and k’s belief if F (k, s) = split and T_{k+1}[s] = T_{k}[s], or if F (k, s) = no split but T_{k+1}[s] is a splitting subtree of T_{k}[s]. If there is such a discrepancy, then it must be fixed by k by changing the tree T_{k+1} according to belief.

We thus say that k requires attention at s if there is a discrepancy between k’s beliefs and reality. If there is some k requiring attention, we act as follows:

• If F (k, s) = no split, we let T_{k+1}[s + 1] = T_{k}[s].

• If F (k, s) = split, we want to define T_{k+1}[s + 1] to be Sp(T_{k}[s], Φ, q) for some q ⊂ p = T_{k}[s]^{−1}(β_{s}); as discussed above, we pick q to be the least such that β_{s} is extended by some string on Sp(T_{k}[s], Φ, q).

How do we effectively find this q? This is similar to the process in the proof of lemma 4.2: we inductively check q = ⟨⟩, q = p ↾ 1, q = p ↾ 2, . . .. We know there is a split extending β_{s}; thus we can search for the least split on the tree T_{k}[s] extending T_{k}[s](q). If neither of the two strings of the split are compatible with β_{s}, this was the wrong q, and we try the next one. If one is, we repeat the process for that part of the split which is an initial segment of β_{s}. We halt with a “yes” answer (for the q checked) if we get to a string extending β_{s}.

In either case we let k(s + 1) = k + 1 and T_{l}[s + 1] = T_{l}[s] for l ≤ k.

If no requirement asks for attention, we let k(s + 1) = k(s) + 1, T_{l}[s + 1] = T_{l}[s] for l ≤ k(s) and T_{k(s)+1}[s + 1] = T_{k(s)}[s].

Now either β_{s} is not on T_{k(s+1)}[s + 1], but properly extended by some string which is on this tree; or β_{s} is on T_{k(s+1)}[s + 1] and not terminal on it. Thus we can properly extend β_{s} to some β_{s+1} on that tree. That’s the end of stage s.

We verify that the objects constructed indeed have the desired properties. We first show that the sequence of trees stabilizes.

Lemma 4.3. For all k there is a stage s^{∗}(k) such that for all t ≥ s^{∗}(k), k(t) > k.

By the construction, we have that for all t > s^{∗}(k), T_{k}[t] = T_{k}[s^{∗}(k)]; we let T_{k} be this final tree.

Proof. s^{∗}(0) = 1. Assume s^{∗}(k) exists, we will show that s^{∗}(k + 1) exists too. Suppose that k = M_{Φ}. Suppose that after t > s^{∗}(k), G(T_{k}, Φ, s) has stabilized on the correct answer. Then we can let s^{∗}(k + 1) = t, because neither k, nor any stronger requirement, will seek attention after t.

Corollary 4.4. Each M_{Φ} succeeds.

Proof. The guesses are eventually correct. Thus if B splits on T_{k}, then T_{k+1} is some splitting subtree of B; if B doesn’t split on T_{k} then we’re done anyway.

Also as a corollary, we have that if B splits on T_{k} then eventually, at every s, a split above β_{s} on T_{k} is found at stage s of the construction; this allows us to calculate the function f as required.

Finally,

Lemma 4.5. Assume that k = M_{Φ} and that B splits on T_{k}. Then T_{k+1} = Sp(T_{k}, Φ, q) where q is the least string such that B ∈ [Sp(T_{k}, Φ, q)].

Proof. Say T_{k+1} = Sp(T_{k}, Φ, q), and was finally defined at stage s. Of course B ∈ [T_{k+1}]. If r ⊊ q then at stage s we verified that β_{s} went off Sp(T_{k}, Φ, r) (no string on that tree extends β_{s}), thus B ∉ [Sp(T_{k}, Φ, r)].

4.3 Coding D

We now add more subtrees to our sequence T_{k} so that we will be able to recover D from ⟨T_{k}⟩.

We have new requirements C_{n}, whose aim is to code the answer to n ∈ D? into the sequence of trees.

We organize all C_{n} and M_{Φ} requirements effectively and identify each requirement with its place on the list.

For C_{n}, we use two different kinds of narrow subtrees.

Definition. For p ∈ 2^{<ω}, let nar_{p}, row_{p}: 2^{<ω} → 2^{<ω} be defined as follows

nar_{p}(σ) = p^{⌢}00σ(0)00σ(1)00σ(2) … 00σ(|σ| − 1)
row_{p}(σ) = p^{⌢}11σ(0)11σ(1)11σ(2) … 11σ(|σ| − 1).

Now, suppose that T is a tree and that p ∈ dom T. We let Nar(T, p) = T ∘ nar_{p} and Row(T, p) = T ∘ row_{p}.

It is easy to see that if T is partial recursive, then so are Nar(T, p) and Row(T, p), and an index for each can be obtained uniformly from p and an index for T.

Lemma 4.6. Suppose that T is a tree, and that p, q ∈ dom T. Then

[Nar(T, p)] ∩ [Row(T, q)] = 0.

This property motivates us to satisfy k = C_{n} by letting T_{k+1} = Nar(T_{k}, p) for some p if n ∈ D and T_{k+1} = Row(T_{k}, p) for some p otherwise. As we did for the splitting subtrees, to be able to recover T_{k+1} from T_{k} and (A ⊕ B)′ we eliminate the element of chance in the game by ensuring that T_{k+1} = Nar(T_{k}, p) for the least p such that B ∈ [Nar(T_{k}, p)] (or Row, as D decides).

Lemma 4.7. Suppose that T is partial recursive and X ∈ [T]. Then

{p ∈ dom T : X ∈ [Nar(T, p)]}

is recursive in X′ (similarly for Row).

Proof. From X we can determine the h ∈ 2^{ω} such that X ⊃ T [p^{⌢}h] (if T (p) ⊄ X then X knows that p is not in the set). Then we simply ask if for such h and all n ≠ 0 mod 3, h(n) = 0 (1 for Row).

So indeed if we code as promised, then B′ can find T_{k+1} from T_{k} by inductively asking, for longer and longer p, such that T_{k}(p) ⊂ B, whether B ∈ [Nar(T_{k}, p)] or B ∈ Row(T_{k}, p). The first “yes” answer we get is the correct one (and also tells us whether n ∈ D).

It would seem that all we need to do now is add this last element to the construction, namely if at stage s, k = k(s) = C_{n} and no stronger requirement asks for attention, then we should define T_{k+1}[s] to be Nar(T_{k}[s], p) (or Row(T_{k}[s], p) if n ∉ D) for the shortest p such that β_{s} is extended by some string on Nar(T_{k}[s], p). However, this is not so easy, for the reason that β_{s} may be nonterminal on T_{k}[s] for some k < k(s), but terminal on the narrow subtree T_{k+1}[s]; for p = T_{k}^{−1}(β_{s}), T_{k}(p^{⌢}0) may be defined but T_{k}[s](p^{⌢}00) or T_{k}[s](p^{⌢}000) may be undefined. In this case we would not be able to extend β_{s} and would be stuck.

We note, however, that the reason that T_{k}[s](p^{⌢}00) or T_{k}[s](p^{⌢}000) are undefined, is that some split was not found on an earlier tree T_{l}[s]. The strategy to extricate ourselves from this situation is to try and extend β_{s} on T_{l}[s] until we find the necessary split or guess that such a split does not exist. In the former case we can go on with the construction; in the latter we change our guess about T_{l+1} and remove later trees.

4.4 Construction II

We first describe the idea of the construction. The new construction attempts to follow in the footsteps of the previous construction; requirements k = M_{Φ} define subtrees T_{k+1} which are splitting subtrees or not, and amend the trees according to their guesses. New requirements k = C_{n} will define T_{k+1} to be some narrow subtree of T_{k}, the type of which will be determined by whether n ∈ D or not. All goes well as long as our initial segment β = β_{s} is nonterminal on the trees. Suppose, however, that β is terminal on T_{k[s]}[s], even after the action of M requirements. We then look at the greatest l ≤ k(s) such that T_{l}[s] is a splitting subtree of T_{l−1}[s]. We note that β must be nonterminal on T_{l}[s]; otherwise, l − 1 would have redefined T_{l} to be equal to T_{l−1}.

Let p = T_{l}^{−1}β. The reason that β is terminal on T_{k(s)} is that for some q, T_{l}(p^{⌢}q) is undefined; the latter is undefined because sufficiently many splits above β have not been discovered on T_{l−1}. If some extension γ of β on T_{l−1} really doesn’t split on T_{l−1}, then we would like to extend β to γ and redefine T_{l} = T_{l−1}; this would resolve the issue. Otherwise, we will find more and more splits until β will be discovered to not be terminal on T_{k(s)} after all. The question is how to tell whether there is such γ. After all, our guessing function G only answers questions about initial segments of B, not arbitrary nodes on the tree.

The solution is to gradually extend β, at substages of the stage s. As β is not terminal on T_{l}, we can extend it for one step on T_{l}. Now we search for splits on T_{l−1} as usual; if we believe there are none T_{l−1} can act and set T_{l} = T_{l−1}. Otherwise, a split is found which means we can extend β one step further on T_{l}. The process continues until β is nonterminal on T_{k(s)}, or a node γ as described is found and set as an initial segment of B.

We note a notational decision. It could be the case that at the beginning of the stage, some k ∈ [l, k(s)) redefines T_{k+1} = T_{k} because β is terminal on T_{k}. Also, it could be the case that at some some substage we believe that β can no longer be extended on T_{l−1} (and redefine T_{l} = T_{l−1}); no previous tree is acting, which means that the problem which was just described has just reappeared, for a smaller pair (l, k(s)). The above actions will have to be repeated, but we do this at the next stage s + 1 (we can move on because β is on all trees, even if terminal on some; between substages we will not change the trees, as the indexing would become cumbersome.)

We now give the full construction. At stage s we are given a sequence of trees ⟨T_{k}[s]⟩_{k≤k(s)} and a string β_{t} on all of those trees.

The guessing function G(T, Φ, s) is defined as before; it approximates the answer to the same question:

Is there some t such that β_{t} is on T and there is no Φ-split extending β_{t} on T?

The elements of the construction are as follows:

Guessing Splitting

We define guessing functions H and F. At stage s, at a substage at which we have β_{r} as an initial segment of B, and for k = M_{Φ}, H(k, s, r) is defined to be the least stage u > r+s such that either G(T_{k}[s], Φ, u) = yes, or a Φ-split extending β_{r} is found on T_{k}[s] after running the tree for u many steps. F (k, s, r) is defined analogously; it is split in the former outcome and no split in the latter.

Discrepancy between belief and reality is defined as in the previous construction; at the particular stage and substage, k feels the discrepancy if F (k, s, r) = split but T_{k+1}[s] = T_{k}[s], or if F (k, s, r) = no split but T_{k+1}[s + 1] is a splitting subtree of T_{k}[s].

At any stage and substage, if there is some requirement k = M_{Φ} < k(s) asking for attention, then the strongest such requirement receives it and redefines T_{k+1} according to its belief F. As before, it lets T_{k+1}[s + 1] = T_{k}[s] if F (k, s, t) = no split, and T_{k+1}[s + 1] = Sp(T_{k}[s], Φ, p) for the shortest p such that β_{r} is extended by some string on the latter tree. It lets k(s + 1) = k + 1 and leaves the trees T_{l} for l ≤ k unchanged.

If β_{r} is not on T_{k+1}[s + 1] then it is extended by some string on that tree; we let β_{r+1} be such a string. Otherwise, we hand β_{r} to the next stage.

Action of the last tree

At some substage of stage s, we may instruct the last requirement k(s) to act (this may happen if no other requirement asks for attention and if β_{r} is not terminal on T_{k(s)}[s]). k(s) first extends β_{r} to some string β_{r+1} on T_{k(s)}[s]. Then,

• If k(s) = M_{Φ}, it lets T_{k+1}[s + 1] = T_{k}[s].

• If k(s) = C_{n} and n ∈ D, then k(s) lets T_{k+1}[s+1] = Nar(T_{k}[s], p) for p the shortest substring of T_{k}[s]^{−1}(β_{r+1}) such that β_{r+1} is extended by some node on Nar(T_{k}[s], p). If necessary, β_{r+1} is extended again to β_{r+2} so that it actually lies on the new tree.

• If k(s) = C_{n} and n ∉ D, we act as in the previous case, but with Row replacing Nar.

In both cases, we let k(s+1) = k(s)+1, and leave the trees T_{l} for l ≤ k(s) unchanged.

Construction

The instructions at stage s are as follows. If some M requirement asks for attention, we let the strongest one act and end the stage. If no M requirement asks for attention at the beginning of the stage, and if β_{t} is not terminal on T_{k(s)}[s], then k(s) is asked to act and to end the stage.

Otherwise, we let T_{l}[s] be the last tree in our sequence which is a splitting subtree of its predecessor T_{l−1}[s]. There is a function h which is either the identity or a composition of functions of the form nar_{q} and row_{q} such that T_{k(s)}[s] = T_{l}[s] ∘ h. Let p = T_{l}^{−1}(β_{t}), q = T_{k(s)}[s]^{−1}(β_{t}) = h^{−1}(p) and r = h(q^{⌢}0). Our aim is to extend β_{t} to be T_{l}[s](r) = T_{k(s)}[s](q^{⌢}0). This is done in substages.

As noted above, we must have β_{t} not terminal on T_{l−1}[s], for we found a split on T_{l−1} extending β_{t} (or l − 1 would have acted). Therefore also β_{t} is not terminal on T_{l}[s]. Thus we can extend it and let β_{t+1} = T_{l}[s](r ↾ |p| + 1). We move to the first substage.

In general, at the beginning of substage i we have β_{t+i} = T_{l}[s](r ↾ |p| + i), already discovered to be on T_{l}[s]. If no M requirement wishes to act at this substage, then it must be that a split extending β_{t+i} was found on T_{l−1}; we can thus further extend this string on T_{l} and move to the next substage.

If at some substage an M requirement wishes to act, then that action ends the stage. Otherwise, at the end of the i = |r|−|p|^{th} substage we have β_{t+i} = T_{l}[s](r) = T_{k(s)}[s](p^{⌢}0). (Note that during substages, β_{t+j} may be not a string on T_{k(s)}[s], but at this last substage it is.) If β_{t+i} is terminal on T_{k(s)}[s] we do not change any of the trees and move on to stage s + 1 (we let k(s + 1) = k(s)). Otherwise, we can let k(s) act and end the stage.

4.5 Verifications II

The proof of lemma 4.3 goes through unaltered, noticing that if k = C_{n} then once T_{k} has stabilized, so will T_{k+1}, since k never acts to change the next tree.

As a corollary, we get that β_{t} gets extended infinitely often (so we do get a set B at the end). This is because if k(s + 1) > k(s) (i.e. if k(s) gets to act), β_{t} has been extended at stage s (in fact, β_{t} has been extended at every stage except perhaps at stages at which some M requirement acts at the beginning of the stage, making k(s + 1) ≤ k(s).)

We now may conclude that the construction succeeds; the rest of the verifications are as above: we showed that ⟨T_{k}⟩ ≤ (A ⊕ B)′ and that D can be obtained from ⟨T_{k}⟩.

References

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

[Eps75] R. L. Epstein. Minimal degrees of unsolvability and the full approximation construction. Mem. Amer. Math. Soc., 3(iss.1, 162):viii+136, 1975.

[Eps81] R. L. Epstein. Initial segments of degrees below 0′. Mem. Amer. Math. Soc., 30(241):vi+102, 1981.

[Fri57] R. Friedberg. A criterion for completeness of degrees of unsolvability. J. Symb. Logic, 22:159–160, 1957.

[Ish99] S. Ishmukhametov. Weak recursive degrees and a problem of Spector. In Recursion theory and complexity (Kazan, 1997), volume 2 of de Gruyter Ser. Log. Appl., pages 81–87. de Gruyter, Berlin, 1999.

[Joc77] C. G. Jockusch, Jr. Simple proofs of some theorems on high degrees of unsolvability. Canad. J. Math., 29(5):1072–1080, 1977.

[JP78] C. G. Jockusch, Jr. and D. B. Posner. Double jumps of minimal degrees. J. Symbolic Logic, 43(4):715–724, 1978.

[JS84] C. G. Jockusch, Jr. and R. A. Shore. Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers. J. Symbolic Logic, 49(4):1205–1236, 1984.

[KP54] S.C. Kleene and E.L. Post. The upper semi-lattice of the degrees of recursive unsolvability. Annals of Mathematics, 59:379–407, 1954.

[Ler83] M. Lerman. Degrees of Unsolvability. Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983.

[Ler85] M. Lerman. On the ordering of classes in high/low hierarchies. In Recursion theory week (Oberwolfach, 1984), volume 1141 of Lecture Notes in Math., pages 260–270. Springer, Berlin, 1985.

[Ler86] M. Lerman. Degrees which do not bound minimal degrees. Ann. Pure Appl. Logic, 30(3):249–276, 1986.

[Lew03] A. E. M. Lewis. Aspects of complementing in the Turing degrees. PhD thesis, University of Leeds, 2003.

[Mar66] D. A. Martin. Classes of recursively enumerable sets and degrees of unsolvability. Z. Math. Logik Grundlagen Math., 12:295–310, 1966.

[MM68] W. Miller and D. A. Martin. The degrees of hyperimmune sets. Z. fur Math. Logik und Grund. der Math., 14:159–66, 1968.

[NSS98] A. Nies, R. A. Shore, and T. A. Slaman. Interpretability and definability in the recursively enumerable degrees. Proc. London Math. Soc. (3), 77(2):241–291, 1998.

[Pos77] D. B. Posner. High degrees. PhD thesis, University of California, Berkeley, 1977.

[Pos81] D. B. Posner. The upper semilattice of degrees ≤ 0′ is complemented. J. Symbolic Logic, 46(4):705–713, 1981.

[PR81] D. B. Posner and R. W. Robinson. Degrees joining to 0′. J. Symbolic Logic, 46(4):714–722, 1981.

[Rob72] R. W. Robinson. Degrees joining 0′. Notices of the American Mathematical Society, 19:A–615, 1972.

[Sac61] G. E. Sacks. A minimal degree less than 0′. Bull. Amer. Math. Soc., 67:416–419, 1961.

[Sas74] L. P. Sasso, Jr. A minimal degree not realizing least possible jump. J. Symbolic Logic, 39:571–574, 1974.

[SS89] T. A. Slaman and J. R. Steel. Complementation in the Turing degrees. J. Symbolic Logic, 54(1):160–176, 1989.

[SS99] R. A. Shore and T. A. Slaman. Defining the Turing jump. Math. Res. Lett., 6(5-6):711–722, 1999.