Recursively inseparable sets

In computability theory, recursively inseparable sets are pairs of sets of natural numbers that cannot be "separated" with a recursive set (Monk 1976, p. 100). These sets arise in the study of computability theory itself, particularly in relation to Π0
1
classes
. Recursively inseparable sets also arise in the study of Gödel's incompleteness theorem.

Definition

The natural numbers are the set ω = {0, 1, 2, ...}. Given disjoint subsets A and B of ω, a separating set C is a subset of ω such that A C and B C = (or equivalently, A C and B 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 recursive separating set, then the two sets are recursively inseparable.

Examples

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

References

This article is issued from Wikipedia - version of the Friday, August 21, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.