# Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference

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?

• Hint: is your class closed under complementation? Nov 14, 2018 at 22:04
• @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... Nov 14, 2018 at 22:15
• Now try to answer your question using this information. Nov 14, 2018 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.)