The Theories of the T, tt and wtt R. E. Degrees: Undecidability and Beyond

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

Abstract

We discuss the structure of the recursively enumerable sets under three reducibilities: Turing, truth-table and weak truth-table. Weak truth-table reducibility requires that the questions asked of the oracle be effectively bounded. Truth-table reducibility also demands such a bound on the the length of the computations. We survey what is known about the algebraic structure and the complexity of the decision procedure for each of the associated degree structures. Each of these structures is an upper semilattice with least and greatest element. Typical algebraic questions include the existence of infima, distributivity, embeddings of partial orderings or lattices and extension of embedding problems such as density. We explain how the algebraic information is used to decide fragments of the theories and then to prove their undecidability (and more). Finally, we discuss some results and open problems concerning automorphisms, definability and the complexity of the decision problems for these degree structures.

∗This paper was given at both the Annual meeting of the ASL (Duke, 1992) in honor of Joseph Shoenfield and the LASML (Bahia Blanca, 1992). The research was partially supported by NSF Grants DMS-891279 and DMS-9204308 and ARO through MSI, Cornell University DAAL-03-91-C-0027.

In this paper we will discuss the structure of the recursively enumerable sets, those that can be effectively enumerated, under various reducibilities. The primary reducibility is that of Turing:

B ≤_{T} A ≡ There is Turing machine Φ which, when equipped with an oracle for A, can compute (the characteristic function of) B, Φ^{A} = B.

(We refer the reader to Rogers [1967] or Odifreddi [1989] for basic information on recursion theory and any unexplained notation.)

This reducibility is the most general effective one and allows for computations potentially unbounded in both the amount of information they require of the oracle and the number of steps they take to converge. Indeed, for various machines, oracles and inputs, Φ^{A}(x) may not converge at all. We wish to consider two other reducibilities that restrict access to the oracle by imposing recursive a priori bounds on the questions that can be asked, i. e. we specify a recursive function f and require that the computation of B(x) from A via Turing machine Φ use only information about the initial segment of A of length f(x). If this is the only restriction put on the reduction of A to B, the resulting reducibility is called weak truth table, wtt, reducibility: B ≤_{wtt} A.

Here too, there is no a priori bound on the length of the computation and some computations Φ^{A}(x) may still diverge. If, in addition, we recursively bound the length of the computations (and give some default output such as 0 if the computation has not converged within the specified time bound), or equivalently require that Φ^{A}(x) converge for every A and x, then we get the more familiar notion of truth table reducibility:

B ≤_{tt} A ≡ There is a recursive function h which for, every x, specifies a truth table h(x) based on elements of size at most f(x) such that x ∈ B iff A satisfies the truth table given by h(x).

(Bounding the length of the computations in this way obviously implies that they always converge. For the other direction of the equivalence (due to Nerode) look at the tree of all possible computations for any set oracle. If the computations with input x halt along every path (i. e. for every oracle) then, by König’s Lemma, the whole tree is finite. Thus we can recursively find a bound on the length of all possible computations on input x for any oracle.)

Each of these reducibilities, r, induces, in the usual way, an equivalence relation on sets with equivalence classes given by deg_{r}(A) = {B|A ≤_{r} B & B ≤_{r} A}, the class of sets equicomputable (with respect to r-reducibility) with A. The induced partial ordering ≤_{r} on the equivalence classes defines the associated degree structure R_{r}. These three partial orderings, R_{T}, R_{tt} and R_{wtt}, share several basic algebraic properties:

1. All of the structures are upper semi-lattices with least element 0 (the degree of the recursive sets) and greatest element 1, the degree of the halting problem, i. e. of the complete r. e. set

K = {⟨x, y⟩| the x^{th} T uring machine, Φ_{x}, halts on input y}.

