A non-splitting theorem for d.r.e. sets (Q2564047)

From MaRDI portal
Revision as of 06:47, 3 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
A non-splitting theorem for d.r.e. sets
scientific article

    Statements

    A non-splitting theorem for d.r.e. sets (English)
    0 references
    0 references
    26 June 1997
    0 references
    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.
    0 references
    0 references
    difference recursively enumerable sets
    0 references
    \(T\)-degrees
    0 references

    Identifiers