Relative Splittings of in the-Enumeration Degrees
M. M. Arslanov, Andrea Sorbi · Cambridge University Press eBooks · 2017
. We prove some results on the degrees. We show that splits in the e -degrees above any incomplete degree; on the other hand, one can find a splitting of into e -degrees b and d , such that for any degree Introduction A set A is enumeration reducible ( e-reducible ) to a set B if there exists a recursively enumerable (r. e.) set (called in this context an enumeration operator , or, simply, an e-operator ) such that The structure De of the e-degrees is the structure of the equivalence classes (called e -degrees) of sets of numbers under the equivalence relation generated by the preordering the e -degree of A is denoted by the symbol. De is in fact an uppersemilattice with least element where any r. e. set W : the partial ordering relation of will be denoted by Throughout the paper we will refer to some fixed acceptable numbering of the (r. e.) sets; we therefore obtain a corresponding listing of the e -operators. We will consider finite recursive approximations to the r.e. sets (in the sense of [20, p.16]). We get corresponding finite recursive approximations to the e -operators. We will indicate by the approximation to defined by where is some fixed finite recursive approximation to K . We adopt the usual notational conventions: see for instance Soare [20], and Cooper [9]. Given a set F , let and. Thus, We sometimes identify a given finite set with its canonical index, thus writing for instance to denote the number where u is the canonical index of F . If B and then if then It is known ([16], [19]) that the e -degrees extend the structure of the Turing degrees: the mapping defined by (where and denote the Turing degree and the characteristic function of A , respectively) defines an order theoretic embedding preserving joins and least element. The degrees McEvoy ([15]) defines a jump operation on. Of particular interest is the structure (it is known that. It is shown in [8] that S is dense and S coincides with the structure of the (in fact, if and only if). One can distinguish several substructures of S . In particular, the correspond, under the above mentioned embedding, to the r. e. Turing degrees a is a if and only if for some r. e.