Difference of two decidable languages?

Question

I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their difference L1 - L2 also decidable?

Answer 1

We know that if a language $L$ is decidable, then the complement $\overline{L}$ is also decidable, since we can simply reverse the accept and reject conditions in the Turing machine deciding $L$.

Furthermore, if $L_1$ and $L_2$ are decidable languages, then their intersection $L_1 \cap L_2$ is decidable, since we can accept if both the Turing machines for $L_1$ and $L_2$ accept, and reject if one of them rejects.

Since $L_1 - L_2 = L_1 \cap \overline{L_2}$, we therefore get that if $L_1$ and $L_2$ are decidable languages, then $L_1 - L_2$ is also decidable.

---

A more direct way to see this is to let $M_1$ and $M_2$ be Turing machines deciding $L_1$ and $L_2$, respectively and construct a Turing machine $M$ which accepts if and only if $M_1$ accepts and $M_2$ rejects. Then $M$ decides the language $L_1 - L_2$.