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.
[1] These sets arise in the study of computability theory itself, particularly in relation to
Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.
The natural numbers are the set
, a separating set
itself is a separating set for the pair, as is
If a pair of disjoint sets
has no computable separating set, then the two sets are computably inseparable.
is a non-computable set, then
and its complement are computably inseparable.
However, there are many examples of sets
that are disjoint, non-complementary, and computably inseparable.
to be computably inseparable, disjoint, and computably enumerable.