Conjectures and Questions from Gerald Sacks’s Degrees of Unsolvability^{∗}

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

Abstract

We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks’s Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.

Gerald Sacks has had a major influence on the development of logic, particularly recursion theory, over the past thirty years through his research, writing and teaching. Here, I would like to concentrate on just one instance of that influence that I feel has been of special significance to the study of the degrees of unsolvability in general and on my own work in particular — the conjectures and questions posed at the end of the two editions of Sacks’s first book, the classic monograph Degrees of Unsolvability (Annals of Mathematics Studies, Number 55, Princeton University Press, 1963 and 1966).

∗This paper was presented at the symposium in honor of Gerald Sack’s sixtieth birthday in May, 1993 and written shortly thereafter. Rather than try to rewrite it at press time three years later, I have simply added a few footnotes and refernces to the more important recent results.

§Partially supported by NSF Grants DMS-9204308, DMS-93-44740, DMS-9503503 and the U.S. ARO through ACSyAM at the Mathematical Sciences Institute of Cornell University Contract DAAL03-91-C-0027.

In presenting his list of six conjectures and five questions in [1963], Sacks suggested that each solution should require a “new idea”. He was remarkably prophetic in that the techniques developed to solve these problems, generally speaking, represent the most important advances in the subject since 1963. Moreover, as they have been discovered, the answers to these problems have played a crucial role in the development of new results, lines of research and indeed our whole attitude toward what constitutes the proper analysis of degree structures. As we shall see, however, the facts have led us to a vision of the degrees quite different from the one that motivated many of the conjectures of [1963] and [1966].

In [1963], Sacks says that he believes each of the conjectures presented there “because behind each of them stands several false but plausible proofs”. The list begins with three conjectures about the structure of R, the recursively enumerable degrees ordered by Turing reducibility.

(C1) If a and c are recursively enumerable degrees such that a < c, then there exists a recursively enumerable degree b such that a < b < c.

(C2) There exist two nonzero, recursively enumerable degrees whose greatest lower bound is 0.

(C3) There exist two recursively enumerable degrees with no greatest lower bound in the upper semi-lattice of recursively enumerable degrees.

The first conjecture is now known as the Sacks Density Theorem as Sacks himself proved it in [1964]. Both this remarkable theorem and the methods introduced to prove it had important consequences for the study of the structure of the r.e. degrees.

The study of the r.e. degrees begins with Post’s famous problem [1944] to construct an r.e. set which is neither recursive nor complete. This problem was solved by Friedberg [1957] and Muchnik [1956] who introduced the priority method to construct such sets. It is this method that has since been viewed as the hallmark of recursion theory. The form of the method they introduced is now known as the finite injury method. In it, actions to satisfy each of the requirements that guarantee the desired result interfere with (injure) other (lower priority) ones only finitely often. For the next several years, this technology was the mainstay of the subject. It has, however, serious limitations. These limitations were overcome by Sacks in [1963a] and in a stronger way in the [1964] proof of the density theorem.

Theorem 1 (Sacks Jump Theorem [1963a]) Every degree c which is r.e. in and above 0′ is the jump of an r.e. degree.

The proof of this theorem also exploited the arguments introduced in that of Sacks [1963b].

Theorem 2 (Sacks Splitting Theorem [1963b]) For every nonrecursive r.e. degree a there are r.e. degrees b, c < a such that b ∨ c = a.

The method introduced in the proofs of the Sacks Jump Theorem [1963a] and Sacks Density Theorem [1964] is now called the infinite injury method as actions for single requirements can cause infinitely many injuries to ones of lower priority. The proofs of the jump and density theorems were the first application of these methods to the study of R and continued to be most influential.

A basic form of the construction used in the proof of the Sacks Jump Theorem [1963a] had been introduced independently and somewhat earlier in Shoenfield [1961] to produce an incomplete r.e. theory in which every recursive function is representable. Another version was later introduced by Yates [1966a] in his study of index sets. Since their introduction, these techniques have been used to prove many important theorems and have served as the basis for further extension of the priority method.

The density theorem itself engendered the idea that the r.e. degrees should be, in some way, a homogeneous structure and so a “nice” one in the sense that rationals are a nice linear ordering. This idea was first formulated by Shoenfield [1965] in his famous conjecture at the Model Theory Symposium of 1963 in Berkeley. Shoenfield conjectured that the r.e. degrees are, in the model theoretic sense, an ω-saturated uppersemilattice (usl) with a least and a greatest element (0 and 1). A direct formulation of this conjecture can be phrased in terms of extensions of embeddings.

Extension of Embedding Problem (for partial orderings or usls): Characterize the pairs P ↪ Q of partial orderings (usls) with 0, 1 such that, for every embedding f : P → R, there is an extension g of f to an embedding of Q into R.^{1} Shoenfield’s Conjecture [1965]: For every pair P ↪ Q of finite usls with 0, 1 and every embedding f : P → R, there is an extension g of f to an embedding of Q into R.

1Slaman and Soare [1995], [1997] have now solved this problem.

If true, this conjecture would have implied that the r.e. degrees had many of the familiar properties of structures like dense linear ordering or atomless Boolean algebras which satisfy the corresponding property for the appropriate family of structures (linear orderings and Boolean algebras). Such structures are countably categorical (i.e. there is a unique such countable structure up to isomorphism) and so, if axiomatizable, have decidable theories. They are countably homogeneous (every structure preserving map from one finite subset to another can be extended to an automorphism) and so have continuum many automorphisms. A positive solution to Shoenfield’s conjecture would thus have constituted an essentially complete characterization of the structure of the r.e. degrees.

At a more algebraic or local level, Shoenfield’s conjecture would also imply (C3): R is not a lattice. (Given any r.e. degrees c < a, b, the extension of embeddings property would say that we can find an r.e. degree d ≤ a, b with d ≰ c.) On the other hand, this very application contradicts (C2). Both conjectures were settled by Lachlan [1966a],[1966b] and Yates [1966] independently. They each verified (C2) by constructing a minimal pair of r.e. degrees, i.e. nonrecursive a and b such that a ∧ b = 0. This construction represented a new turn in the methodology of the infinite injury argument. It eventually lead to the tree constructions introduced in Lachlan [1975] which now underlie the basic approach to developing and presenting almost all priority arguments. The demonstration that (at least) some degrees have infima in R, began what has been an important chapter in the study of the r.e. degrees: Lattice embeddings. We cite three examples:

Theorem 3 (Lachlan, Lerman, Thomason; see Soare [1987] IX.2) Every countable distributive lattice can be embedded into R as a lattice preserving 0.

Theorem 4 (Lachlan [1972]) Each of the two basic nondistributive lattices M_{5} (Figure 1) and N_{5} (Figure 2) can be embedded (as lattices) in R.

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

Figure 1: The lattice M_{5}

Theorem 5 (Lachlan and Soare [1980]) The lattice S_{8} (Figure 3) cannot be embedded in R.