2. Every countable partial ordering can be embedded in each structure and so the three structures have the same decidable ∃-Theory. (That is, there is an effective procedure for determining which sentences in the language with just ordering which consist of an initial string of existential qualifiers followed by a quantifier free matrix are true in the structure: Any sentence in the language of partial orderings of the form ∃x_{1}∃x_{2}...∃x_{n}Ψ(x_{1}, x_{2}, ..., x_{n}) with Ψ quantifier free is true in R_{r} iff it is consistent with the theory of partial orderings, i. e. there is a partial ordering of size at most n in which it is true. The truth of this last assertion can clearly be determined effectively.)

The three degree orderings, however, are very different once one goes up even slightly in the complexity of the questions one is considering to either the ∀∃-Theories of the structures (sentences with one alternation of quantifiers, i. e. of the form ∀y_{1}...∀y_{m}∃x_{1}...∃x_{n}Ψ(x_{1}, ..., x_{n}, y_{1}, ..., y_{m})) or even to the extension of embedding problem (when, given two partial orderings X ⊆ Y, is it always possible to find, for every embedding f of X into R_{r}, an extension g of f which maps all of Y into R_{r}). The archetypic example of such questions is whether the structures are dense. In the first format, this is the question of the truth of the sentence ∀x∀y∃z(x < y → x < z < y). In the second format, the question is if, for every embedding of the partial order X with two elements x < y, there is an extension to the partial order Y with three elements x < z < y. The investigation of these sorts of problems has been a source a much of our knowledge about the structures R_{r}.

Sacks [1964] answered this archetypic problem for R_{T} by proving that it is dense. This prompted Shoenfield [1965] to conjecture that R_{T} might be dense even as an usl with 0 and 1 (or as one might prefer to say now, saturated with respect to finite sets of quantifier free formulas consistent with the theory of an usl with least and greatest elements 0 and 1). As with Cantor’s theorem for dense linear orderings, this conjecture would have implied, by the usual back and forth argument, that R_{T} is a model of a theory of usl’s which has, up to isomorphism, only one countable model. On general model theoretic grounds, its theory, like that of dense linear orderings, would then be decidable.

The first counterexample to Shoenfield’s conjecture was the existence of minimal pairs proven by Lachlan [1966] and Yates [1966]: There exist nonzero r. e. T-degrees a and b such that there the only r. e. degree below both of them is 0. (Thus the formula Ψ(x) = (x < a & x < b & x ≠ 0), although consistent with the theory has no realization in R_{T}.) The constructions of Lachlan and Yates began, in terms of both structural analysis and technology of proofs, the long road to the proof of the undecidability of R_{T} :

Theorem (Harrington & Shelah [1982]): R_{T} is undecidable, i. e. there is no recursive procedure for determining the truth of sentences (in the language with ≤_{T}) in R_{T}. Proof Plan: Given a Δ_{2}^{0} (or, equivalently, recursive in K) partial ordering P = ⟨{p_{i}|i ∈ ω}, ≤⟩, one constructs r. e. degrees a, a_{i}, b, c and d such that

1. {a_{i}} is the set of maximal degrees x ≤_{T} a such that c ≰_{T} b ∨ x.

2. p_{i} ≤ p_{j} ⇔ a_{i} ≤_{T} a_{j}∨d.

Note that any sentence true in some partial ordering is true in a Δ_{2}^{0} one by an analysis of the standard Henkin completeness proof. Thus this construction provides an interpretation of the theory of partial orderings in that of R_{T} . The undecidability of the theory of partial orderings then gives the undecidability of R_{T} . In fact, it suffices to code all finite partial orderings into a structure to show that its theory is undecidable. The proof of this fact relies on the hereditary undecidability of the theory of partial orderings. (A general exposition of these procedures for proving undecidability can be found in Ambos-Spies, Nies and Shore [1992]).

The situation for R_{tt} is quit different. Indeed, Degtev [1973] and Marchenkov [1975] proved that there is a minimal r. e. tt-degree. The proof they provide, however, is quite indirect and does not lend itself to the construction of other initial segments of R_{tt}. A direct construction of such a degree was found by Fejer and Shore [1989]. This construction was then extended to prove the undecidability of R_{tt} :

