On cardinalities of Rogers semilattices for families in the Ershov hierarchy
Ng K.M. Bazhenov N. Kalmurzayev B. Nurlanbek D.
November 2025Elsevier Inc.
Information and Computation
2025#307
The theory of numberings provides classification results for families of sets in various computability-theoretic hierarchies. The algorithmic content of numberings is typically calibrated via the reducibility between numberings. For a given family of sets S, this reducibility gives rise to an upper semilattice of degrees that is often called the Rogers semilattice of S. This paper studies the cardinalities of Rogers semilattices for families of sets at finite levels of the Ershov hierarchy. The classical result of Khutoretskii (1971) shows that the Rogers semilattice of a family of c.e. sets is either one-element or countably infinite. Badaev and Lempp (2009) constructed a family of d.c.e. sets that demonstrates that the methods of Khutoretskii cannot be applied to obtain a similar result for Rogers semilattices already at the second level of the Ershov hierarchy. We prove that for any finite family of sets S at any finite level of the Ershov hierarchy, the corresponding Rogers semilattice is either one-element or countably infinite. We also obtain another sufficient condition for a Rogers semilattice to be infinite. This condition implies that the Rogers semilattice of Badaev and Lempp is also infinite.
Computable numbering , Reducibility of numberings , Rogers semilattice , The Ershov hierarchy
Text of the article Перейти на текст статьи
Nanyang Technological University, 50 Nanyang Avenue, 639798, Singapore
Novosibirsk State University, 2 Pirogova Street, Novosibirsk, 630090, Russian Federation
Kazan Federal University, 18 Kremlevskaya Street, Kazan, 420008, Russian Federation
Kazakh-British Technical University, 59 Tole Bi Street, Almaty, 050000, Kazakhstan
Nanyang Technological University
Novosibirsk State University
Kazan Federal University
Kazakh-British Technical University
10 лет помогаем публиковать статьи Международный издатель
Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026