[Math] If $L_1 \cap L_2$ is decidable, prove/disprove that $L_1$ and/or $L_2$ are decidable

formal-languagesproof-verificationturing-machines

Question:

Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are).

Definition of a decidable language:
A language L is decidable if there exists a Turing-machine $M$ such that on input $x$, $M$ accepts if $x \in L$, otherwise $M$ rejects $x$.

Proof:

By the definition of a decidable language, we know that $M$ over $\Sigma$ accepts input $x \in L_1 \cap L_2$ and rejects $x$ otherwise. This means we can construct another Turing-machine $M'$ such that, $M'$ accepts $x \in \overline{L_1} \cup \overline{L_2}$ when $M$ rejects and reject when $M$ accepts. We know that both $L(M)$ and $L(M')$ are both decidable languages. Since $L(M) \cup L(M') = \Sigma^*$, $\Sigma^*$ is decidable and so $L_1 \subseteq \Sigma^*$, $L_1$ must be a decidable language. By the same logic $L_2 \subseteq \Sigma^*$ which means $L_2$ is also a decidable language.

Best Answer

Let $U$ be an undecidable subset of the natural numbers. Let $L_1$ be the set of all $2x$, where $x$ ranges over $U$, and let $L_2$ be the set of all $2x+1$, where $x$ ranges over $U$.

Then $L_1\cap L_2$ is empty, hence trivially decidable, but $L_1$ and $L_2$ are not.

Remark: In more "language" language, let $L_0$ be an undecidable language over the alphabet $\{x\}$. Let $L$ be the same language, considered over the alphabet $\{x,a,b\}$. Let $L_1$ be obtained from $L$ by replacing every occurrence of $t$ by the letter $a$, and let $L_2$ be obtained in the same way, using the letter $b$. Then $L_1\cap L_2$ is clearly decidable, while $L_1$ and $L_2$ are not.