View source for Immune set

An infinite set of natural numbers not containing an infinite recursively-enumerable subset (cf. [[Enumerable set]]). In particular, an immune set is not itself recursively enumerable. From the point of view of saturation by recursively-enumerable subsets, immune sets are in a certain sense opposite to [[productive set]]s. Recursively-enumerable sets with immune complements are called simple and form one of the important classes of non-recursive recursively-enumerable sets. Recursive equivalence types of immune and finite sets, called ''isols'', are of interest from the point of the view of the recursive analogue of the theory of [[cardinal number]]s. 

In [[recursive set theory]] and its applications one also uses certain special subclasses of the class of immune sets, in particular the hyperimmune sets.  A ''hyperimmune'' set is a set of natural numbers such that when its elements are arranged in increasing order as a sequence, it is not majorized by any general recursive function; a recursively-enumerable set with a hyperimmune complement is called ''hypersimple''.

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)</TD></TR>
</table>

[[Category:Computability and recursion theory]]

{{TEX|done}}