zbMATH — the first resource for mathematics

Rogers semilattices of families of arithmetic sets. (Russian, English) Zbl 0989.03040
Algebra Logika 40, No. 5, 507-522 (2001); translation in Algebra Logic 40, No. 5, 283-291 (2001).
The authors study the algebraic properties of Rogers semilattices. They consider problems of existence of minimal elements, minimal coverings, and ideals without minimal elements.
In particular, they prove that the Rogers semilattice of any infinite \(\Sigma_{n+2}^0\)-computable family of sets contains infinitely many minimal elements (Theorem 1); and that if a family \({\mathcal A}\subseteq\Sigma^0_{n+2}\) possesses a \(\Sigma^0_{n+2}\)-computable Friedberg numbering then the Rogers semilattice \({\mathcal R}_{n+2}({\mathcal A})\) contains an ideal without minimal elements.

03D45 Theory of numerations, effectively presented structures
Full Text: EuDML