SPLITTING THEOREMS IN RECURSION-THEORY

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets su ch that A1 or A2 = A. Theorems about splittings have played an importa nt 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, epsilon, of recursively enumerable sets and in the uppersemilattice, R, of rec ursively enumerable degrees (since A1 less-than-or-equal-to T A, A2 le ss-than-or-equal-to T A and A less-than-or-equal-to T A1 + A2). Thus s plitting theorems have been used to obtain results about the structure of epsilon, the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splitti ngs have often generated important new technical developments in recur sion theory. In this article we survey most of the results and techniq ues associated with splitting properties of r.e. sets in ordinary recu rsion theory.