Concept in computability theory
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 formula_1 classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.
Definition.
The natural numbers are the set formula_2. Given disjoint subsets formula_3 and formula_4 of formula_5, a separating set formula_6 is a subset of formula_5 such that formula_8 and formula_9 (or equivalently, formula_8 and formula_11, where formula_12 denotes the complement of formula_13). For example, formula_14 itself is a separating set for the pair, as is formula_15.
If a pair of disjoint sets formula_14 and formula_17 has no computable separating set, then the two sets are computably inseparable.
Examples.
If formula_14 is a non-computable set, then formula_14 and its complement are computably inseparable. However, there are many examples of sets formula_14 and formula_21 that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for formula_14 and formula_17 to be computably inseparable, disjoint, and computably enumerable. 
References.
 ;templatestyles src="Reflist/styles.css" / ;