Degree Structures: Local and Global Investigations

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

January 15, 2006

1 Introduction

The occasion of a retiring presidential address seems like a time to look back, take stock and perhaps look ahead.

Institutionally, it was an honor to serve as President of the Association and I want to thank my teachers and predecessors for guidance and advice and my fellow officers and our publisher for their work and support. To all of the members who answered my calls to chair or serve on this or that committee, I offer my thanks as well. Your work was both needed and appreciated.

A major component of the efforts of the Association is devoted to our publications. My first important task as President was to deal with the need to reorganize the reviews section of the JSL and eventually to move it to the BSL. Appropriately enough, my first administrative job for the Association, some thirty years ago, was to serve on a committee to plan a reorganization of the reviews. I thank all those who helped with this transition and who took over the task of running the new reviews section. I hope that it will be another thirty years before further major changes are needed in this area and that someone else will be making them.

When I began my term as President, we had a number of other projects in mind. On some we have made significant progress. Among these were developing our book publishing venture, extending our presence in electronic publishing, strengthening our relations with the logic/computer science community and increasing support for students and postdocs. Looking forward, more needs to be done in these areas and new ones will continue to arise. I am glad to see the new President, officers and publisher well on their own way to maintaining and improving the Association. I urge all of you to answer their calls to serve and take on the many and varied tasks needed to keep the Association strong and serve our community.

∗This paper is a slightly expanded version of the Retiring Presidential Address delivered to the ASL at the 2005 Annual Meeting at Stanford University, Palo Alto CA. The work was partially supported by NSF Grant DMS-0100035.

We turn now to our taking stock in the mathematical realm. For the last few years, I have worked to a large extent on what some might call applications of recursion theory to effective algebra, combinatorics and model theory, reverse mathematics and related issues. My long term primary interests, however, have certainly been in the study of relative complexity in its “pure” setting of degree theory. Of particular interest, has been the relation between the ordering of relative computability and issues of definability, automorphisms and the complexity of the theories of the orderings.

There are many notions of relative complexity of computation and I have worked on a fair number of them ranging from polynomial time to relative constructibility. All of these notions have their own interest and uses along with their specific flavor and challenges. I have always felt, however, that the primary and foundationally most important notion of both absolute and relative computability is that of Gödel-Herbrand, Church-Kleene and Turing. So in this paper I will discuss only Turing reducibility and degrees. Although these have been fruitfully studied in a variety of settings and domains and much of what we will say is relevant to other structures, we will further restrict our attention to the three most studied structures: the recursively enumerable degrees, R; the degrees computable in the halting problem, D(≤ 0′); and the degrees of all sets and functions, D. Our plan is to briefly outline past results, views and directions; consider some changes over time and, finally, to suggest some questions for the future.

2 Degree Structures

Much of the early work in degree theory can be seen as a purely algebraic/order-theoretic investigation of the upper semilattice (usl) or partial order structure of R, D(≤ 0′) and D as well as the development of important techniques and construction procedures. It begins with the study of embedding problems to understand or characterize the class of substructures of these degree orderings. For D and D(≤ 0′) the countable case was settled in the first paper on the structure D of the Turing degrees as a whole, Kleene-Post [1954], using the finite extension method that they developed. (From a more modern viewpoint this method is essentially Cohen forcing for one quantifier formulas of arithmetic.)

Theorem 2.1. (Kleene-Post [1954]) Every countable partial ordering or usl can be embedded into D and even D(≤ 0′).

For R, the corresponding results relied on the development of the finite injury (or 0′) method by Friedberg [1957] and Muchnik [1958].

Theorem 2.2. (Friedberg [1957], Muchnik [1958], Sacks [1963]) Every countable partial ordering or even usl can be embedded into R.

After embedding usls the next level of algebraic questions about the structures concern extension of embeddings. The first example here is density (or, from the other side minimal degrees or covers). At this level the structures diverge. The existence of minimal degrees in D was proven by Spector [1956] and in D(≤ 0′) by Sacks [1961]. The key idea in Spector’s construction was what is now called forcing with perfect (recursive) trees. Sacks uses partial trees and a priority argument as well.

Theorem 2.3. (Spector [1956]; Sacks [1961]) There are minimal degrees in D and, in fact, in D(≤ 0′). Indeed, every degree x has a minimal cover y < x′ (i.e. there is no z with x < z < y).

On the other hand, Sacks proved that the r.e. degrees are dense and that every nonzero element can be split in two. Sacks’s proof of the density theorem built on the splitting theorem and introduced infinite injury (or 0′′) arguments into the study of R. (Somewhat weaker versions of the infinite injury argument had been previously used by Sacks [1963b] in his characterization of the degrees of the jumps of r.e. sets and even earlier by Shoenfield [1961] to produce an r.e. theory not of complete degree in which every recursive function is representable.)

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

Theorem 2.5. (Sacks [1964]) For every pair of nonrecursive r.e. degrees a < b there is one c such that a < c < b.

These results lead Shoenfield [1965] to formulate his famous conjecture presented at the Model Theory Symposium of 1963 in Berkeley. The “niceness” of R suggested by the splitting and density theorems was expressed as the sweeping conjecture that R is a countably saturated usl with least and greatest elements (0 and 1). Thus he suggested that R should be to the theory of such usls as the rationals are to that of linear orderings. A direct formulation of this conjecture can be phrased in terms of extensions of embeddings.

Problem 2.6. (Extension of Embedding) 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.

