[Math] Example for 2 disjoint languages that cannot be separated by a decidable language

computability

Question:
Let A, B be languages such that A ∩ B = ∅.
Say that a language C separates A and B if: A ⊆ C and B ⊆ $C^c$.
Describe two languages A, B ∈ RE, that cannot be separated by any C, such
that C ∈ R.
R is the class of decidable languages and RE is that class of Recursively Enumerable languages.

Thoughts:
First I thought about taking language and it's complement- But I've read that both language and complement cannot reside at the same time in RE.
Second try: (on $\Sigma=${a,b,c})
(M is a TM)

A={$<M>$ | $L(M) \subseteq a^*$} (we've seen in class this is undecidable)

B={$<M>$ | $L(M) \subseteq b^*$}

C={$<M>$ | $L(M) \subseteq a^*c^*$}

So C is also in RE as I see it, But I'm afraid also that $C^c$ is also in RE which may destroy my idea.
Is this a good direction? Other suggestions?

Best Answer

Consider an acceptable programming system $\varphi_i$ for $i\in\mathbb N$.

  1. Let $A=\{i\;|\;\varphi_i(i)=0\}$
  2. Let $B=\{i\;|\;\varphi_i(i)=1\}$

$A$ and $B$ are RE.

Suppose there is a recursive set $C$ that separates $A$ and $B$. As $C$ is recursive, there is $c$ such that $\varphi_c(x)=1$ if $x\in C$ else $0$

Then $$\varphi_c(c)=1 \Rightarrow c\in B \Rightarrow c\notin C\Rightarrow \varphi_c(c)=0$$

$$\varphi_c(c)=0 \Rightarrow c\in A \Rightarrow c\in C\Rightarrow \varphi_c(c)=1$$

This is impossible : there is no such recursive set $C$.

Related Question