As can be seen from these results, the characterization of the lattices embeddable in R (with ∨ and ∧ preserved) is nontrivial. The best results to date are in Ambos-Spies and Lerman [1986] and [1989] but the general problem remains open.^{2} Thus the construction of minimal pairs in the r.e. degrees also presaged the change from “simplicity” to “complexity” as the slogan for the study of the structure of R.

Lachlan [1966a] and Yates [1966] each showed that R is not a lattice by proving (C3) by very different methods. Yates [1966] suggested using the same techniques devised to construct a minimal pair to build a strictly ascending sequence c_{0} < … < c_{n} < … with an exact pair, i.e. incomparable degrees a and b such that c_{i} ≤ a, b for each i and every c ≤ a, b is below some c_{i}. No such a and b can have an infimum. (If a ∧ b = c, then for some i, c ≤ c_{i}. As c_{i} < c < a, b, we have contradicted the assumption that c is the greatest lower bound of a and b.) A more complicated construction along these lines is carried out in Cooper [1972] where he also answers the fourth

2A new type of nonembeddable lattice has been discovered by Lempp and Lerman [1997].

[figure: 0; 1]

Figure 2: The lattice N_{5}

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

Figure 3: The lattice S_{8} Question (Q4) in Sacks [1963] discussed below. Lachlan’s proof of this result was quite different. It was based on a relativization of the following:

Theorem 6 (Nondiamond Theorem, Lachlan [1966a]) There are no r.e. degrees a and b such that a|b, a ∨ b = 1, a ∧ b = 0.

This theorem is now known as the nondiamond theorem as it says that there is no lattice embedding of the diamond shaped four element lattice (0, 1 plus two incomparable intermediate elements) into R preserving 0, 1 and the lattice structure. Lachlan’s proof of this result introduced the idea of nonuniform constructions. Given a pair a, b of incomparable potentiality complementary r.e. degrees, Lachlan constructed infinitely many degrees one of which witnesses that either a ∨ b ≠ 1 or a ∧ b ≠ 0. The idea that one can use the failure of a set being constructed to satisfy some requirement to construct another set with an alternate property has been quite useful in later work.

An excellent source for modern proofs of almost all the results cited about the r.e. degrees, as well as general descriptions of the techniques involved, is Soare’s textbook [1987]. A current overview of our knowledge about the structure of R can be found in Shore [1997].

The remaining conjectures and questions at the end of [1963] deal with the structure of all the degrees D and the relations between this ordering, the r.e. degrees and the jump operator. The three conjectures all deal with embedding problems in D.

(C4) A partially ordered set P is imbeddable in the degrees if and only if P has cardinality at most that of the continuum and each member has at most countably many predecessors.

(C5) If S is a set of independent degrees of cardinality less than the continuum, then there exists a degree d ∉ S such that S ∪{d} is an independent set of degrees.

(C6) S is a finite initial segment of degrees if and only if S is orderisomorphic to a finite, initial segment of some upper semi-lattice with a least member.

Once again, the first two of these conjectures express the view that the degrees are “nice” in a model theoretic sense. The first, (C4), says that D is a universal partial order of size the continuum with the countable predecessor property ({x| x<y} is countable for every element y). The second, (C5), was presented as a likely approach to a proof of the first. It represents an instance of a positive solution to an extension of embedding problem for partial orderings of size less than the continuum. The particular extension of embedding problem represented in (C5) can be solved by the finite extension methods of Kleene and Post [1954] when S is countable. Thus, using these methods, (C4) can be verified if the continuum hypothesis holds, i.e. 2^{ℵ_{0}} = ℵ_{1}. Actually in §3 of [1963], Sacks had proven (C4) for partial orderings P such that {x| x>y} has size at most ℵ_{1} for every element y by a rather ingenious argument. Despite many efforts, no progress was made on these conjectures for many years. The reason for the difficulties was revealed in Groszek and Slaman [1983]: (C5) is independent of the axioms of set theory.

Theorem 7 (Groszek and Slaman [1983]) Assuming the consistency of ZFC, there are models of ZFC in which 2^{ℵ_{0}} > ℵ_{1} and in which there are maximal independent sets of size ℵ_{1}.

The basic embedding problem (C4), however, remains open. It is perhaps the last algebraic question about the structure of the degrees at this basic level. It has defied many attempts at solving it and, if true, will surely require the new idea that Sacks and all of us look forward to seeing.

The solution to the final conjecture (C6) of [1963] in Lerman [1971] represented a milestone in the long history of the attempts at characterizing the initial segments of D. This project had its beginnings in Spector’s [1956] construction of a minimal nonrecursive degree. In §9 of [1963] Sacks brought in the priority method to show that there is a minimal degree below 0′. Many researchers contributed partial results providing more and more lattices which were isomorphic to initial segments of D. We cite three other results on initial segments of D.

Theorem 8 (Lachlan [1968]) Every countable distributive lattice is isomorphic to an initial segment of D.

Theorem 9 (Lachlan and Lebeuf [1976]) Every countable usl with 0 is isomorphic to an initial segment of D.

Theorem 10 (Abraham and Shore [1986]) Every usl of size at most ℵ_{1} with 0 and the countable predecessor property is isomorphic to an initial segment of D.

Of course, assuming the continuum hypothesis, this theorem completely characterizes the initial segments of D. Without such set theoretic assumptions, however, this is pretty much the end of the story.

Theorem 11 (Groszek and Slaman [1983]) If ZFC is consistent then it is consistent that the continuum is ℵ_{2} and there is an usl of size ℵ_{2} with 0 and the countable predecessor property which is not isomorphic to any initial segment of D.

The best textbook source for initial segment construction and most other information about the degrees as a whole is Lerman [1983]. A current view of our knowledge about the structure of D can be found in Slaman [1997].

As Sacks had expected in [1966], these results (either Lachlan [1968] or Lerman [1971] suffice) imply the undecidability of D. Although these theorems at first might be viewed as tending towards characterizing the structure of D in some “nice” way as would (C4) and (C5), we actually have here the beginnings of the change from “simplicity” to “complexity” as the appropriate slogan for D as well as R. The conjectures that replaced those solved between 1963 and 1966, (C1), (C2) and (C3) of [1966], also reflected the view that R and D are model theoretically “nice” in some way (saturation, homogeneity or universality). Their solutions, however, laid the foundations of a new attitude toward the structure of R and D. Before considering them, however, we will discuss the five questions at the end of [1963].

These questions deal with the degrees below 0′ and the relation between these degrees, the r.e. degrees, and the jump operator.

(Q1) If d is a nonzero, recursively enumerable degree, then there exists a minimal degree less than d.

(Q2) If d is a nonzero degree less than 0′ then there exists a nonzero degree b less than 0′ such that the greatest lower bound of d and b exists and is equal to 0.

