INTERVALS WITHOUT CRITICAL TRIPLES

PETER CHOLAK, ROD DOWNEY AND RICHARD SHORE

Abstract. This paper is concerned with the construction of intervals of computably enumerable degrees in which the lattice M_{5} (see Figure 1) cannot be embedded. Actually, we construct intervals I of computably enumerable degrees without any weak critical triples (this implies that M_{5} cannot be embedded in I, see Section 2). Our strongest result is that there is a low_{2} computably enumerable degree e such that there are no weak critical triples in either of the intervals [0, e] or [e, 0′].

1. Introduction

A set of natural numbers is computably (or recursively) enumerable if it is the range of a function computed by a Turing machine. We say one set of natural numbers, A, is Turing computable from another, B, if there is a Turing machine, which using an oracle for B, computes A. Equivalence classes under this reduction are called Turing degrees or just degrees. In this paper we will restrict our attention to those degrees which contain a computably enumerable set; the computably enumerable degrees.

The computably enumerable degrees form an upper semilattice, R. Despite the fact that R is not a lattice, there has been a long series of results each demonstrating larger and larger classes of lattices that could be embedded into R. Examples include the results of Lachlan [1972] and Ambos-Spies and Lerman [1989]. On the other hand, in Lachlan and Soare [1980] it is shown that not every lattice can be embedded into R. Naturally, understanding precisely which lattices can be embedded into R is central to the question of the decidability

1991 Mathematics Subject Classification. Primary 03D25. Key words and phrases. computably enumerable, critical triples, embeddings. Research partially supported by a Mathematical Sciences Postdoctoral Research

Fellowship (Cholak); ARO through MSI, Cornell University, DAAL-03-C-0027 (Cholak, Downey, Shore); a U.S.-New Zealand Binational Cooperative Research grant NSF INT 90-20558 (Cholak, Downey and Shore); IGC of Victoria University, Wellington (Downey); New Zealand Marsden Fund for Basic Science under contract number VIC-509 (Downey) and NSF Grants DMS-9204308 and DMS-9503503 (Shore).

[figure: b_{1}; b_{0}; a; 1; 0]

Figure 1. The lattice M_{5}

of the ∃∀ theory of R. For instance, in the language of {≤}, one needs to demonstrate an algorithm that will decide which lattices can be embedded into R (or the nonexistence of such an algorithm).

In the present paper, our concern is the lattice M_{5} (see Figure 1), the modular 5 element lattice and its distribution in R. In Lachlan [1972] it is shown that M_{5} is embeddable into R. However, Lachlan’s proof exhibited certain technical features such as “continuous tracing” which had not been necessary in previous lattice embedding theorems. Lachlan and Soare’s proof that S_{8} (see Figure 2) is not embeddable in some sense demonstrates that to embed M_{5} requires such features and furthermore these features can be incompatible with other lattice properties such as simultaneously controlling the infima of a pair (or more) of degrees as with a_{1} ∩ a_{2} = a_{3} in Figure 2).

These observations led Lerman to conjecture that essentially the “M_{5} phenomenon” interacting with the infima was the only blockage to embeddability. The central role of the “M_{5} phenomenon” was also demonstrated in Downey [1990] and Weinstein [1988] where it was proved that there are initial segments of R into which M_{5} cannot be embedded.

Actually, the Downey and Weinstein results were stated in terms of (weak) critical triples (see Section 2 for a definition). Critical triples is a lattice theoretic condition which reflects the need for “continuous tracing” in the construction of such a triple. These results as well as Cholak and Downey [1993] demonstrate that embedding of critical triples and the structure of R interact in very interesting ways.

Indeed, embeddings of nondistributive lattices is closely tied to the structure of R. For instance, following the work in Downey and Lempp

[figure: a_{3}; 0; a_{0}; a_{1}; 1]

Figure 2. The lattice S_{8}

[figure: 0; 1]

Figure 3. The lattice N_{5}

[n.d.], it is shown in Ambos-Spies and Fejer [1996] that the degrees which are tops of N_{5} (see Figure 3) are precisely the “noncontiguous” degrees which are not “locally distributive” in R.

We remark that recently in Lempp and Lerman [n.d.] it is shown that there are lattices without critical triples which are not embeddable into R. But despite the fact that critical triples do not completely capture the nonembeddability picture, it is obvious that their definition plays a central role in our understanding of embeddings into R.

Critical triples and nondistributive lattices also seem to have a connection with a natural operator on the Turing degrees called the jump operator. Informally the jump of a set of natural numbers X, X′, is the set of numbers e such that the eth Turing machine (under some standard indexing of all Turing machines) with an oracle for X halts with input e. We use the jump operator to define jump classes: sets of degrees which have the same nth jump for some n. For example, Low_{2} is the collection of all computably enumerable Turing degrees d whose double jump is as low as possible, i.e. d′′ ≡ 0′′.

Now in Downey and Shore [1996], it is demonstrated that if d is nonlow_{2} then one can embed M_{5} below d. The Ambos-Spies and Fejer result proves that if d is nonlow_{2} then d is the top of an N_{5}. Because of these results one is led to believe that lattice embeddings and the jump operator are deeply related.

In the back of our minds when we began this project we hoped to show that the low_{2} degrees are definable in the computably enumerable Turing degrees (in the language of partial orders) via embedding properties of M_{5}. There are techniques for working with low_{2} computably enumerable degrees [Shore and Slaman, 1991; Downey and Shore, 1995] and nonlow_{2} computably enumerable degrees [Downey and Shore, 1996]. Downey and Shore used these techniques to show that a computably enumerable tt degree d is low_{2} iff d has a minimal cover in the computably enumerable tt degrees [Downey and Shore, 1995] and hence the low_{2} computably enumerable tt degrees are definable in the computably enumerable tt degrees. Our plan was to use these techniques to show d is low_{2} iff there is a computably enumerable degree e such that the lattice M_{5} cannot be embedded into either [0, e] or [e, d].

We had reason to hope that we might be successful: Downey and Shore [1996] had recently shown that the lattice M_{5} can be embedded below any nonlow_{2} computably enumerable Turing degree and from Cholak and Downey [1993] we knew how to construct intervals of computably enumerable degrees where it is impossible to embed M_{5}. Hence, we needed to first extend the Downey and Shore result to the following: If d is nonlow_{2} and e is a low_{2} degree below d (and so d is nonlow_{2} relative to e), then the lattice M_{5} can be embedded in the interval [e, d]. And second, improve the techniques of Cholak and Downey to show that for each low_{2} degree d we could find an e such that the lattice M_{5} cannot be embedded into the intervals [0, e] and [e, d]. This would have given us a formula defining low_{2}.

However, one of our results implies that there is a computably enumerable degree e such that the lattice M_{5} cannot be embedded into either [0, e] or [e, 0′]. Thus the proposed formula does not define the low_{2} computably enumerable Turing degrees.

Before we turn to our own work we should note that Nies, Shore and Slaman [n.d.] have recently announced that the jump classes Low_{n} and High_{m} are definable, for n ≥ 2 and m ≥ 1. Their methods however, rely on coding models of arithmetic and analyzing the complexity of certain lattice like structures that can be coded below a given degree. We should also mention that there have been at least two other unsuccessful attempts to show that Low_{2} is “naturally” definable: one by Leonhardi [Leonhardi, 1994] and the other by Cooper and Yi [Cooper and Yi, n.d.]. For more of a discussion of definability and computably enumerable degrees, the reader is directed to Shore [Shore, n.d.].

The rest of this paper is concerned with the construction of intervals of computably enumerable degrees in which M_{5} cannot be embedded. Actually, we construct intervals I of computably enumerable degrees without any weak critical triples (this implies M_{5} cannot be embedded in I). The definitions of and the relationship between critical triples and weak critical triples (and the lattice M_{5}) are isolated in the next section.

The concept of a critical triple first arose implicitly in Ambos-Spies and Lerman [1986] and Ambos-Spies and Lerman [1989]. In Ambos-Spies and Lerman [1989] it is shown that a finite lattice L can be embedded into R if there is no (weak) critical triple a, b_{0} and b_{1} and no pair p and q in L such that b_{0} ≤ p ∩ q ≤ b_{0} ∪ a. The concept of a critical triple was first explicitly isolated in Downey [1990]. In Downey [1990], it is shown that there is a degree which does not bound a critical triple. In Cholak and Downey [1993], this work was extended to show that if a < b are degrees then there is a degree e such that a < e < b and there is no critical triple in the interval [a, e]. The definition of a weak critical triple first appeared in Weinstein [1988] under the name of “pre 1-3-1”. He showed that there is a degree below which there is no weak critical triple. Our results further point out the importance of critical triples and weak critical triples in our quest to know what lattices can and cannot be embedded into intervals of computably enumerable degrees.

Our results fall into two groups. The first group of results concerns degrees which do not bound a weak critical triple. We show that every degree can be split into two degrees neither of which bounds a weak critical triple. Hence, the class of degrees which fail to bound a weak critical triple generates R. We also show that there is a properly low_{2} degree with no weak critical triple below it. Therefore, the result of Downey and Shore [Downey and Shore, 1996] that the lattice M_{5} can be embedded below any non-low_{2} degree is the best possible in terms of jump classes. These results are presented in Section 4. The other group of results is presented in Section 6 and concerns degrees above which there is no weak critical triple. We show there is an incomplete degree above which there is no weak critical triple. In addition, we show there is a degree above and below which there is no weak critical triple. By the above result of Downey and Shore such a degree must be low_{2}.

There are two different types of requirements that reflect the grouping of results: There are the requirements N_{e} which ensure that there is no weak critical triple in the desired lower cone and there are requirements P_{i} which ensure that there is no weak critical triple in the desired upper cone. Each N_{e} is a negative requirement in that it restrains elements from entering the constructed set. The requirements N_{e} are presented in Section 3. Each P_{i} is an infinite positive requirement; it may add infinitely many elements into the constructed set. The requirements P_{i} are presented in Section 5. The two types of requirements and the strategies used to meet them are in a sense duals of each other.

