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
# N"S" is infinite and contains no infinite recursively enumerable set
# "S" is recursively enumerable.

An equivalent condition to 1 above is that "S" ∩ "X" ≠ ø for any infinite recursively enumerable set "X". The complement of a simple set is known as an immune set. There are immune sets whose complements are also immune; these sets are called bi-immune.

[There is a problem somewhere: if "A" is immune then its complement is recursively enumerable, by the definition given above. So if "A" is bi-immune, then it is recursive, so it cannot be simple.]

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