Difference between revisions of "Immune set"
m (typo) |
m (→References: + ZBL link) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | 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 '' | + | 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 ''[[isol]]s'', 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''. | 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''. | ||
| Line 5: | Line 5: | ||
====References==== | ====References==== | ||
<table> | <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> | + | <TR><TD valign="top">[1]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) {{ZBL|0183.01401}}</TD></TR> |
</table> | </table> | ||
Latest revision as of 11:08, 17 March 2023
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 sets. 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 numbers.
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
| [1] | H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) Zbl 0183.01401 |
Immune set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Immune_set&oldid=37583