# 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}$).