An immune set is an infinite set of natural numbers that contains no infinite recursively enumerable set as a subset. An immune set cannot itself be a recursively enumerable set, since it would then itself be an infinite recursively enumerable set contained in the immune set. The complement of a simple set is immune.
Immune Set
See also
Recursively Enumerable Set, Simple Set, SubsetExplore 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. "Immune Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ImmuneSet.html