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

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.mendeley.com/catalogue/6d2942aa-65e6-3cfc-9628-949a1bff37a4/

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

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 -