a1 Department of Mathematics, University of Chicago, Chicago, IL 60637, USA. E-mail: firstname.lastname@example.org
a2 Department of Mathematics, Cornell University, Ithaca, NY 14853, USA. E-mail: email@example.com
a3 Department of Mathematics, University of California, Berkeley, CA 94720, USA. E-mail: firstname.lastname@example.org
§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  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 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 .
The (positive) solution of Post's problem by Friedberg  and Muchnik  was followed by various algebraic or order theoretic results that were interpreted as saying that the structure was in some way well behaved:
Theorem 1.1 (Embedding theorem; Muchnik , Sacks ). Every countable partial ordering or even uppersemilattice can be embedded into .
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 ). For every pair of nonrecursive r.e. degrees a < b there is an r.e. degree c such that a < c < b.
(Received September 26 1996)