Theorem (Haught & Shore [1990]): For every n ∈ ω, there are r. e. tt degrees a and b such that, in R_{tt}, [a, b] (= {x|a ≤ x ≤ b}) is isomorphic to the lattice of all equivalence relations on a set of n elements. Indeed, a and b can be constructed so that {0} ∪ [a, b] is an initial segment of R_{tt} (or even of all the tt-degrees).

Corollary (Haught & Shore [1990]): R_{tt} is undecidable.

At first glance, this approach to the undecidability of R_{tt} seems somewhat ad hoc or forced. Why not prove that every finite lattice (or at least some reasonable collection of them) is isomorphic to an initial segment of R_{tt} and so get the undecidability of its theory. This after all was the route to the undecidability of the theory of the r-degrees of all sets for many reducibilities including Turing, tt and wtt. (See Lachlan [1968] for the distributive lattices and Lerman [1971] for all finite ones and Nerode and Shore [1980] for transferring the results to reducibilities other than Turing.) As it turns out, this is not possible. Various restrictions on the initial segments of R_{tt} have been found by Harrington and Haught [1993] including the following: Every finite initial segment of R_{tt} has a least nonzero element.

Now R_{wtt} lies between R_{T} and R_{tt} in many ways that defeat both types of attempts at proving undecidability. Like R_{T}, R_{wtt} is dense and has minimal pairs (the same proofs work), but R_{wtt} is much more homogeneous than R_{T}:

1. In R_{T} some degrees are branching (i. e. they are the infimum of two other degrees) but not all; in R_{wtt} all degrees are branching. (See Lachlan [1966], Yates [1966] and Ladner and Sasso [1975].)

2. In R_{T} some degrees b can be split over all lower degrees (i. e. for every c < b there are b_{0} and b_{1} such that c < b_{0}, b_{1} < b and b_{0} ∨ b_{1} = b) but not all; in R_{wtt} every degree b splits over every c < b. (See Sacks [1963], Lachlan [1975] and Ladner and Sasso [1975].)

The most striking algebraic difference between the structures is that R_{wtt} is distributive (as an usl):

If a_{0} ∨ a_{1} ≥ b, then (∃b_{i} ≤ a_{i})(b_{0}∨b_{1} = b).

(See Lachlan [1972] and Stob [1983].) (To see that this corresponds to the notion of distributivity in a lattice, suppose we actually had a lattice structure and consider c = (a_{0} ∨ a_{1}) ∧ b. Distributivity would say that c = (a_{0} ∧ b) ∨ (a_{1} ∧ b). Thus the required degrees would be b_{0} = (a_{0} ∧ b) and b_{1} = (a_{1} ∧ b).) On the other hand, both basic nondistributive lattices are embeddable (as lattices) in R_{T} (Lachlan [1972]).

As Shoenfield pointed out to me in 1984, the proofs of undecidability of R_{T} can not work for R_{wtt}. The type of constructions used in the proofs for R_{T} inherently produce unbounded Turing reductions. The problem is that they are tree arguments at the level of 0′′′ which directly build the required reductions in complicated ways. Moreover, as Stob [1983] also remarks, the codings themselves are inherently nondistributive. (In a dense, distributive usl there is no maximal x < a such that c ≰ x ∨ b, i.e. for every x < a, and every b and c with c ≤ a ∨ b but c ≰ x ∨ b, there is a y such that x < y < a and c ≰ y ∨ b: By hypothesis, x ∨ b < a ∨ b = a ∨ b ∨ c; by density, ∃d(x ∨ b < d < a ∨ b); by distributivity, (∃y < a)(y ∨ b = d); finally, as x < d and c ≰ d, we may take y ∨ x to be the required counterexample to maximality.)

There are really two problems:

1. Find an “easier” proof that R_{T} is undecidable.

