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

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.

• How does $L_1$ - decidable follow from $L(M) \cup L(M') = \Sigma^*$ and $L_1 \subseteq \Sigma^*$? – xyzzyz Jan 28 '14 at 22:00
• Oh I was assuming that $\Sigma^*$ is decidable since $L(M) \cup L(M')$ are both decidable? I missed putting that in. – 1337holiday Jan 28 '14 at 22:07
• $\Sigma^*$ is always decidable : it is recognized by a Turing machine which always accepts. – fkraiem Jan 28 '14 at 22:08
• hmm yes that makes sense, I'm confused about how $M$ works then, when it says that $M$ accepts $x \in L_1 \cap L_2$, does it mean that $M$ checks if $x \in L_1$ and $x \in L_2$, in which case accept, otherwise reject? – 1337holiday Jan 28 '14 at 22:13
• I'd suggest supposing that $L_1$ contains a bunch of nonsense and {a,b,c}, then $L_2$ contains different nonsense and {a,b,c}. Then suppose further that $L_1 \cap L_2 = \{a,b,c\}$ is decidable. What would you say about $L_1$ and $L_2$, then? – jasotastic Jan 28 '14 at 22:20

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.
• I see, but what property of $L_1$ and $L_2$ makes them undecidable, is it because they are an infinite set? – 1337holiday Jan 28 '14 at 22:21
• No. Suppose that we had an algorithm for deciding, for any $y$, whether $y$ is in $L_1$. Then we could input $2x$ into that algorithm, and we would get an algorithm for deciding whether $x\in U$. By the definition of $U$, there is no such algorithm. (And you know that there are undecidable subsets of the natural numbers, just pick your favourite.) – André Nicolas Jan 28 '14 at 22:26