Although demonstrating that there are no weak critical triples in some interval is stronger than the corresponding result for critical triples, it is actually easier to construct intervals of computably enumerable degrees without weak critical triples than it is to construct intervals of computably enumerable degrees without critical triples (at least, as this was done in Downey [1990] and Cholak and Downey [1993]). Fix a triple of computably enumerable degrees, a, b_{0} and b_{1} such that a ∪ b_{0} = a ∪ b_{1}. To show, as in Downey [1990] and Cholak and Downey [1993], that a, b_{0} and b_{1} is not a critical triple a computably enumerable degree d is built such that d ≤ b_{0}, b_{1} and if a ≰ b_{0} then d ≰ a. Determining whether a is Turing reducible to b_{0} is a Σ_{3} question and therefore it is not surprising that these arguments turn out to be 0′′′ arguments. To show that a, b_{0} and b_{1} is not a weak critical triple, we construct a computably enumerable degree d such that d ≤ b_{0}, b_{1} and b_{0} ≤ d ∪ a. As it turns out, this can be done by a 0′′ argument. In terms of lattice embeddings, however, the results are equivalent for, as we will see below, a lattice contains a critical triple if and only if it contains a weak critical triple.

A question we tried to answer but could not is whether the lattice M_{5} can be embedded above every low degree. For more on this issue, the reader is directed to Section 6.3. It is also open whether one can extend our result that there is an incomplete degree which does not bound a weak critical triple to show such a degree must exist above every nonlow_{2} degree.

Remark 1.1 (Notation). Our notation is standard and generally follows [Soare, 1987] with the following important exceptions: The use of a computation Φ(X_{s}; x) is denoted by φ_{s}(x) and similarly for other Greek letters. We assume the uses of all functionals not constructed by us to be nondecreasing in the stage, s, and increasing in the argument, x, for each stage. Furthermore, if the underlying set involved in a computation changes below the use of the computation at some stage s, we will assume that computation diverges at stage s. For example, if we are given Ψ and for some x and s, Ψ_{s}(X_{s}; x)↓ and X_{s} ↾ (ψ_{s}(x)+1) ≠ X_{s+1} ↾ (ψ_{s}(x)+1) then Ψ_{s+1}(X_{s+1}; x)↑. When the oracle of a functional is given as the join of sets we assume the use to be computed separately on each set. To make life easier, we will assume that X ⊕ Y ⊕ Z is defined as {3x : x ∈ X}∪{3y +1 : y ∈ Y }∪{3z +2 : z ∈ Z}. All other joins are defined normally. When we choose a large number we mean a number larger than any other number mentioned or used so far. For any of the functionals (or parameters) which we are building, we will assume that if the underlying set changes at some stage on the use (for this stage) then this functional (or parameter) is undefined at this stage unless otherwise explicitly defined. For example, if we are building Γ and for some x and s, Γ_{s}(X_{s}; x) ↓ and X_{s} ↾ (γ_{s}(x) + 1) ≠ X_{s+1} ↾ (γ_{s}(x) + 1) then unless we otherwise explicitly define Γ_{s+1}(X_{s+1}; x), Γ_{s+1}(X_{s+1}; x)↑. Otherwise, all parameters remain the same from stage to stage unless explicitly redefined. We assume the reader is familiar with 0′′ arguments as in Soare [1987].

2. Definitions and Examples

Definition 2.1. Let a, b_{0} and b_{1} be elements in any upper semilattice L (such as the Turing degrees or the computably enumerable Turing degrees). We say that a, b_{0} and b_{1} form a critical triple if a ∪ b_{0} = a ∪ b_{1}, b_{0} ≰ a and for d ∈ L, if d ≤ b_{0}, b_{1} then d ≤ a.

Definition 2.2. Let a, b_{0} and b_{1} be elements in any upper semilattice L. We say that a, b_{0} and b_{1} form a weak critical triple if a∪b_{0} = a∪b_{1}, b_{0} ≰ a and for d ∈ L, if d ≤ b_{0}, b_{1} then b_{0} ≰ d ∪ a.

Any upper semilattice in which the lattice M_{5} (for a diagram of the lattice M_{5} see Figure 1) can be embedded (as a lattice) contains a

[figure: b_{1}; b_{0}; a ∪ (b_{0} ∩ b_{1}); a; 0; 1]

Figure 4. A weak critical triple which is not a critical triple

critical triple. If a, b_{0} and b_{1} form a critical triple in some upper semilattice L then a, b_{0} and b_{1} form a weak critical triple in L. In Figure 4, a weak critical triple a, b_{0} and b_{1} is identified within a lattice. Within this lattice, a, b_{0} and b_{1} do not form a critical triple but the elements a ∪ (b_{0} ∩ b_{1}), b_{0} and b_{1} do. In fact, if a, b_{0} and b_{1} form a weak critical in an upper semilattice L and b_{0} ∩ b_{1} exists (for example, this must occur if L is a lattice), then a ∪ (b_{0} ∩ b_{1}), b_{0} and b_{1} form a critical triple in L. On the other hand, it is possible to construct an infinite upper semilattice which contains a weak critical triple but no critical triples.

As for R, it is unknown whether there exists an interval I such that there is a weak critical triple in I but I does not contain a critical triple or whether there exits an interval I such that there is a critical triple in I but M_{5} cannot be embedded into I.

3. The requirements N_{e}

Our goal is to build a computably enumerable set E such that the following requirements are met:

If Λ(E) = A ⊕ B_{0} ⊕ B_{1} and Ψ_{i}(A ⊕ B\overline{i}) = B_{i} then there exists a computably enumerable set D

N and functionals Δ_{i} and Γ such that Δ_{i}(B_{i}) = D and Γ(A ⊕ D) = B_{0}

where Λ and Ψ_{i} (i = 0, 1) are functionals and A, B_{0} and B_{1} are computably enumerable sets. These six items, the requirement, the set D and the three functionals Δ_{i} and Γ will later be indexed in some fashion by e; but for now, we will drop the e. If we meet N then either E does not bound the computably enumerable sets A, B_{0} and B_{1} or the degrees represented by these sets do not form a weak critical triple. (If B_{0} ≤_{T} A then the requirement can be easily met.)

We will need some auxiliary functions (at first it may seem that we are generating more notation than needed but we will use all these functions later in the construction):

\begin{matrix}L(s) = max\{x : & (∀y < x)(∀z ∈ \{3y, 3y + 1, 3y + 2\}) \\ [Λ_{s}(E_{s}; z) = A_{s} ⊕ B_{0,s} ⊕ B_{1,s}(z)]\} \end{matrix} (3.1)

L(s) is the length of agreement function between Λ_{s}(E_{s}) and A_{s}⊕B_{0,s}⊕ B_{1,s}. We use the convention that if Λ_{s}(E_{s}; y) = A_{s} ⊕ B_{0,s} ⊕ B_{1,s}(y) and E_{s} ↾ λ_{s}(y) + 1 does not change then no new numbers can enter A_{s} ⊕ B_{0,s} ⊕ B_{1,s} ↾ y + 1. Let \{i, \overline{i}\} = \{0, 1\}.

l^{Ψ_{i}}(s) = max\{x : (∀y < x)[Ψ_{i,s}(A_{s} ⊕ B_{\overline{i},s}; y) = B_{i,s}(y)

and ψ_{i,s}(y) < L(s)]} (3.2)

l^{Ψ_{i}}(s) is the E_{s}-correct length of agreement function between Ψ_{i,s}(A_{s} ⊕ B_{\overline{i},s}) and B_{i,s}. We will use these length of agreement functions to define, by induction, the following length of agreement and use functions:

l^{0}(s) = l^{Ψ_{0}}(s) (3.3)

If x < l^{0}(s) let ρ^{0}(A, x, s) = ψ_{0,s}(x),

ρ^{0}(B_{1}, x, s) = ψ_{0,s}(x) and ρ^{0}(B_{0}, x, s) = x. (3.4)

\begin{matrix}l^{2i+1}(s) = max\{x : (∀y < x) & [y < l^{2i}(s) and \\ ρ^{2i}(B_{1}, y, s) < l^{Ψ_{1}}(s)]\} \end{matrix} (3.5)

If x < l^{2i+1}(s) let ρ^{2i+1}(A, x, s) = ψ_{1,s}(ρ^{2i}(B_{1}, x, s)),
ρ^{2i+1}(B_{0}, x, s) = ψ_{1,s}(ρ^{2i}(B_{1}, x, s)) and
ρ^{2i+1}(B_{1}, x, s) = ρ^{2i}(B_{1}, x, s).

(3.6)

\begin{matrix}l^{2i+2}(s) = max\{x : (∀y < x) & [y < l^{2i+1}(s) and \\ ρ^{2i+1}(B_{0}, y, s) < l^{Ψ_{0}}(s)]\} \end{matrix} (3.7)

If x < l^{2i+2}(s) let ρ^{2i+2}(A, x, s) = ψ_{0,s}(ρ^{2i+1}(B_{0}, x, s)),
ρ^{2i+2}(B_{1}, x, s) = ψ_{0,s}(ρ^{2i+1}(B_{0}, x, s)) and
ρ^{2i+2}(B_{0}, x, s) = ρ^{2i+1}(B_{0}, x, s).

(3.8)

If x < l^{i}(s), let ρ^{i}(E, x, s) = max{λ_{s}(3ρ^{i}(A, x, s)),

λ_{s}(3ρ^{i}(B_{0}, x, s) + 1), λ_{s}(3ρ^{i}(B_{1}, x, s) + 2)}. (3.9)

(3.10) If x > l^{i}(s) then for all X ∈ {A, B_{0}, B_{1}, E}, ρ^{i}(X, x, s)↑ .

If for almost all stages s, ρ^{i}(X, x, s)↓ then let

ρ^{i}(X, s) = lim ρ^{i}(X, x, s), for X ∈ {A, B_{0}, B_{1}, E}. (3.11)

