If $A$ and $B$ are recursively enumerable sets that are said to be recursively inseparable if they are disjoint, but there is no recursive set that contains $A$ and is disjoint from $B$, show that a recursively inseparable pair of recursively enumerable set exists.

Are there any standard proofs that show this result? I've tried searching online but I haven't been able to find anything concerning the nature of recursively inseparable pairs.

  • $\begingroup$ Yes, there is a standard proof (for two sets whose definiton only involves Turing machines). One place where you can find this is in Theorem 3.3.5 of the wonderful notes "Syllabus Computability Theory" written by Sebastiaan A. Terwijn math.ru.nl/~terwijn/teaching.html After you know these two sets are inseparable you can easily prove the inseparability of sets with a "logic" flavour (like in Biderman answer) $\endgroup$ – boumol Mar 19 '14 at 10:55
  • 1
    $\begingroup$ The standard example is $\{ e: \phi_e(0) = 0\}$ and $\{e : \phi_e(0)= 1\}$. Get a copy of Soare's book, which is arguably the standard textbook at the moment; it will have this and many other things. $\endgroup$ – Carl Mummert Mar 19 '14 at 11:49
  • $\begingroup$ I removed the philosophy tag; that should be reserved for questions explicitly about philosophy of mathematics. $\endgroup$ – Carl Mummert Mar 19 '14 at 11:56

The wikipedia article lists two. The second one is related to Godel's second incompleteness theorem.

"Let # be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set A = { #(ψ) : PA ⊢ ψ} of provable formulas and the set B = { #(ψ) : PA ⊢ ¬ψ} of refutable formulas are recursively inseparable. The inseparability of the sets of provable and refutable formulas holds for many other formal theories of arithmetic (Smullyan 1958)."


Biderman gives the example of such sets. I will give a proof why such sets are recursively inseparable.

Let $A$ be a set of Gödel numbering of theorems of PA (that is, $A=\{\sharp\sigma : \mathsf{PA}\vdash \sigma\}$ and $B$ denotes a set of sentences that refutes from PA.

Assume that there is a recursive $R$ such that $A\subset R$ and $B\subset \Bbb{N}-R$. Then there is a formula $\varphi(x)$ with one free variable that defines $R$. By Gödel's fixed number theorem, there is a sentence $\tau$ such that \[ \mathsf{PA}\vdash \tau \leftrightarrow \lnot \varphi( S^{\sharp \tau}0). \] If $\sharp\tau\in R$, then $\varphi( S^{\sharp \tau}0)$ is a theorem of $\mathsf{PA}$ so $\lnot \tau$ is a theorem of $\mathsf{PA}$ so $\mathsf{PA}$ refutes $\tau$. Therefore $\sharp\tau\in B$, contradicting that $B$ is a subset of $\Bbb{N}-R$. Similar contradiction is appears when we assume that $\sharp \tau\notin R$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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