2. Prove that R_{wtt} is undecidable. Two years ago two answers to the first problem were found. Both had the same basic plan as the Harrington & Shelah proof: Find a definition Φ(x, a⃗) from parameters a⃗ such that, for enough partial orderings P, there are degrees a⃗ and d such that ⟨{x ∨ d|Φ(x, a⃗)}, ≤_{T} ⟩ ≅ P :

Slaman & Woodin [1994]: Φ(x, a, b, c) ≡ x is minimal ≤ a such that c ≤_{T} x ∨ b; “enough” = all Δ_{2}^{0}.

Ambos-Spies & Shore [1993]: Φ(x, a, b) ≡ x is maximal such that there is a b with b ∧ x = a; “enough” = all finite.

The second construction supplies a particularly simple proof that uses only the branching and nonbranching degree constructions (as in Soare [1987, IX]) in a standard 0′′ priority argument. However, in the setting of the wtt-degrees, the nontriviality of either of these definable sets also violates distributivity.

More recently, a quite different approach to the undecidability of R_{wtt} has been found:

Theorem (Ambos-Spies, Nies & Shore [1992]): R_{wtt} is undecidable. Proof Plan: 1. (Ambos-Spies & Soare [1989]): There exists a uniformly r. e. sequence of sets A_{i} such that, in both R_{T} and R_{wtt}, their degrees a_{i} are pairwise minimal pairs but no one of them bounds a minimal pair.

2. The ideals I of r. e. wtt-degrees with a uniformly r. e. (or equivalently a Σ_{3}^{0}) sequence of representatives are precisely those with exact pairs x and y, i. e. I = {z|z ≤_{wtt} x & z ≤_{wtt} y}.

3. By an algebraic argument, the distributivity of R_{wtt} now guarantees that the set of degrees A = {a_{i}} given in (1) is independent (no element is below the join of any finite number of other elements of the set) and definable from the exact pair for the ideal it generates. It then follows that the class of subsets of A which generate ideals determined by exact pairs is isomorphic to E^{3} the lattice of all Σ_{3}^{0} subsets of the natural numbers N:

⟨{C ⊆A|∃x, y∀z(z ∈ C ⇔ z < x & z > y}, ⊆⟩ ≅ ⟨E^{3}, ⊆⟩.

4. (Herrmann [1983] and [1984]): E, the lattice of all r. e. (Σ_{1}^{0}) subsets of N and indeed, for each n, E^{n}, the lattice of all Σ_{n}^{0} subsets of N, is hereditarily undecidable. Thus any structure in which we can interpret E^{n} with parameters is undecidable. Of course, the above steps show that we can interpret E^{3} in R_{wtt} using as parameters the exact pair defining the ideal generated by A.

We must admit, however, that the proofs of the results used here from Ambos-Spies & Soare [1989] and Herrmann [1983] and [1984] are quite difficult and so we can hardly claim to have an elementary proof of the undecidability of R_{wtt}. In addition, this proof does not work for R_{T} and so we still have no uniform proof for the two structures.

We must now explain the word “beyond” of our title. We have in mind several aspects of the theories of the degree structures that we are discussing. First, what more can we about the complexity of the theories than that they are undecidable. As recursion theorists we are not satisfied simply with the assertion that they are not recursive. We want to know the precise degree of the theory of each structure; to characterize their “true theories”. For both the r. e. Turing and truth-table degrees the theories of their structures are as complicated as possible. Of course, both are definable in first order arithmetic and so are reducible to the true theory of N, the natural numbers with addition and multiplication. The degree of this theory is that of ∅^{(ω)} = {⟨x, n⟩|n ∈ ∅^{(n)}}, the recursive join of all finite iterations of the halting problem. This is also the degree of each of these theories. Indeed they are 1-1 equivalent. (This is equivalent to the existence of a recursive permutation of N that takes one set of sentences to the other.)

Theorem (Harrington & Slaman; Slaman & Woodin [1994]):

T h(R_{T}) ≡_{1−1} T h(N , +, x, 0, 1) ≡_{1−1} 0^{(ω)}.

Theorem (Nies & Shore [1993]):

T h(R_{tt}) ≡_{1−1} T h(N , +, x, 0, 1) ≡_{1−1} 0^{(ω)}.

Proof Plan: In addition to coding models of arithmetic, we must definably pick out some (codes for) standard models. The proofs for R_{T} use the previous codings and pick out some standard models as ones whose natural numbers are embeddable in all other models. It uses among other ideas the definability of prompt simplicity (a property of enumerations of r. e. sets) in degree theoretic terms (Ambos-Spies et al. [1984]). The proof for R_{tt} extends the previous embedding results to include certain recursive lattices of equivalence relations that are used to code nicely generated models of arithmetic. The standard ones are then picked out as the ones all of whose proper initial segments which are defined by exact pairs have greatest elements. It need a new exact pair theorem for R_{tt}: If I is a Σ_{3}^{0} ideal in R_{tt} and every member of I is strictly below K in Turing degree, then I has an exact pair in R_{tt}.

Along these lines, we mention two, perhaps related, open questions:

Question: T h(R_{wtt}) ≡_{1−1} T h(N , +, x, 0, 1) ≡_{1−1} 0^{(ω)}? Question: T h(E) ≡_{1−1} T h(N , +, x, 0, 1) ≡_{1−1} 0^{(ω)}?

Another measure of the complexity of a theory is the number of 1-types consistent with it. The results of Ambos-Spies and Soare [1989] show that ℵ_{0} many 1-types are realized in R_{T} and R_{wtt} while those of Haught and Shore [1990] give the same result for R_{tt}. The proof of undecidability of R_{T} in Ambos-Spies and Shore [1993] also shows that its theory has as many 1-types as possible, 2^{ω}.

Question: Are there continuum many 1-types over the theories of R_{tt} and R_{wtt}?

Finally, we come to our last topic beyond undecidability, the related issues of definability and automorphisms. There are one or two examples of classes of r. e. degrees with natural nonorder theoretic definitions which are definable from the ordering on degrees:

Theorem (Ambos-Spies, Jockusch, Shore & Soare [1984]): The promptly simple r. e. Turing degrees are the noncappable ones (i. e. those degrees a such that there is no b with a ∧ b = 0).

Theorem (Downey & Shore [1993]): The low_{2} r. e. tt-degrees (i. e. those a such that a′′ = 0′′) are precisely those with minimal covers (i. e. those a such that there is a b < a with no c between a and b).

There are some hopes for defining the low_{2} r. e. T-degrees as well as Slaman and Shore [1990], [1993] have definably separated the low_{2} from the high degrees in R_{T}.

Question: Is any degree other than 0 and 0′ definable in any of these structures? Are any of the jump classes definable in R_{T}?

The last issue we want to address is the problem of the existence of automorphisms. A purely algebraic argument based on distributivity supplies us with isomorphic intervals in R_{wtt}. (Suppose a ∧ b = c. The map taking x ∈ [c, a] to x ∨ b ∈ [b, a ∨ b] is an isomorphism. It is onto by a direct application of distributivity. To see that it is one-one, suppose that x < y but x ∨ b = y ∨ b. As y < x ∨ b, there is a d < b such that d ∨ x = y. Note, however, that as d < y, d < a. Thus d < a, b and so d ≤ c. As this would imply that d ∨ x = x, we have the desired contradiction.) Similarly, the initial segment results for R_{tt} supply isomorphic intervals. Otherwise, almost nothing is known about the possible existence of automorphisms for any of the structures. This leaves us with the obvious questions:

Question: Are there any nontrivial automorphisms of R_{T},R_{tt} or R_{wtt}? Indeed, are there any nontrivial isomorphic initial segments of R_{T} or R_{wtt}?

There is, however, a quite remarkable result connecting this problem with that for the Turing degrees of all sets:

Theorem (Slaman & Woodin [1994] see also Slaman [1991]): If R_{T} is rigid, i. e. has no nontrivial automorphisms, then so is D_{T} the structure of all the Turing degrees.

The most intriguing suggestion is Harrington’s far reaching proposal that R_{T} might be interdefinable (or biinterpretable) with (the standard model of) arithmetic, that is not only can we define the standard model of arithmetic in R_{T} but we can define a map taking each r. e. degree a to (a code for) an index e for a representative W_{e} ∈ a in the model. Now Simpson [1977] and Shore [1982] provide such outright (parameterless) interpretations of second order arithmetic in D′_{T} and D_{T} respectively that are correct on a cone (i. e. on the set of degrees above a fixed degree z). Slaman & Woodin prove the above result on rigidity by constructing such an interpretation which is correct for all of D_{T} from r. e. parameters.(See Slaman [1991], where Slaman and Woodin conjecture that this proposal is true, for a discussion of this notion in various degree structures and many applications.) In particular, a proof of the interdefinability of first order arithmetic and R_{T} would show that every r. e. Turing degree is definable in R_{T}, that R_{T}, D_{T} and many other degree structures are rigid and indeed that D_{T} is interdefinable with second order arithmetic. We are thus lead to our final open problem, or perhaps better, program:

OPEN PROBLEM (PROGRAM): Work towards proving the interdefinability of R_{T} (R_{tt} and R_{wtt}) and first order arithmetic!

References

Ambos-Spies, K., Jockusch, C. G., 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., Nies, A. and Shore, R. A. [1992], The theory of the recursively enumerable weak truth-table degrees in undecidable, J. Symb. Logic 57, 864-874.

Ambos-Spies, K. and Shore, R. A, Undecidability and 1-types in the recursively enumerable degrees [1993], Ann. Pure and Applied Logic, to appear.

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.

Downey, R. and Shore, R. A. [1993], Degree theoretic definitions of the low_{2} recursively enumerable sets, to appear.

Harrington, L. and Haught, C. [1993], Limitations on initial segment embeddings in the r. e. tt-degrees, to appear.

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

Haught, C. and Shore, R. A. [1990], Undecidability and initial segments of the (r. e. ) tt-degrees, J. Symb. Logic 55, 987-1006.

Herrmann, E. [1983], Definable Boolean pairs and the lattice of recursively enumerable sets, Proc. Conf. Model Th., Seminarberichte 49, Sektion Mathematik, Humboldt-Universität, Berlin, 42-67.

Herrmann, E. [1984], The undecidability of the elementary theory of the lattice of recursively enumerable sets (abstract), in Proc. 2^{nd} Frege Conference at Schwerin, GDR, 1984, G. Weschung, ed., Akademie-Verlag, Berlin, Math. Forschung 20, 66-72.

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

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

Lachlan, A. [1972], Embedding nondistributive lattices in the recursively enumerable degrees, in Conf. in Math. Logic, London (1970), W. Hodges, ed., LNMS 255, Springer-Verlag, Berlin, 149-177.

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

Ladner, R. E. and Sasso, L. P. [1975], The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8, 429-448.

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

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.

Nies, A. and Shore, R. A. [1993], Interpreting true arithmetic in the theory of the r. e. truth-table degrees, to appear.

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

Rogers H. Jr. [1967], Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (reprinted MIT Press, Cambridge, Mass., 1988).

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

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

Shoenfield, J. R. [1965], Applications 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. [1982], 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. [1990], Working below a low_{2} recursively enumerable degree, Archive for Math. Logic 29, 201-211.

Shore, R. A. and Slaman, T. [1993], Working below a high recursively enumerable degree, J. Symb. Logic, to appear.

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

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

Slaman, T. and Woodin, H. [1994], Definability in Degree Structures, in preparation.

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

Stob, M. [1983], wtt-degrees and T-degrees of r. e. sets, J. Symb. Logic 48, 921-930.

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