Encyclopedia

Computably inseparable

Concept in computability theory

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated July 3, 2025

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.

01Definition

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=\emptyset$ (or equivalently, $A\subseteq C$ and $B\subseteq C'$ , where $C'=\mathbb {N} \setminus C$ denotes the complement of $C$ ). For example, $A$ itself is a separating set for the pair, as is $B'$ .

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

02Examples

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

Watch videos about Computably inseparableExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Computably inseparable”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.