Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. recursiveinseparability

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.

share|cite|improve this question
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
up vote 7 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.