Preview

Вестник Казахстанско-Британского технического университета

Расширенный поиск

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

https://doi.org/10.55452/1998-6688-2025-22-2-200-206

Аннотация

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

Об авторах

А. А. Исахов
Казахстанско-Британский технический университет; Международный университет информационных технологий
Казахстан

 Ph.D., профессор 

 г. Алматы



Б. С. Калмурзаев
Казахстанско-Британский технический университет
Казахстан

Ph.D., ассоц. профессор 

г. Алматы 



Ф. Ракымжанкызы
Казахский национальный университет им. аль-Фараби
Казахстан

 докторант 

 г. Алматы 



Список литературы

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.


Рецензия

Для цитирования:


Исахов А.А., Калмурзаев Б.С., Ракымжанкызы Ф. ОБОБЩЕННАЯ НУМЕРАЦИЯ ДЛЯ ЛИНЕЙНЫХ ПОРЯДКОВ. Вестник Казахстанско-Британского технического университета. 2025;22(2):200-206. https://doi.org/10.55452/1998-6688-2025-22-2-200-206

For citation:


Issakhov A.A., Kalmurzayev B.S., Rakymzhankyzy F. GENERALIZED NUMBERING FOR LINEAR ORDERS. Herald of the Kazakh-British Technical University. 2025;22(2):200-206. https://doi.org/10.55452/1998-6688-2025-22-2-200-206

Просмотров: 19


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1998-6688 (Print)
ISSN 2959-8109 (Online)