Show that two disjoint languages are not separable

691 Views Asked by At

What is the general method to show that two disjoint languages are not separable? As an example, suppose we have:

$A = \{\langle M \rangle : M ( \langle M \rangle )$ halts and says ACCEPT$\}$

$B = \{\langle M \rangle : M ( \langle M \rangle )$ halts and says REJECT$\}$

If there are any resources that shed light on the matter, it would be helpful if these are linked, but I'm primarily seeking a proof technique for general problems of this nature (specifically this one, if possible).

1

There are 1 best solutions below

2
On BEST ANSWER

I do not know of any general way to know if sets are separable.

There are some condition for which we know separations do exists.

$\Pi_1^0$ or co-recursively enumerable disjoint subsets of the natural numbers can always be separated by a computable ($\Delta_1^0$) subsets of the natural numbers.

In general, for Polish spaces, $\mathbf{\Pi}_\xi^0$ have the separation property in the sense that disjoint $\mathbf{\Pi}_\xi^0$ subsets can always be separated by $\mathbf{\Delta}_\xi^0$ subsets. $\mathbf{\Sigma}_1^1$ disjoint subsets can be separated by $\mathbf{\Delta}_1^1$ sets. $\mathbf{\Pi}_2^1$ disjoint sets can be separated by $\mathbf{\Delta}_2^1$ sets. Higher separations require set theoretic assumptions. For example $V = L$ and determinacy give differing separation property for the higher projective pointclasses.

However, when you are outside of these cases whether or not a separation exists is more of a cases by cases argument. Usually you assume there is a separation and by some diagonalization argument obtain a contradiction.


Suppose there is a computable set $C$ such that $B \subset C$ and $C \cap A = \emptyset$. $C$ being computable means there is a Turing machine $U$ which halts on all inputs and $n \in C$ if and only if $U(n)$ accepts. Now lets ask where is $\langle U \rangle$. If $\langle U \rangle \in B \subseteq C$, then by defintion of $B$, $U(\langle U \rangle)$ halts and rejects. But $\langle U \rangle \in C$ which by defintion of $U$, one must have $U(\langle U \rangle)$ halts and accepts. Contradiction. Suppose $\langle U \rangle \in A$. Then $\langle U \rangle \notin C$. So $U (\langle U \rangle)$ halts and rejects. This implies that $\langle U \rangle \in B \subseteq C$ which is a contradiction again.