If x < l^{i}(s) then we have an E_{s}-correct computation involving i + 1 layers, that is Ψ_{0,s}(A_{s} ⊕ B_{1,s}) ↾ x + 1 = B_{0,s} ↾ x + 1, Ψ_{1,s}(A_{s} ⊕ B_{0,s}) ↾ ρ^{0}(B_{1}, x, s) + 1 = B_{1,s} ↾ ρ^{0}(B_{1}, x, s) + 1, Ψ_{0,s}(A_{s} ⊕ B_{1,s}) ↾ ρ^{1}(B_{0}, x, s) + 1 = B_{1,s} ↾ ρ^{1}(B_{0}, x, s)+1, … and ρ^{i}(X, x, s) is the initial segment of the set X used in this computation, for all X ∈ {A, B_{0}, B_{1}, E}. Diagram 5 may be helpful at this point. If we preserve E_{s} below ρ^{i}(E, x, s) + 1 then the computations used in defining l^{i}(s) > x will not change and we will preserve X_{s} below ρ^{i}(X, x, s) + 1, for all X ∈ {A, B_{0}, B_{1}}.

Associated with each number x will be another number i(x). We should view i(x) as the number of injuries Γ_{s}(A_{s} ⊕D_{s}; x) = B_{0,s}(x) can sustain and still ensure that Γ(A ⊕ D; x) = B_{0}(x) (more on this later). The value of i(x) will be determined before the construction. In fact, determining the value of i(x) will play a large role in all of our proofs. We will assume that i(x) is a non-decreasing function. We will define the length of agreement l(s) as

l(s) = max{x : (∀y < x)[y < l^{i(y)}(s)]}. (3.12)

[figure: B_{0}; A; B_{1}; E; x; ρ^{0}(B_{1},x,s)=ψ_{0,s}(x); ρ^{0}(A,x,s)=ψ_{0,s}(x); ρ^{1}(A,x,s); ρ^{1}(B_{0},x,s)=ψ_{1,s}(ρ^{0}(B_{1},x,s)); ρ^{2}(A,x,s); ρ^{2}(B_{1},x,s)=ψ_{0,s}(ρ^{1}(B_{0},x,s)); ρ^{3}(A,x,s); ρ^{3}(B_{0},x,s); λ_{s}(3ρ^{3}(A,x,s)); λ_{s}(3ρ^{3}(B_{1},x,s)+2); λ_{s}(3ρ^{3}(B_{0},x,s)+1)=ρ^{3}(A,x,s)]

Figure 5. 4 layers

If x < l(s) then let ρ(X, x, s) = ρ^{i(x)}(X, x, s) and ρ(X, x) = ρ^{i(x)}(X, x). Think of ρ(X, x, s) as the complete use function for x on X. We say a stage s is expansionary iff s = 0 or t < s is the last expansionary stage and l(s) > l(t).

If Λ(E) = A ⊕ B_{0} ⊕ B_{1} and Ψ_{i}(A ⊕ B\overline{i}) = B_{i} then there will be infinitely many expansionary stages. Hence, to meet N it is enough to build a computably enumerable set D and the functionals Δ_{i} and Γ such that if there are infinitely many expansionary stages then Δ_{i}(B_{i}) = D and Γ(A ⊕ D) = B_{1}. We will do this by splitting N into infinitely many subrequirements, N_{x}:

If there are infinitely many stages s such that l(s) > x then

Γ(A ⊕ D; x) = B_{0}(x) and Δ_{i}(B_{i}) ↾ (γ(x) + 1) = D ↾ (γ(x) + 1). N_{x}

Informally, the strategy to meet N_{x} is first to redefine Γ_{s}(A_{s} ⊕D_{s}; x) to reflect any change in B_{0,s}(x), if we can. If Γ_{s}(A_{s} ⊕ D_{s}; x)↓≠ B_{0,s}(x) and for all i ∈ {0, 1}, Δ_{i,s}(B_{i,s}; γ_{s}(x)) ↑ then add γ_{s}(x) to D_{s+1} which will allow us to later redefine Γ(A ⊕ D; x). Our goal is to prove that this works.

We will now present the formal details. We will have two additional parameters e^{x}(s) and p^{x}(s); they will be used to keep track of which layer has been “peeled away” with e^{x}(s) ∈ {0, 1} indicating which side has changed and p^{x}(s) at which layer.

Action for N_{x} at stage s + 1. Assume l(s + 1) > x (otherwise do nothing). Let t < s + 1 be the last stage such that Γ_{t}(A_{t} ⊕ D_{t}; x)↓ and l(t) > x, if such a stage exists. Do the first of the following cases which applies:

Case 1: t does not exist.

Action: Let d be large, define Γ_{s+1}(A_{s+1} ⊕D_{s+1}; x) = B_{0,s+1}(x) with use γ_{s+1}(x) = d > ρ(A, x, s), and define Δ_{i,s+1}(B_{i,s+1}; d) = 0 with use δ_{i,s}(d) = ρ(B_{i}, x, s). For all γ_{s+1}(x − 1) < y < d, if Δ_{i,s}(B_{i,s}; y)↑ then define Δ_{i,s+1}(B_{i,s+1}; y) = D_{s+1}(y) with use

0. If i(x) is even let e^{x}(s + 1) = 1, otherwise let e^{x}(s + 1) = 0. Let p^{x}(s + 1) = i(x) + 1.

Case 2: There is a stage t′ such that t < t′ < s + 1 and either Case 3, 4 or 5 applies at stage t′ for some N_{y}, where y ≤ x. Action: Same as in Case 1.

Case 3: A_{s+1} ↾ ρ(A, x, t) ≠ A_{t} ↾ ρ(A, x, t).

Action: Do nothing. Case 4: For i ∈ {0, 1}, and l = p^{x}(t) − 1, B_{i,s+1} ↾ ρ^{l}(B_{i}, x, t) ≠

B_{i,t} ↾ ρ^{l}(B_{i}, x, t) (hence Δ_{i,s+1}(B_{i,s+1}; γ_{t}(x)) will diverge). Action: Add γ_{t}(x) to D_{s+1} (by our convention this will cause

Γ_{s+1}(A_{s+1} ⊕ D_{s+1}; x) ↑ and will cause Case 2 to apply at the next possible stage).

Case 5: Currently never applies. Will be used in Section 5. Case 6: For i = e^{x}(t) and l = p^{x}(t), B_{i,s+1} ↾ ρ^{l}(B_{i}, x, t) ≠ B_{i,t} ↾

ρ^{l}(B_{i}, x, t) (hence, by Equations (3.6) and (3.8), B_{i,s+1} ↾ ρ^{l−1}(B_{i}, x, t) ≠ B_{i,t} ↾ ρ^{l−1}(B_{i}, x, t) and therefore Δ_{i,s+1}(B_{i,s+1}; γ_{t}(x)) would diverge except that we now redefine it). Action: Let e^{x}(s + 1) = \overline{i} and p^{x}(s + 1) = p^{x}(s) − 1. If

Γ_{s}(A_{s} ⊕ D_{s}; x)↑ then define Γ_{s+1}(A_{s+1} ⊕ D_{s+1}; x) = B_{0,s+1}(x) with use γ_{t}(x). Define Δ_{i,s+1}(B_{i,s+1}; γ_{t}(x)) = 0 with large use. For γ_{t}(x−1) < y < γ_{t}(x) and j ∈ {0, 1}, let Δ_{j,s+1}(B_{j,s+1}; y) = Δ_{j,t}(B_{j,t}; y) with use δ_{j,t}(y). For j = \overline{i}, let Δ_{j,s+1}(B_{j,s+1}; γ_{t}(x)) = Δ_{j,t}(B_{j,t}; γ_{t}(x)) with use δ_{j,t}(γ_{t}(x)).

Case 7: Otherwise.

Action: If Γ_{s}(A_{s} ⊕ D_{s}; x)↑ then define Γ_{s+1}(A_{s+1} ⊕ D_{s+1}; x) = B_{0,s+1}(x) with use γ_{t}(x). For γ_{t}(x − 1) < y ≤ γ_{t}(x) and j ∈ {0, 1}, let Δ_{j,s+1}(B_{j,s+1}; y) = Δ_{j,t}(B_{j,t}; y) with use δ_{j,t}(y).

Remark 3.1 (Coordinating the action for different N_{x}). We will assume that at any stage s we take the action needed for N_{x}, for x < s, in increasing order. Hence since i(x) is a nondecreasing function, γ_{s}(x) is nondecreasing as a function of s and increasing as a function of x. Similarly for the use functions γ_{i,s}.

Definition 3.2. If Cases 1 or 2 apply or s + 1 = 0 then we call s + 1 a free-clear stage. If Cases 3, 4 or 5 apply for some N_{y}, where y ≤ x, we call s + 1 an almost free-clear stage (assuming that there are infinitely many stages where l(s) > x, the next such stage will be a free-clear stage).

Definition 3.3. Let t be a free-clear stage. Let t′ be the next almost free-clear stage or ∞ if there is none. We let s ∈ I_{x}^{t} if either s = t or t < s < t′ and p^{x}(s) < p^{x}(s − 1) (i.e. Case 6 holds).

Lemma 3.4. Let t be a free-clear stage. Suppose for all s ∈ I_{x}^{t}, p^{x}(s) ≥ 0. Then

(i) For all l < p^{x}(s) and for all X ∈ {A, B_{0}, B_{1}, E}, X_{s} ↾ (ρ^{l}(X, x, t) + 1) = X_{t} ↾ (ρ^{l}(X, x, t)+1) (by induction on s, this implies that ρ^{l}(X, x, s) = ρ^{l}(X, x, t)). (ii) For l = p^{x}(s) and i = e^{x}(s), B_{i,s} ↾ (ρ^{l}(B_{i}, x, t) + 1) = B_{i,t} ↾ (ρ^{l}(B_{i}, x, t) + 1) (again, by induction, this implies that ρ^{l}(B_{i}, x, s) = ρ^{l}(B_{i}, x, t)).

Proof. By induction. Clearly the lemma holds for s = t. Let j = e^{x}(s − 1) = \overline{i}. Since s is in I_{x}^{t} and ρ^{l}(B_{j}, x, t) = ρ^{l+1}(B_{j}, x, t) (see Equations (3.6) and (3.8)), for some k ≤ l, B_{j,s−1} ↾ (ρ^{k}(B_{j}, x, t) + 1) ≠ B_{j,t} ↾ (ρ^{k}(B_{j}, x, t) + 1). Let k be as small as possible. Suppose k < l. Then, by the layering and the induction hypothesis, for some X ∈ {A, B_{i}}, X_{s} ↾ (ρ^{k}(X, x, t) + 1) ≠ X_{t} ↾ (ρ^{k}(X, x, t) + 1). So either Case 3 or 4 applies at stage s and hence s ∉ I_{x}^{t}. Hence k = l and (i) holds. B_{i,s} ↾ (ρ^{l}(B_{i}, x, t) + 1) = B_{i,t} ↾ (ρ^{l}(B_{i}, x, t) + 1), otherwise s is an almost free-clear stage.

We have just shown that, between (almost) free-clear stages, we only peel back the layers one at a time with changes alternating between B_{0} and B_{1}. The idea of peeling back the layers is called the “top-down approach” in Weinstein [1988]. We say that it is possible to peel back (or away) the p^{x}(s)^{th} layer of x at stage s.

It may be helpful to refer to Diagram 6 this point. This Diagram is a sub-diagram of Diagram 5. The numbered areas show where the changes in these sets must occur to peel back all 4 layers. The numbers refer to the sequence of events; i.e. there must be a change in first region followed by a change in the second, etc.

Lemma 3.5. Either Γ(A ⊕ D; x) ↓ and for all y ≤ γ(x), Δ_{i}(B_{i}; y) ↓ (i.e. the functionals are well-defined) or it is not the case that Λ(E) = A ⊕ B_{0} ⊕ B_{1} and Ψ_{i}(A ⊕ B\overline{i}) = B_{i}.

Proof. By induction on x. We can assume that there are infinitely many stages s where l(s) > x (otherwise we are done). Case 1 can only apply once. If Case 2 applies infinitely often then it is not the case that Λ(E) = A ⊕ B_{0} ⊕ B_{1} and Ψ_{i}(A ⊕ B\overline{i}) = B_{i}. Case 6 can apply at

[figure: B_{0}; A; B_{1}; 1; 2; 3; 4]

Figure 6. Where the changes must occur, in the required order, to peel back all 4 layers

most i(x) − 2 times between stages where Case 1 or 2 apply. Hence we can assume Case 7 applies almost always. Therefore lim_{s} γ_{s}(x) exists and Γ(A ⊕ D; x) ↓. Furthermore, for all γ(x − 1) < y ≤ γ(x), δ_{i}(y) = lim_{s} δ_{i,s}(y) exists and Δ_{i}(B_{i}; y)↓.

Lemma 3.6. Suppose Λ(E) = A ⊕ B_{0} ⊕ B_{1} and Ψ_{i}(A ⊕ B\overline{i}) = B_{i}, there is a last free-clear stage t and |I_{x}^{t}| ≤ i(x) + 1. Then N_{x} is met.

Proof. By induction on x. By the above lemma, Γ(A⊕D; x)↓ and for all y ≤ γ(x), Δ_{i}(B_{i}; y)↓. Since t is the last free-clear stage, Γ(A ⊕ D; x) = Γ_{t}(A_{t} ⊕ D_{t}; x) and for all y ≤ γ(x), Δ_{i}(B_{i}; y) = Δ_{i,t}(B_{i,t}; y).

Let s be the greatest stage in I_{x}^{t}. By Lemma 3.4 and the above hypothesis, B_{0,s} ↾ (ρ^{0}(B_{0}, x, t)+1) = B_{0,t} ↾ (ρ^{0}(B_{0}, x, t)+1). ρ^{0}(B_{0}, x, s) = ρ^{0}(B_{0}, x, t) = x. Therefore B_{0,s}(x) = B_{0,t}(x) = B_{0}(x) (otherwise s is not the greatest stage in I_{x}^{t}). Hence Γ(A ⊕ D; x) = Γ_{t}(A_{t} ⊕ D_{t}; x) = B_{0,t}(x) = B_{0}(x).

Let γ(x − 1) < y ≤ γ(x) (by Remark 3.1, we know γ(x) is an increasing function). By the induction hypothesis, y can only enter D at some stage s iff y = γ_{t′}(x′), l(s) > x, and for both i, Δ_{i,s+1}(B_{i,s+1}; y)↑, for some x′ and t′, where t′ ≤ t (see Case 4 or 5). By stage t we will have to redefine Δ_{i} to reflect this change in D with use 0. Hence Δ_{i}(B_{i}) ↾ (γ(x) + 1) = D ↾ (γ(x) + 1).

Corollary 3.7. Suppose for every free-clear stage t, |I_{x}^{t}| ≤ i(x) + 1. Then N_{x} is met.

Definition 3.8. Let s be a stage such that we act for N_{x} as above at stage s and let t be the greatest stage less than s such that we act for N_{x} as above at stage t (see Remark 3.13). Then s ∈ I_{x} iff E_{t} ↾ (ρ(E, x, t) ↓ +1) ≠ E_{s} ↾ (ρ(E, x, t) ↓ +1) (if t does not exist then s ∉ I_{x}).

Corollary 3.9. If |I_{x}| ≤ i(x) + 1 then N_{x} is met.

Proof. If s ∈ I_{x}^{t} then s ∈ I_{x}. (Note that the converse of the last statement does not hold.)

Hence the easy way to met N_{x} is to ensure that |I_{x}| ≤ i(x) + 1. In this case N_{x} applies finite restraint. We will close this section with a few remarks: Remark 3.10 (The priority ordering). We will always assume that N_{x} has higher priority than N_{y} if and only if x < y. Remark 3.11 (Initializing the strategy used for N_{x}). We cannot initialize N_{x} without initializing N_{y} for all y. The strategies used by these requirements are all helping construct the same sets and functionals. Hence we will only allow initialization of all N_{x}, in which case we can restart the construction of the needed sets and functionals and redefine the function i(x). A requirement R will be allowed to initialize (cancel) the N_{x}’s iff R has higher priority than N_{0} (and hence all the N_{x}’s, by the above remark). Remark 3.12 (Outcomes of N_{x}). N_{x} has i(x) + 2 outcomes which we will use when needed. If Case 1, 3, 4 or 5 applies at stage s + 1 then this strategy has outcome 0 at stage s + 1. Otherwise this strategy has outcome p^{x}(s + 1) + 1 at stage s + 1. The final outcome of the strategy is the lim inf of the outcomes. Since our hope is to meet N_{x}, by Corollary 3.7, we can assume that p^{x}(s) ≥ 0, for all s. So if this strategy has outcome 0, then Γ(A ⊕ D; x)↑ (the converse is not true). Remark 3.13 (Stages). In one of the following proofs we will need to restrict the stages that action for N_{x} can take place to accessible stages (see Section 4.3). In another we will need to restrict the action for N_{x} to expansionary stages (see Section 6.2). The above lemmas and discussion still hold true as long as we restrict all stages used above to appropriate stages. Remark 3.14 (Indexing). All the sets A, B_{0} and B_{1} and all the functionals Λ, Ψ_{0} and Ψ_{1} should be indexed in some uniform fashion. Let e be an index for the sets A, B_{0} and B_{1} and the functionals Λ, Ψ_{0} and Ψ_{1}. The above requirement and everything associated with it should be indexed by e. In particular, the subrequirement N_{x} should be N_{e,x} and i(x) should be i_{e}(x).

4. Lower Cones

In this section we present three theorems. All of these theorems involve the construction of a degree(s) which does not bound a weak critical triple. This section is split into three subsection each containing a theorem and its proof.

4.1. Nonbounding.

Theorem 4.1 ([Weinstein, 1988; Downey, 1990]). There is a noncomputable, computably enumerable degree e which does not bound a weak critical triple in the computably enumerable degrees.

It is enough to build a computably enumerable set E which meets all the requirements N_{e,x} and the requirements

\overline{E} ≠ W_{e}. R_{e}

We meet R_{e} by using the following procedure:

Action for R_{e} at stage s + 1. Do the first of the following cases which applies:

Case 1: If there is no witness w for R_{e} and E_{s} ∩ W_{e,s} = ∅, choose

a large witness w. Case 2: If a witness w for R_{e} exists, E_{s} ∩ W_{e,s} = ∅ and w ∈ W_{e,s},

add w to E_{s+1}. (If this case occurs then we say R_{e} acts.) This requirement is positive; it wants to add elements to E. R_{e}

acts at most once. To initialize this strategy means to discard the current witness. This strategy will met R_{e} as long as it is not initialized infinitely often.

Choose some appropriate computable ω-ordering of all the requirements. Given a requirement N_{e,x} we will let i_{e}(x) be the number of positive requirements of higher priority.

The Construction at stage s + 1. For the first s requirements take the action described above (in order of increasing priority). For all e and x, if ρ_{e}^{s}(E, x, s) ↓≠ ρ_{e}^{s}(E, x, s − 1) then initialize all positive requirements which have lower priority than N_{e,x}.

Lemma 4.2. (i) |I_{e,x}| ≤ i_{e}(x). Hence N_{e,x} is met. Furthermore, either ρ_{e}(E, x) exists or for almost all s, ρ_{e}(E, x, s)↑.

(ii) R_{e} is only initialized finitely often. Hence R_{e} is met.

Proof. By induction on priority.

(i) By the above initialization, only those R_{e′} with higher priority can put s into I_{e,x} and each one of these i_{e}(x) requirements can act at most once. By the induction hypothesis, there is a stage t by which all higher priority R_{e′} which ever act have acted. If there is a stage s ≥ t such that ρ_{e}(E, x, s)↓ then ρ_{e}(E, x) = ρ_{e}(E, x, s).

