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)

We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, (...) we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (shrink)

The main topic of the present work is the relation that a set X is strongly hyperimmune-free relative to Y . Here X is strongly hyperimmune-free relative to Y if and only if for every partial X -recursive function p there is a partial Y -recursive function q such that every a in the domain of p is also in the domain of q and satisfies p (...) Y , one also says that X is pmaj-reducible to Y . It is shown that between degrees not above the Halting problem the pmaj-reducibility coincides with the Turing reducibility and that therefore only recursive sets have a strongly hyperimmune-free Turing degree while those sets Turing above the Halting problem bound uncountably many sets with respect to the pmaj-relation. So pmaj-reduction is identical with Turing reduction on a class of sets of measure 1. Moreover, every pmaj-degree coincides with the corresponding Turing degree. The pmaj-degree of the Halting problem is definable with the pmaj-relation. (shrink)

A completely mitotic computably enumerable degree is a c.e. degree in which every c.e. set is mitotic, or equivalently in which every c.e. set is autoreducible. There are known to be low, low2, and high completely mitotic degrees, though the degrees containing non-mitotic sets are dense in the c.e. degrees. We show that there exists an upper cone of c.e. degrees each of which contains a non-mitotic set, and that the completely mitotic c.e. degrees are nowhere dense in the c.e. (...) degrees. We also show that there is a set computably enumerable in and above 0′ which is not the jump of any completely mitotic degree. (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.

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 prove that for any computably enumerable degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c d = 0′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

We provide three new results about interpolating 2-r.e. or 2-REA degrees between given r.e. degrees: Proposition 1.13. If c h are r.e. , c is low and h is high, then there is an a h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h g there is a properly d-r.e. degree a such that h a g and a is r.e. in h . Theorem 3.1. There is an incomplete nonrecursive r.e. A (...) such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob . The second combines highness with a modified version of the proof strategy of Cooper et al. . The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction. (shrink)

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.

We complete a study of the splitting/non-splitting properties of the enumeration degrees below by proving an analog of Harrington’s non-splitting theorem for the enumeration degrees. We show how non-splitting techniques known from the study of the c.e. Turing degrees can be adapted to the enumeration degrees.