The biinterpretability conjecture for the r.e. degrees asks whether, for each sufficiently large k, the [Formula: see text] relations on the r.e. degrees are uniformly definable from parameters. We solve a weaker version: for each k ≥ 7, the [Formula: see text] relations bounded from below by a nonzero degree are uniformly definable. As applications, we show that Low 1 is parameter definable, and we provide methods that lead to a new example of a ∅-definable ideal. Moreover, we prove that (...) automorphisms restricted to intervals [d, 1], d ≠ 0, are [Formula: see text]. We also show that, for each c ≠ 0, can be interpreted in [0, c] without parameters. (shrink)

§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)

In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to showing that the index set of the c.e. strongly jump traceables is image-complete.

We consider the relationship of the lattice-theoretic properties and the jump-theoretic properties satisfied by a recursively enumerable Turing degree. The existence is shown of a high2 r.e. degree which does not bound what we call the base of any Slaman triple.

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)

Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, ${{\bf 0' = b \lor x}}$ if and only if (...) ${{\bf 0' = a \lor x}}$ . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. (shrink)

We show that there is a computable procedure which, given an ∀∃-sentence ${\varphi}$ in the language of the partially ordered sets with a top element 1 and a bottom element 0, computes whether ${\varphi}$ is true in the Medvedev degrees of ${\Pi^0_1}$ classes in Cantor space, sometimes denoted by ${\mathcal{P}_s}$.

We study the jump hierarchy of d.c.e. Turing degrees and show that there exists a high d.c.e. degree d which does not bound any minimal pair of d.c.e. degrees.

It is shown that there exists a low2 Harrington non-splitting base-that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if $0' = x \vee y$ , then either $0' = x \vee a$ or $0' = y \vee a$ . Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the $low_{2}-ness$ requirements to be satisfied, and the proof given involves new techniques with potentially wider application.