Computably inseparable

In computability theory, two disjoint sets of natural numbers are called computably inseparable or recursively inseparable if they cannot be "separated" with a computable set.¹ These sets arise in the study of computability theory itself, particularly in relation to ${\displaystyle \Pi _{1}^{0}}$ classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

The natural numbers are the set ${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$. Given disjoint subsets ${\displaystyle A}$ and ${\displaystyle B}$ of ${\displaystyle \mathbb {N} }$, a separating set ${\displaystyle C}$ is a subset of ${\displaystyle \mathbb {N} }$ such that ${\displaystyle A\subseteq C}$ and ${\displaystyle B\cap C=\emptyset }$ (or equivalently, ${\displaystyle A\subseteq C}$ and ${\displaystyle B\subseteq C'}$, where ${\displaystyle C'=\mathbb {N} \setminus C}$ denotes the complement of ${\displaystyle C}$). For example, ${\displaystyle A}$ itself is a separating set for the pair, as is ${\displaystyle B'}$.

If a pair of disjoint sets ${\displaystyle A}$ and ${\displaystyle B}$ has no computable separating set, then the two sets are computably inseparable.

If ${\displaystyle A}$ is a non-computable set, then ${\displaystyle A}$ and its complement are computably inseparable. However, there are many examples of sets ${\displaystyle A}$ and ${\displaystyle B}$ that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for ${\displaystyle A}$ and ${\displaystyle B}$ to be computably inseparable, disjoint, and computably enumerable.

• Let ${\displaystyle \varphi }$ be the standard indexing of the partial computable functions. Then the sets ${\displaystyle A=\{e:\varphi _{e}(0)=0\}}$ and ${\displaystyle B=\{e:\varphi _{e}(0)=1\}}$ are computably inseparable (William Gasarch1998, p. 1047).
• Let ${\displaystyle \#}$ be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set ${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$ of provable formulas and the set ${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$ of refutable formulas are computably inseparable. The inseparability of the sets of provable and refutable formulas holds for many other formal theories of arithmetic (Smullyan 1958).