Some reducibilities and splittings of recursively enumerable sets (Q1972524): Difference between revisions

Let \(r\) be a reducibility. A computably enumerable (c.e.) set A has a strong \(r\)-universal property (s.u.p) if for all c.e. sets \(B_0\), \(B_1\), if \(A\equiv_r B_0\oplus B_1\) then there exist disjoint c.e. sets \(A_0\), \(A_1\) such that \(A=A_0\cup A_1\) and \(A_0\equiv_r B_0\), \(A_1\equiv_r B_1\). This property was studied previously for Turing reducibility by Ambos-Spies and Fejer. The author proves that no c.e. semirecursive set possesses s.u.p. relatively to \(Q\)-reducibility. A c.e. set \(A\) has a universal \(R-r\) reduction property if for any c.e. \(B\), if \(B\leq_R A\), then \(B\leq_r A\). Theorem 2 asserts that every non-zero contiguous \(T\)-degree contains a c.e. set possessing the \(T-Q\) universal reduction property but not \(T-Q\) maximal. Some other results concerning semirecursive and speedable c.e. sets are proved.