(ii) Wait for a stage s where all higher priority R_{e′} which are going to act have acted and for all higher priority N_{e,x} if ρ_{e}(E, x) exists then ρ_{e}(E, x) = ρ_{e}(E, x, s). R_{e} is never initialized after stage s.

4.2. Splitting. Clearly there are computably enumerable degrees which bound a weak critical triple in the computably enumerable degrees. The next theorem implies that the set of computably enumerable degrees which do not bound a weak critical triple generates the computably enumerable degrees (under join) and so does not form an ideal in the computably enumerable degrees.

Theorem 4.3. Every degree g is the join of two degrees e_{0} and e_{1} neither of which bound a weak critical triple in the computably enumerable degrees.

It is enough to build a pair of computably enumerable sets E_{0} and E_{1} and a functional Θ such that the requirements N_{e,x}^{j} (replace “E” with “E_{j}”, for j ∈ {0, 1}, and index everything with an additional superscript “j” in the discussion in Section 3) are met and the requirements

Θ(E_{0} ⊕ E_{1}; y) = G(y) Θ_{y}

are met. To meet Θ_{y}, we will use the following simple scheme: For all y, if Θ_{s}(E_{0,s} ⊕ E_{1,s}; y)↓≠ G_{s}(y) then add some z ≤ θ_{s}(y) to one of the E_{i}’s. Θ_{y} is a positive requirement.

Choose some appropriate computable ω-ordering of all the requirements such that Θ_{y} has higher priority than Θ_{z} iff y < z. Assume N_{e_{k},x_{k}}^{j_{k}} is the kth negative requirement. Let z_{k}^{∗} be the least number such that Θ_{z_{k}^{∗}} has lower priority than N_{e_{k−1},x_{k−1}}^{j_{k−1}}. We define two functions p and p̃ by induction as follows: p(1) = p̃(1) = 1, p(k + 1) = p(k) + p̃(k + 1), and

p̃(k + 1) = z_{k+1}^{∗} + ∑_{k′≤k} p̃(k′), (4.1)

Let i_{e_{k}}^{j_{k}}(x_{k}) = p(k). We make no claims that this function is a tight bound on the number of injuries. In the future we will drop the k from z^{∗} since the requirement to which the z_{k}^{∗} refers will always be clear from the context.

The Construction at stage s + 1. For the first s requirements take the action described above (i.e for N_{e,x}^{i}) or below (i.e. for Θ_{y}) in order of increasing priority.

Action for Θ_{y} at stage s + 1. Do the first of the following cases which applies, if any:

Case 1: Suppose Θ_{s}(E_{0,s} ⊕ E_{1,s}; y) ↑. Then define Θ_{s+1}(E_{0,s+1} ⊕

E_{1,s+1}; y) = G_{s+1}(y) with large use. Case 2: Suppose Θ_{s}(E_{0,s} ⊕ E_{1,s}; y)↓≠ G_{s}(y). Let N_{e,x}^{j} be the high-

est priority negative requirement such that if ρ^{l}(E_{j}, x, s) ↓ then ρ^{l}(E_{j}, x, s) ≥ θ_{s}(y), where l = p_{e}^{j,x}(s) − 1. If N_{e,x}^{j} exists, then add θ_{s}(z^{∗}) and θ_{s}(y) to E\overline{j} ; s+1 (in this case we say that N_{e,x}^{j} takes action for Θ). If N_{e,x}^{j} does not exist, then add θ_{s}(y) to E_{s+1}^{0}.

Clearly all the positive requirements are met. The following lemma shows that the negative requirements are also met.

Lemma 4.4. N_{e,x}^{j} only takes action for Θ at most p̃(k) times, where N_{e,x}^{j} is the kth negative requirement. |I_{e,x}^{j}| ≤ i_{e}^{j}(x). Hence N_{e,x}^{j} is met.

Proof. By induction on priority order. Assume ρ_{e}^{l}(E_{j}, x, s) ↓, where l = p_{e}^{j,x}(x) − 1 and θ_{s}(z) ≤ ρ_{e}^{l}(E_{j}, x, s) enters E_{j} at stage s. Then for all z′ ≥ z and all stage t > s, if θ(z′) ↓, θ(z′) > ρ_{e}^{l−1}(E_{j}, x, s). Unless some θ_{t}(z′) later enters E_{j}, where z′ < z, N_{e,x}^{j} will never take action for Θ again. By induction, the higher priority negative requirements can only cause such a z′ to later enter E_{j}, ∑_{k′<k} p̃(k′) many times. There are z^{∗} − 1 many positive requirements which also could cause such a z′ to later enter E_{j}. Hence Equation 4.1 bounds the number of times N_{e,x}^{j} can take action.

4.3. Nonlow nonbounding.

Theorem 4.5. There is a nonlow computably enumerable degree e which does not bound a weak critical triple in the computably enumerable degrees.

To show E is not low it is enough to build E and a set, W^{E}, which is computably enumerable in E, such that the following requirements are met:

R_{e} w ∈ W^{E} iff lim_{l} φ_{e}(w, l) = 0, for some witness w.

(If E is low then every set which is computably enumerable in E can be computably approximated. Hence W^{E} witnesses the fact that E is not low.) We meet R_{e} by using the following procedure:

Action for R_{e} at stage s + 1. Do the first of the following cases which applies, if any:

Case 1: A witness w does not exist. Choose a large witness w and a large use u_{e,s+1}(w) and let w ∈ W_{s+1}^{E_{s+1}} iff φ_{e,s}(w, s) ≠ 0. If φ_{e,s}(w, s)↓ then let l(s + 1) = s + 1, otherwise let l(s + 1) = s.

Case 2: A witness w exists, φ_{e,s}(w, l(s)) = 0 and w ∉ W_{s}^{E_{s}}. Add u_{s}(w) to E_{s+1}, add w to W_{s+1}^{E_{s+1}}, let u_{e,s+1}(w) be large and let l(s + 1) = l(s) + 1.

Case 3: A witness w exists, φ_{e,s}(w, l(s)) = 1 and w ∈ W_{s}^{E_{s}}. Add u_{s}(w) to E_{s+1}, remove w from W_{s+1}^{E_{s+1}}, let u_{e,s+1}(w) be large and let l(s + 1) = l(s) + 1.

Case 4: A witness w exists and φ_{e,s}(w, l(s))↓. Let l(s+1) = l(s)+1.

This is a positive requirement; it wants to add elements to E. R_{e} can act infinitely many times. We say this strategy has outcome 0 if Case 2 or 3 applies infinitely often and outcome 1, otherwise. To initialize this strategy means to discard the current witness. This strategy will meet R_{e} as long as it is not initialized infinitely often.

We will meet all the negative requirements N_{e,x} and all the positive requirements R_{e} by using a priority tree. Let T = {ω}^{<ω} (the subtree of nodes which are accessible at some stage will be a finitely branching tree). Choose some appropriate computable ω-ordering of all the requirements N_{e,x}. Assume N_{e_{k},x_{k}} is the kth negative requirement. Let i_{e_{k}}(x_{k}) = 2^{2k−1} (as always we make no claims this bound is tight). All the nodes of length 2k will work on meeting N_{e_{k},x_{k}} using the same strategy as described in Section 3. Each node, α, of length 2e + 1 will work on meeting R_{e} using the above procedure on stages where α is accessible with its own witness w_{α}.

The Construction of E at stage s + 1. By induction on k. Let β_{s+1,0} = λ. Let β = β_{s+1,k}. There are two cases:

Case 1: Suppose |β| = 2m. Use the above procedure for N_{e_{m},x_{m}}. Let o be the outcome of this strategy as determined in Remark 3.12. If k < s + 1 then let β_{s+1,k+1} = β_{s+1,k} o.

Case 2: Suppose |β| = 2m + 1. Use the above procedure for R_{m} (using the witness w_{β}). If k < s + 1 then if either Case 2 or Case 3 applies (for the strategy based at the node β), let β_{s+1,k+1} = β_{s+1,k} 0, otherwise let β_{s+1,k+1} = β_{s+1,k} 1.

Let β_{s+1} = β_{s+1,s+1}. Initialize all nodes of odd length which are to the right of β_{s+1}.

Lemma 4.6. Let f = lim inf β_{s}. For all k, (i) For all stages t, |I_{e_{k},x_{k}}^{t}| ≤ i_{e_{k}}(x_{k}). Hence N_{e_{k},x_{k}} is met. (ii) Let α = f ↾ (2k + 1). α is only initialized finitely often. Hence

R_{k} is met.

Proof. By induction on k.

(i) Let e = e_{k} and x = x_{k}. We say α injures N_{e,x} at stage s + 1 if s + 1 is not an almost free-clear stage, s + 1 is not a free-clear stage, u_{s}(w_{α}) < ρ_{e}^{l}(E, x, s) and u_{s}(w_{α}) enters E at stage s + 1, where l = p_{e}^{x}(s) − 1. Let t < s + 1 be the last free-clear stage and t′ < t be the last almost free-clear stage (let t′ = t, if such a stage does not exist). At stage t′ all α such that |α| > 2k, |α| is odd and α(2k) ≠ 0 are initialized. Hence no such α can injure N_{e,x}. If α is such that |α| > 2k, |α| is odd and α(2k) = 0 then α can only act at almost free-clear stages for N_{e,x}. Hence no such α can injure N_{e,x}. Therefore if α injures N_{e,x} at stage s + 1, |α| < 2k and α cannot injure again N_{e,x} until after the next almost free-clear stage (its use is too large). There are less than 2^{2k−1} such nodes.

(ii) Clear.

5. The requirement P_{i}

For X ∈ {A, B_{0}, B_{1}}, let X̂ = X ⊕ E. Let Ê = K. Our goal is to build a computably enumerable set E such that the following requirements are met:

If Λ̂(Ê) = Â ⊕ B̂_{0} ⊕ B̂_{1} and Ψ̂_{i}(Â ⊕ B̂\overline{i}) = B̂_{i}
then there exists a computably enumerable set D̂
and functionals Δ̂_{i} and Γ̂ such that

P

Δ̂_{i}(B̂_{i}) = D̂ and Γ̂(Â ⊕ D̂) = B̂_{0}

where Λ̂ and Ψ̂_{i} are functionals and Â, B̂_{0} and B̂_{1} are computably enumerable sets. If we meet P then the degrees represented by these three sets do not form a weak critical triple.

P is the dual of N under the operation of hatting. Hence we can use the dual of the strategy used for N to meet P and the dual of everything in Section 3 applies to the requirement P. As in Section 3, we split P into infinitely many subrequirements:

If there are infinitely many stages s such that l̂(s) > x then

Γ̂(Â ⊕ D̂; x) = B̂_{0}(x) and Δ̂_{i}(B̂_{i}) ↾ (γ̂(x) + 1) = D̂ ↾ (γ̂(x) + 1).

P_{x}

The strategy for P_{x} is the dual of the strategy used for N_{x} with two additional features. First, there is a restraint function r̂_{x}(s). r̂_{x}(s) will be controlled by the negative requirements and at each stage will be determined before the strategy for P_{x} acts. r̂_{x}(s) will be a nondecreasing function (in s). (Initially, r̂_{x}(0) = 0.) Second, Case 5 now reads:

Case 5: For i = ê^{x}(t) and l = p̂^{x}(t), B̂_{i,s+1} ↾ ρ̂^{l}(B̂_{i}, x, t) ≠ B̂_{i,t} ↾ ρ̂^{l}(B̂_{i}, x, t) and δ̂_{\overline{i},s}(x) > r̂_{x}(s + 1).

Action: Add δ̂_{\overline{i},s}(x) to E_{s+1} and γ̂_{t}(x) to D̂_{s+1} (by our convention this will make Δ̂_{\overline{i},s}(B̂\overline{i}, x) ↑, Γ̂_{s+1}(Â_{s+1} ⊕ D̂_{s+1}; x) ↑ and will cause Case 2 to apply at the next possible stage).

By Definition 3.2, we know if Case 5 applies at stage s+1, then s+1 is an almost free-clear stage. Case 5 adds numbers to E. In fact, this strategy may add infinitely many numbers into E. Hence this strategy is an infinite positive strategy (this makes sense since the dual of a negative strategy should be a positive strategy). Using the dual of the arguments in Section 3, one can prove:

Lemma 5.1 (The Dual of Corollary 3.7). Suppose for every free-clear stage t, |Î_{x}^{t}| ≤ î(x) + 1. Then P_{x} is met.

A word of caution: Since Ê = K, we cannot control |Î_{x}^{t}| (|Î_{x}|). Hence while Lemma 5.1 (the dual of Lemma 3.9) holds we cannot ensure that the hypothesis holds. We need some other way to ensure that P_{x} is met.

Definition 5.2. Let t be a free-clear stage. Let t′ be the next almost free-clear stage or ∞ if there is no such stage. We let s ∈ R̂_{x}^{t} iff either s = t or t < s < t′ and r̂_{x}(s) > r̂_{x}(s − 1) (since r̂_{x}(s) is nondecreasing in s, these are the only stages at which the value of r̂_{x}(s) changes).

Lemma 5.3. Suppose for every free-clear stage t, |R̂_{x}^{t}| ≤ \frac{1}{2}î(x) − 1. Then |Î_{x}^{t}| ≤ î(x) and so P_{x} is met.

Proof. First note there cannot be three stages, s_{0}, s_{1} and s_{2}, such that t ≤ s_{0} ≤ s_{1} < s_{2} < t′, s_{0} ∈ R̂_{x}^{t}, s_{1} ∈ Î_{x}^{t}, s_{2} ∈ Î_{x}^{t} and for all s if s_{0} < s ≤ s_{2}, then s ∉ R̂_{x}^{t}. (Assume otherwise then at stage s_{2} Case 5 will apply rather than Case 6 and hence s_{2} is an almost free-clear stage.) So two layers cannot be peeled away between stages when the restraint increases. Therefore |Î_{x}^{t}| ≤ 2(|R̂_{x}^{t}| + 1) ≤ î(x).

One should think of \frac{1}{2}î(x)−1 as a bound on the number of times the restraint can increase between a free-clear stage and the next almost free-clear stage and still meet P_{x}.

6. Upper Cones

In this section we present two theorems each of which is presented in its own subsection. Both of these theorems involve the construction of a degree above which there is no weak critical triple (in the computably enumerable degrees). We end this section with a subsection which concerns mixing the requirements P_{x} with the standard lowness requirements.

6.1. Upward nonbounding. The following theorem follows from Theorem 4.1 and the pseudo-jump theorem in Jockusch and Shore [1983] (see Cholak and Downey [1993] for more details). A direct proof of the theorem using Harrington’s “levels” method appears in Weinstein [1988].

Theorem 6.1 ([Weinstein, 1988]). There is an incomplete computably enumerable degree e above which there is no weak critical triple in the computably enumerable degrees.

To show E is not complete it is enough to build E and a computably enumerable set, W such that the following requirements are meet:

R_{e} w ∈ W iff Φ_{e}(E; w) = 0, for some witnesses w.

(If E is complete then every set which is computably enumerable is computable in E. Hence W witnesses that E is not complete.) We meet R_{e} by using the following procedure:

Action for R_{e} at stage s + 1. Do the first of the following cases which applies, if any:

Case 1: If a witness w does not exist, then choose a large witness

w. Case 2: If a witness w exists and Φ_{e,s}(E_{s}; w) = 0, add w to W and

restrain E below φ_{e,s}(w) + 1.

This is a negative requirement; it wants to stop elements from entering E. This strategy is injured if w ∈ W_{s} and some x later enters E below φ_{e,s}(w) + 1. When this occurs we will initialize the strategy. To initialize this strategy means to discard the current witness. R_{e} can act at most once unless initialized. This strategy will meet R_{e} as long as it is not initialized infinitely often.

We will meet all the negative requirements R_{e} and all the positive requirements P_{e,x} by using a tree. Let T = {ω}^{<ω} (again, the subtree of nodes which are accessible at some stage will be a finitely branching tree). Let f be the true path and β_{s} be the approximation to the true path at stage s.

Choose some appropriate computable ω-ordering of all the requirements P_{e,x}. Assume P_{e_{k},x_{k}} is the kth positive requirement. All the nodes of length 2k will work on meeting P_{e_{k},x_{k}} using the same strategy as described in Section 5 and the same restraint r̂_{e_{k},x_{k}}. For shorthand, we will let r̂_{e_{k},x_{k}} = r̂_{2k}.

A node β of length 2e + 1 will work on meeting R_{e} using the above procedure at stages when β is accessible with its own witness w_{β}. It would be nice if no node below β could injure the strategy used at β but this is not possible. We can only restore all needed layers of a positive requirement when there is an almost free-clear stage. Hence we cannot ensure the needed layers are available when the computation converges. These layers may have been used on a previous computation which was later injured or initialized.

To determine î_{e_{k}}(x_{k}) we need the following functions:

If k ≤ e then g(2e + 1, k) = 0 (6.1) If k + 1 > e then g(2e + 1, k + 1) = 1 + 2g(2e + 1, k) (6.2)

h(k) = ∑_{j<k}(g(2j + 1, k) + 1) (6.3)

î_{e_{k}}(x_{k}) = 2(h(k) + 1) (6.4)

(We make no claims that our bounds are tight.)

The Construction of E at stage s + 1. By induction on k. Let β_{s+1,0} = λ. Let β = β_{s+1,k}. There are two cases:

Case 1: Suppose |β| = 2m. Use the above procedure for P_{e_{m},x_{m}}. We say β injures α at stage s + 1 if |α| = 2e + 1, φ_{e,s}(w_{α}) ↓ and Case 5 applies and adds a number less than or equal to φ_{e,s}(w_{α}) into E at stage s + 1. Let o be the outcome of this strategy as determined by the dual of Remark 3.12. If k < s + 1 then let β_{s+1,k+1} = β o.

Case 2: Suppose |β| = 2m + 1. Use the above procedure for R_{m} (using the witness w_{β}). If k < s + 1 then let β_{s+1,k+1} = β 0. Let t > 2m be the last stage such that β_{t} <_{L} β (if such a stage does not exist then let t = 2m + 1). If |α| > t then increase r̂_{|α|}(s + 1) to s + 1. For |α| ≤ t, let t_{α} be the last stage such that α injured β at stage t_{α}. Suppose that t_{α} exists, t < t_{α} and for all γ if |γ| > |α| then either t_{γ} does not exist or t_{γ} < t_{α}. Then increase r̂_{|α|}(s + 1) to s + 1.

Let β_{s+1} = β_{s+1,s+1}. Initialize all nodes of odd length which are to the right of β_{s+1}.

Lemma 6.2. Let β ⊂ f (the true path on T) and |β| = 2e + 1. Fix t, t′ and k. Assume that for all stages s if t ≤ s < t′, β ≤ β_{s}. Assume no node of length 2k + 1 or greater injures β during those stages s where t ≤ s < t′. Then β can be injured at most g(2e + 1, k) times during those stages s where t ≤ s < t′.

Proof. By induction on k. Clearly, the lemma holds for k ≤ e (otherwise β is initialized). All the nodes of length 2k are using the same strategy. If one of these nodes injures β, they all are later restrained from injuring β. Hence, collectively, these nodes can injure β at most once. But this injury allows all the nodes of length less than 2k to reinjure β, if needed.

Lemma 6.3. Let β ⊂ f and |β| = 2e + 1. Let 2k > |β|. Then β can only increase the restraint function r̂_{2k} (g(2e + 1, k) + 1) times between a free-clear stage (for P_{e_{k},x_{k}}) and the next almost free-clear stage (for P_{e_{k},x_{k}}).