Conjecture 2.7. (Shoenfield [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.

If true, this conjecture would have implied that the r.e. degrees have many of the familiar properties of structures like dense linear orderings or atomless Boolean algebras which satisfy the corresponding property for the appropriate family of structures. 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. Of course, the existence of minimal degrees precludes such a conjecture for D or D(≤ 0′) but there was still a feeling that these structures should be “nice” in various ways. One important expression of this view was expressed by Rogers [1967] at the 1965 Logic Colloquium.

Conjecture 2.8. (Rogers [1967]) Homogeneity: For every degree d, D(≥ d), the degrees greater than or equal to d are isomorphic to all the degrees D.

Shoenfield’s conjecture was, however, refuted almost immediately. The instance of the extension of embedding problem that failed was the simple one asking for a nonzero z below any given pair of r.e. degrees x and y.

Theorem 2.9. (Lachlan [1966]; Yates [1966]) There is a minimal pair x and y of r.e. degrees, i.e. ones such that ∀z(z ≤ x, y → z = 0).

Nonetheless, the paradigm expressed in Shoenfield’s conjecture of the r.e. degrees being well behaved continued to hold sway. Sacks [1966] proposed two additional conjectures capturing some of the flavor of those of both Shoenfield and Rogers.

Conjecture 2.10. (Sacks [1966]) The theory of R is decidable.

Conjecture 2.11. (Sacks [1966]) For every d, R^{d}, the degrees r.e. in and above d, are isomorphic to the r.e. degrees R.

The investigation of extension of embeddings problems in D and D(≤ 0′) concentrated on continuing that begun with the construction of minimal degrees by trying to determine all the possible lattices or usls which could be initial segments of the structures. This was done through a long series of papers by many authors over a long period of time. Particularly important steps for D were taken by Lachlan [1968] who showed that every countable distributive lattice is isomorphic to an initial segment of D and Lerman [1971] who showed that every finite lattice is as well. Already with Lachlan’s [1968] result one had as a corollary that the theory of D is undecidable. The corresponding result for D(≤ 0′) was achieved in Epstein [1979] and Lerman [1983, XII]. We now have essentially complete classifications.

Theorem 2.12. (Abraham and Shore [1986]) An usl of size ℵ_{1} is isomorphic to an initial segment of D if and only if it has a least element and every element has at most countably many predecessors.

Theorem 2.13. (Lerman [1983, XII]) Every usl with 0 that is recursive in 0′′ is isomorphic to an initial segment of D(≤ 0′).

Theorem 2.14. (Kjos-Hanssen [2002], [2003]) An usl with least and greatest elements is isomorphic to an initial segment of D(≤ 0′) if and only if it is Σ_{3} presentable (i.e. isomorphic to a structure in which ≤ is Σ_{3} and ∨ is Δ_{3} modulo the equivalence relation that a ≡ b ⇔ a ≤ b & b ≤ a.

(The result for D is best possible in ZFC as every element of D has at most countably many predecessors and Groszek and Slaman [1983] show that there is a model in which the continuum is large and there is a lattice of size ℵ_{2} that is not isomorphic to an initial segment of D. There is a small gap in our knowledge for D(≤ 0′) whose nonemptyness is witnessed by the fact (Shore [1981]) that there are usl initial segments of D(≤ 0′) which are not lattices but whose only presentations have degree 0^{(4)}.)

Even though they brought in the specter of the undecidability of the full theories of D and D(≤ 0′), the initial segment results (even for finite lattices) coupled with the methods of Kleene and Post and, for D(≤ 0′), with some additional use of priority and permitting methods from the r.e. degrees, were sufficient to settle the full extension of embedding problem. Essentially, any instance of the problem with the extension to Q not ruled out by realizing P as an initial segment in D (or except for 1 as an initial segment of D(≤ 0′) with all joins of maximal elements being 1 = 0′) can always be realized (Shore [1978]; Lerman [1983, VII.4]; Lerman and Shore [1988]).

The situation for even lattice embeddings in R turned out to be much more complicated. Subsequent results and the structure itself were often viewed as chaotic. Countable distributive lattices are embeddable (Lachlan, Lerman, Thomason; see Soare [1987, IX.2]). Many finite nondistributive lattices are embeddable (e.g. Lachlan [1972], Ambos-Spies and Lerman [1989], Lerman [2000]) but others are not for a variety of reasons (e.g. Lachlan and Soare [1980], Ambos-Spies and Lerman [1986], Lempp and Lerman [1997]). The number of types of r.e. degrees proliferated reaching countably many realized ones in Lerman, Shore and Soare [1984] and Ambos-Spies and Soare [1989] and eventually uncountably many (consistent) one-types in Ambos-Spies and Shore [1993]. The extension of embeddings problem was eventually solved by Slaman and Soare [1995], [2001] but the conjectures of Sacks about the r.e. degrees and Rogers about D all turned out to be false (Harrington and Shelah [1982], Shore [1982] and Shore [1979], [1982a], respectively). All in all, it was some twenty years after the refutation of Shoenfield’s Conjecture that a dramatically different view become the prevailing paradigm.

We will follow two lines of development both starting with the undecidability of our degree structures. The first seeks to find the dividing line (in terms of fragments of the theories) between decidability and undecidability. This provides, on one side, a full algebraic understanding relative to the fragment of the structure. On the other side, it requires the most precise information necessary to do coding and get undecidability. It could well have been followed on its own but, in fact, it used both methods and ideas from the second.

The second line of investigation begins with showing that the full theories are as complicated as possible. This road leads to the global analysis of definability and automorphisms and a new paradigm. Rather than seeing the complexity of the structures as an obstacle to characterization, it suggests that a sufficiently strong proof of complexity would completely characterize each structure. Instead of expecting the structure to be decidable and homogeneous, for all degrees to look the same and for there to be many automorphisms, one looks to prove that the theory is as complicated as possible, there are as many different types of degrees as possible and that the structure is rigid. At the end of this road lie the Biinterpretability Conjectures (see Slaman [1991].).

Conjecture 2.15. Biinterpretability (Harrington for R; Slaman and Woodin for D and D(≤ 0′)) There is a definable relation which associates each degree d with ones c that code sets S of degree d by some specified coding scheme in definable standard models of arithmetic. For R and D(≤ 0′) this amounts to a definable procedure taking each degree d to an element of a specified definable standard model of arithmetic which is, in that model, an index for an r.e. or Δ_{2} set, respectively, of degree d.

These conjectures imply that the structures are rigid and that all possible relations are definable in the degree structures. More precisely, that every degree is definable in R and D(≤ 0′) and every relation on degrees definable in first order arithmetic is definable in R and D(≤ 0′). In D, it says that every degree and relation on degrees definable in second order arithmetic is definable. Thus they represent an attempt at a full analysis of the degree structures following the path of characterization by complexity rather than the one via simplicity represented in the early conjectures of Shoenfield, Sacks and Rogers.

3 Decidability and Undecidability: the Boundary

3.1 Fragments of T h(D)

We first consider the theory of D in the simplest natural language, i.e. with just the ordering relation ≤. The decidability of the one quantifier or ∃-theory of D is an immediate corollary to the embedding results of Kleene-Post [1954]. (An existential sentence is true if and only if it is consistent with the theory of partial orders, or equivalently, if there is a partial order with a domain of size the number of variables in the formula that satisfies it.)

Theorem 3.1. (essentially Kleene-Post [1954]) The ∃-theory of D is decidable.

The initial segment constructions and the methods used to settle the extension of embedding problem sufficed to prove the undecidability of the two quantifier or ∀∃- theory of D. The argument also depends on the specific algebraic nature of the way the extension of embedding problem is solved. In particular, a single embedding as an initial segment suffices to rule out all forbidden extensions at once.

Theorem 3.2. (Shore [1978], Lerman see [1983, VII.4) The ∀∃-theory of D is decidable.

The initial segment results of Lerman [1971] were also sufficient to draw the boundary between decidability and undecidability in this setting. They allowed Schmerl to use the fact that the ∃∀-theory of finite lattices in the language with just ≤ is strongly undecidable to get undecidability at the next level. (Some corrections need to be made in the version of the proof presented in Lerman [1983, VII.4.6].)

Theorem 3.3. (Schmerl) The three quantifier or ∀∃∀-Theory of D is undecidable.

Expanding the language considered is the next natural step in this investigation but it required new approaches and techniques. The first extension is to make the upper semilattice structure explicit by adding a join operator. The Kleene and Post embedding theorem still gives the decidability of the one quantifier theory since usls are locally finite and the size of the substructures generated by any n elements is recursively bounded in n. The two quantifier theory, however, needs a new type of forcing to control the join.

Theorem 3.4. (Jockusch and Slaman [1993]) The ∀∃-theory of D in the language with both ≤ and ∨ is decidable.

In the direction of undecidability, we already have the three quantifier theory in the language with just ≤. One route to expand the language and sharpen the result is to add on some way to talk about infima. Of course, infima are definable in D but the quantifier complexity of the definition is such that the results are sensitive to the language at the level of one or two quantifiers. One first thinks to simply add on the usual binary function symbol ∧. The problem here is that D is not a lattice and so the operation is not always defined. A plausible alternative is to add a ternary predicate for x ∧ y = z and this route has been followed in the direction of decidability in the investigations of other degree structures. General considerations, however, show that it is not possible to get undecidability at the two quantifier level with only relation symbols and it would seem as if the join operator alone would not be sufficient to overcome these arguments. (The argument in general depends on only needing to check structures of finite size bounded by the complexity of the formula being decided (see Shore [1999, p. 179]). The local finiteness of usls suggests that a similar argument applies to the proposed language.) Thus the only hope is to add on a function symbol. The solution to the problem of partialness of infima in D is to show that the undecidability argument works uniformly for any total extension of the infima relation and so is intrinsic to the structure. One also needs a more efficient coding of undecidable facts to get the result. Register machines are used for that reason. Otherwise, for D the known initial segment results are sufficient.

Theorem 3.5. (Miller, Nies and Shore [2004]) The ∀∃-theory of D in the language with ≤, ∨ and ∧ is undecidable for any extension of the infimum relation to a total function

The other natural extension of our language for D is gotten by including a unary function symbol ′ for the jump operator. Again the jump is definable (Shore and Slaman [1999] and see §4.4 below) but not obviously so and certainly at a level of quantifier complexity far beyond what we are considering here. The addition of the jump operator makes the analysis of the structure and so the proof of any decision procedure much more complicated. The considerations now go beyond the local ones uses before where all constructions took place within a jump or two of the degrees being considered. We must obviously go through the arithmetic hierarchy and often indeed beyond. The first decidability result at even the one quantifier level used forcing constructions that extended beyond the hyperarithmetic.

Theorem 3.6. (Hinman and Slaman [1991]) The ∃-theory of D in the language with ≤ and ′ is decidable.

The next step in the decidability direction was to add on the join operator. Here too, many additional techniques were called upon including forcing with new coding methods, hyperarithmetic theory, pseudojump hierarchies, Fraissé limits, and Barwise compactness.

Theorem 3.7. (Montalbán [2003]) The ∃-Theory of D in the language with ≤, ∨ and ′ is decidable.

This result brings us once again to the boundary between decidability and undecidability.

Theorem 3.8. (Shore and Slaman [2006]) The ∀∃-Theory of D in the language with ≤, ∨ and ′ is undecidable.

Here one used coding with an extension of Kumabe-Slaman forcing to control formulas with join and jump at the two quantifier level. A very recent result returns to the one quantifier level but adds on a constant 0 for the least degree. The issues here are that now one must embed arbitrary structures with a jump operator into the arithmetic degrees with precise control over the level at which sets appear. The previous methods of producing the desried substructures beyond the hyperarithmetic degrees by complicated forcing constructions and pseudojump hierarchies cannot help. What is needed is an iteration of priority arguments simultaneously to all levels of the arithmetic hierarchy. Much of the machinery was developed over many years primarily in settings dealing with the r.e. degrees and the various jump relations on them by Lempp and Lerman [1992], [1995], [1966]. The final result is the desired decision procedure.

Theorem 3.9. (Lerman [2008]) The ∃-theory of D in the language with ≤, ∨,′ and 0 is decidable.

3.2 Fragments of T h(D(≤ 0′))

We now turn to the degrees below 0′. At the one quantifier level, nothing new is needed as the Kleene-Post methods of forcing one quantifier sentences automatically produce sets below 0′.

Theorem 3.10. (Kleene-Post [54]) The ∃-theory of D(≤ 0′) in the language with ≤ and ∨ is decidable.

Once one leaves the realm of Cohen forcing for one quantifier sentences, however, the situation becomes much more complicated. The initial segment results needed, in particular those cited above by Lerman, are much more difficult than even the ones for D. Still, once one has all finite lattices as initial segments of D(≤ 0′), the same algebraic coding argument gives undecidability at the three quantifier level for ≤. Similarly, the embeddability of all recursive lattices as initial segments of D(≤ 0′) provides the same undecidability result as for D at the two quantifier level in the language with ≤ , ∨ and ∧.

Theorem 3.11. (Lerman [1983], Schmerl; Miller, Nies and Shore [2004]) The ∀∃∀-theory of D(≤ 0′) and the ∀∃-Theory of D(≤ 0′) in the language with ≤, ∨ and ∧ are undecidable.

The analysis at the two quantifier level even with just ≤ requires additional work both for the initial segment results (to get ones that have the joins of every pair of maximal elements of the initial segment join to 0′) and for the extension of embedding results (to work below 0′ by using priority and permitting techniques).

Theorem 3.12. (Lerman and Shore [1988]) The ∀∃-theory of D(≤ 0′)is decidable.

3.3 Fragments of T h(R)

Once again one simply needs to embed finite partial orderings or usls to get the decidability of the existential theory. Friedberg–Muchnik type finite priority arguments suffice.

Theorem 3.13. (Sacks [1963]) The ∃-theory of R in the language with ≤ and ∨ is decidable.

The next steps toward decidability have proven extremely difficult. Despite an enormous amount of effort by many people some of which were mentioned in §1, even the question of which finite lattices are embeddable in R remains unsettled. After forty years of work the best result is that of Lerman [2000] which shows that the class of embeddable finite lattices in a special but important class is at worst Π_{2}^{0}. The best positive result in terms of fragments is for the extension of embedding problem which goes far beyond the density theorem and needs more than basic infinite injury priority arguments.

Theorem 3.14. (Slaman and Soare [2001]) The extension of embedding problem for R is decidable.

We do, however, have undecidability results similar to those for D and D(≤ 0′).

Theorem 3.15. (Lempp, Nies and Slaman [1998]) The ∀∃∀-theory of R is undecidable.

The methods here include coding bipartite finite graphs via a 0′′′ argument. (To explain this terminology note that in a finite injury argument each requirement is injured only finitely often. Hence 0′ can determine when and how each one is satisfied. In an infinite injury argument, the action of at least some types of requirements is infinitary (for example, putting in an infinite recursive set), Here it takes 0′′ to determine how each requirement is satisfied. At the next level, there are additional interactions that restart the infinitary requirements finitely often. Hence, it requires 0′′′ to determine how they are satisfied. Thus we have Harrington’s classification of such constructions as 0′, 0′′ or 0′′′, respectively.) In the language with supremum and infimum operators (in the sense of arbitrary total extensions of the infimum relation as before) we again have undecidability at the two quantifier level. The methods here include coding register machines via lattice embeddings using pinball machines arguments on trees simultaneously with 0′′′ and other priority methods.

Theorem 3.16. (Miller, Nies and Shore [2004]) The ∀∃-theory of R in the language with ≤, ∨ and ∧ is undecidable.

3.4 Summary for Fragments

We conclude this section with some tables that summarize the state of our knowledge about the boundary between decidability and undecidability in D, D(≤ 0′) and R. We will return to the entries with question marks in §5.

R  D  D(≤ 0′)
∃(≤, ∨)  Decidable  Decidable  Decidable
∀∃(≤, ∨)  ?  Decidable  ?
∀∃∀(≤, ∨) Undecidable Undecidable Undecidable

R  D  D(≤ 0′)
∃(≤, ∨, ∧)  ?  Decidable  Decidable
∀∃(≤, ∨, ∧) Undecidable Undecidable Undecidable

D
∃(≤, ∨,′, 0) Decidable
∀∃(≤,′)  ?
∀∃(≤, ∨,′) Undecidable

4 The Path to Characterization via Complexity

4.1 Theories and Biinterpretability

This road begins with the characterizations of the full theories of the three degree structures by showing that they are as complicated as possible given that the structures can be defined in first (D(≤ 0′) and R) or second (D) order arithmetic. The overall idea is to first find some definable coding of sets and relations that is sufficiently general to code models of (a finitely axiomatized version) of arithmetic. The next step is to definably code enough quantification over subsets of the model to definably pick out the standard ones.

Theorem 4.1. (Simpson [1977]) There are recursive translations S_{2} and T_{2} with S_{2} taking sentences ϕ of second order arithmetic to sentences ϕ^{S_{2}} of partial orderings and T_{2} taking sentences ψ of partial orders to ones ψ^{T_{2}} of second order arithmetic such that N ⊧ ϕ ⇔ D ⊧ ϕ^{S_{2}} and D ⊧ ψ ⇔ N ⊧ ψ^{T_{2}}.

The proof here uses linearly ordered initial segments plus a coding into joins to define models of arithmetic and Spector’s [1956] exact pair theorem that every countable ideal in D is the intersection of two principal ideals to convert quantification over countable ideals into first order quantification over pairs of degrees. This conversion allows one to quantify over all subsets of the model. Another proof of this theorem by Nerode and Shore [1980], [1980a] used initial segment embeddings of general lattices to code arithmetic and again exact pairs to quantify over subsets. It was instrumental in proving the analogous results for D(≤ 0′).

Theorem 4.2. (Shore [1981]) There are recursive translations S_{1} and T_{1} with S_{1} taking sentences ϕ of first order arithmetic to sentences ϕ^{S_{1}} of partial orderings and T_{1} taking sentences ψ of partial orders to ones ψ^{T_{1}} of first order arithmetic such that N ⊧ ϕ ⇔ D(≤ 0′) ⊧ ϕ^{S_{1}} and D(≤ 0′) ⊧ ψ ⇔ N ⊧ ψ^{T_{1}}.

Of course, one can’t quantify over all subsets of a model in a first order way in a countable structure. An added issue here is then to show that the coding can be done in a sufficiently effective way so as to guarantee that the needed subsets (i.e. the standard part of any coded model) can be defined within the structure. Still one gets at the end a definable class of standard models as one had for D. Yet another proof of each of these theorems are based on a new forcing procedure to provide a coding method introduced by Slaman and Woodin [1986]. This coding depended only on Cohen type forcing rather than on the more difficult perfect forcing and initial segment results. This forcing along with other more metamathematical methods were then later instrumental many of the global results on D.

The methodology for R was, of course, much different. Here no initial segment results are available nor are Cohen type forcing arguments. One must instead turn to priority arguments to construct subsets of R definable from parameters. The first coding of this sort was introduced by Harrington and Shelah [1982] to prove the undecidability of R. It used 0′′′ methods to define sets of maximal degrees (in an interval) with some nonjoin property relative to other parameters. It was later extended by Harrington and Slaman to characterize the full theory. A dual coding using minimal degrees with a join property was used by Slaman and Woodin to produce a somewhat simpler proof. Although both of these arguments determined the theory of R, nether provided a definition of a model of arithmetic. That was done by Nies, Shore and Slaman [1998] using a variety of priority techniques including lattice embeddings as well as tree arguments of various sorts.

Theorem 4.3. (Harrington and Slaman; Slaman and Woodin; Nies, Shore and Slaman [1998]) There are recursive translations S_{0} and T_{0} with S_{0} taking sentences ϕ of first order arithmetic to sentences ϕ^{S_{0}} of partial orderings and T_{0} taking sentences ψ of partial orders to ones ψ^{T_{0}} of first order arithmetic such that N ⊧ ϕ ⇔ R ⊧ ϕ^{S_{1}} and R ⊧ ψ ⇔ N ⊧ ψ^{T_{1}}.

Once one has not merely a translation of sentences but actually a definable class of standard models, one can work toward the Biinterpretability Conjectures in each structure by attempting to define relations that associate degrees with codes for sets of those degrees in such models. The short version of the long road to the current state of affairs is that we have the Biinterpretability Conjectures up to double jump.

Theorem 4.4. (Biinterpretability up to Double Jump) There are definable relations in D, D(≤ 0′) and R which associate each degree d with ones c that code sets S in a definable standard model of arithmetic such that S′′ ∈ d′′ where all the definable relations are given by some specified coding schemes for sets and models.

We would cite as essentially the sources of these versions of the results Slaman and Woodin [2006] (see Slaman [1991]) for D, Shore [1988] for D(≤ 0′) and Nies-Shore-Slaman [1998] for R.

There are many results of independent interest which are either corollaries of these theorems or ingredients in their proofs. We list a few of the most interesting ones. Some of the following results are truly corollaries, others are ingredients of the proofs and yet others are derived along the path. Again, there were often many earlier weaker results along the way but the current best ones typically are in the three papers cited for the theorem.

4.2 Automorphisms of D

Theorem 4.5. Every automorphism of D is the identity above 0′′.

Theorem 4.6. There is a single d recursive in 0^{(5)} such that every automorphism φ of D is determined by φ(d).

Theorem 4.7. There are at most countably many automorphisms of D.

4.3 Failures of Homogeneity

Theorem 4.8. If D(≥ a) ≅ D(≥ b), D[a, a′] ≅ D[b, b′] or R^{a} ≅ R^{b}, a′′ = b′′.

4.4 Definability

Theorem 4.9. Every relation definable in second (first) order arithmetic which is invariant under the double jump is definable in D (D(≤ 0′), R).

Theorem 4.10. The jump classes H_{n} and L_{n+1} (n ≥ 1) are definable in D(≤ 0′), R.

The double jump limit comes into play in all of these results because of the complexity of Turing reducibility itself. The relation that A is Turing reducible to B is Σ_{3}^{0} in A and B. Thus it seems as if the best one can do in terms of coding via Turing reducibility is to have a relation that are Σ_{3}^{0} in the coding parameters. As the sets Σ_{3}^{0} in any A are determined by and, in fact, determine the degree of A′′, this seems like the natural boundary for such general results or at least of the methods employed working along the lines of the biinterpretability conjectures. The case of the definability of H_{1} in R and D(≤ 0′) seems to go beyond the double jump limit but actually is based on the double jump result plus some special properties of high degrees. One major result, however, does go beyond this limit.

Theorem 4.11. (Shore and Slaman [1999]) The operation of the Turing jump is definable in D.

We should say something about the history of this result. The Turing jump plays a central role in almost all investigations of degree theory. Indeed, the first major results (Jockusch and Simpson [1976]) on definability in D were actually in the structure with the Turing jump as well as ≤_{T}. The issue of whether the jump is definable from the ordering of Turing reducibility alone was raised explicitly already in the first paper on the general structure of D, Kleene and Post [1954]. The first approximation to a definition of the Turing jump was the definition of the hyperartihmetical degrees and the hyperjump (Harrington and Shore [1981]). It used codings of arithmetic and the calculation (Kechris and Harrington [1975]) that Kleene’s O is the base of a cone of minimal covers, i.e. ∀x ≥_{T} O∃y ≤_{T} x¬∃z(y <_{T} z <_{T} x). Jockusch and Shore [1984] then analyzed the notion of pseudojumps or iterated REA operators (e.g. J_{e}(A) = A ⊕ W_{e}^{A} and then iterations of such operators into the transfinite allowing uniform lists of indices e for the operators and taking effective joins at limit levels). This analysis lead to a proof that 0^{(ω)} is the base of a cone of minimal covers. (No 0^{(n)} can be a minimal cover by Jockusch and Soare [1970]). An additional cone avoiding argument for all ω-REA operators that correspond to ω-r.e. set operators like that of Sacks’s [1963] minimal degrees below 0′, produced a definition of the arithmetic degrees and so by relativization one of the relation “arithmetic in”. (A set A is n-r.e. (for n < ω) if there is a recursive function f(n, s) such that f(n, 0) ≡ 0, lim f(x, s) = A(x) for every x and there are at most n many s such f(x, s) ≠ f(x, s + 1) for each x. A is ω-r.e. if there is such an f with the number of s with f(x, s) ≠ f(x, s + 1) bounded by a recursive function of n.) This definition is natural in the sense that it is phrased in relatively simple terms based on ≤_{T} and makes no mention of codings.

Definition 4.12. A = {d|∃n(d ≤ 0^{(n)})}. C_{0} = {c|∀z(z ∨ c is not a minimal cover of z}. \overline{C}_{0} = \{d|∃c ∈C_{0}(d ≤ c)\}.

Theorem 4.13. (Jockusch and Shore [1984]) A = \overline{C}_{0} and the relation a is arithmetic in b is definable in D (by relativization).

Cooper [1990, 1993 and elsewhere] suggested a similar approach to the problem of defining the jump operator. His plan was to use a version of the Jockusch and Shore cone avoiding theorem for simple REA operators derived from 2-r.e. set ones and a suitable 2-r.e. set to replace the ω-r.e. set of minimal degree used in the definition of “arithmetic”. What was required was a 2-r.e. operator that would produce a degree with an order-theoretic property that no r.e. degree could have (again even relative to any degree below it). He defined the following notions and classes.

Definition 4.14. 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 < d_{0}, d_{1} < 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 ≤ c)\}.

Now, of course, it was already known by Sacks [1963] that every r.e. degree d is in C_{1}. For the other direction Cooper [1990, 1993] claimed as his main theorem that there is a 2-r.e. set and so a 2-r.e. operator J such that for every C there are a and b such that d ≡_{T} deg(J(C)) is not splittable over a avoiding b. Such a result would provide a natural definition of 0′ as the maximum degree in \overline{C}_{1} and, by relativization, a natural definition of the jump operator.

At the Boulder meeting in 1999, we suggested that a stronger join theorem applicable to all n-REA operators should provide a route to a simpler proof of the definability of the jump. With Slaman we proved this stronger theorem by using a forcing introduced by Kumabe and Slaman to prove a similar theorem for ω-REA operators. However, we were unable to find a suitable 2-REA operator to play the role of Cooper’s notion of splittability. We then attempted to prove the original theorem as had been claimed by Cooper. Our analysis of the difficulties arising in such a proof lead us to the conclusion that Cooper’s main theorem was false. Indeed, not only is there no 2-r.e. operator as claimed, there is not even any n-REA one. (Every n-r.e. set is n-REA by Jockusch and Shore [1984.)

Theorem 4.15. (Shore and Slaman [1999]) If a, b ≤_{T} d, b ≰_{T} a and d is n-REA in a, then d can be split over a avoiding b.

Thus Cooper’s claimed definition of the jump operator does not define it. He then (in 2000) proposed a variant of the first property that he called “discretely splittable over a avoiding b” and posted a proof on his website that there are such sets which are 2-r.e. and so claimed a different definition of the jump. This claim fell to a similar argument and Slaman and Shore showed that no n-REA degree is discretely splittable over a avoiding b for any appropriate a and b. Cooper [2001] then tried a third much more complicated attempt at a 2-r.e. operator that would give a definition of the jump. (It was again called “discretely splittable” but with a new definition.) This one seems too complicated to be refuted by the type of analysis in Shore and Slaman [2001] but as Jockusch [2002] has pointed out, the requirements listed for his construction would not suffice to prove the theorem even if satisfied.

Nonetheless, the jump is definable. The join theorem proved by Shore and Slaman [1999] was strong enough to show provide a definition based on much earlier work of Slaman and Woodin that provided the required definable 2-REA operator: the double jump. Although not included in the announcement of their work in Slaman [1991] (as described above), their metamathematical arguments that gave the biinterpretability conjecture up to two jumps also proved that the double jump was definable in D. (The definition requires the entire machinery of Slaman and Woodin to internalize the analysis of automorphisms of D within D itself. It relies on forcing to collapse the continuum and absoluteness arguments to capture full automorphisms of D by countable approximations that can then be defined within the structure.) The full proof appears in Slaman and Woodin [2006]. Together with the join theorem for n-REA operators it gives the following definition of the Turing jump from that of the double jump..

Theorem 4.16. (Shore and Slaman [1999]) For any degree x, x′ is the greatest degree z such that there is no g greater than or equal to x such that z ∨ g is equal to g′′.

5 Questions

5.1 Fragments

There are four question marks in tables at the end of §3 suggesting areas for future investigations, one each for D and D(≤ 0′) and two for R. If we begin with D we face the decision problem for the ∀∃-Theory of D(≤,′). This is a very rich theory with many interesting and difficult subproblems including Lerman’s [2008] decidability result for ∃-Theory of D(≤, ∨,′ , 0). If we attempt to follow the path trodden without the jump operator, the natural starting point towards more decidability is the analysis of the extension of embeddings problem. Here the work in D begins with initial segment results and then uses Kleene-Post methods to carry out the possible extensions. In the language with the jump operator we might start with analyzing the interactions of the jump operator with initial segment results. Some work in this direction is done in Gabay [2004] for the double jump but controlling the single jump of initial segments is a much harder problem and not much is known beyond Cooper’s [1973] jump inversion theorem that every degree above 0′ is the jump of a minimal degree.

Turning to the theory of D(≤ 0′), the area suggested is the decision problem for the ∀∃ theory with ≤ and ∨ in the language. Based on the general situation of usls at the two quantifier level, it would seem that our only hope is to prove decidability. Again, one would start with the extension of embedding problem. We have the required initial segment results to eliminate various possible extensions as in the proof of decidability without ∨. Moreover, we might expect that, since we have initial segments, we could reduce the two quantifier theory to the extension of embedding problem as is done for D. We would then hope to be left with an extension argument that could be done along the lines of the decision procedure for the two quantifier theory of D(≤ 0′). These problems, however, turns out to be far from straightforward. The extension of embeddings part, for example, has surprisingly something of the flavor of the ∀∃ theory of R and Montalbán has shown that we cannot reduce the full ∀∃ decision problem to the extension of embedding problem.

Theorem 5.1. (Montalbán) For every x_{1} < x_{2} in (0, 0′) there is either a y such that 0 < y < x_{1} or one such that x_{1} < y < 1 and x_{2} ∨ y = 1 but neither disjunct holds for every x_{1} < x_{2} in (0, 0′).

This is reminiscent of the nondiamond (Theorem ??) and other related phenomenon in R. It suggests that there are many problems to consider here.

Finally, in R the question mark for ∃(≤, ∨, ∧) is essentially the long standing problem of characterizing the finite lattices embeddable in R. Something of a survey and the suggestion of a new approach along somewhat different lines than the work cited in §1, is Lempp, Lerman and Solomon [2006].

The full ∀∃-theory introduces many other issues including the nondiamond phenomena and other related problems. While there are pairs of r.e. degrees that join to 0′ (by Theorem ??) and ones that inf to 0 (by Theorem ??) there are none that do both.

Theorem 5.2. (Lachlan [1966a]) There are no two r.e. degrees x and y such that x ∨ y = 0′ and x ∧ y = 0.

This result shows that the full two quantifier theory cannot be reduced to the extension of embedding problem as is done for D. Nonetheless, the methods of Slaman and Soare [2001] used to solve the extension of embedding problem should be applicable to analyzing the rest of two quantifier theory should the lattice embedding problem be solved in a nice way. Other techniques and ideas that are relevant include the analysis of Ambos-Spies, Jockusch, Shore and Soare [1984] of the promptly simple degrees (as the filter of ones that are not half of minimal pairs) and the complementary filter of ones which are halves of minimal pairs as well as the analysis of lattice embeddings preserving 0 and 1 as in Ambos-Spies, Lempp and Lerman [1994, 1994a]. A possible approach suggested by Lerman is outlined in Lempp [1998]. Still, much other work remains and some of it can be tackled independently of the lattice embedding problem.

5.2 Biinterpretability

The obvious overarching question is to settle the Biinterpretability Conjectures for D, D(≤ 0′) and R. As we have mentioned, the conjectures for each structure easily imply rigidity. Here too, Cooper [1997], [1997a] has claimed to have settled the problem by showing that there are nontrivial automorphisms of both R and D (and hence D(≤ 0′) as well). Despite many attempts by Cooper to present his arguments and the concerted efforts of a number of expert readers to work through his write ups, no one has been able to even claim an understanding of the fundamental nature of his construction. Thus we must view the question as still entirely open.

We should, however, point out that if one allows parameters then Slaman and Woodin’s work [2006] shows that the biinterpretability conjecture holds for D (see Slaman [1991]). The point here is that they show first that that rigidity implies biinterpretability and second that if g is any 5-generic degree then the action of any automorphism is determined by its action on g. Thus any such g will suffice as a parameter to define the relations needed for biinterpretability. Some preliminary investigations by Slaman and Woodin suggested to them that D(≤ 0′) should also have a finite automorphism base and be biinterpretability with parameters. We view these as plausible conjectures.

For R, even biinterpretability relative to parameters or the existence of a finite automorphism basis remains a wide open question. The closest one has come so far is Nies [2003] which give biinterpretability with parameters for all nontrivial upper cones in R. Moreover, we do not know if any single r.e. degree is definable in R or even fixed under all automorphisms.

5.3 Definability

Almost all of the definability results described above are proved by using coding methods to interpret arithmetic and, in the case of D, even metamathematical methods of forcing and absoluteness. There are a few “natural definitions in D that we have mentioned such as of the arithmetic and hyperarithmetic degrees. There are many interesting questions along these lines and we refer to Shore [2000] for an extensive list. Here we just mention a few that fit in with our analysis so far.

The first obvious problem is to find a natural definition of the jump in D. A natural definition of any finite iteration of the jump would be sufficient by the arguments used to go from the double jump to the single one. This can be accomplished by finding an order theoretic property P and an n-REA operator J such that, (∀x)[(∀a ∈R)(D(≥ x) ⊧ P (x ∨ a)) & D(≥ x) ⊧ ¬P (J(x)].

Indeed, even a definition of REA = ∪{x| ∃n(x is n-REA)} would suffice to give a definition of the jump without any metamathematical considerations. There are a number of natural classes such as C_{0} and C_{1} defined in §??. Are any of them actually equal to REA? A (relativizable) proof even that every member of such a definable class bounds a nonzero r.e. degree also would give a direct definition of the jump. Many other important classes that are definable from the jump can be used to directly define the jump without the metamathematical considerations of Slaman and Woodin [2006]. Some examples are each of the jump classes L_{2} through H_{2}. It seems as if the jump is even directly definable from the class of array nonrecursive degrees of Downey, Jockusch and Stob [1990]. (The r.e. array nonrecursive degrees are actually relatively definable as the those element of R which have strong minimal covers in D by Ishmukhametov [1999].) So direct definitions of any of these classes would be of interest. (That such definitions would give ones for the jump is not obvious but can be proven.)

Inside R and D(≤ 0′) we ask for natural definitions of any of the jump classes L_{n} or H_{n}. The strongest candidates are L_{2} and H_{1} given the large amount of information we have on the behavior of degrees in these classes. Any definition (natural or not) of L_{1} or of any single degree in R or D(≤ 0′) would be of great interest.

6 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., Jockusch, C. G. Jr., Shore, R. A. and Soare, R. I. [1984], An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Transactions of the American Mathematical Society 281 (1984), 109-128.

Ambos-Spies, K., Lempp, S. and Lerman, M. [1994], Lattice embeddings into the r.e. degrees preserving 1, in Logic, methodology and philosophy of science, IX (Uppsala, 1991), Stud. Logic Found. Math., 134, North-Holland, Amsterdam, 179–198.

Ambos-Spies, K., Lempp, S. and Lerman, M. [1994a], Lattice embeddings into the r.e. degrees preserving 0 and 1, J. London Math. Soc. (2) 49, 1–15.

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.

Ambos-Spies, K. and Soare, R. I. [1989], The recursively enumerable degrees have infinitely many one-types, Ann. Pure and Applied Logic 44, 1-23.

Cooper, S. B. [1973], Minimal degrees and the jump operator, J. Symb. Logic 38. 249-271.

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, University of Leeds, Department of Pure Mathematics Preprint Series No. 7.

Cooper, S. B. [1997], Beyond Gödel’s theorem: the failure to capture information content, in Complexity, logic, and recursion theory, A. Sorbi ed., Lecture Notes in Pure and Appl. Math., 187, Dekker, New York, 93–122.

Cooper, S. B. [1997a], The Turing Universe is not rigid, University of Leeds Department of Mathematics Preprint Series no. 16.

Cooper, S. B. [2001], On a conjecture of Kleene and Post. Math. Log. Q. 47, 3–33. Downey, R. G., Jockusch, C. G. Jr. and Stob, M. [1990], Array nonrecursive sets

and multiple permitting arguments, in Recursion Theory Week, K. Ambos-Spies, G. H. Müller and G. E. Sacks eds., Springer-Verlag, Berlin, 141-174.

Epstein, R. L. [1979], Degrees of Unsolvability: Structure and Theory, LNM 759, Springer-Verlag, Berlin.

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

Gabay, Y. [2004], Double jump inversions and strong minimal covers in the Turing degrees, Ph.D. thesis, Cornell University.

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. 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 Shore, R. A. [1981], Definable degrees and automorphisms of D, Bul. Am. Math. Soc. (NS) 4, 97-100.

Hinman, P. G. and Slaman, T. A. [1991], Jump embeddings in the Turing degrees, J. Symbolic Logic 56, 563–591.

Ishmukhametov, Sh. [1999], Weak recursive degrees and a problem of Spector, in Recursion Theory and Complexity, Proceedings of the Kazan ’97 Workshop, Kazan, Russia, July 14-19, 1997, Arslanov, M. and Lempp, S. eds., de Gruyter Series in Logic and its Applications 2, Walter de Gruyter, Berlin, 81-88.

Jockusch, C. G. Jr. [2002], review of Cooper [2001], Math. Rev. MR1808943 (2002m:03061).

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 Simpson, S. G. [1976], A degree theoretic definition of the ramified analytic hierarchy, Ann. Math. Logic 10, 1-32.

Jockusch, C. G. Jr. and Slaman, T. A. [1993], On the Σ_{2}-theory of the upper semilattice of Turing degrees, J. Symbolic Logic 58, no. 1, 193–204.

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

Kjos-Hanssen, B. [2002], Lattice initial segments of the Turing degrees, Ph.D. thesis, University of California, Berkeley.

Kjos-Hanssen, B. [2003], Local initial segments of the Turing degrees, Bul. Symb. Logic 9, 26-36.

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

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. and Soare, R. I. [1980], Not every finite lattice is embeddable in the recursively enumerable degrees, Adv. in Math. 37, 74-82.

Lempp, S. [1998] Decidability and undecidability in the enumerable Turing degrees, in Proceedings of the Sixth Asian Logic Conference (Beijing, 1996), World Sci. Publishing, River Edge, NJ, 151-161.

Lempp, S. and Lerman, M. [1992], The existential theory of the poset of r. e. degrees with a predicate for single jump reducibility, J. Symb. Logic 57, 1120-1130.

Lempp, S. and Lerman, M. [1995], A general framework for priority arguments, Bul. Symb. Logic 1, 189-201.

Lempp, S. and Lerman, M. [1996], The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations, Adv. Math. 120, 1–142.

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 87, 167-185.

Lempp, S., Lerman, M. and Solomon, R. [2006], Embedding finite lattices into the computably enumerable degrees - a status survey, to appear.

Lempp, S., Nies, A. and Slaman, T. A. [1998], The Π_{3}-theory of the computably enumerable Turing degrees is undecidable, Trans. Am. Math. Soc. 350, 2719-2736.

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. [2000], A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees, Annals of Pure and Applied Logic 101, 275–297.

Lerman, M. [2008], The existential theory of the uppersemilattice of Turing degrees with least element and jump is decidable, in preparation.

Lerman, M. and Shore, R. A [1988], Decidability and invariant classes for degree structures, Trans. Am. Math. Soc. 310, 669-692.

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.

Miller, R. G., Nies, A. O. and Shore, R. A. [2004], The ∀∃-theory of R(≤, ∨, ∧) is undecidable, Trans. Am. Math. Soc. 356, 3025-3067.

Montalbán, A. [2003], Embedding jump upper semilattices into the Turing degrees, J. Symbolic Logic 68, 989-1014.

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. [2003], Parameter definability in the recursively enumerable degrees. J. Math. Log. 3, 37–65.

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

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.

Sacks, G. E. [1961], A minimal degree less than 0′, Bul. Am. Math. Soc. 67, 416-419. Sacks, G. E. [1963], Degrees of unsolvability, Annals of Math. Studies 55, Princeton

Univ. Press, Princeton NJ.

Sacks, G. E. [1963a], On the degrees less than 0′, Ann. of Math.(2) 77, 211-231. Sacks, G. E. [1963b], Recursive enumerability and the jump operator, Trans. Am.

Math. Soc. 108, 223-239.

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.

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.

Shore, R. A. [1978], On the ∀∃-sentences of α-recursion theory, in Generalized Recursion Theory II, J. E. Fenstad, R. O. Gandy and G. E. Sacks eds., Studies in Logic and the Foundations of Mathematics 94, North-Holland, Amsterdam, 331-354.

Shore, R. A. [1979], The homogeneity conjecture, Proc. Nat. Ac. Sci. 76, 4218-4219. Shore, R. A. [1981], The theory of the degrees below 0′, Journal of the London Math-

ematical Society 24, 1-14.

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. [1988], Defining jump classes in the degrees below 0′, Proceedings of the American Mathematical Society 104, 287-292.

Shore, R. A. [1999], The recursively enumerable degrees, in Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics 140, North-Holland, Amsterdam, 169–197.

Shore, R. A. [2000], Natural definability in degree structures, in Computability Theory and Its Applications: Current Trends and Open Problems, P. Cholak, S. Lempp, M. Lerman and R. A. Shore eds., Contemporary Mathematics 257, AMS, Providence RI, 255-272.

Shore, R. A. and Slaman, T. A. [1999], Defining the Turing jump, Math. Res. Lett. 6, 711–722.

Shore, R. A. and Slaman, T. A. [2001], A splitting theorem for n-REA degrees, Proc. American Mathematical Society 129, 3721-3728.

Shore, R. A. and Slaman, T. A. [2006], The ∀∃-theory of D(≤, ∨,′) is undecidable, in Logic Colloquium ’03, V. Stoltenberg-Hansen and J. Väänänen eds., Lecture Notes in Logic, ASL, to appear.

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. 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. [2001], Extension of embeddings in the recursively enumerable degrees, Ann. Math. 153, 1-43.

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. [2006], Definability in Degree Structures, to appear. Soare, R. I. [1987], Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin. Spector, C. [1956], On degrees of recursive unsolvability, Ann. Math. (2) 64, 581-592. Yates, C. E. M. [1966], A minimal pair of recursively enumerable degrees, J. Symb.

Logic 31, 159-168.