Abstract: The study of local and global invariants of the Rogers semilattice is an important and fundamental problem in numbering theory and computability theory. Global invariants include properties such as an existence of a universal numbering, the number of minimal numberings, the cardinality of the entire semilattice, and a criterion for determining whether a semilattice is a lattice. Local invariants, in turn, describe structures, such as initial segments or intervals within the semilattice. We say that a numbering is universal if any other numbering reduces to . The study of universal numberings is important for understanding the structure of semilattices and their classification. In this paper, an existence of universal numberings is considered for finite families of computably enumerable sets located at finite levels of the Ershov hierarchy. The main result is that for any two-element family of computably enumerable sets , its Rogers semilattice, considered at the third level of the Ershov hierarchy, has universal numberings.

Cite: Kalmurzayev B.S. , Nurlanbek D.D. , Bazhenov N.A.
On universal numberings of two-element families in the Ershov hierarchy
Вестник Казахстанско-Британского технического университета. 2026. Т.23. №2. С.46-52. DOI: 10.55452/1998-6688-2026-23-2-46-52 Scopus OpenAlex

Dates:

Submitted:	Mar 17, 2026
Accepted:	Apr 30, 2026
Published print:	Jul 23, 2026
Published online:	Jul 23, 2026

Identifiers:

≡ Scopus:	2-s2.0-105043728468
≡ OpenAlex:	W7166311876

Altmetrics: