Definability in the recursively enumerable degrees^{∗}

André Nies^{†} University of Chicago, Chicago IL 60637

Richard A. Shore^{§} Cornell University, Ithaca NY 14853 USA

Theodore A. Slaman^{‡} University of Chicago, Chicago IL 60637

1. Introduction

Natural sets that can be enumerated by a computable function (the recursively enumerable or r. e. sets) always seem to be either actually computable (recursive) or of the same complexity (with respect to Turing computability) as the Halting Problem, the complete r. e. set K. The obvious question, first posed in Post [1944] and since then called Post’s Problem is then just whether there are r. e. sets which are neither computable nor complete, i. e., neither recursive nor of the same Turing degree as K?

Let R be the r. e. degrees, i. e., the r. e. sets modulo the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order (indeed, an uppersemilattice or usl) with least element 0, the degree (equivalence class) of the computable sets, and greatest element 1 or 0′, the degree of K. Post’s problem then asks if there are any other elements of R.

∗ Most of the material in this paper was presented to the Association at its annual meeting in Madison, March 1996 in a lecture given by the second author.

† Partially supported by NSF Grant DMS-9500983.

§ Partially supported by NSF Grants DMS-9204308, DMS-9204308, DMS-9503503 and ARO through MSI, Cornell University, DAAL-03-C-0027.

‡ Partially supported by NSF Grant DMS-9500878 and a CNR Visiting Professorship at the University of Siena.

The (positive) solution of Post’s problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure R was in some way well behaved:

Theorem 1.1. (Embedding theorem; Muchnik [1958], Sacks [1963]) Every countable partial ordering or even uppersemilattice can be embedded into R.

Theorem 1.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.

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

These results led Shoenfield in 1963 to formulate the view that the structure was “nice” as the sweeping conjecture that the r. e. degrees, R, are a “dense” (or more formally, a countably saturated) usl with least and greatest elements:

