Simple set
From Wikipedia, the free encyclopedia
In computability theory a simple set is an example of a set which is recursively enumerable but not recursive.
[edit] Definition
A subset S of the natural numbers N is called simple if it satisfies the following properties
- N\S is infinite
- S is recursively enumerable
- S ∩ X ≠ ø for any infinite recursively enumerable set X
[edit] 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 simple and cofinite sets form a filter in the lattice of recursively enumerable sets.
[edit] Reference
- Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987. ISBN 0-387-15299-7