(Q3) There exists a nonzero d such that no degree less than or equal to d is minimal.

(Q4) There exists a sequence of simultaneously recursively enumerable degrees which has an r.e. degree as one of its minimal upper bounds.

(Q5) There exists a recursively enumerable degree d such that 0^{(n)} < d^{(n)} < 0^{(n+1)} for all n.

The first question, (Q1), was solved in Yates [1970]. To solve it, Yates introduced what is now called the full approximation method of constructing sets (generally) below 0′. This method builds sets below 0′ by constructing recursive approximations that are eventually constant at every point of the sets’ characteristic functions. An alternative technology introduced later to solve these types of problems builds a set below a given r.e. d (such as 0′) by a direct construction recursive in the oracle d. Such arguments are called oracle constructions. When such constructions are possible, they are almost always easier than the full approximation method. However, it is often the case that the first, or even only solution, to many problems has been achieved by the more difficult but more flexible technique introduced to solve (Q1). An introduction to these methods can be found in Posner [1980]; a current survey of the degrees below 0′ is Cooper [1997].

The second question (Q2) was solved in Shoenfield [1966] by constructing a minimal degree b below 0′ incomparable with the given degree d. Of course, b then has the properties required in (Q2). This paper is particularly important as the first source of tree arguments in initial segment constructions. The terminology and approach introduced here were vital to the later development of initial segment results (as described above in the discussion of (C6)). Considerable additional work along these lines culminated in various complementation theorems.

Theorem 12 (Posner [1980]) Every degree d < 0′ is complemented, i.e. there is a b such that d ∨ b = 0′ & d ∧ b = 0. In fact, by Slaman and Steel [1989], b can be taken to be 1-generic and found uniformly in d.

Lachlan’s [1968] proof that every countable distributive lattice is isomorphic to an initial segment of D, of course, gives an affirmative answer to (Q3): Embed any distributive lattice with no nonzero minimal elements as an initial segment of D. At about the same time, Martin [1967] (see Odifreddi [1989], Theorem V.3.16, p. 481) produced a quite different solution. He employed a Baire category theoretic argument to prove that “most” degrees fail to have minimal predecessors. (The class of sets of with predecessors of minimal degree is meager.) Much later Paris [1977] showed that this set also has measure zero. Indeed, Kurtz [1979] shows that the set of degrees which are r.e. in some strictly smaller degree (and so, for example, have every partial ordering embedded below them) has measure one. These and other results of this sort are the descendants of the work in §10 of [1963].

The next question, (Q4), was answered in Cooper [1972]. Cooper constructed a uniformly r.e. sequence B_{i} which is ascending in degree and an r.e. A ≰ B_{i} whose degree is a minimal upper bound for those of B_{i}. The construction technique is closely related to that for minimal pairs used to settle (C2). Combining this result with the Thickness Lemma derived from Shoenfield [1961] and Sacks [1963a] as described in Soare [1987, VIII.1], immediately gives an r.e. set C ≱ A whose degree is an upper bound for those of the B_{i}. It is clear that the degrees of A and C can have no infimum (as it would have to be strictly below A but above all the B_{i}). Thus this result also supplies a solution to (C3).

As Sacks indicated in [1963], the final question there, (Q5), seems to go far beyond the techniques developed to construct r.e. sets in that it asks to control not just the set A being constructed and is its jump A′ but all its iterated jumps A^{(n)}. Actually, what one needed was not really a whole new arsenal of construction procedures but a new insight into the uniformities present in most existing arguments. Solutions were produced by Lachlan [1965] and Martin [1966] and then by Sacks [1967]. The insights revealed in these arguments have become quite important in applications of the priority method to recursive model theory and other areas in which it is crucial to simultaneously control the properties of structures being built at all levels of the arithmetic hierarchy. In his paper constructing arithmetically incomparable arithmetic singletons Harrington [1975] appropriately says: “Our proof is to be found in that shiny little box which was first opened by Sacks [1967] … the key which unlocks this box is the recursion theorem together with the remarkable uniformities prevalent in most recursion theoretic agreements.” For those who have not had the pleasure of attempting to unravel these constructions, we might add that what one finds inside, of course, is a shiny little box.

Three of the conjectures, (C1)-(C3), and two of the questions, (Q1)-(Q2), proposed in [1963] were solved before the second edition of Sacks’s Degrees of Unsolvability appeared in [1966]. Despite the failure of Shoenfield’s conjecture implied by the proof of (C2), the idea that D and R should somehow still be simple persisted and is reflected in the new conjectures. Of the r.e. degrees Sacks says “We guess that there is some simple way of characterizing its ordering, but we are unable to frame a strong conjecture. (L1) [the density theorem] suggests its ordering is homogeneous, but (L2) [the existence of minimal pairs] and (L4) [there are r.e. a < b such that no r.e. c joins a to b (Lachlan[1966a])] say otherwise.” Sacks then made two conjectures along these lines about the nature of r.e. degrees and added one suggested by Hartley Rogers [1967] and [1967a] about the homogeneity of the degrees as a whole. We should point out that Rogers seems to have been the first to stress the importance of the global questions about definability and automorphisms that now seem to be the central problems in the analysis of recursion theoretic structures. Already at the Logic Colloquium of 1965 (see Rogers [1967]), Rogers set forth the program of investigating these issues for structures including R, D and E, the lattice of r.e. sets. Even then, Rogers wrote of these problems that “I do not believe that they have received much attention up to the present time. Yet they are easily stated and appear to be of central significance in the foundations of recursive function theory.” The exposure given to these questions in Sacks [1966] and Rogers [1967a] and the approach to recursion theory that they represented promoted much of the work we will discuss below.

(C1)′ The elementary theory of the ordering of the recursively enumerable degrees is decidable.

(C2)′ For each degree d, the ordering of degrees recursively enumerable in and ≥ d is order-isomorphic to the recursively enumerable degrees.

(C3)′ For each degree d the ordering of degrees ≥ d is order-isomorphic to the ordering of degrees.

All of these conjectures turned out to be false. The first to fall was (C2)′. The source of the failure was in the embedding results for R. Lerman, Shore and Soare [1984] proved that finite partial lattices (those in which infimum is not always defined) with a certain structural property (the trace probe property) derived from an analysis of the known embedding techniques could be embedded into R. They used this result to show that there are infinitely many 3-types realized in R. It follows from the Ryll-Nardjewski theorem that R fails to have one of the “nice” model theoretic properties implied by the Shoenfield conjecture:

Theorem 13 (Lerman, Shore and Soare [1984]) R is not ℵ_{0} categorical.

