Simple set

In recursion theory a simple set is an example of a set which is recursively enumerable but not recursive.

Definition

A subset S of the natural numbers N is called simple if it satisfies the following properties

1. N\S is infinite and contains no infinite recursively enumerable set
2. S is recursively enumerable.

An equivalent condition to 1 above is that S ∩ X ≠ ø for any infinite recursively enumerable set X. A set whose complement satisfies condition 1 is known as an immune set; thus the complement of a simple set is immune. There are immune sets whose complements are also immune; these sets are called bi-immune, and are necessarily not simple (because they are not recursively enumerable).

Properties

• The set of simple sets and the set of creative sets are disjoint. A simple set is never creative and a creative set is never simple.
• The collection of sets that are simple or cofinite forms a filter in the lattice of recursively enumerable sets.

References

• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987. ISBN 0-387-15299-7