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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q199794
RedirectionBot (talk | contribs)
Changed an Item
Property / reviewed by
 
Property / reviewed by: Roland Sh. Omanadze / rank
 
Normal rank

Revision as of 17:41, 10 February 2024

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
    difference recursively enumerable sets
    0 references
    \(T\)-degrees
    0 references

    Identifiers