TY - JOUR

T1 - On cardinalities of Rogers semilattices for families in the Ershov hierarchy

AU - Ng, Keng Meng

AU - Bazhenov, Nikolay

AU - Kalmurzayev, Birzhan

AU - Nurlanbek, Dias

N1 - Ng is supported by The Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (MOE-T2EP20222-0018) and Academic Research Fund Tier 1 (RG104/24). The work of Bazhenov was supported by the Russian Science Foundation (project no. 24-11-00227). This research is funded by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No. AP19576325).

PY - 2025/11

Y1 - 2025/11

N2 - 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.

AB - 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.

KW - Computable numbering

KW - Reducibility of numberings

KW - Rogers semilattice

KW - The Ershov hierarchy

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=105015299663&origin=inward

UR - https://www.mendeley.com/catalogue/6d2942aa-65e6-3cfc-9628-949a1bff37a4/

U2 - 10.1016/j.ic.2025.105354

DO - 10.1016/j.ic.2025.105354

M3 - Article

VL - 307

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 105354

ER -