# Two Disjoint Turing-recognizable languages do not have a decidable language

Let languages $A, B$ be defined as \begin{align} A &= \{\langle M\rangle\mid M(\langle M\rangle)=reject\}\\ B &= \{\langle M\rangle\mid M(\langle M\rangle)=accept\} \end{align} In other words, $A$ is the set of descriptions of TMs which reject their own descriptions and $B$ is defined similarly. The languages $A$ and $B$ are disjoint, and are both Turing-recognizable. Prove that there does not exist a decidable language $C \subseteq \Sigma^*$ such that $A \subseteq C$ and $B \subseteq \overline{C}$, the complement.

Suppose there was a decidable language, $C$, of TM descriptions such that $A\subseteq C$ and $B\subseteq \overline{C}$. Since $C$ was assumed to be decidable, there is a decider TM, $D_C$, for it. Then either $\langle\,D_C\,\rangle\in C$ or $\langle\,D_C\,\rangle\in \overline{C}$. Let's run $D_C$ on its own description:
• If $\langle\,D_C\,\rangle\in C$, then $D_C$ will accept $\langle\,D_C\,\rangle$ and hence $\langle\,D_C\,\rangle\in B\subseteq \overline{C}$, a contradiction.
• In a similar way, if $\langle\,D_C\,\rangle\in \overline{C}$, we again reach a contradiction, that $\langle\,D_C\,\rangle\in A\subseteq C$.
Since we reach a contradiction in either case, we can conclude that there is no such $C$, as desired. This non-existence, by the way, has a name: we say that $A$ and $B$ are recursively inseparable.