Proof. Let t be a free-clear stage and t′′ be the next almost free-clear stage. Let t′ be the least stage such that t < t′ ≤ t′′ and either β_{t′} <_{L} β or some node γ of length greater than 2k injures β. After stage t′, β will not increase the restraint function r̂_{2k} until after stage t′′. If such a t′ does not exist let t′ = t′′. Now by the above lemma, β can be injured at most g(2e + 1, k) times during those stages s where t ≤ s < t′.

Lemma 6.4. Let 2k > |β|.

(i) The restraint function r̂_{2k} only increases h(k) times between a free-clear stage (for P_{e_{k},x_{k}}) and the next almost free-clear stage (for P_{e_{k},x_{k}}).

(ii) |R̂_{e_{k},x_{k}}^{t}| ≤ \frac{1}{2}î_{e_{k}}(x_{k}) − 1. Hence P_{e_{k},x_{k}} is met.

Proof. (i) Follows from Lemma 6.3 and the fact that if |β| > 2k then β can never increase r̂_{2k}.

(ii) Follows from (i) and Lemma 5.3.

Lemma 6.5. Let β ⊂ f and |β| = 2e + 1. β is only injured finitely often. Hence R_{e} is met.

Proof. Let 2t ≥ 2e+1 be the least stage such that for all stages s ≥ 2t, β ≤_{L} β_{s}. No node of length 2e or less ever injures β after stage t. No node of length 2t + 1 or greater ever injures β after stage t. Now, by Lemma 6.2, β is injured at most g(2e + 1, t) more times.

6.2. Upward and downward nonbounding.

Theorem 6.6. There is a computably enumerable degree e above which there is no weak critical triple and below which there is no weak critical triple.

By Downey and Shore [1996] we know that e must be low_{2} since they show that below every nonlow_{2} degree one can embed a copy of M_{5}.

We will meet all the negative requirements N_{e,x} and all the positive requirements P_{e,x} by using a tree. Let T = {ω}^{<ω} (again, the subtree of nodes which are accessible at some stage will be a finitely branching tree). Let f be the true path and β_{s} be the approximation to the true path at stage s.

Choose some appropriate computable ω-ordering of all the requirements P_{e,x}. Assume P_{e_{k},x_{k}} is the kth positive requirement. If x_{k} = 0 then all nodes of length 2k will work on meeting P_{e_{k},x_{k}}; each using a different strategy. Such a node is called a parent node. If |α| = 2k, α’s parent node is the substring of length 2k′, where e_{k′} = e_{k} and x_{k′} = 0 (by the dual of Remark 3.10 such a k′ always exists). All nodes α of length 2k which share the same parent node will work on meeting P_{e_{k},x_{k}} using the same strategy as described in Section 5 and the same restraint r̂_{α}. Such a node is called a child node of its parent. Hence if α and α′ are using the same strategy to meet a positive requirement, r̂_{α} = r̂_{α′}.

Choose some appropriate computable ω-ordering of all the requirements N_{e,x}. Assume N_{e_{k},x_{k}} is the kth negative requirement. If x_{k} = 0 then all nodes of the nodes of length 2k+1 will work on meeting N_{e_{k},x_{k}}; each using a different strategy. Such a node is called a parent node. If γ is a parent node and |γ| is odd then let l_{γ} be the length of agreement function as defined in Equation 3.12. If |α| = 2k + 1, α’s parent node is the substring of length 2k′ + 1, where e_{k′} = e_{k} and x_{k′} = 0 (by Remark 3.10 such a k′ always exists). All nodes α of length 2k + 1 which share the same parent node will work on meeting N_{e_{k},x_{k}} using the same strategy as described in Section 3. Such a node is called a child node of its parent (parents are children of themselves). We will let ρ_{α}(E, s) = ρ_{e_{k}}(E, x_{k}, s) if α is working on N_{e_{k},x_{k}}. Hence if α and α′ are using the same strategy to meet a negative requirement, ρ_{α}(E, s) = ρ_{α′}(E, s).

We can initialize parent nodes γ (see Remark 3.11) and all of their children. At which point we can redefine the function i_{e_{k}}(x_{k}) for those children which are initialized.

We will meet N_{e_{k},x_{k}} by using Corollary 3.9. Hence, we must be able to count the number of possible injuries. Similarly, since we will use Lemma 5.3, we must also count the number of times the restraint for P_{e_{k},x_{k}} will increase between free-clear stages.

Informally, the key idea is: Assume β is working on N_{e_{k},x_{k}}. Let γ be β’s parent node. Let α be a node of even length. Let 2t^{∗} + j < t (for j ∈ {0, 1}) be the last stage at which γ was initialized (if such a stage does not exist let t^{∗} = 0). If |α| > t^{∗} + |β| then α can never injure β. Assume |α| ≤ t^{∗} + |β|. If α is started before β, α may injure β once. After this initial injury, α cannot injure β unless some α′, where |α′| > |α| injures β first.

Actions and accessibility at stage s + 1: Assume β is working on N_{e_{m},x_{m}}. Fix a stage s ≥ |β|. Let γ be β’s parent node. s + 1 is γ-expansionary iff s = 0 or l_{γ}(s) > l_{γ}(t), for all t < s. β will only act at accessible γ-expansionary stages s + 1 where l_{γ}(s) > x_{m}. We say β is started by stage s + 1 if some β′ working on N_{e_{m},x_{m}} using the same strategy as β acts (for the first time) by stage s + 1.

Injuries at stage s + 1: Assume that α is working on P_{e_{m},x_{m}} and that α acts by adding a number n into E at stage s + 1. Assume β is working on N_{e_{k},x_{k}}, γ is β’s parent node, γ ⊂ α and β has not been injured since the last stage t when it acted (defined below). If n < ρ_{β}(E, t) then we say α injures β at stage s + 1. If α injures β at stage s + 1 and α′ is also working on P_{e_{m},x_{m}} using the same strategy as α, then we say α′ injures β. The same thing occurs when β and β′ are both using the same strategy to meet N_{e_{k},x_{k}}. Hence a child of γ can be injured at most once between γ-expansionary stages. Let C = {β_{i}} be a finite collection of γ’s children. We say this finite collection is injured at stage s + 1 if the collection has not been injured since the last γ-expansionary stage and some β_{i} is injured at stage s + 1.

Restraint at stage s+1: Assume that β is working on N_{e_{m},x_{m}} and that β acts at stage s + 1. Let γ be β’s parent. Let 2t^{∗} + j < s + 1 be the last stage at which γ was initialized and j ∈ {0, 1} (if such a stage does not exist let t^{∗} = 0). Let t + 1 ≤ s be the last γ-stage. If ρ_{β}(E, t) ≠ ρ_{β}(E, s) or β is started by stage s + 1 then do the following: Assume α is working on P_{e_{k},x_{k}} and γ ⊂ α. If |α| > 2t^{∗} + |β| then increase r̂_{α}(s+1) to s+1. Let t′ be the last stage when α injured some child of γ (if t′ does not exist let t′ = 0). Suppose that 2t^{∗} + j < t′ and β was started by stage t′. For |α′| > |α| let t_{α′} be the last stage such that α′ injured some child of γ at stage t_{α′}. Suppose for all α′, if |α| < |α′| then either t_{α′} does not exist or t_{α′} < t. Then increase r̂_{α}(s + 1) to s + 1.

Determining the stages s + 1 at which β restrains α only depends on whether s + 1 is γ-expansionary, the last stage where γ was initialized, l_{γ}(s) > x_{m} and ρ_{β}(E, s) has increased since the last γ-expansionary stage. Hence this only depends on γ and the stage. We will assume that α’s restraint at stage s + 1 is determined before α acts at stage s + 1.

To determine i_{e_{k}}(x_{k}) and î_{e_{k}}(x_{k}) we need the following functions: Given k, let p(k) be the length of the parent node for all nodes of length k (this is a well-defined function).

If k ≤ m then g(2m + 1, k) = 0 (6.5)

\begin{matrix}If m < k + 1 then \\ g(2m + 1, & k + 1) = 2^{2k} + (2^{2k} + 1)g(2m + 1, k) \end{matrix} (6.6)

h(k) = ∑_{m<k} 2g(2m + 1, k − 1) + (k − m) + 2 (6.7)

î_{e_{k}}(x_{k}) = 2(h(k) + 1) (6.8)

If β is working on N_{e_{k},x_{k}} and β is initialized at stage 2t^{∗} + j, where j ∈ {0, 1}, then define i_{e_{k}}(x_{k}) = g(p(2k + 1), t^{∗} + k) at stage 2t^{∗} + j. (We make no claim that our bounds are tight.)

The Construction of E at stage s + 1. By induction on k. Let β_{s+1,0} = λ. Let β = β_{s+1,k}. There are two cases:

Case 1: Suppose |β| = 2m. Use the above procedure for P_{e_{m},x_{m}} (in Section 5). Let o be the outcome of this strategy as determined by the dual of Remark 3.12. If k < s + 1 then let β_{s+1,k+1} = β o.

Case 2: Suppose |β| = 2m + 1. Let γ be β’s parent node. If s is β-expansionary and l_{γ}(x) > x_{m}, use the above procedure for N_{e_{m},x_{m}} (in Section 3) and impose restraint as described above. If k < s + 1 then let β_{s+1,k+1} = β 0 (we do not care about the outcome in the sense of Remark 3.12).

Let β_{s+1} = β_{s+1,s+1}. Initialize all nodes whose parent node is to the right of β_{s+1}.

Lemma 6.7. Let γ be a parent node of length 2m+1. Fix k and some stages t < t′. Assume for all stages s, if t ≤ s ≤ t′, γ ≤ β_{s}. Let 2t^{∗} + j < t (for j ∈ {0, 1}) be the last stage at which γ was initialized (if such a stage does not exist let t^{∗} = 0). Let C = {β_{i}} be a finite collection of γ’s children such that for all i either β_{i} has been started by stage t or 2t^{∗} + |β_{i}| < 2k. Assume no node of length 2k + 1 or greater injures any β_{i} during those stages s where t ≤ s < t′. Then the collection {β_{i}} can be injured at most g(2m + 1, k) times by nodes of length 2k or smaller during stages s where t ≤ s < t′.

