ОБ УНИВЕРСАЛЬНЫХ НУМЕРАЦИЯХ ДЛЯ ДВУХЭЛЕМЕНТНЫХ СЕМЕЙСТВ В ИЕРАРХИИ ЕРШОВА

Изучение локальных и глобальных инвариантов полурешетки Роджерса является важной и фундаментальной задачей в теории нумерации и теории вычислимости. Глобальные инварианты включают такие свойства, как существование универсальной нумерации, число минимальных нумераций, мощность всей полурешетки и критерий определения того, является ли полурешетка решеткой. Локальные инварианты, в свою очередь, описывают структуры, такие как начальные сегменты или интервалы внутри полурешетки. Мы говорим, что нумерация является универсальной, если любая другая нумерация сводится к . Изучение универсальных нумераций важно для понимания структуры полурешеток и их классификации. В данной работе рассматривается существование универсальных нумераций для конечных семейств вычислимо перечислимых множеств, расположенных на конечных уровнях иерархии Ершова. Основной результат заключается в том, что для любого семейства вычислимо перечислимых множеств , состоящего из двух элементов, его полурешетка Роджерса, рассматриваемая на третьем уровне иерархии Ершова, имеет универсальную нумерацию.

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