A simple set is a recursively enumerable set 
of natural numbers whose complement
is an immune set. Equivalently, 
is a recursively
enumerable set, its complement is an infinite
set, and the complement contains no infinite recursively enumerable set.
No simple set is a recursive set. Otherwise its infinite complement would also be a recursively
enumerable set, contradicting the defining property of an immune
set. The existence of simple sets was proved by Post (1944).
See also
Immune Set,
Recursive
Set,
Recursively Enumerable Set
Explore with Wolfram|Alpha
References
Post, E. L. "Recursively Enumerable Sets of Positive Integers and Their Decision Problems." Bull. Amer. Math. Soc. 50,
284-316, 1944. https://doi.org/10.1090/S0002-9904-1944-08111-1.Rogers,
H. Theory
of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press,
1987.
Cite this as:
Weisstein, Eric W. "Simple Set." From
MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SimpleSet.html
Subject classifications
