×

Arithmetical m-degrees. (Russian, English) Zbl 1224.03021

Sib. Mat. Zh. 49, No. 6, 1391-1410 (2008); translation in Sib. Math. J. 49, No. 6, 1109-1123 (2008).
Summary: We describe the isomorphism types of the principal ideals of the join semilattice of m-degrees which are generated by arithmetical sets. A result by A. H. Lachlan [Algebra Logic 11, 127–132 (1972; Zbl 0309.02046)] on computably enumerable m-degrees is extended to the arbitrary levels of the arithmetical hierarchy. As a corollary, a characterization is given of the local isomorphism types of the Rogers semilattices of numberings of finite families, and the nontrivial Rogers semilattices of numberings which can be computed at the different levels of the arithmetical hierarchy are proved to be nonisomorphic provided the difference between the levels is greater than 1.

MSC:

03D45 Theory of numerations, effectively presented structures
03D25 Recursively (computably) enumerable sets and degrees

Citations:

Zbl 0309.02046
PDFBibTeX XMLCite
Full Text: EuDML EMIS