a1 University of Connecticut, Storrs, Connecticut 06068
a2 University of California at San Diego, La Jolla, California 92093
We say that a pair of r.e. sets B and C split an r.e. set A if B ∩ C = ∅ and B ∪ C = A. Friedberg [F] was the first to study the degrees of splittings of r.e. sets. He showed that every nonrecursive r.e. set A has a splitting into nonrecursive sets. Generalizations and strengthenings of Friedberg's result were obtained by Sacks [Sa2], Owings [O], and Morley and Soare [MS].
The question which motivated both [LR] and this paper is the determination of possible degrees of splittings of A. It is easy to see that if B and C split A, then both B and C are Turing reducible to A (written B ≤ T A and C ≤ T A). The Sacks splitting theorem [Sa2] is a result in this direction, as are results by Lachlan and Ladner on mitotic and nonmitotic sets. Call an r.e. set A mitotic if there is a splitting B and C of A such that both B and C have the same Turing degree as A; A is nonmitotic otherwise. Lachlan [Lac] showed that nonmitotic sets exist, and Ladner [Lad1], [Lad2] carried out an exhaustive study of the degrees of mitotic sets.
The Sacks splitting theorem [Sa2] shows that if A is r.e. and nonrecursive, then there are r.e. sets B and C splitting A such that B < T A and C < T A. Since B is r.e. and nonrecursive, we can now split B and continue in this manner to produce infinitely many r.e. degrees below the degree of A which are degrees of sets forming part of a splitting of A. We say that an r.e. set A has the universal splitting property (USP) if for any r.e. set D ≤ T A, there is a splitting B and C of A such that B and D are Turing equivalent (written B ≡ T D).
(Received February 03 1982)
(Revised April 03 1982)
1 Research supported by the National Science Foundation under grant number MCS 78-01849
2 Research supported by the National Science Foundation under grant number MCS 79-03406