As is pointed out in Shore [1982], the proof that all finite partial lattices with the trace probe property can be embedded in R actually shows that any such recursive partial lattice can be embedded in R. Shore [1982] also constructs, for each subset A of the natural numbers, a finitely generated partial lattice L_{A} of this type which is recursive in A and codes A in the sense that A is recursive in the jump of any presentation of L_{A} even as an usl. As L_{A} is finitely generated, A is then also recursive in any usl in which L_{A} can be embedded as a partial lattice. As usual, the proof of the embedding theorem for recursive partial lattices with the trace probe property relativizes to any degree a. Thus L_{A} can be embedded in the degrees r.e. in and above a for any degree a. As the degrees r.e. in and above a can be presented as an usl recursive in a^{(3)}, this suffices to refute (C2)′. Strengthening the result to apply to partial lattices recursive in a^{(2)} and applying the same sort of argument about complexity of presentations provides another direct reflection of the complexity of R.

Theorem 14 (Shore [1982]) If the degrees r.e. in and above a are isomorphic to those r.e. in and above b then a and b are contained in the same arithmetic degree. (In fact, one can get a^{(2)} ≤ b^{(5)}.)^{3}

Corollary 15 (Shore [1982]) The structure R is not recursively presentable, i.e. it is not isomorphic to any recursive partial ordering.

At about the same time Harrington and Shelah [1982] announced the solution to (C1)′:

3Nies, Shore and Slaman [1997] have improved the conclusion to be a′′ = b′′. Indeed they show that if the degrees r.e. in and above a are elementary equivalent to the r.e.

degrees then a′′ = 0′′.

Theorem 16 (Harrington and Shelah [1982]) The theory of R is undecidable.

As the proof of undecidability includes a definable coding of partial orderings into R which, of course also relativizes, it also supplies another refutation of (C2)′ as well. (Once again the argument is based on the complexity of presentations of the degrees r.e. in d.) While finitely generated codings suffice for (C2)′ and such isomorphism results, the codings needed for undecidability must be more explicit. Interpreting a theory in R requires a definable coding scheme. Harrington and Shelah [1982] exploit the new priority techniques introduced in Lachlan [1975] to construct sets of degrees which are definable from finitely many parameters. These sets are then used as the domains for partial orderings defined by other parameters.

Theorem 17 (Harrington and Shelah [1982]) For each partial ordering ⟨P, ≤⟩ recursive in 0′ there are r.e. degrees a, b, c, d such that if M = {x| x is maximal among the degrees below a such that c ≰ b ∨ x} and ⪯ is defined on M by x ⪯ y ⇔ x ≤_{T} y ∨ d, then ⟨M, ⪯⟩ ≅ ⟨P, ≤⟩ .

The new type of constructions needed to prove this theorem were originally called “monstrous injury arguments” because of their complexity. Lachlan, introduced them to prove that the Sacks Splitting and Density theorems cannot be combined:

Theorem 18 (Lachlan [1975]) There are r.e. degrees d < a for which there are no r.e. degrees b, c such that d < b, c < a and b ∨ c = a.

These arguments are now called 0′′′ constructions because an oracle for 0′′′ is needed to determine how the requirements are satisfied. In this terminology, introduced by Harrington, finite and infinite injury arguments are, respectively, 0′ and 0′′ constructions. There are now simpler proofs of the undecidability of R (Slaman and Woodin [ta] and Ambos-Spies and Shore [1993]) that do not rely on Lachlan’s 0′′′ methods but the method itself has continued to play a crucial role in the study of the r.e. degrees.

The next step in the elucidation of the complexity of R was the characterization of the degree of its theory: It is as complicated as possible.

Theorem 19 (Harrington and Slaman; Slaman and Woodin [ta]) The theory of R is recursively isomorphic to that of true first order arithmetic.^{4}

A similar path had been followed somewhat earlier in the study of D. As we have mentioned, its undecidability follows from initial segment embedding results (Theorem 8 or (C6)). The first proofs that its theory is as complicated as possible exploited such results along with Spector’s theorem [1957] on exact pairs : If I is a countable ideal in D then there are degrees x, y such that I = {z| z ≤ x, y}.

Theorem 20 (Simpson [1977]) The theory of D is recursively isomorphic to that of true second order arithmetic.

Nerode and Shore [1980] and [1980a] produced another proof of this theorem as well as many other results on the global structure of D. In particular, they proved that every automorphism ϕ of D is the identity on a cone, i.e. ∃z∀x ≥ z(ϕ(x) = x). A more precise calculation of the base of such cones combined with results of Jockusch and Soare [1970] and either Jockusch [1973] or Harrington and Kechris [1975] on cones of minimal covers (see the discussion of (Q2)′ of [1966] below) led to the refutation of (C3)′:

Theorem 21 (Shore [1979]) If d ≥O (the complete Π_{1}^{1} set), then the degrees above d are not order isomorphic to D.

Now the failure of (C3)′, like that of (C2)′, was not due to a counterexample to the phenomena of relativization which prompted Rogers to suggest the conjecture. Indeed, in each case, the proofs relied heavily on relativizing many results on the structure of D and R to other degrees. Their failure was due instead to the fact that the degrees, like the r.e. degrees, are much more complicated than was expected in the 1960’s. Had D and R been simply characterizable along the lines of density and Shoenfield’s conjecture, then both conjectures would have been true. The problem was that they turned out to be much more complicated. More to the point, they turned out to be so complicated that the degrees above any d, and indeed even those r.e. in d, are in many senses as complicated as possible. As complicated as possible implies that the structures reflect or encode the complexity inherent in the given degree d. This was precisely the method of refuting (C2)′ described above. It also lies at the heart of the refutation of (C3)′ as can be seen from the proof of a stronger result.

4See Nies, Shore and Slaman [1997] for a new proof of this result and various definability results for R.

Theorem 22 (Shore [1982a]) If d ≥O, then the degrees above d are not elementarily equivalent to D.

The key idea in this paper is an extension (implicit in Simpson [1977]) of the idea that one can code second order arithmetic in D. The crucial procedure is to define in D, not only standard models of arithmetic, but also a map taking a degree d to (the code for) a set (in the defined model of arithmetic) which has degree d. One can then translate any property definable in arithmetic into the degrees. In particular, any relation on degrees definable in second order arithmetic becomes definable in D with such a translation.

Actually, the map constructed in Shore [1982a] worked correctly only on sufficiently large degrees (the ones above O). Thus corollaries on definability and failure of homogeneity worked only for such degrees. Since then, much work has been devoted to extending and improving these results. An important step was taken in Jockusch and Shore [1984] where they defined the class of degrees of arithmetic sets in D and so brought “sufficiently large” down to 0^{(ω)}.

Now, many of the results in this area had earlier proofs or more refined versions for the degrees with the jump operator. (Including, for example, the refutation of the homogeneity conjecture with the jump operator by Feiner [1970].) A truly remarkable result of Cooper’s then eliminated the need for the added hypothesis.

Theorem 23 (Cooper [1990], [ta]) The jump operator is definable in D (from just the ordering Turing reducibility). In fact, the relation “a is r.e. in b” is definable in D.

