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 ${\Pi }_1^0$ classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

Definition

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

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

Examples

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

• Let $\phi$ be the standard indexing of the partial computable functions. Then the sets $A=\{e:{\phi }_e(0)=0\}$ and $B=\{e:{\phi }_e(0)=1\}$ are computably inseparable (William Gasarch1998, p. 1047).
• Let $\mathrm{\#}$ be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set $A=\{\mathrm{\#}(\psi ):PA⊢\psi \}$ of provable formulas and the set $B=\{\mathrm{\#}(\psi ):PA⊢\mathrm{\neg }\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).