# Existence of recursively inseparable sets that are recursively enumerable

A set $A \subseteq \mathbb{N}$ is recursively enumerable if there exists a $\mu$-recursive function which enumerates it. Two sets $A, B \subseteq \mathbb{N}$ are recursively inseparable if there does not exists a set $C \subseteq \mathbb{N}$ such that $A \subseteq C$ and $B \cap C = \varnothing$. That is to say, any superset of $A$ will necessarily also capture some of $B$ as is illustrated in the following figure.

How do I actually prove that there are recursively enumerable sets $A \subseteq \mathbb{N}$ and $B \subseteq \mathbb{N}$ which are recursively inseparable? I am currently working on a paper on non-standard models of Peano arithmetic and I am finding myself having to prove this as a lemma. In the proof, I want to avoid partial functions and Turing machines if possible, because I don't use Turing machines anywhere else and don't want to add an additional 3 pages to my paper discussing Turing machines.

-
I assume you want $A$ and $B$ to be disjoint and $C$ to be recursive. –  Robert Israel Apr 6 '12 at 2:50
In the first paragraph I assume you mean "superset of $A$" –  Carl Mummert Apr 6 '12 at 10:17

I don't think you can avoid bringing up partial functions, as the sets $A$ and $B$ cannot be recursive, and so they cannot be the domain of total functions.

Let $A$ be the set of $x$ such that $\varphi_{x}(x) = 0$ (so that the relation holds and is defined) and let $B$ be the set of $x$ such that $\varphi_{x}(x) = 1$. These sets are semirecursive, so recursively enumerable, and disjoint by construction. Suppose a recursive set $C$ existed satsifying the above-mentioned qualities. Then we can let $\chi$ be its characteristic function, and let $e$ code for $\chi$. We now ask: is $e$ in $C$? If $e$ is in $C$, then

$$\varphi_{e}(e) = 1$$

So that $e \in B$, which is impossible. Conversely, if $e$ is not in $C$, then

$$\varphi_{e}(e) = 0$$

But then $e \in A$, and hence in $C$, which gives a contradiction.

-

A standard example of recursively inseparable sets is $A=\{ \phi : P A\vdash \phi\}$ and $B=\{ \phi : P A\vdash \lnot\phi\}$. However it is not easy for me to prove those sets are inseparable without mentioning Turing machines or another model of computability.

-