Highness and bounding minimal pairs

Rodney G. Downey^{∗} Victoria University of Wellington, New Zealand

Steffen Lempp^{†}

University of Wisconsin–Madison Richard A. Shore^{‡} Cornell University

March 16, 1993

Abstract

We show the existence of a high r.e. degree bounding only joins of minimal pairs and of a high_{2} nonbounding r.e. degree.

0 Introduction

An important topic in the study of recursively enumerable sets and degrees has been the interaction between the jump operator and the order theoretic properties of an r. e. set A (in the lattice E of all r. e. sets) and of its degree a in R, the upper semilattice of the r. e. degrees. An early theme in this area was the idea that sets with “low” jumps should behave like the recursive sets while those with “high” jumps should exhibit properties like the complete sets. For example, in the lattice E^{∗} of r. e. sets modulo finite sets, we know from Soare[23] that if A is low, i. e. A′ ≡_{T} ∅′, then L^{∗}(A), the lattice of r. e. supersets of A, is isomorphic to E^{∗}. In R there are many instances of the low degrees behaving like the recursive one. A classic example is the Robinson [15] Splitting Theorem: If d < c and d is low then there are r. e. a and b with d < a, b < c such that a ∨ b = c. (This generalizes the Sacks[16] Splitting Theorem in which d is recursive.) For the high sets (A′ ≡_{T} ∅′′) and degrees, the trend of results has been that anything possible happens. Here the classic examples are Martin’s [14] theorem that every high degree contains a maximal set and Cooper’s [2] result that there is a minimal pair (a, b ≠ 0 with a ∧ b = 0) below every high degree. More recently, Shore and Slaman [19] and [20] have shown that other important phenomena (the special triples of Slaman[21] and the nonsplitting pairs of Lachlan [12], respectively) occur below every high degree. As for the lattice E^{∗}, Cholak[1] and Harrington and Soare [10] have proven that every possible lattice of supersets L^{∗}(A) occurs as one of a high set B, i. e. there is a high B with L^{∗}(A) ≅ L^{∗}(B). Indeed, if A is not recursive, they construct an automorphism of E^{∗} which takes A to B.

∗Partially supported by IGC of Vicoria University, Wellington and ARO through MSI, Cornell University, DAAL-03-C-0027.

†Partailly supported by NSF Grants DMS-9100114 and INT-9020558.

‡Partially supported by NSF Grants DMS-9204308 and INT 90-20558and ARO through MSI, Cornell University, DAAL-03-C-0027.

There has been some recent work extending such results on low sets to low_{2} ones (A′′ ≡_{T} ∅′′). Harrington et al. [9] have shown that if A is low_{2} then L^{∗}(A) ≅ E^{∗}. In R, Shore and Slaman [18] have shown that all extensions of embedding not ruled out by two classical theorems can be done in the low_{2} r. e. degrees. (They also supply a proof of Harrington’s extension of the Robinson splitting theorem to the situation where c is assumed low_{2} and d can be an arbitrary degree below c.) In E^{∗}, these results have supplied various characterizations of the high and low_{2} degrees. The high ones, for example, are precisely the ones containing maximal sets (Martin [14]). The low_{2} degrees are precisely those containing sets with no maximal superset (Lachlan [11] and Shoenfield [17]). In R, the above mentioned results of Shore and Slaman [18], [19] have separated these two classes. More recently,Groszek and Slaman [8] have combined Lachlan’s nonbounding theorem [13] (there is a nonzero degree with no minimal pair below it) with Lachlan’s [12] nonsplitting theorem to provide a definable class that is disjoint from both the high and low_{2} degrees. There are, however, no definitions or characterizations of any of the jump classes in R. (In contrast, Downey and Shore [4] have actually defined the low_{2} r. e. sets in R_{tt}, the structure of the r. e. truth table degrees, as precisely those with minimal covers in R_{tt}.)

The obvious general problem is to give order theoretic characterizations of the jump classes in R, in particular, of the high or low_{2} degrees. More specific questions include the possibility of extending each of the various results mentioned so far about these two jump classes to others such as the high_{2} (A′′ ≡_{T} ∅′′′) or low_{3} (A′′′ ≡_{T} ∅′′′) degrees. Until now there have been no direct constructions of high_{2} degrees with (order theoretic) properties that guarantee that they are not high. We show (Theorem 4.1) that Lachlan’s nonbounding degree [13] can be made high_{2} and so Cooper’s result [2] that every high degree bounds a minimal pair cannot be extended to the high_{2} degrees. (This result has recently been proven independently by both Lerman and Kučera. Kučera uses an approach different from ours.) We also indicate an application of our methods to question about E^{∗} by showing that not all high_{2} degrees contain hemimaximal sets (halves of splittings of maximal sets). (On the other hand, Downey and Stob [5] show that every high degree contains such a set.) This application answers a question of Downey and Stob [6] and [6]. On the low side of the jump hierarchy, Shore and Slaman [19] show that the Slaman triples can have a low_{3} top. Taken together, these results indicate that the classes defined by Slaman and Groszek cannot be further restricted in the jump hierarchy. We also feel that they indicate that we are far from having a definition of the high degrees. On the other hand, there are now techniques for working both above and below a low_{2} degree and there should be some hope for defining this class in R.

