A non-splitting theorem for d.r.e. sets (Q2564047): Difference between revisions

A set is called d.r.e. if it is a difference of two recursively enumerable sets. Sacks showed that for each nonrecursive r.e. set \(A\) there are disjoint r.e. sets \(B\), \(C\) which cover \(A\) such that \(A\) is recursive in neither \(A\cap B\) nor \(A\cap C\). In this paper the author constructs a counterexample which shows that Sacks' theorem is not a general true when \(A\) is d.r.e. rather than r.e. More precisely the following is proved: Theorem. There exists a properly d.r.e. set \(D\) such that for all sets \(A_0\), \(A_1\): \[ D\subseteq A_0\cup A_1 \Rightarrow [D\leq_TA_0 \cap D\vee D\leq_TA_1 \cap D]. \] The proof of this theorem is long and complicated.