A SPLITTING THEOREM FOR n − REA DEGREES

RICHARD A. SHORE AND THEODORE A. SLAMAN

Abstract. We prove that, for any D, A and U with D >_{T} A ⊕ U and r.e. in A ⊕ U, there are pairs X_{0}, X_{1} and Y_{0}, Y_{1} such that D ≡_{T} X_{0} ⊕ X_{1}; D ≡_{T} Y_{0} ⊕ Y_{1}; and, for any i and j from {0, 1} and any set B, if X_{i} ⊕ A ≥_{T} B and Y_{j} ⊕ A ≥_{T} B then A ≥_{T} B. We then deduce that for any degrees d, a, and b such that a and b are recursive in d, a ≱_{T} b, and d is n − REA in to a, d can be split over a avoiding b. This shows that the Main Theorem of Cooper [1990] and [1993] is false.

1. Introduction

The basic formal definitions of computable sets and functions were proposed independently, and in various equivalent forms, in the 30s by many researchers. The standard model now is that of the Turing machine. Turing [1939] also introduced the notion of relative computability to capture the idea of one set A being easier to compute than another B in the sense that if we knew how to settle membership questions in B we could do the same for A. The model here consists of Turing machines with oracles, i.e. black boxes that supply the required answers about B. We say that A is computable from (or recursive in) B if there is a Turing machine which, when equipped with an oracle for B, computes (the characteristic function of) A, i.e. for some e, ϕ_{e}^{B} = A. (Here we are assuming a standard listing ϕ_{e}^{B} of the Turing machines with oracles for B.) We denote this relation by A ≤_{T} B which we read as A is (Turing) reducible to B or A is recursive (computable) in B. This relation is transitive and reflexive and so induces an equivalence relation ≡_{T} (A ≡_{T} B ⇔ A ≤_{T} B ∧ B ≤_{T} A) and a partial order also denoted by ≤_{T} on the equivalence classes. These equivalence classes are called (Turing) degrees and the equivalence class of a set A ⊆ ω is called its degree. It is typically denoted by a or deg(A).

The structure D of these degrees has been the object of extensive study over the past fifty or sixty years. (A survey from the early 80s is Shore [1985]. Current ones can be found in Griffor [1999].) At first, attention focused on basic structural questions about D such as determining which partial orders or lattices can be embedded in D and characterizing its initial segments. For the past twenty years a considerable amount of attention has been paid to more global issues such as automorphisms of, and definability in, D. Of course, some of the vast store of structural information discovered earlier on played important roles in these later investigations. Particularly important examples in the early work on global issues include some of the results on initial segments and Spector’s exact pair theorem that says that every countable ideal is the intersection of two principal ideals. More specific local structural results that have played central roles in definability results for D include ones revolving around density, or the lack thereof, and the interactions between certain special subclasses of degrees related to recursive enumerability and all of the degrees. (A degree b is recursively enumerable relative to (or in) a degree a if there is a set B ∈ b which can be enumerated by a function recursive in an A ∈ a, i.e. B is the range of some ϕ_{e}^{A}.)

1991 Mathematics Subject Classification. Primary 03D25, 03D30; Secondary 03D55.

Key words and phrases. degrees, Turing degrees, recursively enumerable degrees,splitting theorems.

Partially supported by NSF Grant DMS-9802843.

Partially supported by NSF Grant DMS-97-96121.

In particular, Jockusch and Shore [1984] used two such facts due to Sacks [1963] and an analysis of operators corresponding to iterations of recursive enumerability and ones corresponding to sets which are effective Boolean combinations of r.e. ones to show that the class A of degrees of arithmetic sets (those definable in arithmetic) is definable in D. The basic structural facts needed were that no r.e. degree a can be a minimal cover of any degree b, i.e. if b < a and a is r.e. then there is always a degree c strictly between b and a, and that every degree b has a minimal cover a which is the degree of a set which is an effective Boolean combination of sets r.e. in B of a particular form.

In a similar vein, Cooper proposed an approach to defining 0′, the degree of the halting problem, and so the jump operator taking a to a′. (Here a′ is the degree of the halting problem for machines with an oracle for A, i.e. a′ = deg(A′) where A′ = {e|the computation of ϕ_{e}^{A}(e) eventually halts}.) The structural property he considered was considerably more complicated than the nonminimality one of r.e. degrees used by Jockusch and Shore but was also based, in one direction, on an old result of Sacks’. Here are Cooper’s property, some associated classes of degrees and the relevant theorem of Sacks corresponding to the nonminimality results for r.e. degrees.

