Proving a language is not recognizable

2.7k Views Asked by At

I have the following question that I just want to verify I have done correctly.

Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is not recognizable then $L_1$ is not recognizable.

Proof

By definition since we know $L_2$ is decidable then there exists a Turing machine $M$ over $\Sigma$ such that for some input $w \in L_2$, $M$ either accepts or reject $w$.

Case 1:

Suppose that $L_2 = \emptyset$ then, $L = L_1 \cup \emptyset$ and thus $L = L_1$. By the original assumption, if $L$ is not recognizable then neither is $L_1$.

Case 2:

We know that $L = L_1 \cup L_2$ and that $L_2$ is decidable. Since $L_2$ is decidable, by definition, it is also recognisable by some recogniser $R$. We also know that $L$ is not recognizable. Suppose now that $L_1$ was recognisable by some recogniser $Q$. This means that we can use the recogniser $R$ and $Q$ in an alternating fashion to recognise $L$, but $L$ is unrecognisable so this is a contradiction. Therefore $L_1$ must be unrecognisable.