Together with earlier results of Nerode and Shore [1980a], this theorem brought sufficiently large down to 0′′′. Slaman and Woodin [1986] developed a considerably simpler approach to coding second order arithmetic in D.

They then introduced techniques from set theory, including forcing and absoluteness, to push these result even farther. “Sufficiently large” came down to 0′′.^{5} They have conjectured that the true answer is 0.

Biinterpretability Conjecture for D (Slaman and Woodin [ta], see Slaman [1991]): There is a definable coding of true second order arithmetic in D for which the map taking a degree d to the code in the model for a set of degree d is also definable.^{6}

This conjecture really expresses the strongest form of our new view of the structure of the degrees as being as complicated as possible. We should stress, however, that it does not represent a failure of our attempts to characterize the ordering of the degrees. Rather, it is itself a strong characterization of the structure of D. It would provide complete information for example about definability in D (everything possible would be definable) and automorphisms for D (none other than the identity would exist). Slaman and Woodin [ta] have proven many remarkable results related to this conjecture both for D and for many other degree structures. We cite a few and refer to Slaman [1991] and [1997] for a more complete summary.

Theorem 24 (Slaman and Woodin [ta]) There are at most countably many automorphisms of D.

Theorem 25 (Slaman and Woodin [ta]) Second order arithmetic is biinterpretable in D with parameters, i.e. the definitions required in the biinterpretability conjecture can be given using parameters from D.

Theorem 26 (Slaman and Woodin [ta]) D is rigid, i.e. it has no automorphisms other than the identity, if and only if it is biinterpretable with second order arithmetic.

A similar change has taken place in our attitude toward the r.e. degrees. They too seem as complicated as possible. As mentioned above, this has been verified for the theory of R, but we have fewer other results supporting the corresponding conclusion. In particular, there are as yet no results on definability or automorphisms.^{7} Nonetheless, the analogous conjecture has been proposed.

5See Nies, Shore and Slaman [1997] for a new proof of this result by simply improving the coding procedures.

6Cooper [1996] has announced that there is there is a nontrivial automorphism of D and hence the biinterpretability conjecture fails.

Biinterpretability Conjecture for R (Harrington; Slaman and Woodin [ta], see Slaman [1991]): There is a definable coding of first order arithmetic in R for which the map taking an r.e. degree d to the code in the model for a set of degree d is also definable.^{8}

As with D, this strong conjecture would imply that R is rigid and every relation on r.e. degrees definable in arithmetic is definable in R. It too then represents a new proposal for a solution to the problem of characterizing the ordering of the r.e. degrees quite different from the ones that Sacks was considering in [1963] and [1966]. Surprisingly, the conjecture for R implies the one for D. Indeed, even more is true.

Theorem 27 (Slaman and Woodin [ta]) If R is rigid then so is D. In fact, there are finitely many r.e. degrees a_{1}, …, a_{n} such that if Φ is an automorphism of D with Φ(a_{i}) = a_{i} for each i ≤ n, then Φ is the identity map.

We conclude our paper with a discussion of the four questions posed at the end of [1966] that did not appear in [1963]. (The one carried over, (Q4), was discussed above.)

(Q1)′ Does there exist a Gödel number e such that for all sets A, W_{e}^{A}, the e^{th} set recursively enumerable in A, is of higher degree than A and of lower degree than A′, and such that if A and B have the same degree, then W_{e}^{A} and W_{e}^{B} have the same degree?

7Nies, Shore and Slaman [1997] have shown that every automorphism of R preserves the double jump and that all relations on R which are definable in arithmetic and invariant under the double jump are definable in R.

8Cooper [1996] has announced that there is a nontrivial automorphism of R and indeed one that moves a low degree to a nonlow one. This implies that the biinterpretability conjecture for R also fails.

(Q2)′ Is the elementary theory of the ordering of degrees elementary equivalent to the elementary theory of the degrees of arithmetical sets?

(Q3)′ Is there some simple property of complements of r.e. sets (in the style of Post) which implies noncompleteness?

(Q5)′ Is there an elementary difference between the ordering of r.e. degrees and the ordering of metarecursively enumerable degrees?

Both (Q1)′ and (Q3)′ deal with Post’s problem from [1944] to construct an incomplete nonrecursive r.e. set. As we have mentioned, it was solved with the introduction of the priority method by Friedberg [1957] and Muchnik [1956]. The first question asks for what is now called an invariant solution to Post’s problem as it asks for a single construction procedure that gives a solution to the relativized version of Post’s problem (an e such that for every A, A <_{T} W_{e}^{A} < A′) which is invariant with respect to the degree of the oracle. Lachlan [1975a] proved that there is no such solution with certain additional uniformities.

Theorem 28 (Lachlan [1975]) There is no index e as required in (Q1)′ with the additional property that indices for the reductions between W_{e}^{A} and W_{e}^{B} can be found uniformly from ones for the reductions between A and B.

Further work on this problem has been intimately connected with two very sweeping conjectures by Martin about the nature of degree invariant maps under the assumption of the axiom of determinacy. Roughly speaking, the conjectures say that, in the sense appropriate to working with AD, the only (definable) degree invariant operators that always increase degree are the various jump operators and their iterates. Much has been done to characterize such functions. We cite, in particular, the work of Steel [1982], Slaman and Steel [1988] and especially Becker [1988]. From this point of view, Sacks’s question essentially asks if there is a counterexample of a very special type to Martin’s conjectures. The original question, however, remains open. It too will surely require a new idea.^{9}

9Exploiting the work of Steel [1982], Downey and Shore [1966] have shown that any such invariant solution must be low_{2} or high_{2} for all sufficiently large degrees a, i.e., there is a c

Post’s own approach to his problem of constructing a nonrecursive incomplete r.e. set was to try to find a set theoretic property of an r.e. set which would guarantee incompleteness but still be compatible with the set theoretic property of nonrecursiveness. (An r.e. set is recursive if and only if it has an r.e. complement.) The work on this program has motivated much of the study of the set theoretic properties of r.e. sets and in particular the analysis of the lattice E of the r.e. sets under inclusion. Post himself suggested several “simplicity” type properties of an r.e. set implying that its complement is “thin”. While some of these properties guaranteed incompleteness with respect to stronger reducibilities, none seemed to work for Turing degree. Yates’ [1965] proof that maximal sets (which by definition have the “thinnest” possible complement) can be complete showed that this particular approach could not work. On the other hand, Marchenkov [1976] proved that, if one extends Post’s notions by considering both semirecursiveness and the structures derived by dividing E by r.e. equivalence relations, one can guarantee incompleteness by such simplicity type properties.

Theorem 29 (Marchenkov [1976]) No η-maximal semirecursive r.e. set is Turing complete. (An r.e. set A is semirecursive if there is a recursive function f such that f(x, y) ∈ A if either x or y belongs to A; it is η-maximal if it is a maximal element of the lattice of r.e. sets modulo the r.e. equivalence relation η.)