Proof. By induction on k. Clearly, the lemma holds for k ≤ m (otherwise γ is initialized). Suppose a node α of length 2k injures β_{i} at some stage between t and t′. Hence α last injured a child of γ before β_{i} was started and 2t^{∗} + |β_{i}| > 2k. At the next γ-expansionary stage, α is restrained from injuring any β_{i}. There are 2^{2k} such nodes and they may act independently. But each one of these injuries allows all the nodes of length less than k to reinjure the collection C, if needed.

Lemma 6.8. Let γ ⊂ f be a parent node of length 2m+1. Let 2t^{∗}+j < t (for j ∈ {0, 1}) be the last stage at which γ was initialized (if such a stage does not exist let t^{∗} = 0). Let β be a child of γ working on N_{e_{k},x_{k}} of length 2k+1. Then β can be injured at most i_{e_{k}}(x_{k}) = g(2m+1, t^{∗}+k) times after stage 2t^{∗} + j. Hence for all e and x, N_{e,x} is meet.

Proof. First note no node of length greater than 2t^{∗} + 2k + 1 = 2(t^{∗} + k) + 1 can ever injure β. Now apply Lemma 6.7 to C = {β}.

Lemma 6.9. Let γ ⊂ f be a parent node of length 2m+1. Fix k > m. Let α be a node of length 2k. Let t be a free-clear stage for P_{e_{k},x_{k}} and t′ be the next almost free-clear stage t′ (for P_{e_{k},x_{k}}). Let 2t^{∗} + j < t (for j ∈ {0, 1}) be the last stage at which γ was initialized (if such a stage does not exist let t^{∗} = 0).

(i) After stage s, the children β of γ such that 2t^{∗} + |β| > 2k can collectively increase α’s restraint at most g(2m + 1, k − 1) + 1 times between t and t′.

(ii) After stage s, the children of γ such that 2t^{∗} + |β| < 2k can collectively increase α’s restraint at most g(2m + 1, k − 1) + (k − m) + 1 times between t and t′.

(iii) After stage s, the children of γ of any length can collectively increase α’s restraint at most 2g(2m + 1, k − 1) + (k − m) + 2 times between t and t′.

Proof. (i) Let s_{i} be the stages such that t ≤ s_{0} < s_{1} … < s_{j} ≤ t′, r̂_{α}(s_{i}) > r̂_{α}(s_{i} − 1) and this increase was caused by a child β of γ such that 2t^{∗} + |β| > 2k. Let β_{i} be a child of γ such that β_{i} restrained α at stage s_{i} and 2t^{∗} + |β_{i}| > 2k. β_{i} was started by stage t. No α′ such that |α| ≤ |α′| can injure any child of γ between stages t and s_{j} (otherwise β_{j} cannot restrain α at stage s_{j}). γ cannot be initialized between stages t and s_{j} (otherwise β_{j} cannot restrain α at stage s_{j}). Let i < i′. Since s_{i} is a γ-expansionary stage and β_{i′} was started by stage t, ρ_{β_{i′}}(E, s_{i}) ↓< s_{i}. So once β_{i} restrains α, β_{i′} cannot restrain α unless it is later injured. Now Lemma 6.7 applies to C = {β_{i}}. Hence j ≤ g(2m + 1, k − 1) + 1.

(ii) Let s_{i} be the stages such that t ≤ s_{0} < s_{1} … < s_{j} ≤ t′, r̂_{α}(s_{i}) > r̂_{α}(s_{i} − 1) and this increase was caused by a child β of γ such that 2t^{∗} + |β| < 2k. Let β_{i} be a child of γ of length such that β_{i} restrained α at stage s_{i} and 2t^{∗} + |β_{i}| < 2k. No node of length 2k or greater can ever injure any β_{i}. γ cannot be initialized between stages t and s_{j} (otherwise β_{j} cannot restrain α at stage s_{j}). Let i < i′. Since s_{i} is a γ-expansionary stage, if β_{i′} was started by stage s_{i}, ρ_{β_{i′}}(E, s_{i}) ↓< s_{i}. Hence once β_{i} restrains α, β_{i′} cannot restrain α unless it is later started or injured. After (k − m) γ-expansionary stages, all the β_{i} are started. Lemma 6.7 applies to C = {β_{i}}. Hence j ≤ g(2m+1, k−1)+(k−m)+1.

(iii) Since γ has no child of even length this follows from (i) and (ii).

Corollary 6.10. Suppose α is working on P_{e_{k},x_{k}} of length 2k. Let t be a free-clear stage for P_{e_{k},x_{k}} and t′ be the next almost free-clear stage t′ (for P_{e_{k},x_{k}}).

(i) α’s restraint can increase at most h(k) times between t and t′. (ii) |R̂_{e_{k},x_{k}}^{t}| ≤ \frac{1}{2}î_{e_{k}}(x_{k}) − 1. Hence P_{e_{k},x_{k}} is met.

Proof. (i) Only those β whose parent node γ is a substring of α can restrain α. Hence the above lemma applies at most k times.

(ii) Follows from (i) and Lemma 5.3.

6.3. P_{e,x} and lowness requirements. The astute reader might wonder why one could not combine the requirements P_{e,x} and lowness requirements in the following fashion: First note that one meets the standard lowness requirements by finite restraint. All the negative requirements in this section were met by finite restraint. However one cannot meet the standard lowness requirements by acting independently at different nodes on a tree with infinitary positive requirements. Now turn the infinite positive strategy used for P_{e,x} into a finite positive strategy by only allowing Case 5 to act when x actually enters B_{0} and ignoring the outcomes. Hence a negative requirement can be injured at most once by each positive requirement of higher priority. So hopefully we can have enough layers in the positive requirements of lower priority to handle this fixed number of increases in the restraint.

However, the problem with this approach, is that a positive requirement P_{e,x} may in fact injure a negative requirement of higher priority: The strategy used for P_{e,x} may have peeled away all of its layers and be in a position that it must add some number n into E iff x enters B_{0}. Now the computation for the negative requirement converges and wishes to restrain n. Then x enters B_{0} which forces n to enter E. This may be repeated infinitely many times for the same negative requirement. This remains true even if we restrict the positive requirements to a single fixed e. Thus the question of whether M_{5} can be embedded above every low computably enumerable degree remains open.

References

Ambos-Spies, K. and Fejer, P. A. [1996]. Personal communication. Ambos-Spies, K. and Lerman, M. [1986]. Lattice embeddings into the recursively

enumerable degrees, J. Symbolic Logic 51: 257–272. Ambos-Spies, K. and Lerman, M. [1989]. Lattice embeddings into the recursively

enumerable degrees II, J. Symbolic Logic 54: 735–759.

Cholak, P. and Downey, R. [1993]. Lattice nonembeddings and intervals of the

recursively enumerable degrees, Ann. Pure Appl. Logic 61: 195–221. Cooper, B. and Yi, X. [n.d.]. Non-splitting and the high/low hierarchy. In prepara-

tion. Downey, R. G. [1990]. Lattice nonembedding and initial segments of the r. e. de-

grees, Ann. Pure Appl. Logic 49: 97–119. Downey, R. G. and Lempp, S. [n.d.]. Contiguity and distributivity in the com-

putably enumerable turing degrees, J. Symbolic Logic . To appear. Downey, R. G. and Shore, R. A. [1995]. Degree theoretic definitions of low_{2} recur-

sively enumerable sets, J. Symbolic Logic 60(3): 727–756. Downey, R. G. and Shore, R. A. [1996]. Lattice embedding below a nonlow_{2} recur-

sively enumerable degree, Israel J. Math. 94: 221–246. Jockusch, Jr., C. G. and Shore, R. A. [1983]. Pseudo-jump operators I: the r.e. case,

Trans. Amer. Math. Soc. 275: 599–609. Lachlan, A. H. [1972]. Embedding nondistributive lattices in the recursively enumer-

able degrees, in W. Hodges (ed.), Conference in Mathematical Logic, London, 1970, Vol. 255 of Lecture Notes in Mathematics, Springer–Verlag, Heidelberg, pp. 149–177.

Lachlan, A. H. and Soare, R. I. [1980]. Not every finite lattice is embeddable in the

recursively enumerable degrees, Adv. in Math. 37: 74–82. Lempp, S. and Lerman, M. [n.d.]. A finite lattice without a critical triple that cannot

be embedded into the enumerable turing degree, Ann. Pure Appl. Logic . To appear.

Leonhardi, S. [1994]. Generalized Nonsplitting in the Recursively Enumerable De-

grees, PhD thesis, University of Wisconsin. Nies, A., Shore, R. A. and Slaman, T. A. [n.d.]. Definability in the recursively

enumerable degrees. In preparation. Shore, R. A. [n.d.]. The recursively enumerable degrees, in E. Griffor (ed.), The

Handbook of Recursion Theory, North-Holland. To appear. Shore, R. A. and Slaman, T. A. [1991]. Working below a low_{2} recursively enumerable

degree, Ann. Pure Appl. Logic 52: 1–25. Soare, R. I. [1987]. Recursively Enumerable Sets and Degrees, Perspectives in Math-

ematical Logic, Omega Series, Springer–Verlag, Heidelberg. Weinstein, B. [1988]. On Embedding of the Lattice 1-3-1 into the Recursively Enu-

merable Degrees, PhD thesis, University of California, Berkeley.

Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556-5683

  E-mail address: cholak@turing.math.nd.edu

Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand

  E-mail address: rod.downey@vuw.ac.nz

Department of Mathematics, White Hall, Cornell University, Ithaca, NY 14853

  E-mail address: shore@math.cornell.edu