ОБОБЩЕННАЯ НУМЕРАЦИЯ ДЛЯ ЛИНЕЙНЫХ ПОРЯДКОВ

Мы изучаем спектр степеней Тьюринга, позволяющих построить нумерацию для множества всех линейных порядков, изоморфных стандартному порядку натуральных чисел. Известно, что индексное множество всех линейных порядков, изоморфных стандартному порядку натуральных чисел, является П₃-полным. Это означает, что данное множество не имеет вычислимых нумераций. В данной работе мы показываем, что множество всех линейных порядков, изоморфных стандартному порядку натуральных чисел, имеет О’’-вычислимую нумерацию и не имеет O’-вычислимых нумераций. В работах Баженова, Калмурзаева, Торебековой конструируются универсальные в.п. линейный предпорядок в структуре при вычислимой сводимости. Они используют следующий факт: существует вычислимая нумерация некоторого подмножества S₀ в.п. линейных предпорядков такая, что любой в.п. линейный предпорядок лежит в нижнем конусе для некоторого в.п. линейный порядок от S₀. Мы показываем, что аналогичный факт не имеет места для структуры всех линейных порядков, изоморфных стандартному порядку натуральных чисел. Более того, для этой структуры не существует O’-вычислимой нумерации с подобным фактом.

1. Ershov Yu. L. Positive equivalences // Algebra and Logic. – 1971. – Vol. 10. –No. 6. – P. 620–650.

2. Ershov Yu. L. Numeration Theory (Moskow: Nauka, 1977).

3. Andrews U., Sorbi A. Joins and meets in the structure of ceers // Computability. – 2019. – Vol. 8. – No. 3–4. – P. 193–241.

4. Andrews U., Sorbi A. Effective inseparability, lattices, and preordering relations // Rev. Symb. Log. – 2021. – Vol. 14. – No. 4. – P. 838–865.

5. Badaev S.A., Kalmurzayev B. S., Kabylzhanova D. K. and Abeshev K. Sh. Universal positive preorders // News of the National Academy of Sciences of the Republic of Kazakhstan. Physico-Mathematical Series. – 2018. – Vol. 6. – No. 322. – P. 49–53.

6. Badaev S.A., Bazhenov N.A. and Kalmurzaev B.S. On the structure of positive preorders // Algebra Logic. – 2020. – Vol. 59. – No. 3. – P. 201–215.

7. Badaev S.A., Kalmurzayev B.S., Mukash N.K. and Khamitova A.A. Special classes of positive preorders. – Sib. E`lektron. Mat. Izv. – 2021. – Vol. 18. – No. 2. – P. 1657–1666.

8. Askarbekkyzy A., Bazhenov N. A. and Kalmurzayev B.S. Computable reducibility for computable linear orders of type ω // J. Math. Sci. – 2022. – Vol. 267. – No. 4. – P. 429–443.

9. Bazhenov N. A., Kalmurzayev B. S. and Zubkov M.V. A note on joins and meets for positive linear preorders // Siberian Electronic Mathematical Reports. – 2023. – Vol. 20. – No. 1. – P. 1–16.

10. Askarbekkyzy A., Bazhenov N.A. Index sets of self-full linear orders isomorphic to some standard orders // Hearld of the Kazakh-British Technical University. – 2023. – Vol. 20. – No. 2. – P. 36–42.

11. Kalmurzayev B.S., Bazhenov N.A. and Torebekova M.A. Index sets for classes of positive preorders // Algebra and Logic. – 2022. – Vol. 61. – No. 1. – P. 30–53.

12. Rakymzhankyzy F., Bazhenov N.A., Issakhov A.A. and Kalmurzayev B.S. Minimal generalized computable numberings and families of positive preorders // Algebra and Logic. – 2022. – Vol. 61. – No. 3. – P. 280–307.

13. Jockusch C.G. Degrees in which the recursive sets are uniformly recursive // Can. J. Math. – 1972. – Vol. 24. – No. 6. – P. 1092–1099.

14. Bazhenov N.A. and Kalmurzaev B.S. On dark computably enumerable equivalence relations // Siberian Mathematical Journal. – 2018. – Vol. 59. – No. 1. – P. 22–30.