Conjecture 1.4. (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 had 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 (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 there are continuum many automorphisms of the structure. A positive solution to Shoenfield’s conjecture would thus have constituted an essentially complete characterization of the structure of the r. e. degrees.

The conjecture clearly implies, for example, that for any a, b > 0 there is a c > 0 which is below both a and b. Thus the construction of a minimal pairs of r. e. degrees, i. e., nonzero r. e. a and b such a ∧ b = 0, refuted the conjecture.

Theorem 1.5. (Lachlan [1966], Yates [1966]): There are nonrecursive r. e. degrees a and b such that a ∧ b = 0, i. e., any degree recursive in both a and b is recursive.

Many other counterexamples followed. Nonetheless, the paradigm suggested by Shoenfield’s conjecture continued to hold sway. Even Sacks, who had conjectured in [1963] that there were minimal pairs and that R is not a lattice, continued to conjecture in [1966] that the theory of R is decidable and that there is a strong sense of homogeneity for the notion of r. e. in the sense that “for each (not necessarily r. e.) degree d, the ordering of degrees r. e. in d and ≥ d is order isomorphic to the r. e. degrees”.

Both of these conjectures eventually turned out to be false (Harrington and Shelah [1982]; Shore [1982]) and in the intervening years there continued to be a growing list of examples of various types of degrees and examples of complexity in the structure:

• nonzero branching degrees (nontrivial infima) and nonbranching degrees (Lachlan [1966]);

• cappable degrees (halves of minimal pairs) and noncappable degrees (Yates [1966]);

• all distributive finite lattices (Lachlan, Lerman, Thomason; see Soare [1987, p. 157]) and the two basic nondistributive lattices (Lachlan [1972]) are embeddable in R but not all finite lattices are so embeddable (Lachlan and Soare [1980]);

• cuppable degrees , i. e., those which join (cup) to 0′ , (by the Sacks splitting theorem) and noncuppable degrees (Lachlan [1966a]);

• degrees which split over every smaller degree (any low degree a, i. e., a′ = 0′, by Robinson [1971], any low_{2} degree a, i. e. a′′ = 0′′, by Shore and Slaman [1990]) and degrees which do not (Lachlan [1975]);

• degrees over which 0′ splits (any low degree by Robinson [1971]) and degrees over which it does not (Harrington; Jockusch and Shore [1983]);

• degrees which bound particular lattices (Lachlan [1972]) and degrees that do not (Weinstein [1988], Downey [1990]);

• …

These results, and the structure itself, were often viewed as chaotic and it was not until some twenty year after the refutation of Shoenfield’s Conjecture that a dramatically different view of the structure of the r. e. degrees (as well as of the degrees as a whole) became the prevailing paradigm. This view starts from the complexity of the structure but, rather than seeing this complexity as an obstacle to characterizing the r. e. degrees, it suggests that a sufficiently strong proof of complexity would completely characterize the 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 could look to prove that the theory is as complicated as possible, there are as many different types of degrees as possible (even that no two are alike but rather each is definable) and that the structure has no automorphisms.

The first refutations of Sacks’s conjectures about decidability (Harrington and Shelah [1982]) and homogeneity (Shore [1982]) introduced coding techniques into the study of R. The first used definable representations of partial orderings and the second embeddings of finitely generated partial lattices. It is the ultimate expression of such coding procedures that is embodied in the conjecture that crystallized the new paradigm of complexity as a route to characterization:

Conjecture 1.6. (Biinterpretability Conjecture for R, Harrington; Slaman and Woodin; see Slaman [1991]): There is a definable coding of a standard model of arithmetic, N_{0}, in R for which the relation associating each r. e. degree d to the (codes in the model of) sets of its degree is also definable.

(In the context of just the structure R, the definability of the relation described is equivalent to the definability of a map taking each r. e. degree to an index in N_{0} for a set of that degree or even to the definability of any one-one map from R into N_{0}. However, in the degrees as a whole and even in considering relativizations of R, simple indices for sets of the degrees being considered are not usually available and other codings for sets must be used. Thus the formulation given is the appropriate one in general settings. This point will be discussed further in §2.)

More than simply saying that the r. e. degrees are complicated, this conjecture provides a strong characterization of the structure of R. If true it would give complete information, for example, about definability in R (every degree in R would be definable as would every relation on R which is definable in arithmetic) and automorphisms for R (none other than the identity would exist). (Clearly if we can definably relate each degree to the sets of that degree, there can be no automorphism of R. As for the definability claims, just use the definable mapping from R to the standard model of arithmetic and translate the definitions in arithmetic.)

2. Results and Relativizations

Cooper [1996] has announced the existence of an automorphism of R and hence the failure of the biinterpretability conjecture (as we discuss further in §4). On the other hand, the results we are reporting on here show how far we have come in the direction of proving the biinterpretability conjecture. In a sense made precise in the theorem below, our results are within two jumps of the conjecture. The corollaries that we can derive about rigidity (Corollary 2.3) and definability (Corollary 2.4) are then similar to those described from the full conjecture but only “up to two jumps”:

Theorem 2.1. In R there is a definable copy N_{0} of the structure (N , +×) and a definable relation associating each degree a with codes for sets of degree a′′. Indeed, there is a definable map f : R → N_{0} such that, for every a, f(a) is (the code for) the least index of an r. e. set W for which W′′ ∈ a′′.

The following notions help make the idea of “up to two jumps” precise.

Definition 2.2. An n-ary relation P (x_{1}, …, x_{n}) on R is invariant under the double jump if, whenever R ⊧P (x_{1}, …, x_{n}) and x′′_{1} ≡_{T} y′′_{1}, …, x′′_{n} ≡_{T} y′′_{n}, it is also true that R ⊧P (y_{1}, …, y_{n}). P is invariant in R if whenever R ⊧P (x_{1}, …, x_{n}) and φ is an automorphism of R, R ⊧P (φ(x_{1}), …, φ(x_{n})). P is definable in arithmetic if the set of n-tuples of indices of r. e. sets whose degrees satisfy P is definable in (N , +, ×).

The following corollaries about definability (except for the last one) all follow immediately from the theorem by simply translating the appropriate definitions in arithmetic (on indices) to ones in N_{0} and then using the definable function f given by the theorem to associate the indices with the corresponding degrees. (The first one, although also formally a consequence of the Theorem, is actually an ingredient in its proof.)

Corollary 2.3. Any relation on R which is invariant under the double jump is invariant in R.

Corollary 2.4. Any relation on R which is definable in arithmetic and invariant under the double jump is definable in R.

Corollary 2.5. For each k ≥ 2 the relation x ∼_{k}y defined by x^{(k)} ≡_{T} y^{(k)} is definable in R.

Corollary 2.6. For each c r. e. in and above 0′′, the set of r. e. degrees a with double jump c is definable in R.

Corollary 2.7. The jump classes L_{n} = {a| a^{(n+1)} = 0^{(n+1)}} (the low_{n+1}degrees) and H_{n} = {a| a^{(n)} = 0^{(n+1)}}, (the high_{n} degrees) are definable in R for n ≥ 2.

Corollary 2.8. The jump class H_{1} = {a| a′ = 0′′} (the high degrees) is definable in R.

Proof(of Corollary 2.8): It follows from the Robinson Jump Interpolation Theorem [1971] that, for x r. e., x′ = 0′′ if and only if for every c r. e. in and above 0′′ there is a b < x with b′′ = c. As every such c is a′′ for some r. e. a by the Sacks Jump Theorem [1963a], H_{1} = {x|(∀a)(∃b < x)(a ∼_{2}b)} while this class is clearly definable by Corollary 2.5. □

Before describing the proof of Theorem 2.1, we want to discuss the issue of relativization. If z is an arbitrary degree, we denote the relativization of the r. e. degrees, the structure of degrees r. e. in and above z, by R^{z}. Now almost all results about degrees relativize. Indeed all the structural results about R mentioned in §1 are true in every structure R^{z}. On the other hand, we have learned from the various refutations of such homogeneity principles for the degrees as a whole in Shore [1979], [1982a] and the degrees below 0′ in Shore [1981] that it is precisely the types of results that we have established that lead to counterexamples to homogeneity. In the r. e. degrees, codings and embeddings of partial lattices were used in Shore [1982] to show that, in general, R is not isomorphic to R^{z}. We can relativize most, but not all, of our results to every R^{z}. Indeed, we can use the relativizations that are possible to show that R is not even elementarily equivalent to R^{z} for most degrees z.

All the technical lemmas discussed in §3 leading up to and including the proof of Corollary 2.3 relativize and so then does the first version of Theorem 2.1 and almost all the Corollaries mentioned. The notions of invariant and invariant under the double jump are the same for R^{z} as for R. However, as we mentioned before, the notion of a code for a set can no longer be viewed as simply an index. The precise method used to interpret pairs of degrees as codes for sets in N_{0} or N_{0}^{z} is prescribed by Theorem 3.7. Thus we must adjust our definition of “definable in arithmetic” accordingly. We now allow free set variables in our formulas ψ and the usual binary relation symbol ∈ for membership (i. e., the membership of a degree coding a natural number in these coded sets). An n-ary relation P on degrees is then said to be definable in arithmetic if there is such a formula ψ such that P = {⟨deg(X_{1}), …, deg(X_{n})⟩|N ⊧ ψ(X_{1}, …, X_{n})}. (Of course, this agrees with the previous definition when all the sets X_{i} are r. e.)

Theorem 2.9. For every degree z, there is a definable copy N_{0}^{z} of the structure (N , +×) in R^{z}and a definable relation associating each degree a r. e. in and above z with codes for sets of degree a′′.

Corollary 2.10. For every degree z, any relation on R^{z} which is invariant under the double jump is invariant in R^{z}.

Corollary 2.11. For every degree z, any relation on R^{z} which is definable in arithmetic (as redefined above) and invariant under the double jump is definable in R.

Corollary 2.12. For every degree z, and for each k ≥ 2 the relation x ∼_{k}y defined by x^{(k)} ≡_{T} y^{(k)} is definable in R^{z}.

Corollary 2.13. For every degree z, the jump classes L_{n}^{z} = {a| a^{(n+1)} = z^{(n+1)}} and H_{n}^{z} = {a| a^{(n)} = 0^{(n+1)}} are definable in R^{z} for n ≥ 2.

Corollary 2.14. For every degree z, the jump class H_{1}^{z} = {a| a′ = 0′′} is definable in R^{z}.

On the other hand, the proofs of the last part of Theorem 2.1 and of Corollary 2.6 do not relativize. Indeed, any attempt at talking about maps from degrees to indices or even any form of unique codes for sets of given degrees is doomed to failure as any function definable in R^{z} (and so arithmetic) taking degrees d to (unique) representatives of d would contradict arithmetic determinacy. The same is true even if we try to associate degrees (r. e. in and above z) with integers (in the standard model of arithmetic defined in R^{z}) up to any jump:

Theorem 2.15. There are degrees z such that there is no k ∈ ω and no map f from R^{z} to N_{0}^{z}, the isomorphic copy of N definable in R^{z}, which is definable in R^{z}such that a^{k} ≡_{T} b^{k} implies that f(a) = f(b).

Thus, in general, no analog of the second part of Theorem 2.1 is possible for R^{z}. The proof again involves determinacy considerations. A similar argument shows that the analog of Corollary 2.6 also fails:

Theorem 2.16. There are degrees z and c with c r. e. in and above z′′, such that the set of degrees in R^{z} with double jump c is not definable in R^{z}.

We can, in fact, use the relativized results above that do hold to show that for most z and w the structures R^{z} and R^{w} are not isomorphic and are not elementarily equivalent to R.

Theorem 2.17. If z′′≢ w′′ then R^{z} ≅ R̸^{w}.

Theorem 2.18. If z′′≢ 0′′ then R^{z} ≢ R.

As usual, the properties (sentences) demonstrating nonisomorphism (nonelementary equivalence) involve coding sets in N_{0}^{z} within R^{z} that cannot be coded in N_{0}^{w} (N_{0}) within R^{w}(R) or vice versa.

We also note that the coding structures used for the above results on R can be combined with the methods of Shore [1988] to improve the invariance and definability results established there for D(≤ 0′) by one jump (from triple to double) and so derive similar results for D(≤ 0′). The invariance of the double jump in D(≤ 0′) can then be used to give a new proof of Slaman and Woodin’s result that every degree above 0′′ is fixed under every automorphism of D.

3. Lemmas and Proofs

We will now outline the proof of these results and state the technical lemmas needed along the way. Since Theorem 2.1 includes the definability of a standard model of arithmetic, it immediately gives an interpretation of true arithmetic, T h(N , +, ×), in R. Thus, the theory of R is at least as complicated as T h(N , +, ×). (Indeed, as the structure R is obviously definable in arithmetic, the two theories have the precisely same degree.) It is not surprising then that some of the first steps along the road indicated by the biinterpretability conjecture and actually leading to our result were the coding of arithmetic into R used to prove its undecidability (Harrington and Shelah [1982]; Slaman and Woodin; Ambos-Spies and Shore [1993]). It was even known that the theories of R and N were biinterpretable:

Theorem 3.1. (Harrington and Slaman; Slaman and Woodin) There are recursive translations S(T) taking sentences ϕ(ψ) of arithmetic (partial orderings) to sentences ϕ^{S}, ψ^{T} of partial orderings (arithmetic) such that N ⊧ ϕ ↔ R ⊧ ϕ^{S} and R ⊧ ψ ↔ N ⊧ ψ^{T}.

Each proof of this theorem (including our new one) begins with one of the codings of partial orderings in R developed to prove its undecidability. They each provide a translation of the theory of partial orderings into R. As the theory of partial orderings is rich enough to code all of predicate logic, we can view the codings as providing us with models of some finite axiomatization of arithmetic. The real problem, now, is to definably determine the (translations of) sentences true in those models which are isomorphic copies of N, the standard models of arithmetic. The most natural approach to this problem would to be to define a standard model or at least a class of models all of which are standard. One would then simply say that a sentence of arithmetic is true (in N) iff the appropriate translation is true in (any of) the definable standard model(s). The proofs of this theorem by Harrington and Slaman and later by Slaman and Woodin did not manage to define standard models and took much more indirect approaches to the theorem. Thus they interpreted the theory of N but not the structure itself as we do. Our approach begins with Slaman and Woodin’s coding of partial orderings:

Theorem 3.2. (Slaman and Woodin): Given any recursive partial ordering P = ⟨ω, ⪯⟩ there are r. e. degrees p, q, r, l and g_{i} (for i ∈ ω) such that

1. the g_{i} are the minimal degrees x ≤ r such that q ≤ x ∨ p;

2. for i, j ∈ ω, i ⪯ j if and only if g_{i} ⊕ l ≤_{T} g_{j};

3. r ⊕ p ⊕ q is low, i. e. (r ⊕ p ⊕ q)′ = 0′

4. If a > 0 is any given r. e. degree, we can also make r < a.

(Parts 3 and 4 are relatively straightforward technical improvements of Slaman and Woodin’s work that we need later.)

As explained above, we are thinking of the partial ordering P as coding a model of (a finitely axiomatized version of) arithmetic. (We refer the reader to Hodges [1993, 5.3] for precise definitions of what it means to definably code (or as he says, interpret) one structure or theory in another. Roughly speaking, it means to give a sequence of formulas which define first the domain of the coded structure and then the various relations and functions on it that provide the “copy” of the structure being coded.) The key we use to definably select a set of such models that are all standard is the ability to uniformly define comparison maps between (finite) initial segments of certain such models. (The idea here is that the standard models are the models M such that each initial segment of M can be mapped into an initial segment of every model.) The crucial technical lemma needed to define such maps is one that combines Slaman and Woodin coding with cone avoiding and permitting:

Theorem 3.3. Given any recursive partial ordering P = ⟨ω, ⪯⟩ and low r. e. degrees q_{0}, …, q_{m}, r_{0}, r_{1} there are r. e. degrees p, q, r, l and g_{i} (for i ∈ ω) as in Theorem 3.2 such that if g_{f(i)} is the degree corresponding to the natural number i in the model coded by P, then g_{f(i)} ≤_{T} q_{i} and q_{i} ≰_{T} q_{j} ⇒ g_{f(i)} ≰_{T} q_{j} for i, j < m while g_{f(k)} ≰_{T} r_{0}, r_{1} for k > m.

Given two coded low models M_{1}, M_{2}, i. e., all the degrees in the domain of the models are low, we use this theorem to interpolate a third model M so that we can define isomorphisms between the first n numbers of M_{1} and those of M and between the first n numbers of M_{2} and the second n numbers of M. Together with the structure inherent in M, these maps define the desired isomorphism between the first n elements of M_{1} and those of M_{2}.

We now give a sufficient condition for a model to be standard and indicate how to get a definable scheme for maps between initial segments of such models. Thus we can define a class of models which are all standard and such that there are definable isomorphisms between the natural numbers of any two models in the class:

Definition 3.4. A model M of arithmetic (coded by parameters p, q, r, l) with elements all below some c is good with respect to c if M can be embedded into an initial segment of every model whose elements are below c by the scheme described above.

Now, every model all of whose elements are low is good and every good model is standard (as it can be mapped into some standard model). Moreover, given any two good models we can define an isomorphism between them by interpolating two other low models. Thus we can define an equivalence relation on the (codes for) natural numbers in these models and interpretations of the language of arithmetic on these equivalence classes that make the structure so defined a standard model of arithmetic.

Theorem 3.5. There is a coding scheme interpreting arithmetic in R such that all the models so defined are standard. Moreover, there is a definable equivalence relation on the parameters coding these models and the degrees coding the natural numbers in these models such that the coding scheme defines a standard model N_{0} of arithmetic on the equivalence classes.

We now have the definable copy N_{0} of N in R required by the biinterpretability conjecture. We next want to come as close as we can to associating each degree a with some kind of code (or even a standard r. e. index) for sets of that degree. The idea is to first characterize, to the extent possible, a degree a by the isomorphism type of R(≤ a) (the ordering of r. e. degrees below a) relative to certain other parameters and then translate this characterization of isomorphism type into our model of arithmetic.

The first ingredient is a coding scheme for a copy of N which efficiently codes the successor function so that it is Σ_{3} in the sense that the (codes for) the natural numbers can be enumerated recursively in 0′′. The particular method of generating such structures is taken from Shore [1981].

Theorem 3.6. Given any a > 0 and any noncappable u, there are degrees b, e_{0}, e_{1}, f_{0}, f_{1}, p, q, r, l and uniformly r. e. degrees g_{i} (for i ∈ ω) with p, q < u and all the other degrees below both a and u such that

• the minimal degrees x, b < x < r such that q ≤ x ∨ p together with the partial ordering on them defined by x ⪯ y ⇔ x ⊕ l ≤ y define a standard model of arithmetic as described above with the g_{i} as the elements i;

• for each i ∈ ω, (g_{2i} ∨ e_{1}) ∧ f_{1} = g_{2i+1} and (g_{2i+1} ∨ e_{0}) ∧ f_{0} = g_{2i+2}.

(In addition to the construction obviously need to prove this theorem, we use the characterization of the noncuppable degrees as the promptly simple degrees (Ambos-Spies et al. [1984]).)

Given these properties, each g_{i} can be defined by an existential formula using the first eight degrees and g_{0} as parameters. For example, g_{1} = (g_{0} ∨ e_{1}) ∧ f_{1} and so g_{1} is the only degree x such that ϕ_{1}(x) holds where ϕ_{1}(x) says x ≤ g_{0} ∨ e_{1} & x ≤ f_{1} & q ≤ x ∨ p. Next, g_{2} is the only degree y such that ∃x(ϕ_{1}(x) & y ≤ x ∨ e_{0} & y ≤ f_{0} & q ≤ y ∨ p). Similarly, we can define each g_{i} by such a formula. As the ordering of Turing reducibility to any set B is Σ_{3}^{B} and join is recursive on indices we can make this generating procedure recursive in 0′′ by choosing u to be low.

The next ingredient in the desired coding is a procedure that shows that every Σ_{3}^{A} set can be coded on such a set of degrees g_{i} in a positive way using ≤ and ∨ by degrees below a. Its proof uses methods from Nies [1992]. As the ordering on degrees below a is Σ_{3}^{A} (and join is recursive on indices) this would make the set coded Σ_{3}^{A} as well (and nothing better is possible).

Theorem 3.7. If ⟨g_{i}|i ∈ ω⟩ is a uniformly r. e. antichain in R, ⊕g_{i} is low, a = deg(A) and a ≰_{T} g_{i} for each i ∈ ω, then, for each Σ_{3}^{A} set S, there are c, d ≤ a such that S = {i|c ≤_{T} g_{i} ∨ d}.

Together, these results show that precisely the Σ_{3}^{A} sets can be coded in this way. As this class of sets determines a′′, we have shown that the isomorphism type of a in R determines a′′. This proves Corollary 2.3. As the coding scheme is amenable to the comparisons described above between our models of arithmetic, we can translate the codings into codings in our definable standard model and so convert this characterization of a′′ to a formula defining from the degree a a (code for a) set of degree a′′ in our standard model and so an i such that W′′_{i} ∈ a′′. This proves Theorem 2.1 and so also Corollaries 2.4–2.8.

4. Problems and Conjectures

At various earlier points in our work we had schemes for defining first the quadruple and then triple jump classes and hopes of characterizing much more. However, even before we got as far down as the double jump classes, Cooper announced (see Cooper [1966]) that he had constructed an automorphism of R and indeed one that moves a low degree to a nonlow degree so that the class of low degrees is not definable in R. Clearly, the existence of such an automorphism implies that our definability result is the best possible. Given such results, it is easy to list the next questions along these lines. Here are a few possibilities:

• Perhaps no individual degree is definable in R (and one could construct automorphisms to prove this).

• Perhaps (indeed, presumably) there are only countably many automorphisms of R.

• Perhaps each automorphism is definable in some nice way.

Of course, the existence of automorphisms of R and the nondefinability of even one individual degree each contradicts the biinterpretability conjecture and so suggests that it is time for a new paradigm. While individual problems are easy to formulate, it is not at all clear yet what new vision we might adopt. One appealing conjecture is to weaken the biinterpretability conjecture by allowing parameters.

Conjecture 4.1. (Biinterpretability for R with parameters): The relation associating each r. e. degree d to the (codes in N of) sets of its degree is definable in R from parameters.

Again, in the unrelativized setting, this conjecture is equivalent to the definability from parameters of any one-one map from R into N or of the specific map that takes each r. e. degree a to the (least) index of an r. e. set of that degree. Even this weakened form of the conjecture has important implications for automorphisms and definability in R. For example, it obviously implies that there are at most countably many automorphisms of R as each would be determined by the image of the parameters defining the required relation or map. It also implies that each type is principle in the structure of R extended by constant symbols naming these parameters and so that R is the prime model of its theory (without the parameters). (See Hodges [1993, p. 336].) Finally, it characterizes the definable relations on R as those that are definable in arithmetic and invariant in R. We should also point out that Slaman and Woodin (see Slaman [1991]) have shown that N is biinterpretable with parameters in the structure of all degrees below 0′ as well as in the degrees as a whole (with an appropriate second order version of biinterpretability).

Remark: It is obvious that definability in R implies both definability in arithmetic and invariance in R. Cooper’s claim that L_{1} is not invariant implies that the first does not imply the second. The second does not imply the first by our results. Corollary 2.3 easily implies that there are continuum many invariant subsets of R and so not all of them are definable. More specifically, we note that the classes L_{ω} = ∪L_{n} and H_{ω} = ∪H_{n} are invariant by Corollary 2.3 but are not definable in arithmetic as Solovay has shown that they are both Σ_{ω+1} complete (see Soare [1987, p. 265]). This answers two questions raised in Cooper [1996].

5. Bibliography

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, Trans. Am. Math. Soc. 281, 109-128.

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.

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.

Downey, R. G. [1990], Lattice nonembeddings and initial segments of the recursively enumerable degrees, Ann. Pure and Applied Logic 49, 97-119.

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

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

Hodges, W. [1993], Model Theory, Cambridge University Press, Cambridge, England.

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

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

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.

Muchnik, A. A. [1958], Solution of Post’s reduction problem and of certain other problems in the theory of algorithms, Trudy Moskov Mat. Obsc. 7, 391-405.

Nies, A. [1992], Definability and Undecidability in Recursion Theoretic Semilattices, Ph. D. thesis, Universität Heidelberg.

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

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

Sacks, G. E. [1963], Degrees of unsolvability, Annals of Math. Studies 55, Princeton University 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 University. Press, 2^{nd} ed., Princeton NJ .

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. [1979], The homogeneity conjecture, Proc. Nat. Ac. Sci. 76, 4218-4219.

Shore, R. A. [1981], The theory of the degrees below 0′, J. London Math. Soc. 76, 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. and Slaman T. A. [1990], Working below a low_{2} recursively enumerable degree, Archive for Math. Logic 29, 201-211.

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

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

Weinstein, B. J. [1988], On embeddings of the 1-3-1 into the recursively enumerable degrees, Ph. D. thesis, University of California, Berkeley.

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