The natural numbers are the set N = { 0 , 1 , 2 , … } {\displaystyle \mathbb {N} =\{0,1,2,\dots \}} . Given disjoint subsets A {\displaystyle A} and B {\displaystyle B} of N {\displaystyle \mathbb {N} } , a separating set C {\displaystyle C} is a subset of N {\displaystyle \mathbb {N} } such that A ⊆ C {\displaystyle A\subseteq C} and B ∩ C = ∅ {\displaystyle B\cap C=\emptyset } (or equivalently, A ⊆ C {\displaystyle A\subseteq C} and B ⊆ C ′ {\displaystyle B\subseteq C'} , where C ′ = N ∖ C {\displaystyle C'=\mathbb {N} \setminus C} denotes the complement of C {\displaystyle C} ). For example, A {\displaystyle A} itself is a separating set for the pair, as is B ′ {\displaystyle B'} .
If a pair of disjoint sets A {\displaystyle A} and B {\displaystyle B} has no computable separating set, then the two sets are computably inseparable.
If A {\displaystyle A} is a non-computable set, then A {\displaystyle A} and its complement are computably inseparable. However, there are many examples of sets A {\displaystyle A} and B {\displaystyle B} that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for A {\displaystyle A} and B {\displaystyle B} to be computably inseparable, disjoint, and computably enumerable.
Monk 1976, p. 100 ↩