On the other hand, Cholak, Downey and Stob [1992] proved that no property of an r.e. set A which is definable in terms of the lattice of supersets of A alone can guarantee incompleteness and still be compatible with nonrecursiveness as required in (Q3)′.

Theorem 30 (Cholak, Downey and Stob [1992]) For every r.e. A there is a complete r.e. C such that the lattice of r.e. supersets of A is isomorphic to that of C.

On yet the other hand (we seem to need many for this problem), Harrington and Soare have found a lattice theoretic property that guarantees both incompleteness and nonrecursiveness and so provides a positive answer to (Q3)′ for this interpretation of “in the style of Post”.

such that if W_{e}^{A} is degree invariant and increasing in degree then (∀a > c)((W_{e}^{A})′′ ≡_{T} A′′)

or (∀a > c)((W_{e}^{A})′′ ≡_{T} A′′′).

Theorem 31 (Harrington and Soare [1991]) There is a class Q of r.e. sets definable in the lattice of r.e. sets such that any r.e. set A in Q is nonrecursive and incomplete. ^{10}

Basic information about the lattice of r.e. sets can be found in Soare [1987] and a current survey in Soare [1997]. A treatment of the route to Post problem through strong reducibilities and η-maximal sets can be found in Odifreddi [1989, III.3-5].

The remaining two questions (Q2)′ and (Q5)′ once again return us to the theme of the complexity of the theories of R and D. Again, had the nature of degree structures turned out to be “simple” the answers to these questions would presumably have been “yes”. By now, we know enough to expect the answers to be “no”. Indeed, as we know by Theorem 20, the theory of D is recursively isomorphic to that of true second order arithmetic. Thus it cannot possibly be the same as that of the degrees of the arithmetic sets. (The degree of the latter theory is clearly too low.) In fact, the theories of jump ideals, i.e. classes of degrees closed downward and under jump, are equivalent to the corresponding models of arithmetic.

Theorem 32 (Nerode and Shore [1980a]) If C is a jump ideal then the theory of C with the relation of Turing reducibility is recursively isomorphic to that of the structure of second order arithmetic with underlying domain N and set quantification over the sets with degrees in C.

This theorem distinguishes among the theories of the standard jump ideals and so, in particular answers (Q2)′. The first answer to this question, however, came from a study of minimal covers. (A degree b is a minimal cover of a, if a < b and there are no degrees strictly between them.) Jockusch and Soare [1970] uncovered enough about the nature of minimal covers to refute (Q2)′.

Theorem 33 (Jockusch and Soare [1970]) No 0^{(n)} is a minimal cover. On the other hand, there is a degree x such that every y ≥ x is a minimal cover.

(Actually, in [1970] Jockusch and Soare could only note that the second fact follows from Borel determinacy. Jockusch [1973] showed that determinacy for Σ_{4}^{0} sets (which was known to provable in ZFC) sufficed. Of course, Martin [1975] later proved full Borel determinacy in ZFC. Later Harrington and Kechris [1975] showed that open determinacy sufficed and so every degree above O is a minimal cover. This result was the one used in the refutation of (C3) given by Theorem 21. Jockusch and Shore [1983], [1984] introduced and developed the pseudojump operators to show that every degree above 0^{(ω)} is a minimal cover. This result is the best possible by the above theorem. They then used an extension of this result to define the degrees of the arithmetic sets in D as mentioned above.)

10Many more results along these lines are announced in Harrington and Soare [1996].

The final question of [1966], (Q5)′, reflects the beginning of the interest that became Sacks’s primary mathematical passion for the next twenty five years or more: generalized recursion theory. Except for a brief fling with applications of recursion theory to set theory [1969], [1971] and a somewhat extended affair with model theory [1972], [1972a], Sacks’s mathematical energies were devoted to the development of recursion theory on ordinals (admissible and nonadmissible) and set (or E) recursion. This work was capped with his publication of the book in the field Higher Recursion Theory [1990].

Metarecursion theory is a special case of recursion theory on admissible ordinals α where the ordinal α is ω_{1}^{CK}, the first nonrecursive ordinal and so the Church-Kleene effective analog of ω_{1}, the first uncountable ordinal. Although metarecursion is intimately tied to hyperarithmetic theory as well as Kleene’s recursion in higher types, the simplest way to define its concerns (and those of recursion on admissible ordinals α in general) is in terms of Gödel’s constructible universe, L. In α-recursion theory, as the subject is often called, the natural numbers are replaced by the ordinals below α; recursive enumerability becomes Σ_{1} over L_{α}; the finite sets are the members of L_{α}; the appropriate definition of relative computability, ≤_{α}, on subsets of α corresponds to the one in Rogers [1967, §9.2] for sets of natural numbers:

A ≤_{α} B iff there is an r.e. W such that, for every K, K ⊆ A ⇔ (∃ ⟨K, 1, L, M⟩ ∈ W)(L ⊆ B ∧ M ⊆ B̄) and K ⊆ Ā ⇔ (∃ ⟨K, 0, L, M⟩ ∈ W)(L ⊆ B ∧ M ⊆ B̄).

Here K, L, M range over α-finite subsets of α.

A primary motivation for developing α-recursion theory was to analyze the methods and assumptions underlying the classical constructions of recursion theory, in particular, priority arguments and constructions of r.e. sets. Kripke [1964] and Platek [1966] first suggested that admissibility (equivalently Σ_{1} replacement) should be the fundamental axiom for recursion theory on ordinals. The early work in on metarecursion theory (as in Kreisel and Sacks [1965]) and then the extensive development of recursion theory on all admissible ordinals by Sacks, his students and collaborators confirmed that admissibility was indeed a sufficient condition to carry out most of the arguments and constructions of classical recursion theory. (An early survey and introduction can be found in Shore [1977] and a current one in Friedman [1997]. Of course, the current comprehensive reference is Sacks [1990].) Even when certain constructions could not be carried out for all admissible ordinals, it seemed that they could be done with the added assumptions available for ω_{1}^{CK}. (The crucial one is that there is an α-recursive one-one map from ω_{1}^{CK} into ω.) This state of affairs, naturally would lead one to believe that there should be an affirmative answer to (Q5)′. Once again, however, the theme that the r.e. degrees are as complicated as possible suggests instead that this very phenomena of metarecursion mimicking recursion theory on ω should lead to a negative solution.

The first related result came at the level of isomorphism rather than elementary equivalence. The theorems on r.e. degrees that lead to a negative solution to (C2)′ supplied the tools needed.

Theorem 34 (Odell [1983]) Any ω_{1}^{CK}-recursive partial lattice with a property similar to the trace probe property can be embedded in the ω_{1}^{CK}-r.e. degrees. These lattices include the ones L_{A} used in the proof of Theorem 14 for every ω_{1}^{CK}-recursive A.

Corollary 35 (Odell [1983]) The ordering of the ω_{1}^{CK}-r.e. degrees is not arithmetically presentable and so not isomorphic to R.

