# Given 3 disjoint Turing-recognizable languages prove that one of them is decidable

Let $$A$$, $$B$$, $$C$$ be Turing-recognizable languages over an alphabet $$\Sigma$$. Assume that

• $$A\cup B\cup C = \Sigma^*$$, and
• $$A\cap B = A\cap C = B\cap C = \emptyset$$.

Prove that $$A$$ is Turing-decidable.

So far I've tried the following but it really hasn't gotten me anywhere.

Suppose $$A$$ is recognizable but not decidable then, $$\overline{A} = B \cup C$$ so $$B$$ or $$C$$ is undecidable, since decidable languages are closed under union.

In the case that only one is decidable you can show at least that its in $$A$$ or $$B$$ (or $$A$$ or $$C$$ in the other case). Then, ... ?

In the case that both are recognizable, ... ?

• I've no idea if this observation is any use but the setup is completely symmetrical so, if $A$ is decidable, they all are. – David Richerby Nov 16 '16 at 0:41
• $B\cup C$ is the complement of $A$. That should help. – Hendrik Jan Nov 16 '16 at 1:37

$A$ is recognizable by assumption. Since $\overline{A}=B\cup C$ is recognizable (recognizable languages are closed under union) we have that $A$ and $\overline{A}$ are recognizable, and hence $A$ must be decidable (it's a simple exercise to construct a decider for $A$ from the recognizers of $A$ and $\overline{A}$).