# zbMATH — the first resource for mathematics

On the structure of families of immune, hyperimmune and hyperhyperimmune sets. (English. Russian original) Zbl 0586.03035
Math. USSR, Sb. 52, 301-313 (1985); translation from Mat. Sb., Nov. Ser. 124(166), No. 3, 307-319 (1984).
The author investigates the algebraic structures of the families of all immune, hyperimmune and hyperhyperimmune, respectively, sets with respect to $$m$$-reducibility. The main results are: Theorem 1. The family of all immune sets forms with respect to $$m$$-reducibility a $$c$$-universal upper semilattice with the continuum cardinality. Theorem 3. Let $${\mathcal L}$$ be a distributive, at most countable upper semilattice with 0 and 1. Then there exists a hyperhyperimmune set $${\mathcal U}$$ such that the initial segment of $$m$$-degrees, less or equal to the $$m$$-degree of $${\mathcal U}$$, is isomorphic to $${\mathcal L}$$. Some open problems are also given.
##### MSC:
 03D25 Recursively (computably) enumerable sets and degrees 03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: