ИНДЕКСНЫЕ МНОЖЕСТВА САМОПОЛНЫХ ЛИНЕЙНЫХ ПОРЯДКОВ, ИЗОМОРФНЫХ НЕКОТОРЫМ СТАНДАРТНЫМ ПОРЯДКАМ

В работе Баженова Н.А., Зубкова М.В., Калмурзаева Б.С. было начато исследование вопросов существования супремумов и инфимумов позитивных линейных предпорядков относительно вычислимых сводимостей бинарных отношений, в последней главе эти вопросы были рассмотрены в структуре вычислимых линейных порядков, изоморфных стандартному порядку натуральных чисел. Далее, в работе Аскарбеккызы А., Баженова Н.А., Калмурзаева Б.С. было продолжено исследование этой структуры. В последней работе немаловажную роль сыграло понятие самополных линейных порядков. Предпорядок R называется самополным, если для любой вычислимой функции g(x), осуществляющей сводимость R в R, ее область значений пересекает все supp(R)-классы. В данной статье оценивается точная алгоритмическая сложность индексных множеств всех самополных рекурсивных линейных порядков, изоморфных стандартному порядку натуральных чисел и целых чисел. Исследование индексных множеств позволяет оценить точную сложность различных понятий в исследуемых конструктивных структурах. Доказывается, что индексное множество самополных вычислимых линейных порядков, изоморфных стандартному порядку натуральных чисел, является П03-полным множеством. Доказывается, что индексное множество самополных вычислимых линейных порядков, изоиорфных стандартному порядку целых чисел, являетмя П03-полным множеством.

1. Ershov Yu.L. (1977) Theory of numberings. Moscow: Nauka. (In russian).

2. Bernardi C. and Sorbi A. (1983) Classifying positive equivalence relations, The Journal of Symbolic Logic, vol. 48, no. 3, pp. 529–538.

3. Kalmurzayev B.S., Bazhenov N.A. and Torebekova M.A. (2022) Ob indeksnyh mnozhestvah dlya klassov pozitivnyh predporyadkov, Algabra i logika, vol. 61, no.1, pp. 42–76.4 (In russian).

4. Gao S. and Gerdes P. (2001) Computably enumerable equivalence relations, Studia Logica: An International Journal for Symbolic Logic, vol. 67, no. 1, pp. 27–59.

5. Andrews U., Lempp S., Miller J.S., Ng K.M., San Mauro L. and Sorbi A. (2014) Universal computably enumerable equivalence relations, The Journal of Symbolic Logic, vol. 79, no. 1, pp. 60–88.

6. Andrews U. and Sorbi A. (2016) The complexity of index sets of classes of computably enumerable equivalence relations, The Journal of Symbolic Logic, vol. 81, no. 4, pp. 1375–1395.

7. Andrews U. and Sorbi A. (2019) Joins and meets in the structure of ceers, Computability, vol. 8, no. 3–4, pp. 193-241.

8. Andrews U. and Badaev S.A. (2020) On isomorphism classes of computably enumerable equivalence relations, The Journal of Symbolic Logic, vol. 85, no. 1, pp. 61–86.

9. Badaev S.A. and Sorbi A. (2016) Weakly precomplete computably enumerable equivalence relations, Mathematical Logic Quarterly, vol. 62, issue 1–2, pp. 111–127.

10. Soare R.I. (2016) Turing Computability, Theory and applications. Berlin: Springer.

11. Askarbekkyzy A., Bazhenov N.A. and Kalmurzayev B.S. (2022) Computable Reducibility for Computable Linear Orders of Type ω, Journal of Mathematical Sciences, vol. 267, pp. 429–443.

12. Bazhenov N.A., Kalmurzayev B.S. and Zubkov M.V. (2023) A note on joins and meets for positive linear preorders, Siberian Electronic Mathematical Reports, vol. 20, no. 1, pp. 1–16.

13. Kreisel, G., Shoenfield, J. and Wang, H. (1960) Number theoretic concepts and recursive well-orderings, Arch math Logik, vol. 5? 42-64.

14. Ash C.J. and Knight J.F. (1990) Pairs of recursive structures, Annals of Pure and Applied Logic, vol. 46, issue 3, pp.211-234