ЕРШОВ ИЕРАРХИЯСЫНДАҒЫ ЕКІ ЭЛЕМЕНТТІ ЖИЫНДАР ҮЙІРЛЕРІ ҮШІН УНИВЕРСАЛ НӨМІРЛЕУЛЕР ТУРАЛЫ

Роджерс жарты торының локалды және глобалды инварианттарын зерттеу – нөмірлеу теориясындағы маңызды әрі іргелі мәселелердің бірі. Глобалды инварианттарға универсал нөмірлеудің болуы, минималды нөмірлеулер саны, бүкіл жарты тордың қуаттылығы және жарты тордың тор болу критерийі сияқты қасиеттер жатады. Ал локалды инварианттар жарты тор ішіндегі бастапқы сегменттер мен аралықтар тәрізді құрылымдарды сипаттайды. Егер кез келген нөмірлеуі нөмірлеуіне көшірілсе, онда нөмірлеуі универсал балады. Универсал нөмірлеуді зерттеу жарты торлардың құрылымын және олардың жіктелуін түсіну үшін маңызды. Мақалада Ершов иерархиясының шекті деңгейлерінде орналасқан есептелімді жиындардың шекті үйірлері үшін универсал нөмірлеулердің болуы қарастырылады. Негізгі нәтиже – есептелімді жиындардың кез келген екі элементті S үйірі үшін Ершов иерархиясының үшінші деңгейінде қарастырылатын Роджерс жарты торында универсал нөмірлеудің бар екендігі дәлелденеді.

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