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.
03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI EuDML