Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).

I know that the class of decidable languages is closed under symmetric difference, because it is closed under union, complement and intersection. However, does this also apply to the class of partially decidable languages?

  • 1
    $\begingroup$ Hint: is your class closed under complementation? $\endgroup$ – Yuval Filmus Nov 14 '18 at 22:04
  • $\begingroup$ @YuvalFilmus I would say the class of partially decidable language is not closed under complement, due to the halting problem when trying to construct a decider for such a language... $\endgroup$ – Ponsietta Nov 14 '18 at 22:15
  • 1
    $\begingroup$ Now try to answer your question using this information. $\endgroup$ – Yuval Filmus Nov 14 '18 at 22:17

Assume partially decidable languages are closed under symmetric difference, and let $A$ be a language that is partially decidable but not decidable. Then, where $U$ is the language that includes everything,

$A \otimes U = (A - U) \cup (U - A) = \overline{A}$.

Then $\overline{A}$ must also be partially decidable, and $A$ is decidable; this is a contradiction. (This builds on an answer above, which suggested investigating complementation.)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.