ON UNIVERSAL NUMBERINGS OF TWO-ELEMENT FAMILIES IN THE ERSHOV HIERARCHY

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

1. Ershov, Y.L. Teoriya numeratsii [The Theory of Numberings] (Moscow: Nauka, 1977). (In Russian).

2. Ash, C.J., and Knight, J.F. Computable Structures and the Hyperarithmetical Hierarchy (Elsevier Science, 2000).

3. Badaev, S.A., and Talasbaeva, Zh.T. Computable numberings in the hierarchy of Ershov. In: Mathematical Logic in Asia, edited by S.S. Goncharov et al. (Singapore: World Scientific, 2006), pp. 17–30.

4. Abeshev, K.Sh. On the existence of universal numberings for finite families of d.c.e. sets. Mathematical Logic Quarterly, 60 (3), 161–167 (2014).

5. Soare, R.I. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets (Berlin: Springer Science & Business Media, 1999).