In line with our new philosophy, when Harrington and Slaman announced that the theory of the r.e. degrees was equivalent to true first order arithmetic, we were (as Sacks often says) “morally certain” that the answer to (Q5)′ was “no”. Moreover, it was clear that the way to prove the result was to carry out enough of a proof of Theorem 19 in metarecursion theory to code a standard model of arithmetic with an additional predicate for a set which, in ω_{1}^{CK}- recursion theory, could be chosen to be nonarithmetic. (Of course, in the r.e. degrees only arithmetic sets can be coded in standard models.) Carrying out this idea awaited a comprehensible manageable proof of Theorem 19. One was supplied by Slaman and Woodin [ta]. The details of both the statements and proofs of the coding theorems needed in metarecursion theory will appear in Shore and Slaman [ta]. For now we are content to give the solution to the last question of [1966]:

Theorem 36 (Shore and Slaman [ta]) The metarecursively enumerable degrees are not elementarily equivalent to the r.e. degrees.

Bibliography

Abraham, U. and Shore, R. A. [1986], Initial segments of the Turing degrees of size ℵ_{1}, Israel J. Math. 55, 1-51.

Ambos-Spies, K. and Lerman, M. [1986], Lattice embeddings into the recursively enumerable degrees, J. Symb. Logic 51, 257-272.

Ambos-Spies, K. and Lerman, M. [1989], Lattice embeddings into the recursively enumerable degrees II, J. Symb. Logic 54, 735-760.

Ambos-Spies, K. and Shore, R. A. [1993], Undecidability and 1-types in the r.e. degrees, Ann. Pure and Applied Logic 63, 3-37.

Becker, H. [1988], A characterization of jump operators, J. Symb. Logic 53, 708-728.

Cholak, P., Downey, R. and Stob, M. [1992], Automorphisms of the lattice of recursively enumerable sets: promptly simple sets, Trans. Am. Math. Soc. 332, 555-570.

Cooper, S. B. [1972], Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. 5, 445-450.

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. [ta], The recursively enumerable degrees are absolutely definable, to appear.

Cooper, S. B. [1996], Beyond Gödel’s theorem: the failure to capture information content, University of Leeds, Department of Pure Mathematics Preprint Series, No. 4.

Cooper, S. B. [1997], The degrees below 0′, in Handbook of Recursion Theory, E. Griffor ed., North-Holland, Amsterdam, in preparation.

Downey, R. G. and Shore, R. A. [1997], There is no degree invariant half-jump, Proc. Am. Math. Soc., to appear.

Feiner, L. [1970], The strong homogeneity conjecture, J. Symb. Logic 35, 375-377.

Friedberg, R. M. [1957], Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Ac. Sci. 43, 236-238.

Friedman, S. D. [1997], Recursion theory on ordinal numbers, in Handbook of Recursion Theory, E. Griffor ed., North-Holland, Amsterdam, in preparation.

Groszek, M. S. and Slaman, T. A. [1983], Independence results on the global structure of the Turing degrees, Trans. Am. Math. Soc. 277, 579-588.

Harrington, L. [1975], Arithmetically incomparable arithmetic singletons, unpublished manuscript, 28 pp.

Harrington, L. and Kechris, A. S. [1975], A basis result for Σ_{3}^{0} sets of reals with an application to minimal covers, Proc. Am. Math. Soc. 53, 445-448.

Harrington, L. and Shelah, S. [1982], The undecidability of the recursively enumerable degrees (research announcement), Bull. Am. Math. Soc., N.S. 6, 79-80.

Harrington, L. and Slaman, T. [1990], The theory of the r.e. degrees, in preparation.

Harrington, L. and Soare R. I., [1991], Post’s program and incomplete recursively enumerable sets, Proc. Nat. Ac. Sci. 88, 10242-10246.

Harrington, L. and Soare R. I., [1996], Definability, automorphisms and dynamic properties of computably enumerable sets, Bull. Symb. Logic 2, 199-213.

Jockusch, C. G. Jr. [1973], An application of Σ_{4} determinacy to the degrees of unsolvability, J. Symb. Logic 38, 293-294.

Jockusch, C. G. Jr. and Shore, R. A. [1983], Pseudo-jump operators I: the r.e. case, Trans. Am. Math. Soc. 275, 599-609.

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.

Jockusch, C. G. Jr. and Soare, R. I. [1970], Minimal covers and arithmetical sets, Proc. Am. Math. Soc. 25, 856-859.

Kleene, S. C. and Post, E. [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. Math. (2) 59, 379-407.

Kreisel, G. and Sacks, G. E. [1965], Metarecursive sets, J. Symb. Logic 30, 318-338.

Kripke, S. [1964], Transfinite recursion on admissible ordinals I, II (abstracts), J. Symb. Logic 29, 161-162.

Kurtz, S. A. [1979], Randomness and genericity in the degrees of unsolvability, Thesis, University of Illinois.

Lachlan, A. H. [1965], On a problem of G. E. Sacks, Proc. Am. Math. Soc. 16, 972-979.

Lachlan, A. H. [1966], Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. 16, 537-569.

Lachlan, A. H. [1966a], The impossibility of finding relative complements for recursively enumerable degrees, J. Symb. Logic 31, 434-454.

Lachlan, A. H. [1968], Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grund. Math. 14, 457-472.

Lachlan, A. H. [1972], Embedding nondistributive lattices in the recursively enumerable degrees, in Conference in Mathematical Logic, London, 1970, W. Hodges ed., LNMS 255, Springer-Verlag, Berlin, 149-172.

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

Lachlan, A. H. [1975a], Uniform enumeration operators, J. Symb. Logic 40, 401-409.

Lachlan, A. H. and Lebeuf, R. [1976], Countable initial segments of the degrees of unsolvability, J. Symb. Logic 41, 289-300.

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. [1997], A finite lattice without critical triples that cannot be embedded into the enumerable Turing degrees, Ann. Pure and Applied Logic, to appear.

Lerman, M. [1971], Initial segments of the degrees of unsolvability, Ann. of Math. (2) 93, 365-389.

Lerman, M. [1983], Degrees of Unsolvability, Springer-Verlag, Berlin. Lerman, M., Shore, R. A. and Soare, R. I. [1984], The elementary theory

of the recursively enumerable degrees is not ℵ_{0}-categorical, Adv. in Math. 53, 301-320 .

Marchenkov, S. S. [1976], A class of incomplete sets, Mat. Zametki 20, 473-478 (English trans, Math. Notes 20, 823-825).

Martin, D. A. [1966], On a question of G. E. Sacks, J. Symb. Logic 35, 205-209.

Martin, D. A. [1967], Measure, category and degrees of unsolvability, unpublished manuscript, 16 pp.

Martin, D. A. [1975], Borel determinacy, Ann. Math. (2) 102, 363-371. Muchnik, A. A. [1956], On the unsolvability of the problem of reducibility

in the theory of algorithms, Dokl. Akad. Nauk SSSR N.S. 108, 29-32.

Nerode, A. and Shore, R. A. [1980], Second order logic and first order theories of reducibility orderings in The Kleene Symposium, J. Barwise, H. J. Keisler and K. Kunen, eds., North-Holland, Amsterdam, 181-200.

Nerode, A. and Shore, R. A. [1980a], Reducibility orderings: theories, definability and automorphisms, Ann. Math. Logic 18, 61-89.

Nies, A., Shore, R. A. and Slaman, T. [1997] Interpretability and definability in the recursively enumerable degrees, to appear.

Odell, D. [1983], Trace constructions in α-recursion theory, Thesis, Cornell University.

Odifreddi, P. [1989], Classical Recursion Theory, North-Holland, Amsterdam.

Paris, J. B. [1977], Measure and minimal degrees, Ann. Math. Logic 11, 203-216.

Platek, R. [1966], Foundations of Recursion Theory, Thesis, Stanford University.

Posner, D. [1980], A survey of non-r.e. degrees below 0′, in Recursion Theory: Its Generalizations and Applications, F. Drake and S. Wainer eds., LMSLNS 45, Cambridge University Press, Cambridge, England, 52-109.

Posner, D. [1981], The upper semilattice of degrees ≤ 0′, J. Symb. Logic 46, 705-713.

Post, E. L. [1944], Recursively enumerable sets of positive integers and their decision problems, Bull. Am. Math. Soc. 50, 284-316

Rogers, H. Jr. [1967], Some problems of definability in recursive function theory, in Sets, Models, and Recursion Theory, Proceedings of the Summer School in Mathematical Logic and 10^{th} Logic Colloquium, Leicester, August-Sept. 1965, J. N. Crossley ed., North-Holland, Amsterdam.

Rogers, H. Jr. [1967a], Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York.

Sacks, G. E. [1963], Degrees of unsolvability, Annals of Math. Studies 55, Princeton Univ. Press, Princeton NJ.

Sacks, G. E. [1963a], Recursive enumerability and the jump operator, Trans. Am. Math. Soc. 108, 223-239.

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

Sacks, G. E. [1964], The recursively enumerable degrees are dense, Ann. of Math. (2) 80, 300-312.

Sacks, G. E. [1966], Degrees of unsolvability, Annals of Math. Studies 55, Princeton Univ. Press, 2^{nd} ed., Princeton NJ .

Sacks, G. E. [1967], On a theorem of Lachlan and Martin, Proc. Am. Math. Soc. 18, 140-141.

Sacks, G. E. [1969], Measure theoretic uniformity in recursion theory and set theory, Trans. Am. Math. Soc. 142, 381-420.

Sacks, G. E. [1971], Forcing with perfect closed sets, in Axiomatic Set Theory, Proc. Symp. Pure Math. 13, D. Scott ed., Am. Math. Soc., Providence, 331-355.

Sacks, G. E. [1972], The differential closure of a differential field, Bull. Am. Math. Soc. 78, 629-634.

Sacks, G. E. [1972a], Saturated Model Theory, W. A. Benjamin, Inc., Reading, Mass.

Sacks, G. E. [1990], Higher Recursion Theory, Springer-Verlag, Berlin. Shoenfield, J. R. [1959], On degrees of unsolvability, Ann. Math. (2) 69,

644-653.

Shoenfield, J. R. [1961], Undecidable and creative theories, Fund. Math. 49, 171-179.

Shoenfield, J. R. [1965], An application of model theory to degrees of unsolvability, in Symposium on the Theory of Models, J. W. Addison, L. Henkin and A. Tarski eds., North-Holland, Amsterdam, 359-363.

Shoenfield, J. R. [1966], A theorem on minimal degrees, J. Symb. Logic 31, 539-544.

Shore, R. A. [1977], α-Recursion theory, in Handbook of Mathematical Logic, J. Barwise ed., North-Holland, Amsterdam, 653-680.

Shore, R. A. [1979], The homogeneity conjecture, Proc. Nat. Ac. Sci. 76, 4218-4219.

Shore, R. A. [1982], Finitely generated codings and the degrees r.e. in a degree d, Proc. Am. Math. Soc. 84, 256-263.

Shore, R. A. [1982a], On homogeneity and definability in the first order theory of the Turing degrees, J. Symb. Logic 47, 8-16.

Shore, R. A. [1997], The recursively enumerable degrees, in Handbook of Recursion Theory, E. Griffor ed., North-Holland, Amsterdam, in preparation.

Shore, R. A. and Slaman, T. A. [ta], The metarecursively enumerable degrees are not elementarily equivalent to the recursively enumerable degrees, in preparation.

Simpson, S. G. [1977], First order theory of the degrees of recursive unsolvability, Ann. Math. (2) 105, 121-139.

Slaman, T. A. [1991], Degree structures, in Proc. Int. Cong. Math., Kyoto 1990, Springer-Verlag, Tokyo, 303-316.

Slaman, T. A. [1997], The global Turing degrees, in Handbook of Recursion Theory, E. Griffor ed., North-Holland, Amsterdam, in preparation.

Slaman, T. A. and Soare, R. I. [1995], Algebraic aspects of the computably enumerable degrees, Proc. Nat. Ac. Sci. 92, 617-621.

Slaman, T. A. and Soare, R. I. [1997], Extension of embeddings in the recurisvely enumerable degrees, to appear.

Slaman, T. A. and Steel, J. R. [1989], Complementation in the Turing degrees, J. Symb. Logic 54, 160-176.

Slaman, T. A. and Steel, J. R. [1988], Definable functions on degrees, in Cabal Seminar 81-85, A. S. Kechris, D. A. Martin and J. R. Steel eds., LNMS 1333, Springer-Verlag, Berlin, 37-55.

Slaman, T. A. and Woodin, W. H. [1986], Definability in the Turing degrees, Ill. J. Math. 30, 320-334.

Slaman, T. A. and Woodin, W. H. [1997], Definability in Degree Structures, in preparation.

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

Soare, R. I. [1997], The lattice of recursively enumerable sets, in Handbook of Recursion Theory, E. Griffor ed., North-Holland, Amsterdam, in preparation.

Spector, C. [1956], On degrees of recursive unsolvability, Ann. Math. (2) 64, 581-592.

Steel, J. R. [1982], A classification of jump operators, J. Symb. Logic 47, 347-358.

Yates, C. E. M. [1965], Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32, 461-468.

Yates, C. E. M. [1966], A minimal pair of recursively enumerable degrees, J. Symb. Logic 31, 159-168.

Yates, C. E. M. [1966a], On the degrees of index sets, Trans. Am. Math. Soc. 121, 309-328.

Yates, C. E. M. [1970], Initial segments of degrees of unsolvability, Part II: minimal degrees, J. Symb. Logic 35, 243-266.