We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.

§1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity 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 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 with least element 0, the degree 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 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 was in some way well behaved:Theorem 1.1. Every countable partial ordering or even uppersemilattice can be embedded into.Theorem 1.2. For every nonrecursive r.e. degreeathere are r.e. degreesb, c < asuch thatb ∨ c = a.Theorem 1.3. For every pair of nonrecursive r.e. degreesa < bthere is an r.e. degreecsuch thata < c < b. (shrink)

We investigate the algebraic structure of the upper semi-lattice formed by the recursively enumerable Turing degrees. The following strong generalization of Lachlan's Nonsplitting Theorem is proved: Given n ≥ 1, there exists an r.e. degree d such that the interval $\lbrack\mathbf{d, 0'}\rbrack \subset\mathbf{R}$ admits an embedding of the n-atom Boolean algebra B n preserving (least and) greatest element, but also such that there is no (n + 1)-tuple of pairwise incomparable r.e. degrees above d which pairwise join to 0' (and (...) hence, the interval $\lbrack\mathbf{d, 0'}\rbrack \subset\mathbf{R}$ does not admit a greatest-element-preserving embedding of any lattice L which has n + 1 co-atoms, including B n + 1 ). This theorem is the dual of a theorem of Ambos-Spies and Soare, and yields an alternative proof of their result that the theory of R has infinitely many one-types. (shrink)

We show that the $\Pi_4$-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

In this paper we examine a class of pairs of recursively enumerable degrees, which is related to the Slaman-Soare Phenomenon.

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.