In addition to proving that there is a high_{2} nonbounding degree, we consider the question of whether there is one below every high degree. Cooper proved (see Soare [23]( p. 337) that this is not so by constructing a high degree a such that every b < a bounds a minimal pair. No proof of this result has appeared and we do not know how Cooper proceeded. We supply a proof of a somewhat stronger result:

Theorem 1.1: There is a high degree a such that for every b < a, there is a minimal pair c, d such that c ∨ d = b.

1 A High Strongly Bounding Degree

Our first theorem concerns bounding minimal pairs:

Theorem 1.1 . There exists a high r.e. degree a such that any nonrecursive r.e. degree w ≤ a is the join of a minimal pair, i.e. if 0 < w ≤ a then there are r.e. degrees b_{0}, b_{1} > 0 with b_{0} ∩ b_{1} = 0 and b_{0} ∪ b_{1} = w.

Proof: We build an r.e. set A and a p.r. functional Λ.

We make A high by meeting the requirements

H_{x} : lim_{s} Λ^{A}(x, s) = Inf(x),

where Inf = {x | |W_{x}| infinite} is the canonical Π_{2}-complete set.

In order to ensure that deg A only bounds joins of minimal pairs, we build, for each r.e. set W and p.r. functional Φ, two r.e. sets B_{0} and B_{1} and a p.r. functional Δ (all depending on W and Φ) meeting the requirement

R_{W,Φ} : Φ^{A} = W → B_{0}, B_{1} ≤_{T} W and Δ^{B_{0}⊕B_{1}} = W,

and the subrequirements

N_{W,Φ,Ψ} : Φ^{A} = W and Ψ^{B_{0}} = Ψ^{B_{1}} total → Ψ^{B_{0}} ≤_{T} ∅ or W ≤_{T} ∅

for each p.r. functional Ψ, and

P_{W,Φ,i,e} : Φ^{A} = W and B_{i} = {e} → W ≤_{T} ∅

for each i ≤ 1 and each e ∈ ω. (The reductions B_{0}, B_{1} ≤_{T} W will be given by permitting, and we will therefore not name them.) The requirement R_{W,Φ} thus ensures that if Φ^{A} = W then W ≡_{T} B_{0} ⊕ B_{1}; and the N - and Psubrequirements ensure that if W is also nonrecursive then the degrees of B_{0} and B_{1} form a minimal pair.

The basic strategy for a highness requirement H_{x} is to enumerate the r.e. set W_{x} and keep defining Λ^{A}(x, s) = 0 for larger and larger s with some big use λ(x, s). Whenever a new number appears in W_{x} at stage s, say, then for each s′ ≤ s, we enumerate the current use λ(x, s′) into A (if currently Λ^{A}(x, s′) ↓= 0) and redefine Λ^{A}(x, s′) = 1 with use −1, i.e. the axiom defining Λ^{A}(x, s′) does not depend on A. As long as the strategy is prevented from redefining Λ^{A}(x, s′) from 0 to 1 at most finitely often, it will clearly ensure the requirement. Since the construction, as usual for 0′′′- priority arguments, uses a tree of strategies, we have a whole level of this tree reserved for defining Λ^{A}(x, −) for a fixed x, and we will have to coordinate these strategies to make the definition of Λ^{A} uniform in x.

The strategy for R_{W,Φ} consists in a node α on the tree measuring the length of agreement

ℓ_{s}(α) = max{x | ∀y < x(Φ^{A}(y)[s] ↓= W_{s}(y))}.

α imposes an implicit A s-restraint (via initialization) at any α-expan-sionary stage s. At every α-expansionary stage s, for all y < ℓ_{s}(α), α enumerates the use of Δ^{B_{0}⊕B_{1}}(y) into B_{0} or B_{1} if Δ^{B_{0}⊕B_{1}}(y) ↓≠ W (y) and then (re)defines Δ^{B_{0}⊕B_{1}}(y) = W (y) (with big use if Δ^{B_{0}⊕B_{1}}(y) was never before defined). The reductions B_{0}, B_{1} ≤_{T} W will be ensured by permitting on αexpansionary stages (i.e. we allow B_{i}(x) to change only if W x has changed since the last α-expansionary stage).

Below the infinite outcome of an R_{W,Φ}-strategy α (guessing that Φ^{A} = W), we have N_{W,Φ,Ψ}-strategies and P_{W,Φ,i,e}-strategies. An N_{W,Φ,Ψ}-strategy β will measure the length of agreement

ℓ_{s}(β) = max {x | ∀y < x(Ψ^{B_{0}}(y)[s] ↓= Ψ^{B_{1}}(y)[s] ↓ and
∀i ≤ 1(Φ^{A} (ψ^{B_{i}}(y) + 1)[s] ↓) }

and, at each β-expansionary stage, impose restraint to preserve either Ψ^{B_{0}} ℓ_{s}(β) or Ψ^{B_{1}} ℓ_{s}(β) until the next β-expansionary stage. A P_{W,Φ,i,e}-strategy γ (in isolation) will pick a witness z_{0} targeted for B_{i} and wait for z_{0} to become realized (i.e. {e}(z_{0}) ↓= 0). Once z_{j} is realized, γ picks a new larger witness z_{j+1} and repeats the process. If, at any α-expansionary stage (not just at a γ-stage), a realized witness z_{j} is permitted by W then z_{j} is enumerated into B_{i} and P_{W,Φ,e,i} is satisfied forever. If there are infinitely many realized witnesses but none is W -permitted then W is recursive (by the usual permitting argument), representing a global win for requirement R_{W,Φ}.

We next analyze the interaction between strategies. First, let us assume that α ⊂ γ_{0} < γ_{1}, where α is an R_{W,Φ}-strategy and γ_{i} a P_{W,Φ,i,e}-strategy (for i ≤ 1). (Note that γ_{0} and γ_{1} will assume the infinite outcome of α.) On the one hand, we have to ensure that γ_{1}’s action does not interfere with γ_{0}’s. On the other hand, if γ_{0}’s action is infinitary, i.e. if γ_{0} has infinitely many realized witnesses but none is W -permitted then γ_{1} may be initialized infinitely often. Furthermore, if γ_{0} can determine that Φ^{A} is partial then again it can initialize γ_{1} infinitely often. We thus agree that γ_{0} initializes γ_{1} whenever (i) γ_{0}’s most recent witness z_{j}^{0}, say, becomes realized and γ_{0} thus picks a new witness z_{j+1}^{0}; or (ii) for some witness z_{j}^{0}, say, of γ_{0}, either Φ^{A} z_{j}^{0}[s_{0}] ↓ fails or A (φ(z_{j}^{0} − 1) + 1)[s_{0}] ≠ A_{s} (φ_{s_{0}}(z_{j}^{0} − 1) + 1) holds for the greatest α-expansionary stage s_{0} < s (this initialization may be performed at any α-expansionary stage); or (iii) γ_{0} enumerates a witness into B_{0}; or (iv) γ_{0} <_{L} γ_{1} and γ_{0} currently appears to be on the true path.

Note that (iii)-(iv) are as usual in tree constructions but that (i) and (ii) reflect that γ_{0} believes W to be recursive or Φ^{A} to be partial, respectively, and so the initialization for (i)-(ii) only affects strategies ⊃ α working for the same pair (W, Φ) and can occur at any α-expansionary stage. (We call this initialization (W, Φ)-initialization.)

We next analyze the possible injury to an N_{W,Φ,Ψ}-strategy β (below an R_{W,Φ}-strategy α). By the last conjunct of the definition of ℓ_{s}(β), any W (y)- change (for y ≤ max{ψ^{B_{i}}(ℓ(β) − 1)[s] | i ≤ 1}) after a β-expansionary stage s must be preceded by an A (φ(y)[s] + 1)-change, necessarily caused by an H_{x}-strategy ε. No ε ⊂ β will put numbers ≤ s into A unless β is initialized. No ε >_{L} β^{∧}⟨0⟩ (where 0 denotes the infinite outcome of β) will put numbers ≤ s into A by initialization at s. And finally, any ε ⊇ β^{∧}⟨0⟩ can only act at a β-expansionary stage s. So assume that enumeration by some ε ⊇ β^{∧}⟨0⟩ allows Ψ^{B_{i}} ℓ_{s}(β) (for some i ≤ 1) to be destroyed at some (least) α-expansionary stage s′ > s. We distinguish two cases at this stage s′.

Case A: Some P_{W,Φ,i,e}-strategy γ ⊃ α has a realized W -permitted witness z, which it enumerates into B_{i} at s′: Then any P_{W,Φ,i′,e′}-strategy γ′ > γ will be initialized at s′. Also, all witnesses z′ of P_{W,Φ,i′,e′}-strategies γ′ < γ satisfy φ(z′) < least A-change at s. Thus no more numbers ≤ s can enter B_{0} or B_{1} via a P_{W,Φ,i′,e′}-strategy γ′ until the next β-expansionary stage unless β is initialized. Furthermore, at any α-expansionary stage > s′ before the next β-expansionary stage, we allow β to initialize all P_{W,Φ,i′,e′}-strategies γ′ >_{L} β^{∧}⟨0⟩ whenever A (φ_{s}(s − 1) + 1) has changed. This ensures that, whenever W s change, γ is the lowest-priority active P_{W,Φ,i′,e′}-strategy and thus ensures Δ^{B_{0}⊕B_{1}}-correction via B_{i} (rather than B_{1−i}, which could destroy Ψ^{B_{1−i}} ℓ(β)[s]).

Case B: α corrects Δ^{B_{0}⊕B_{1}} via B_{i} at stage s′: Let γ ⊇ β^{∧}⟨0⟩ be the lowest-priority P_{W,Φ,i,e}-strategy active at s′. By the same argument as in Case A, no P_{W,Φ,i′,e′}-strategy γ′ < γ can enumerate a number until the next β-expansionary stage, and again we allow β to initialize P_{W,Φ,i′,e′}-strategies γ′ >_{L} β^{∧}⟨0⟩. So γ again ensures that we never enumerate a number ≤ s into B_{1−i} until the next β-expansionary stage. (Note that this additional (W, Φ)-initialization occurs infinitely often only if β^{∧}⟨0⟩ is on the true path or if Φ^{A} is partial.)

We now describe the construction formally.

2 The Construction for Theorem 1.1

We fix an effective ω-ordering of all requirements H_{x} and R_{W,Φ} and subrequirements N_{W,Φ,Ψ} and P_{W,Φ,i,e} such that each R_{W,Φ} precedes all its subrequirements N_{W,Φ,Ψ} and P_{W,Φ,i,e}.

Our tree of strategies T will be a subtree of the full binary tree 2^{<ω} (where 0 and 1 will denote infinite and finite outcome, respectively). To each strategy ξ ∈ T, we assign the highest-priority requirement that has not been assigned to any strategy η ⊂ ξ, with the following two provisos:

(i) We never assign subrequirements N_{W,Φ,Ψ} or P_{W,Φ,i,e} to strategies ξ ⊇ η^{∧}⟨1⟩ where η is an R_{W,Φ}-strategy. (ξ guesses that η has satisfied the overall (W, Φ)-requirement by showing Φ^{A} ≠ W.)

(ii) We never assign any (sub)requirement to strategies ξ ⊇ η^{∧}⟨0⟩ where η is a P_{W,Φ,i,e}-strategy. (We allow a P-strategy to have only the finite outcome since it enumerates at most one number unless initialized again.)

If (sub)requirement R is assigned to a strategy ξ ∈ T, we call ξ an Rstrategy. A (W, Φ)-strategy is an R_{W,Φ}-, N_{W,Φ,Ψ}-, or P_{W,Φ,i,e}-strategy for the pair (W, Φ).

The construction builds two global objects, the r.e. set A and the p.r. functional Λ (to show highness). Each R_{W,Φ}-strategy ξ ∈ T builds r.e. sets B_{0}, B_{1} and a p.r. functional Δ. (We normally suppress the index ξ on these functionals.) A strategy is initialized by making undefined all its parameters and, in the case of an R_{W,Φ}-strategy, its sets and functional. A parameter is defined big by setting it to a value greater than any number mentioned thus far in the construction.

The construction proceeds in stages s, each of which is divided into substages t < s, with some additional action at the end of stage s, i.e. after the last substage. Within stage s of the construction, we use symbols with no stage identification such as A to denote the value of the appropriate object, e.g. A_{s}, at stage s. At each stage, we define a string δ_{s} of strategies ξ ⊆ δ_{s} eligible to act at that stage, where ξ is eligible to act at substage t = |ξ| of stage s. At stage s, we define a stage s_{ξ} = s_{ξ}[s] as the least stage s′ ≤ s such that ξ ⊆ δ_{s′} and ξ has not been initialized since (substage |ξ| of) stage s′.

At stage 0, we initialize all strategies and let A be empty and Λ totally undefined.

At substage t of stage s + 1, a strategy ξ ⊆ δ_{s+1} of length t is eligible to act. We distinguish cases by the requirement assigned to ξ. (All parameters are measured at the current substage and do not change unless otherwise specified.)

Case 1: ξ is an H_{x}-strategy: Let s_{0} be the greatest stage t ≤ s such that ξ ⊆ δ_{s_{0}} and ξ has not been initialized since t. (If there is no such stage t, set s_{0} = s + 1). If W_{x,s_{0}} = W_{x,s+1} then we set Λ^{A}(x, s′) = 0 (for all s′ ≤ s for which Λ^{A}(x, s′) is currently undefined) with previous use λ(x, s′) (if Λ^{A}(x, s′) has been defined before) or with big use λ(x, s′) (otherwise), and we let ξ^{∧}⟨1⟩ be eligible to act next. Otherwise, i.e. if W_{x,s_{0}} ≠ W_{x,s+1}, we enumerate λ(x, s′) into A for all s′ ≥ s_{ξ} such that currently Λ^{A}(x, s′) ↓= 0. Then we define Λ^{A}(x, s′) = 1 with use −1 for all s′ ≤ s for which Λ^{A}(x, s′) is now undefined, let any R_{W,Φ}-strategy α with α^{∧}⟨0⟩ ⊆ ξ perform additional (W, Φ)-initialization (as defined in Case 2 if (ii) or (iii) of Case 2 holds), and let ξ^{∧}⟨0⟩ be eligible to act next.

Case 2: ξ is an R_{W,Φ}-strategy: We define the length of agreement by

ℓ(ξ) = max{x | ∀y < x(Φ^{A}(y) ↓= W (y))} .

We call s + 1 ξ-expansionary if ξ ⊆ δ_{s+1} and ℓ_{s′}(ξ) < ℓ(ξ) for all s′ ≤ s with ξ ⊆ δ_{s′}. The strategy eligible to act next is ξ^{∧}⟨0⟩ if s + 1 is ξ-expansionary and ξ^{∧}⟨1⟩ otherwise.

If s + 1 is ξ-expansionary then let s_{0} be the greatest ξ-expansionary stage ≤ s and check if there is a (W, Φ)-strategy η ⊇ ξ^{∧}⟨0⟩ (with a witness z if η is a P-strategy) such that

(i) z is realized and W z ≠ W_{s_{0}} z; or

(ii) Φ^{A} z[s_{0}] ↓ fails or A (φ_{s_{0}}(z − 1) + 1) ≠ A (φ(z − 1) + 1)[s_{0}]; or

(iii) η is an N_{W,Φ,−}-strategy and for the greatest η-expansionary stage s′ ≤ s,

Φ^{A} s′[s_{0}] ↓ fails or A (φ_{s_{0}}(s′ − 1) + 1) ≠ A (φ(s′ − 1) + 1)[s_{0}].

For the highest-priority such η and the least such z (if they exist), enumerate z into B (in case (i)) and initialize all (W, Φ)-strategies ≥ η^{∧}⟨1⟩ (in cases (ii)-(iii)) we call this action (W, Φ)-initialization. (The further definition of Δ^{B_{0}⊕B_{1}} is delayed until the end of stage s + 1 to allow strategies ⊇ ξ^{∧}⟨0⟩ to influence whether B_{0}- or B_{1}-enumeration is used for Δ-correction.)

Case 3: ξ is an N_{W,Φ,Ψ}-strategy: We define the length of agreement by

ℓ(ξ) = max {x | ∀y < x(Ψ^{B_{0}}(y) ↓= Ψ^{B_{1}}(y) ↓ and
∀i ≤ 1(Φ^{A} (ψ^{B_{i}}(y) + 1) ↓) }

The notions of ξ-expansionary stage and strategy eligible to act next are defined analogously to Case 1. (The definition of the recursive function describing Ψ^{B_{0}} = Ψ^{B_{1}} is implicit as in the usual minimal pair argument.)

Case 4: ξ is a P_{W,Φ,i,e}-strategy: (Note that ξ may have acted before at this stage via Case 2 for the R_{W,Φ}-strategy ⊂ ξ.) At the beginning of the substage, ξ has a (possibly empty) sequence of witnesses z_{0}, z_{1}, …, z_{n}. We proceed according to the first applicable subcase. (In each subcase, ξ^{∧}⟨1⟩ is eligible to act next.)

Subcase 4a: ξ has a witness z_{j} ∈ B_{i}: Do nothing.

Subcase 4b: z_{n} is not realized and {e}(z_{n}) ↓= 0 (or n = −1): Then z_{n} becomes realized (if n ≥ 0), and we pick a new big unrealized witness z_{n+1} and initialize all (W, Φ)-strategies > ξ.

Subcase 4c: Otherwise: Do nothing.

At the end of substage t, we end the stage if t = s, or let the strategy eligible to act next act at substage t + 1.

At the end of the stage, i.e. after substage s, we initialize all strategies > δ_{s+1} and correct and further define Δ_{α}^{B_{0}⊕B_{1}} for each R_{W,Φ}-strategy α with α^{∧}⟨0⟩ ⊆ δ_{s+1}. For each such α, first check if currently Δ^{B_{0}⊕B_{1}}(y) ↓≠ W (y) for some y. If so then enumerate δ(y) into B_{i_{0}} for the least such y (where i_{0} is chosen such that the lowest-priority P_{W,Φ,i,e}-strategy that has not been initialized at stage s + 1 satisfies i = i_{0} or, if this strategy does not exist, i_{0} = 0). Then, for each y < ℓ(α) for which Δ^{B_{0}⊕B_{1}}(y) is now undefined, define Δ^{B_{0}⊕B_{1}}(y) = W (y) with previous use δ(y) (if any) or big use (otherwise).

This ends the description of the construction.

3 The Verification for Theorem 1.1

We define the true path f ∈ [T] of the construction inductively by

f(n) = μk ≤ 1((f n)^{∧}⟨k⟩ is eligible to act infinitely often).

We first prove some easy facts about the true path:

Lemma 3.1 (True Path Lemma). (i) The true path f is well-defined.

(ii) Any strategy ξ ⊂ f is initialized at most finitely often and thus s_{ξ} = lim_{s} s_{ξ}[s] < ∞ (for s_{ξ} as defined at the beginning of the construction), except that if ξ is an N_{W,Φ,Ψ}- or P_{W,Φ,i,e}-strategy then ξ is possibly initialized infinitely often by the (W, Φ)-initialization.

Proof. (i) Clear since lim_{s} |δ_{s}| = ∞ and T is finite-branching.

(ii) We proceed by induction on |ξ|. Once no η ⊂ ξ is initialized (except for (W, Φ)-initialization), ξ can be initialized only if δ_{s} < ξ, which, by the definition of f, can happen at most finitely often (except for

(W, Φ)-initialization).

We next turn to the highness requirements.

Lemma 3.2 (Highness Lemma). For all x, lim_{s} Λ^{A}(x, s) = Inf(x), and thus A is high.

Proof. Fix x and the H_{x}-Strategy ε ⊂ f.

Since the use of Λ^{A}(x, s) is never increased and Λ^{A}(x, s) is eventually (re)defined by ε whenever necessary, Λ^{A} is clearly total.

First assume that W_{x} is finite, and fix s_{0} ≥ s_{ε} such that ε ⊆ δ_{s_{0}} and W_{x,s_{0}} = W_{x}. Then no definitions Λ^{A}(x, s) = 1 are made by any H_{x}-strategy after stage s_{0}.

Now assume W_{x} to be infinite. Then, by the construction, Λ^{A}(x, s) = 1 for all s ≥ s_{ε} with use −1.

We need one more fact about the action of the H_{x}-strategies:

Lemma 3.3 (H_{x}-Strategy Lemma). If ϵ^{∧}⟨0⟩ ⊆ δ_{s} for an H_{x}-strategy ϵ then no numbers ≤ s are enumerated by any H_{x}-strategy at a stage s′ > s unless ϵ is initialized by stage s′.

Proof. Suppose some H_{x}-strategy ϵ′ enumerates a number ≤ s at a stage s′ > s. If ϵ′ <_{L} ϵ then ϵ is initialized at stage s′. If ϵ′ >_{L} ϵ then s_{ϵ′}[s′] > s, so ϵ′ cannot enumerate numbers ≤ s after stage s (since λ(x, s′′) ≥ s′′). Finally, for ϵ′ =?, we observe that s_{ϵ}[s] ≤ s_{ϵ}[s′] for all s′ > s, so any number ≤ s that ϵ would enumerate after stage s has already been enumerated by stage s.

We now begin verifying the (W, Φ)-requirements:

Lemma 3.4 (R_{W,Φ}-Satisfaction Lemma). If Φ^{A} = W then W ≡_{T} B_{0} ⊕ B_{1}, and furthermore α^{∧}⟨0⟩ ⊂ f for the R_{W,Φ}-strategy α ⊂ f.

Proof. Fix the R_{W,Φ}-strategy α ⊂ f. Since Φ^{A} = W there are infinitely many α-expansionary stages, so α^{∧}⟨0⟩ ⊂ f.

Now B_{0}, B_{1} ≤_{T} W is immediate by permitting on α-expansionary stages. W = Δ^{B_{0}⊕B_{1}} follows since the use of Δ^{B_{0}⊕B_{1}}(y) is never increased and since Δ^{B_{0}⊕B_{1}}(y) is eventually corrected and (re)defined by α whenever necessary.

By Lemma 3.4, if Φ^{A} = W then all subrequirements N_{W,Φ,Ψ} and P_{W,Φ,i,e} are assigned to strategies ⊂ f. We now prove a fact about (W, Φ)-initialization.

Lemma 3.5 ((W, Φ)-Initialization Lemma). Suppose Φ^{A} = W and W is not recursive. Then every N_{W,Φ,Ψ}- or P_{W,Φ,i,e}-strategy ξ < f is initialized at most finitely often.

Proof. Fix an N_{W,Φ,Ψ}- or P_{W,Φ,i,e}-strategy ξ < f and assume it is initialized infinitely often. Let η be the longest common substring of ξ and f, and suppose that we have chosen ξ so that |η| is minimal. By Lemma 3.1(ii) and the construction, ξ must be initialized infinitely often by (W, Φ)-initialization; and since no strategy <_{L} f is eligible to act infinitely often, some N_{W,Φ,Ψ}- or P_{W,Φ,i,e}-strategy ζ ⊂ η must cause this infinite initialization. By the minimality of |η|, we may assume that ζ is initialized at most finitely often.

Fix the stage s_{ζ} = lim_{s} s_{ζ}[s] < ∞ and the R_{W,Φ}-strategy α ⊂ ζ. We distinguish two cases:

Case 1: ζ is an N_{W,Φ,Ψ}-strategy: (W, Φ)-initialization occurs via Case 2(iii) of the construction. We distinguish two subcases.

Subcase 1a: There are infinitely many ζ-expansionary stages: Then ζ^{∧}⟨0⟩ ⊂ f and so ζ^{∧}⟨0⟩ ⊆ ξ; therefore ξ cannot be (W, Φ)-initialized via ζ.

Subcase 1b: There is a last ζ-expansionary stage s_{0}: Then Φ^{A} s_{0} is not permanently defined contradicting our hypothesis.

Case 2: ζ is a P_{W,Φ,i,e}-strategy: Recall that each time ζ (or α for ζ) (W, Φ)-initializes ξ, it does so for some (least) witness z. We distinguish two subcases:

Subcase 2a: There is a (least) witness z for which this initialization occurs infinitely often: Then this initialization for witness z must occur infinitely often via Case 2(ii) of the construction, so Φ^{A} z is not permanently defined contrary to hypothesis.

Subcase 2b: This initialization occurs for each witness at most finitely often: Then there must be infinitely many permanent witnesses for ζ, say z_{0} < z_{1} < z_{2} < …. For each z_{j}, fix the stage s_{j} ≥ s_{ζ} at which z_{j} becomes realized. (Note that necessarily each z_{j} becomes realized.) But now for each j, W_{s_{j}} z_{j} = W z_{j}, or else z_{j} ∈ B and γ will not pick new witnesses. This establishes that W is recursive contrary to hypothesis.

The final lemmas now establish the satisfaction of the (W, Φ)-subrequire-ments.

Lemma 3.6 (P_{W,Φ,i,e}-Satisfaction Lemma). If Φ^{A} = W and W is not recursive then B_{0} and B_{1} are not recursive.

Proof. We fix i and e and establish B_{i} ≠ {e}. Let γ ⊂ f be the P_{W,Φ,i,e}- strategy. By Lemma 3.5, γ is not initialized after stage s_{γ} and can act via Case 2 or via Subcase 4b of the construction at most finitely often. Thus γ has a permanent witness z_{n} such that either z_{n} ∈ B_{i} (and thus {e}(z_{n}) ↓= 0 ≠ B_{i}(z_{n})) or z_{n} is never realized (and thus {e}(z_{n}) ≠ 0 = B_{i}(z_{n})). So B_{i} ≠ {e}.

We now prove a technical fact about (W, Φ)-initialization by N -strategies and about Δ-correction that will be used to establish the satisfaction of the N -requirements.

Lemma 3.7 (Δ-Correction Lemma). Suppose Ψ^{A} = W , W is not recursive and s_{β} is the last stage at which β is initialized.

(i) Let β ⊂ f be an N_{W,Φ,Ψ}-strategy and α ⊂ β an R_{W,Φ}-strategy. Fix two consecutive β-expansionary stages s_{0} and s_{3} (with s_{β} ≤ s_{0} < s_{3}) and two consecutive α-expansionary stages s_{1} and s_{2} (with s_{0} ≤ s_{1} < s_{2} < s_{3}). Suppose that γ and γ′ are the lowest-priority P_{W,Φ,i,e}- and P_{W,Φ,i′,e′}-strategies that have not been initialized at stages s_{0} and s_{2}, respectively. Then γ ≤ γ′ (and, in particular, if γ exists then so does γ′).

(ii) If we also assume that Φ^{A} s_{0}[s_{1}] fails or A_{s_{1}} φ_{s_{1}}(s_{0} − 1) ≠ A_{s_{2}} φ_{s_{1}}(s_{0} − 1) then γ = γ′ (or, if γ does not exist then neither does γ′). Thus Δ^{B_{0}⊕B_{1}}-correction at the end of stages s_{0} and s_{2} uses the same set B_{i}.

Proof. (i) First note that γ < β^{∧}⟨1⟩ by initialization at stage s_{0}. Suppose, for the sake of a contradiction, that γ is initialized by stage s_{2}, say, at stage s′. Then β^{∧}⟨0⟩ ⊆ γ since s_{β} ≤ s_{0}. So γ must be (W, Φ)-initialized at s′ by some strategy η with β^{∧}⟨0⟩ ⊆ η < γ (again since s_{β} ≤ s_{0}). We distinguish two cases for η:

Case 1: η is an N_{W,Φ,Ψ′}-strategy: Then η^{∧}⟨1⟩ ≤ γ, and since γ was not initialized at stage s_{0}, s_{0} is not an η-expansionary stage. Let s_{4} and s_{5} be the greatest η-expansionary and α-expansionary stages < s_{0}, respectively. Since η did not initialize γ at stage s_{0} via Case 2 of the construction, Φ^{A} φ(s_{4} − 1)[s_{5}] was defined and not destroyed by the end of stage s_{0}. By Lemma 3.3 and initialization at stage s_{0}, Φ^{A} φ(s_{4} −1)[s_{5}] can then also not be destroyed by the end of stage s_{2}, contradicting η’s (W, Φ)-initialization of γ.

Case 2: η is a P_{W,Φ,i′′,e′′}-strategy: Let s_{4} be the greatest α-expansionary stage < s_{0}. Since η did not (W, Φ)-initialize γ at stage s_{0}, Φ^{A} z[s_{4}] is not destroyed by the end of stage s_{0} for every witness z of η (and η does not pick a new witness at stage s_{0}). By Lemma 3.3 and initialization at stage s_{0}, Φ^{A} z[s_{4}] can then also not be destroyed by the end of stage s_{2} (for every such z), contradicting η’s (W, Φ)-initialization of γ.

(ii) Now also assume that Φ^{A} s_{0}[s_{1}] fails or A_{s_{1}} φ_{s_{1}}(s_{0} − 1) ≠ A_{s_{2}} φ_{s_{1}}(s_{0} − 1). Suppose, for the sake of a contradiction, that γ < γ′ (or that γ′ exists but not γ). By initialization at stage s_{0} and since s_{2} < s_{3}, necessarily γ′ ≥ β^{∧}⟨1⟩. But then β (W, Φ)-initializes γ′ at stage s_{2}, a contradiction.

Lemma 3.8 (N_{W,Φ,Ψ}-Satisfaction Lemma). If Ψ^{A} = W, W is not recursive, and Ψ^{B_{0}} = Ψ^{B_{1}} is total then Ψ^{B_{0}} is recursive.

Proof. Let β ⊂ f be the N_{W,Φ,Ψ}-strategy and assume the hypotheses of the lemma. By Lemma 3.5, β is not initialized after stage s_{β}, and since there are infinitely many β-expansionary stages, we have β^{∧}⟨0⟩ ⊂ f. We establish the lemma by showing, for each β-expansionary stage s_{0} ≥ s_{β} and each stage s ≥ s_{0}:

(3.1)  Ψ^{B_{0}} ℓ(β)[s_{0}] = Ψ^{B_{0}}[s] ℓ_{s_{0}}(β) or
Ψ^{B_{1}} ℓ(β)[s_{0}] = Ψ^{B_{1}}[s] ℓ_{s_{0}}(β).

For the sake of a contradiction, suppose one of the disjuncts of (3.1) fails at a stage s_{1} and the other at a stage s_{2} where s_{0} ≤ s_{1} < s_{2} < s_{3}, and s_{0} and s_{3} are consecutive β-expansionary stages ≥ s_{β}. Let γ_{0}, γ_{1}, and γ_{2} be the lowest-priority P_{W,Φ,−,−}-strategies that are not initialized at stages s_{0}, s_{1}, and s_{2}, respectively. Since a number ≤ s_{0} enters B_{0} or B_{1} at stages s_{1} and s_{2}, there must be a W s_{0}-change and thus an A φ(s_{0} − 1)-change before these stages. By Lemma 3.7, we have γ_{0} = γ_{1} = γ_{2}. Thus at stages s_{1} and s_{2}, either the P_{W,Φ,i,e}-strategy γ_{0} enumerates a number into B_{i} or causes the R_{W,Φ}-strategy α ⊂ β to correct Δ^{B_{0}⊕B_{1}} via B_{i}. This contradicts our assumption that both disjuncts of (3.1) are destroyed at the end of stage s_{2}.

Lemmas 3.2, 3.4, 3.6, and 3.8 now establish Theorem 1.1.

4 A High_{2} Nonbounding Degree

In the next section we shall develop machinery that allows us to construct properly high_{2} degrees with prescribed properties. In our constructions we shall look only at properties can be possessed by high_{2} but cannot be possessed by high degrees. In this section, we review the nonbounding theorem of Lachlan [13] as presented in Soare [22] and [23].

Theorem 4.1 . There is a high_{2} recursively enumerable degree c that bounds no minimal pair.

Proof. Since the construction of a nonbounding degree is a very well analyzed and documented result, we shall assume that the reader is familiar with the account of Soare [23](pp. 315-337) and will therefore only give the reader a gentle reminder, concentrating on the new ideas needed to make C high_{2}. To this end, we remind the reader that to make C nonbounding we will meet requirements of the form

R_{e} : Φ_{e}^{C} = A_{e} ∧ Ψ_{e}^{C} = B_{e} →
[A_{e} recursive ∨ B_{e} recursive ∨ (D_{e} ≤_{T} A_{e}, B_{e} ∧ (∀j)(R_{e,j}))],

where

R_{e,j} : D_{e} ≠ \overline{W_{j}}.

Here we are building C and D_{e} and our opponent is playing Φ_{e}, Ψ_{e}, A_{e}, B_{e}, and W_{j}. The reader should recall that we regard functionals as controlling enumerations of sets in the sense that if (e.g.) Φ_{e}^{C}(x) = A_{e}(x)[s] then we will not allow A_{e}(x) to change unless C changes below the use, ϕ_{e}(x)[s].

Dropping the subscripts, Lachlan’s basic strategy for the R above was the following: associated with R_{e,j} are three parameters, restraints r_{1} and r_{2} and a current candidate x.

Step 1. Wait for an s with x ∈ W_{j}[s]. At stage s + 1 open an A-gap by setting r_{1}[s + 1] = 0.

Step 2. Wait till the least t ≥ s + 1 such that l^{Φ}[t] > s, where l denotes the relevant length of agreement. At stage t + 1 close the A-gap and perform one of the following.

Step 2a. (Successful Closure.) A[s] x ≠ A[t] x. Open a B-gap by defining r_{2}[t + 1] = 0, keeping r_{1} = 0.

Step 2b. (Unsuccessful Closure.) A[s] x = A[t] x. Define r_{1}[t + 1] = t+1 (preserving A[t] x), reset x to be a big fresh number, and go to Step 1.

Step 3. Wait for the least v ≥ t + 1 such that l^{Ψ}[v] > x. At stage v + 1 close the B-gap via 3a or 3b below. Step 3a. (Successful Closure.) B[v] x ≠ B[t] x. Enumerate x into D and stop.

Step 3b. (Unsuccessful Closure.) B[v] x = B[t] x. Define r_{2}[v + 1] = v + 1, reset x, and go to Step 1.

The reader should recall that the outcomes of the basic module above are

S = {s, g2, g1, w}.

Here s denotes the outcome that we get to the successful closure of a B-gap, g2 denotes the outcome that we cycle through step 3b infinitely often (and hence B is recursive and the collective liminf of the restraints r_{1}, r_{2} is zero), g1 denotes the outcome that we only finitely often cycle through 3b but we infinitely often cycle through 2b (and hence A is recursive and the liminf of r_{1}, r_{2} is the limit of r_{1}), and, finally, w denotes the outcome that we get stuck waiting for something to happen forever. Note that s and w are finite outcomes.

The above plan is implemented on a tree of strategies, with nodes τ devoted to the global action of building D and the reductions from A and B to D for R_{e}. These are called top nodes. Below such nodes are nodes α devoted to the subrequirements R_{e,i}. We write e(α) = e, i(α) = i. Such an α will have outcomes s, g2, g1, w from left to right. Below the outcomes g2 and g1 we will have no nodes η with e(η) = e since these outcomes represent a global win for R_{e}. Furthermore, below such outcomes we will have new (top node) versions of any R_{k} with k > e, this being the so-called “finite injury on the true path” feature. In the construction, whenever we open an α-gap we create a link from τ to α. The next time we hit τ we will travel the link directly from τ to α and see how to resolve the gap at α. We will either play outcome g1 or open a B-gap depending on whether we play, respectively, Step 2b or 2a. In the former case, we remove the link, but in the latter case we do not. If we open a B-gap then we again travel the link at the next τstage. We then remove the link either playing g2 or putting x into D as with the basic module. Note that if τ is the final version of a top node devoted to e on the true path (T P), then below τ every gap opened is closed and hence D_{τ} ≤_{T} A_{e}, B_{e}. Since this is all just a reminder we refer the reader to Soare [23] for more details.

5 Making C High_{2}.

Now we turn to the problem of making C high_{2}. To this end, we shall define a C-recursive function Λ so that for all x, we meet the requirements

H_{x} : lim_{s} lim_{t} Λ(C; x, m, t) = Cof(x).

where Cof = {x|W_{x} is cofinite} is the canonical Σ_{3}^{0}-complete set. For the sake of this requirement we will have nodes β (= β(x, m)), which test if [m, ∞) ⊆ W_{x}. Note that this is a Π_{2} test. Such nodes have outcomes ∞, f. The ∞ outcome corresponds to the Π_{2} node infinitely often looking correct. The other one is the finite outcome. Now β is responsible for defining Λ(C; x, m, t) for each t. However, the reader should note that we need some care since Λ must be C-recursive and this cannot depend on knowledge of which version of β lies on T P. This problem makes us use a whole level of nodes to collectively define Λ(C; x, m, t). We may assume that we initially define Λ(C; x, m, t)[s] = 0, and that Cof will only ask us to redefine this to 1. The fact that we are dealing with double limits allows us to be wrong on a finite number of m. This fact will be the key to getting the coding to work, and is where the argument differs from making C high, which we know is impossible.

The basic idea is that when we hit β, we will redefine all values of Λ(C; x, m, t) for t ≤ s in accordance with the current picture, provided that such actions are not prohibited by higher priority restraints. The point is that to redefine a value of Λ(C; x, m, t) we will need C-enumeration. Hence, at the beginning, when we first set Λ(C; x, m, t) = 0, we will also define a number λ(x, m, t) which we will use to revise the value of Λ(C; x, m, t) should this be necessary. In fact these λ’s can be defined at the beginning of the construction. Note that all nodes devoted to H_{x} want to enumerate the same λ’s (to correct Λ as needed); however whether a particular node actually succeeds will depend upon its priority. Hence if we get to β and we see that, since we have defined λ(x, m, t), the relevant Π_{2} condition saying that x appears in Cof with witness m′ ≤ m has again appeared to hold, we will enumerate λ(x, m, t) into C to allow us to change Λ(C; x, m, t) to be 1. We will do this unless, of course, we are restrained by requirements of higher priority.

We will describe how the construction lives with this idea and what modifications we need to make to the priority tree as a consequence. First, we consider the situation where we have H_{x} of lower priority than R_{e} (which is associated with τ). In the tree architecture we will, of course, have no β’s devoted to H_{x} above τ, although they can be to the right or left of τ. The problem is the following. Suppose we have a situation with nodes τ ⊂ β ⊂ σ where e(τ) = e(σ) = e and τ is σ’s top node. Thus, while σ has higher global priority that β, its local priority is lower. Now, suppose at some stage we open a σ-gap for the sake of candidate z, creating a link from τ to σ at stage s_{0}. At a later stage s_{1} we again get to τ and we wish to travel the link and perhaps to close the gap and preserve A. This causes no problem if σ extends β^{∧}f but there are problems if σ extends β^{∧}∞. The crucial fact needed in the verification is that between gaps no new numbers enter C and so A is recursive since we know it does not change during gaps and, by restraints, does not change between gaps either. Now, when we open the A-gap at σ, we certainly ask that the l[s] > x via σ-correct computations. After all, σ is guessing the Π_{2} outcome ∞ for β and will therefore expect that all the relevant changes below the use needed to make Λ(C; x, m, t) output 1 have occurred. (I.e. we will have put the relevant λ(x, m, t) into C[s_{0}].)

The trouble is that when we next get to τ to travel the link, numbers may have entered C changing the C-use for (e.g.) Φ^{C}(z)[s_{1}]. Now, it might be that Φ^{C}(z)[s_{1}] is no longer σ-correct. For instance, some λ = λ(x, m, q) that we have set aside to change C if we wish to again play β^{∧}∞ may now be less than ϕ^{C}(z)[s_{1}]. The trouble is that when we get to τ we may not yet wish to put λ into C since the Σ_{2} outcome may be looking correct at β. Now, if we close the gap at σ then since β has higher priority than σ, any restraint imposed at stage s_{1} may not be successful since β might later put λ into C. The reader should note that this is precisely the problem that occurs if we try to make C high, and it cannot be overcome in that case.

In our case, we overcome this dilemma as follows. When we hit τ, if we see some λ as above we preempt β by immediately enumerating any λ below the C-use of σ’s current candidate z into C. This means that β cannot later use λ to injure σ. Of course, if there are no such λ around then we would travel the link and act as in the basic Lachlan construction since any restraint we impose will actually succeed provided that σ is on the true path. This is the condition we would like to achieve, but failing that, we’d like to get a global win on R_{e}. Assuming that such a λ exists, what we do is travel the link from τ to σ, but we do not delete the link. Because of this, we now need to add two new outcomes to σ. These are denoted by u1 and u2. Hence, the outcomes of a σ node are now

S = {s, g2, u2, g1, u1, w}.

The new outcomes correspond to the outcome that one of Φ or Ψ has unbounded use on some fixed z. Outcome ui corresponds to gi. If we are in an A-gap when we hit σ and we perform the capricious enumeration of λ indicated above then we will play the outcome u1. We act similarly for u2 and a B-gap. Note that if we get to some z which always has some λ below its C-use, then the net effect will be that τ will define Λ(C; x, m, t) to have limit 1 for a fixed finite set of x and m. Furthermore, for almost all stages there will be a link from τ to σ. This will correspond, however, to a global win for R_{e} since σ is drawing attention to the fact that one of Φ^{C}(z) ↑ or Ψ^{C}(z) ↑ holds. As with the other infinitary outcomes g1, g2, below u2, u1 we will restart all requirements of lower priority than τ, using the list method presented in Soare [23]. The reader should note that we do not restart β since Λ(C; x, m, t) is going to be defined to be 1 for the (finitely many) relevant x and m. The cost of this to H_{x} is that for a finite number of m, lim_{t} Λ(C; x, m, t) may be incorrectly outputting 1 instead of 0. This is, of course, fine provided that we only lose on a finite number of the m. The idea is that we will only lose on an m if we can eliminate one of the requirements of globally higher priority. In this way, we will be certain that we get a loss on only finitely many m’s.

We will employ the following technique from Downey-Stob [7]. When we hit τ, we realize that if there is a link from τ down then this may be a potentially permanent link. To make the combinatorics easier, instead of directly going to σ, we first do a scouting report to see where we would go if there were no link around. If we were to go to a node γ to the left of σ then we will erase the link cancelling z and actually go to γ instead. This technique ensures that the node of highest priority that ever wishes to be visited will be.

The reader should note that if β is on the true path, then either β will be linked over for almost all stages, or we will actually visit β infinitely often. In the latter case, since links from τ′ to σ′ are created at bottom nodes, if β is genuinely on the true path – and not permanently linked over – then its outcome must actually reflect its true nature.

To complete the description of the construction we only need to describe the situation where we are dealing with an H_{x} of higher priority than the R_{e} associated with τ. Suppose we are below τ and τ has so far been below the Σ_{2} outcomes of β’s devoted to x. Suppose further that we have a node β devoted to H_{x} below τ. Then below β^{∧}∞, the Π_{2} outcome of β, we will restart τ in the same way as we do in the case of other global wins.

Thus we can suppose we are looking at the final version of τ and it is below β^{∧}∞. Again, we need to consider some σ, a subrequirement of τ, interacting with β as above as well as a γ also devoted to H_{x} but now with γ between τ and σ. Note that γ only has one outcome: ∞. This is because, if γ is below β^{∧}∞ then γ must agree with β; they do, after all, pertain to the same x. Now the argument is easier, since when we hit τ we will be at a stage when β^{∧}∞ looks correct. Hence if there is a link from τ to σ it is perfectly okay with γ that τ enumerate any potentially injurious λ(x, m′, t) for m′ = m(γ) into C since that is what γ wants to do now anyway! If there is no link then, as in the other case, τ needs to do no C enumeration. The key point is that, in this case, τ cannot injure H_{x} because at the stages at which τ is accessible, it is only doing what H_{x} wants to do now anyway. In this way, we see that H_{x} can only be injured for finitely many m.

Hence, in either case, either we get a permanent link and so a global win on some R_{e} of higher priority, or all nodes are actually visited infinitely often. Since links are created at bottom nodes, when we genuinely visit a node its outlook is the true one; so it follows that the liminf of restraints, etc., on the true path is finite. In this way we see that all requirements are met. This concludes our discussion of Theorem 5.1.

6 Remarks.

For the reader familiar with the details of Downey-Stob [7], we make some remarks concerning the limitations on applying the techniques of the last section to make sets high_{2} when there are permanent links. In [7], Downey and Stob prove that the following holds in the r.e. degrees:

∀c ≠ 0∃a(0 < a < c ∧ ∀b ≤ c(b ≠ 0 → b ∩ a ≠ 0)).

In that construction, it is also the case that there are permanent links. However, in the construction [7], the existence of permanent links necessitated additional guessing at the bottom nodes (corresponding to σ above) as to the Π_{2} behavior of nodes intermediate between the top and bottom of the links. The reason for this was that the links emanated from the top rather than the bottom in the construction. In the general situation of permanent links or other devices that can potentially kill parts of the true path in the sense that they might only be visited finitely often (such as e.g. the tree architecture of Downey-Shore [4]), such additional Π_{2} guessing will be necessary for all Π_{2} nodes that might be jumped over. This is because we will need to guess as to whether they are truly visited or not. Thus the above technique for making a set high_{2} cannot be combined with the link mechanism of the construction [7]. The reader is referred to [7], [3], and [4] for further details.

7 Other High_{2} Applications.

The technique of Section 5 can be applied in other situations. To illustrate this, we give one further example. We shall answer a question from Downey-Stob [5], [6]. Recall from [5] that a nonrecursive r.e. set A is called hemiP if there is a nonrecursive r.e. set B disjoint from A such that A∪B has property P. So a hemimaximal set is half of a (nontrivial) splitting of a maximal set. Hemimaximal sets form an interesting orbit in the automorphism group of the lattice of r.e. sets (Downey-Stob [5]). In [5], Downey and Stob proved that all high r.e. degrees contain hemimaximal sets, and below any given nonzero r.e. degree there is one containing an r.e. hemimaximal set. On the other hand in the same paper they showed that not all r.e. degrees contain hemimaximal sets. Subsequently, Downey and Stob [6] further classified the degrees of hemimaximal sets by showing that the degrees containing hemimaximal degrees jump-invert in the sense that if a is REA(0′) then there is a hemimaximal set whose jump has degree a. They also showed that there is a low_{2}-low r.e. degree b that contains no hemimaximal r.e. set. It is therefore of some interest to resolve the question of the existence of a high_{2} degree containing no hemimaximal r.e. sets, a question left open in [6]. We solve this question here:

Theorem 7.1 . There exists a high_{2} recursively enumerable degree c that contains no hemimaximal sets.

Proof. We sketch the proof using the ideas above. We build an r.e. set C to meet the high_{2}ness requirements H_{x} of the previous theorem as well as the following:

R_{e} : (Δ_{e}(C) = V_{e} ∧ Γ_{e}(V_{e}) = C ∧ W_{e} ∩ V_{e} = ∅) → W_{e} ∪ V_{e} is not maximal.

Here we work over quadruples consisting of two functionals Δ, Γ and two disjoint r.e. sets W, V. Let V̂ = V ∪W. For the sake of these requirements, we will define collections of markers Q = \{q(e, i, s) : i ∈ ω\}, and Q̂ = \{\overline{q}(e, i, s) : i ∈ ω}. For any triple ⟨e, i, s⟩, only a finite number of elements will share the same label q(e, i, s) (\overline{q}(e, i, s), respectively). By abuse of notation if x has a marker q(e, i, s) upon it at stage s, then we will write x ∈ q(e, i, s). The idea is that the q and \overline{q} are to form disjoint sets. We will ensure that for all i, j, lim_{s} q(e, i, s) and lim_{s} \overline{q}(e, j, s) exist and are distinct. Furthermore, for all i at least one element labelled q(e, i, s) (respectively \overline{q}(e, i, s)) will be in \overline{V̂}. In this way Q and Q̂ will be r.e. sets essentially splitting \overline{V̂}. The construction can easily be altered so as to put all the numbers not put into Q̂ into Q and hence in fact guarantee that c will not even contain hemi-r-maximal r.e. sets.

Before we discuss the high_{2} version of the construction of a nonhemimaximal degree, we briefly recall the construction from [5] of a (low) nonhemimaximal degree. We split R_{e} into infinitely many subrequirements of the form

R_{e,i} : q(e, i) = lim_{s} q(e, i, s) exists ∧ ∃x(x ∈ q(e, i) ∧ x ∈ \overline{V̂}),

\overline{R_{e,i}} : \overline{q}(e, i) = lim_{s} \overline{q}(e, i, s) exists ∧ ∃x(x ∈ \overline{q}(e, i) ∧ x ∈ \overline{V̂}).

Let

l(e, s) = max{x : ∀y < x(Γ_{e}(V_{e}; y) = C ∧(∀z ≤ γ(y))(Δ_{e}(C; z) = V_{e}(z)))[s]}.

That is l(e, s) is the C-controllable length of agreement at stage s. Again we regard C as controlling V below the length of agreement, and hence once l(e, s) > x then V_{e} γ_{e}(x)[s] = V_{e,s} γ_{e}(x)[s] unless we change C δ_{e}(γ_{e}(x))[s]. We concentrate upon R_{e,i}, the \overline{R_{e,i}} being exactly the same. The idea for R_{e,i} is to wait till an e-expansionary stage s_{0}, with, say, l(e, s_{0}) = l_{0} and use δ_{e}(γ_{e}(l_{0}))[s_{0}] = d_{0}, and assign a candidate z which is large and fresh. R_{e} has now asserted control, and in particular restrains C s_{0} to preserve the current picture. We now wait till a stage s_{1} > s_{0} where l(e, s_{1}) > z. At stage s_{1}, we put a q(e, i, s_{1}) marker on all y ∈ [γ_{e}(l_{0}), γ_{e}(z)[s_{1}]], and now restrain C s_{1}. Note that we have succeeded in meeting R_{e,i} unless all q(e, i, s_{1}) enter V̂. However, if there occurs a stage where all x ∈ q(e, i, s) have entered V̂, then we can globally win R_{e} by enumerating z into C but otherwise restraining C. Assuming this restraint is successful, we have that C s_{0} = C_{s_{0}} s_{0}, and hence, in particular, we have C d_{0} = C d_{0}. This fact implies that V_{e,s_{0}} γ_{e}(l_{0})[s_{0}] = V_{e} γ_{e}(l_{0})[s_{0}]. As z enters C since l(e, s_{1}) > z, we know that V [s_{1}] must change below γ_{e}(z)[s_{1}]. But by the above, V [s_{1}] cannot change below γ_{e}(l_{0}), so it must change in the interval [γ_{e}(l_{0}), γ_{e}(z)[s_{1}]]. But such a change is impossible if V_{e} and W_{e} are to remain disjoint: we have enumerated z because [γ_{e}(l_{0}), γ_{e}(z)[s_{1}]] ⊆ V̂ and V̂ = V_{e} ∪ W_{e}.

As we will see, the ideas from the last section needed to make C high_{2} are essentially the same as those we have met for the nonbounding theorem. Again we need to resort to a strategy tree. On this tree there are two sorts of nodes associated with an R_{e}. There are τ-nodes where we measure l(e, s) and σ-nodes devoted to the requirements R_{e,i}. (The parallels with the nonbounding theorem should be obvious.) Again we have nodes β devoted to the H_{x}, for ⟨x, m⟩. The action of a β-node is exactly the same as it was in the last theorem. The action of a σ-node is the following. At a σ-stage s_{0}, which is by definition τ-expansionary, σ will seek to get a setup as above. Its action is to pick a candidate z and then set up a link from τ to σ and wait till the first τ-stage s_{1} with l(τ, s_{1}) > z. Again σ will only wish to put a q(σ, s_{1}) = q(e(σ), i(σ), s_{1}) marker on the numbers in the interval [γ(l_{0}), γ(z)[s_{1}]]. Again, we must ensure that at the stage at which we perform this action, it is safe to impose C-restraint to preserve this setup. As the gap began at a σ-stage, we see that the l(e, s_{0})-computations are σ-correct. Now if there is a β^{∧}∞ between τ and σ we see that at stage s_{1} the computations ensuring l(e, s_{1}) > z might not be β^{∧}∞-correct. So as with the nonbounding theorem our solution is to capriciously enumerate the relevant λ(x, m, t) into C to attempt to ensure β^{∧}∞-correctness for the z-computation (each time playing a u-outcome below σ) or getting a global win for R_{e}. The details now go through virtually as before.

.

References

[1] P. Cholak, “Automorphisms of the Lattice of Recursively Enumerable sets”, Ph. D. Thesis, University of Wisconsin, 1992.

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

[3] R. Downey, Notes on the 0′′′ priority method with special attention to density arguments, in: “Recursion Theory Week”, Proceedings, Oberwolfach 1989, Springer-Verlag Lecture Notes in Mathematics, 1990, pp. 111-140.

[4] R. Downey and R. Shore, Density and infima in the recursively enumerable degrees, in preparation.

[5] R. Downey and M. Stob, Automorphisms of the lattice of recursively enumerable sets: orbits, Advances in Math. 92 (1992), 237-265.

[6] R. Downey and M. Stob, Jumps of hemimaximal sets, Z. Math. Logik Grundlag. Math. 37 (1991), 113-120.

[7] R. Downey and M. Stob, Minimal pairs in lower cones, in preparation.

[8] M. Groszek and T. A. Slaman, in preparation.

[9] L. Harrington, A. H. Lachlan, W. Maass and R. I. Soare, New methods for automorphisms of the recursively enumerable sets and applications to the low_{2} sets, in preparation.

[10] L. Harrington and R. I. Soare, A solution of Post’s program; r.e. sets automorphic to complete sets; and new noninvariant jump classes of r,e, degrees, in preparation.

[11] A. H. Lachlan, Degrees of recursively enumerable sets which have no maximal supersets, J. Symbolic Logic 33 (1968), 431-443.

[12] A. H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1975), 307-365.

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

[14] D. A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlag. Math. 12 (1966), 295-310.

[15] R. W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. Math. (2) 93 (1971), 285-314.

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

[17] J. R. Shoenfield, Degrees of classes of r.e. sets, J. Symbolic Logic 41 (1976), 695-696.

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

[19] R. A. Shore and T. A. Slaman, Working below a high recursively enumerable degree, J. Symbolic Logic, to appear.

[20] R. A. Shore and T. A. Slaman, Splitting and density cannot be combined below a high recursively enumerable degree, in preparation.

[21] T. A. Slaman, The recursively enumerable degrees as a substructure of the Δ_{2}^{0} degrees, to appear.

[22] R. I. Soare, Tree arguments in recursion theory and the 0′′′ priority method, in: “Recursion Theory”, A. Nerode and R.A. Shore, editors, Proc. Symp. Pure Math., American Mathematical Society, Providence, 1985, pp. 53-106.

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