Definition 1.1. d is splittable over a avoiding b if either a, b ≮ d or b ≤ a or there are d_{0}, d_{1} such that a <_{T} d_{0}, d_{1} <_{T} d, d_{0} ∨ d_{1} = d and b ≰ d_{0}, d_{1}. C_{1} = \{c|∀a, b(a ∨ c is splittable over a avoiding b\}. \overline{C}_{1} = \{d|∃c ∈C_{1}(d ≤_{T} c)\}.

Theorem 1.2. (Sacks [1963]) Every r.e. degree d is in C_{1}.

The analog of the Sacks’ minimal cover theorem in Cooper’s work was his Main Theorem that there is a set C which is d − r.e., i.e. the set-difference of two r.e. sets, (and so a corresponding operator) such that there are a and b such that c ≡_{T} deg(C) is not splittable over a avoiding b. Together with a general theorem on the range of such operators and their interaction under join with degrees not below 0′, this result would have sufficed to define 0′ and so, by relativization, the jump operator itself. Cooper [1990] proposed to argue for the existence of such a set with a 0′′′ priority construction similar to that proving the Nonsplitting Theorem of Lachlan [1975] for the recursively enumerable degrees. In this paper, we prove a splitting theorem (Theorem 2.3) a special case of which shows that there is no such set C and so Cooper’s proposed property does not define the jump. We then indicate how to use the same type of argument to refute another recent proposal by Cooper of an alternate definition of the jump in the same style. In Shore and Slaman [2000] we provide a very different definition of 0′ and the jump operator.

2. The Splitting Theorem

We begin with the definition of the iteration of recursive enumerability basic to the work of both Jockusch and Shore and Cooper.

Definition 2.1. A set W is 1 − REA relative to, or in, A if it is r.e. in A and above it in Turing degree. W is (n + 1) − REA in A if it is 1 − REA relative to some U which is n − REA in A. A degree w is n − REA relative to, or in, a if it contains a set W which is n − REA relative to some set A ∈ a . If a = 0, we just say that W and w are n − REA.

As Lachlan has shown that every d − r.e. set is of 2 − REA degree (see Jockusch and Shore [1984] for a proof of a more general fact), it suffices to prove that every 2 − REA degree d is splittable over every a avoiding any b to show that there is no d − r.e. set as claimed in the Main Theorem of Cooper [1990], [1993]. In fact, we prove this for every n − REA degree d. The proof is not uniform in the sense that given D, A and B we do not construct a splitting (D_{0}, D_{1}) of D that lies above A and not above B in such a way as to effectively produce indices for the D_{i} from those of the given sets. Instead, we produce various candidates some pair of which constitute the desired splitting. The case for n = 1 is the Sacks splitting theorem (Theorem 1.2). We begin with a result that suffices for the case n = 2 and then use it in an induction argument to get the full result.

Theorem 2.2. Let D, A and U be given so that D >_{T} A ⊕ U and D is recursively enumerable in A ⊕ U. Then there are pairs X_{0}, X_{1} and Y_{0}, Y_{1} with the following properties.

1. D ≡_{T} X_{0} ⊕ X_{1} and D ≡_{T} Y_{0} ⊕ Y_{1}.

2. For any i, j ∈ {0, 1}, and any set B, if X_{i} ⊕ A ≥_{T} B and Y_{j} ⊕ A ≥_{T} B then A ≥_{T} B.

The desired splitting theorem for n − REA degrees is an easy corollary of Theorem 2.2.

Theorem 2.3. Suppose that d, a, and b are given and d is n − REA in a. Then d can be split over a avoiding b.

Proof. Without loss of generality we may assume that a and b are recursive in d and a ≱_{T} b. We deduce Theorem 2.3 from Theorem 2.2 by an induction on n. Let D, A, and B be representatives of d, a, and b, respectively.

When n is equal to 1, D is recursively enumerable in A. By the Sacks Splitting Theorem (Theorem 1.2) relativized to A, d can be split over a avoiding a ∨ b.

Now assume that n is greater than 1 and assume that Theorem 2.3 holds for all numbers less than n. Since d is n − REA in a, there is a set U such that U is (n − 1) − REA relative to A, U is recursive in D and D is recursively enumerable in U.

First, if D is recursive in U, then D has the same degree as U and the inductive hypothesis verifies the claim of Theorem 2.3. So, assume D is not recursive in U. Then D >_{T} A ⊕ U and is recursively enumerable in A ⊕ U. Thus we can apply Theorem 2.2 to get X_{0}, X_{1} and Y_{0}, Y_{1} as indicated in its conclusion. If neither A ⊕ X_{0} nor A ⊕ X_{1} computes B, then the degrees of A ⊕ X_{0} and A ⊕ X_{1} form a splitting of d over a avoiding b. Otherwise, B is recursive in either A ⊕ X_{0} or A ⊕ X_{1}. By the second condition in Theorem 2.2, B cannot be recursive in either A ⊕ Y_{0} or A ⊕ Y_{1}. Consequently, the degrees of A ⊕ Y_{0} and A ⊕ Y_{1} form a splitting of d over a avoiding b. Thus, in either case, d can be split over a avoiding b as required.

The remainder of this paper is devoted to proving Theorem 2.2. As in the statement of Theorem 2.2, let D, A and U be given so that D >_{T} A ⊕ U and D is recursively enumerable relative to A ⊕ U. We construct pairs X_{0}, X_{1} and Y_{0}, Y_{1} to satisfy the conclusions of the theorem.

In the following, we will identify sets with their characteristic functions. For example, D(n) = 0 is synonymous with n ∉ D, and D(n) = 1 is synonymous with n ∈ D. We first describe the requirements that we need to satisfy and then provide the construction of the desired sets from D and finally the verifications that the requirements are satisfied..

2.1. Join requirements. We directly ensure that X_{0} ⊕ X_{1} and Y_{0} ⊕ Y_{1} compute D by enforcing the following conditions.

(2.1) (∀n)[n ∈ D if and only if X_{0}(n) = X_{1}(n)]

(2.2) (∀n)[n ∈ D if and only if Y_{0}(n) = Y_{1}(n)].

Note that we can specify X_{i} or Y_{j} arbitrarily and still define X_{1−i} or Y_{1−j}, respectively, to satisfy Equations 2.1 and 2.2.

2.2. Infima requirements. We ensure that our sets satisfy the second claim in Theorem 2.2 by a priority construction. We consider requirements P of the following form, in which i and j belong to {0, 1}, Φ and Ψ are Turing functionals, and B is a free variable.

(2.3) If Φ(X_{i} ⊕ A) = Ψ(Y_{j} ⊕ A) = B, then A ≥_{T} B.

Let (P_{i} : i ∈ ℕ) be a recursive enumeration of all requirements of the above form. To fix our notation, let P_{k} be the requirement

(2.4) If Φ_{k}(X_{i_{k}} ⊕ A) = Ψ_{k}(Y_{j_{k}} ⊕ A) = B_{k}, then A ≥_{T} B_{k}.

We organize our construction so that for all P_{k}, either one of Φ_{k}(X_{i_{k}} ⊕ A) or Ψ_{k}(Y_{j_{k}} ⊕ A) is not total, they are not equal, or their common value is recursive in A. During the construction, we search for an argument at which we can make Φ_{k}(X_{i_{k}} ⊕ A) and Ψ_{k}(Y_{j_{k}} ⊕ A) unequal. If no such opportunity appears and both functions are total, then we conclude that their common value must be recursive in A.

2.3. Constructing the X_{i}’s and Y_{j}’s recursively in D.

Definition 2.4. 1. A finite condition on one of the X_{i}’s or Y_{j}’s is a 0-1 valued function whose domain is a finite initial segment of ℕ. That is, a finite condition on a set is a specification of a finite initial segment of the values of that set. Two conditions are compatible if they agree on the domain they have in common.

2. A P_{k}-split over A consists of a natural number n, a pair of finite conditions p_{0} and p_{1}, and a pair of computations in Φ_{k} and Ψ_{k} of lengths less than the domains of p_{0} and p_{1} such that Φ_{k}(n, p_{0} ⊕ A) and Ψ_{k}(n, p_{1} ⊕ A) are defined by these computations and have different values.

3. We say that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x extend the conditions in the above P_{k}-split if X_{i_{k}} extends p_{0} and Y_{j_{k}} extends p_{1}.

4. We say that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x are compatible with the conditions in the above P_{k}-split if X_{i_{k}} and p_{0} are compatible and Y_{j_{k}} and p_{1} are compatible.

Note, if X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x extend the conditions in a P_{k}-split, then Φ_{k}(X_{i_{k}} ⊕A) and Ψ_{k}(Y_{j_{k}} ⊕A) take different values at the number n mentioned in that split.

In the following, we assume we have a universal enumeration over all k of all P_{k} splits over A.

Definition 2.5. 1. Let D[s] denote the set of numbers less than or equal to s which are enumerated in D relative to A ⊕ U by computations of length less than or equal to s.

2. For each x ∈ ℕ, let s_{x} be the least stage s such that D[s] and D are equal on all numbers less than or equal to x, that is D[s] ↾ x + 1 = D ↾ x + 1.

We now compute the X_{i}’s and Y_{j}’s from D by recursion as follows.

1. To compute these sets at argument x, first compute their restrictions to all numbers less than x. If x is 0, then these restrictions are null functions.

2. Compute s_{x}.

3. Say that k requires attention at x if k is less than or equal to x and the following conditions hold.

(a) X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x do not extend the conditions in any P_{k}-split enumerated at or before stage s_{x} (of our fixed enumeration for the P_{k} splits over A).

(b) There is a P_{k}-split enumerated at or before stage s_{x} such that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x are compatible with the conditions in that split. If there is no k which requires attention at x, then let X_{0}(x) and Y_{0}(x)

both equal 1 and let X_{1}(x) and Y_{1}(x) both equal D(x). Thus, X_{0}(x) = X_{1}(x) if and only if Y_{0}(x) = Y_{1}(x) if and only if D(x) = 1.

If there is a k which requires attention at x, then let p_{0} and p_{1} be the conditions mentioned in the P_{k}-split which appeared first in our universal enumeration of splits among those P_{k}-splits of highest priority, i.e. with the smallest k, which are compatible with X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x. Define X_{i_{k}}(x) and Y_{j_{k}}(x) to equal p_{0}(x) and p_{1}(x), respectively, where those are defined. This leaves at least one of each pair {X_{0}, X_{1}} and {Y_{0}, Y_{1}} undefined at x. Define the sets whose values at x have not yet been determined to ensure the equivalences X_{0}(x) = X_{1}(x) if and only if Y_{0}(x) = Y_{1}(x) if and only if D(x) = 1.

Here is a short summary of the algorithm. Use the enumeration of D relative to A ⊕ U to produce a finite set of splits for various P_{k}’s, and then define the X_{i}’s and Y_{j}’s at x compatibly with the split for the highest priority requirement which requires attention.

Remark 2.6. Recursively in A ⊕ U, we can compute the function mapping D ↾ x to the tuple ⟨s_{x−1}, X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, Y_{1} ↾ x⟩.

Proof. Suppose we are given D ↾ x and by induction have computed X_{0} ↾ x − 1, X_{1} ↾ x − 1, Y_{0} ↾ x − 1, and Y_{1} ↾ x − 1. We can run the enumeration of D relative to A ⊕ U until the stage s_{x−1} at which each element of D ↾ x has been enumerated.

The universal enumeration of P_{k} splits over A is recursive in A, and so we can compute the set of splits enumerated at or before stage s_{x−1} using A ⊕ U. The values of the X_{i}’s and Y_{j}’s at x−1 are effectively determined from this collection of splits and the value of D at x − 1, data which is now seen to be available to A ⊕ U from D ↾ x.

Definition 2.7. Let X_{0}[s], X_{1}[s], Y_{0}[s], and Y_{1}[s] be the sets computed from D[s] in the way that we specified that D computes X_{0}, X_{1}, Y_{0}, and Y_{1}.

2.4. Satisfaction of the requirements.

Lemma 2.8. For each k, there are only finitely many x such that P_{k} requires attention at x.

Proof. We verify Lemma 2.8 by a Friedberg-style priority argument. By induction on k, choose x_{0} so that for all x greater than x_{0} no requirement of index less than k requires attention at x. Suppose that P_{k} requires attention at some x_{1} greater than x_{0}. Then the values of X_{i_{k}} and Y_{j_{k}} at x will be defined so that X_{i_{k}} ↾ x+1 and Y_{j_{k}} ↾ x + 1 are compatible with the conditions in the first P_{k}-split for which this is possible. Since no requirement of lower index can require attention, the same P_{k}-split will be used during subsequent stages until reaching an x_{2} such that the X_{i}’s and Y_{j}’s restrictions to x_{2} extend that P_{k}-split. But then P_{k} cannot require attention for any argument greater than x_{2}.

Lemma 2.9. Suppose that Φ_{k}(X_{i_{k}} ⊕A) = Ψ_{k}(Y_{j_{k}} ⊕A) and their common value B_{k} is not recursive in A. Then for all x there is an s greater than x with the following properties.

1. s ≥ s_{x}.

2. There is a P_{k}-split which is enumerated at or before stage s such that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x are compatible with the conditions in that split.

Proof. For a contradiction, fix x so that there is no s which satisfies the conclusions of Lemma 2.9.

Then every t greater than s_{x} satisfies the first property specified in the conclusion of Lemma 2.9, so there cannot be any P_{k}-split such that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x are compatible with the conditions in that split.

Consider any conditions p_{0} and p_{0}^{∗} extending X_{i_{k}} ↾ x. If there were an n such that Φ_{k}(n, p_{0} ⊕ A) and Φ_{k}(n, p_{0}^{∗} ⊕ A) are defined and give incompatible values, then one of them could be paired with the initial segment of Y_{j_{k}} used to compute Ψ_{k}(n, Y_{j_{k}} ⊕ A) to produce a P_{k}-split.

Now, conclude that B_{k} is recursive in A: Given n, find p_{0} extending X_{i_{k}} ↾ x such that Φ_{k}(n, p_{0} ⊕ A) is defined. The value of Φ_{k}(n, p_{0} ⊕ A) must equal B_{k}(n), since it must equal Φ_{k}(n, X_{i_{k}} ⊕ A). Thus, A ≥_{T} B_{k} for the desired contradiction.

Lemma 2.10. For all k, if Φ_{k}(X_{i_{k}} ⊕ A) = Ψ_{k}(Y_{j_{k}} ⊕ A), then their common value is recursive in A.

Proof. For a contradiction, suppose that Φ_{k}(X_{i_{k}} ⊕A) = Ψ_{k}(Y_{j_{k}} ⊕A) and that their common value is not recursive in A. We will show that D is recursive in A ⊕ U.

By Lemma 2.8, fix t_{0} so that for all k^{∗} less than or equal to k and all x greater than t_{0}, P_{k^{∗}} does not require attention at x.

Take D ↾ t_{0} as a given finite amount of data. We compute the value of D at arguments x > t_{0} using the already computed D ↾ x as follows.

1. Compute s_{x−1}, X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x. (See Remark 2.6 and text proceeding it for the effectiveness of this step relative to A ⊕ U.)

2. Compute the least t such that the following conditions are satisfied. (a) t is greater than the maximum of x and s_{x−1}.

(b) There is a P_{k}-split which is enumerated at or before stage t such that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x are compatible with the conditions in that split. We let t_{x} denote this t.

3. Return the value of D[t_{x}] at x as the value of D at x.

By Lemma 2.9, there is a stage t and a P_{k}-split which is enumerated at or before stage t such that X_{0} ↾ x, X_{1} ↾ x, Y_{0} ↾ x, and Y_{1} ↾ x are compatible with the conditions in that split. Thus, the above procedure will find some t_{x} and will return some value for D at x.

We chose t_{0} so that no strategy with index less than or equal to k requires attention after stage t_{0}. In particular, P_{k} cannot require attention at x. But then, the P_{k}-split which is enumerated before or during stage t_{x} can not have been enumerated before or during stage s_{x}. Consequently, s_{x} is less than t_{x} and D(x) = D[t_{x}](x). Thus, the calculation relative to A ⊕ U correctly returns the value of D at x.

The conclusion that D is recursive in A ⊕ U is the desired contradiction, which proves Lemma 2.10 and so Theorem 2.2.

After seeing these results (in August 1999), Cooper (personal communication) said that a minor modifications of his original definition and proof would provide a correct definition of the jump and that, after presenting them at the Leeds seminar, he would post an account of these modifications at his web site. In January 2000, Cooper posted a revised definition of his splitting property and so a revised proposal to define 0′ (Cooper [2000]).

Definition 2.11. d is discretely splittable over a avoiding b iff d is splittable over a with witnesses d_{i} as in Definition 1.1 each of which is greater than or equal to a minimal cover m_{i} of a such that m_{i} ≰ d_{1−i}.

Cooper’s revised Main Theorem was then that there is a d − r.e. degree d and degrees a, b ≤ d with b ≰ a such that d is not discretely splittable over a avoiding b. He then argued from this in the same way as from his original Main Theorem that 0′ is definable. However, our techniques show that there is no such d − r.e. degree.

Theorem 2.12. For every 2−REA degree d and every a and b, if a, b ≤ d, b ≰ a then d is discretely splittable over a avoiding b.

If d is r.e. in a then the result follows by relativizing classical results about the r.e. degrees from Sacks [1963] and Cooper and Epstein [1987]. If not, suppose d is REA in u which is r.e. In this case, d is strictly above a ⊕ u which is r.e. in and strictly above a. For i = 0, 1 we can now choose pairwise incomparable minimal covers m_{i} and n_{i} of a below a ⊕ u (see Epstein [1979]). We can then construct X_{i} and Y_{i} as in Theorem 2.2 with the added requirements on their degrees that m_{i} ≤ x_{j} , n_{i} ≤ y_{j}, m_{1−i} ≰ x_{i} ∨ m_{i} and n_{1−i} ≰ y_{i} ∨ n_{i} for i, j ∈ {0, 1}. The proof of this fact is essentially the same as that of Theorem 2.2. The essential changes are that we now look for splits with oracles of the form p_{0} ⊕ M_{i_{k}} and p_{1} ⊕ N_{j_{k}} for the infima requirements and, in addition, have new requirements that look for splits between p_{0} ⊕ M_{i} and M_{1−i} and similarly between p_{1} ⊕ N_{i} and N_{1−i}. The construction proceeds recursively in D as before given the new list of requirements. The argument that the requirements are satisfied is also essentially as above using, at the end, the fact that d ≰ a ∨ u.

We also note that Theorem 2.12 can be generalized to all n − REA degrees in much the same way as we derived Theorem 2.3 from Theorem 2.2.

Finally, we should point out that after seeing Theorem 2.12, Cooper announced a further revision to his splitting property and claimed that it can be used to define 0′ in the same way as in his earlier proposals.

References

Cooper, S. B. [1990], The jump is definable in the structure of the degrees of unsolvability (research announcement), Bull. Am. Math. Soc. 23, 151-158. Cooper, S. B. [1993], On a conjecture of Kleene and Post, Department of Pure Mathematics, Leeds University, 1993 Preprint Series No. 7. Cooper, S. B. [2000], The Turing definability of the relation of “computably enumerable in”, Computability Theory Seminar, University of Leeds. Cooper, S. B. and Epstein, R. L. [1987], Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34, 15–32. Epstein, R. [1979], Degrees of Unsolvability: Structure and Theory, Lecture Notes in Mathematics 759, Springer–Verlag, Heidelberg. Griffor, E. (ed.) [1999], Handbook of Computability Theory, North-Holland, Amsterdam. Jockusch, C. G. Jr. and Shore, R. A. [1984], Pseudo-jump operators II: transfinite iterations, hierarchies and minimal covers, J. Symb. Logic 49, 1205-1236. Sacks, G. E. [1963], On the degrees less than 0′, Ann. of Math. (2) 77, 211-231. Shore, R. A. 1985, The structure of the degrees of unsolvability, in Recursion theory, Proc. Symp. Pure Math. 42, A. Nerode and R. A. Shore eds., Amer. Math. Soc., Providence RI, 33–51. Shore, R. A. and Slaman, T. A. [2000], Defining the Turing jump, to appear. Turing, A. M. [1939], Systems of logic based on ordinals,Proc. London Math. Soc. (3) 45, 161-228.

Department of Mathematics, Cornell University, Ithaca NY 14853

E-mail address: shore@math.cornell.edu
URL: http://www.math.cornell.edu/~shore/

University of California, Berkeley, Berkeley, CA 94720-3840,

E-mail address: slaman@math.berkeley.edu
URL: http://www.math.berkeley.edu/~slaman/