kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2025-22-2-200-206kaz29-2000Research ArticleМАТЕМАТИЧЕСКИЕ НАУКИMATHEMATICAL SCIENCESОБОБЩЕННАЯ НУМЕРАЦИЯ ДЛЯ ЛИНЕЙНЫХ ПОРЯДКОВGENERALIZED NUMBERING FOR LINEAR ORDERShttps://orcid.org/0000-0001-7020-7988ИсаховА. А.IssakhovA. A.

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

 г. Алматы

 PhD., Professor 

 Almaty 

asylissakhov@gmail.comhttps://orcid.org/0000-0002-4386-5915КалмурзаевБ. С.KalmurzayevB. S.

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

г. Алматы 

 PhD., Associate Professor 

 Almaty 

birzhan.kalmurzayev@gmail.comhttps://orcid.org/0000-0002-6517-5560РакымжанкызыФ.RakymzhankyzyF.

 докторант 

 г. Алматы 

 PhD doctoral candidate 

 Almaty 

fariza.rakymzhankyzy@gmail.comКазахстанско-Британский технический университет; Международный университет информационных технологийКазахстанKazakh-British Technical Universityж International Information Technology UniversityKazakhstanКазахстанско-Британский технический университетКазахстанKazakh-British Technical UniversityKazakhstanКазахский национальный университет им. аль-ФарабиКазахстанAl-Farabi Kazakh National UniversityKazakhstan202506072025222200206Copyright © Исахов А.А., Калмурзаев Б.С., Ракымжанкызы Ф., 20252025Исахов А.А., Калмурзаев Б.С., Ракымжанкызы Ф.Issakhov A.A., Kalmurzayev B.S., Rakymzhankyzy F.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/2000

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

We study spectre of Turing degrees permitting to construct numbeings for the set of all linear orders isomorphic to the standard order of natural numbers. It is known that the index set of all linear orders isomorphic to the standard order of natural numbers is П3-comlete. This mean that this set has no computable numberings. In this work we show that the set of all linear orders isomorphic to the standard order of naturals has O’’-computable numbering, and has no O’-computable numberings. In the Bazhenov, Kalmurzayev and Torebekova’s work they construct universal c.e. linear preorder in the structure under computably reducibility. They use the following fact: there is computable numbering for some subset S0 of c.e. linear preorders such that any c.e. linear preorder lies in lower cone for some c.e. linear order from S0. We show that the similar fact is not hold for the structure of all linear orders isomorphic to the standard order of naturals. Moreover, for this structure there is no O’-computable numbering with simiral fact.

позитивный предпорядокпозитивная эквивалентностьпозитивный линейный предпорядоквычислимая сводимостьpositive preorderpositive equivalencepositive linear preordercomputable reducibilityThe work was supported by the Ministry of Science and Higher Education of the Republic of Kazakhstan, grant AP19676989 “Logical and algorithmic foundations for online computations”.ReferencesErshov Yu. L. Positive equivalences // Algebra and Logic. – 1971. – Vol. 10. –No. 6. – P. 620–650.Ershov Yu. L. Positive equivalences // Algebra and Logic. – 1971. – Vol. 10. –No. 6. – P. 620–650.Ershov Yu. L. Numeration Theory (Moskow: Nauka, 1977).Ershov Yu. L. Numeration Theory (Moskow: Nauka, 1977).Andrews U., Sorbi A. Joins and meets in the structure of ceers // Computability. – 2019. – Vol. 8. – No. 3–4. – P. 193–241.Andrews U., Sorbi A. Joins and meets in the structure of ceers // Computability. – 2019. – Vol. 8. – No. 3–4. – P. 193–241.Andrews U., Sorbi A. Effective inseparability, lattices, and preordering relations // Rev. Symb. Log. – 2021. – Vol. 14. – No. 4. – P. 838–865.Andrews U., Sorbi A. Effective inseparability, lattices, and preordering relations // Rev. Symb. Log. – 2021. – Vol. 14. – No. 4. – P. 838–865.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.Jockusch C.G. Degrees in which the recursive sets are uniformly recursive // Can. J. Math. – 1972. – Vol. 24. – No. 6. – P. 1092–1099.Jockusch C.G. Degrees in which the recursive sets are uniformly recursive // Can. J. Math. – 1972. – Vol. 24. – No. 6. – P. 1092–1099.Bazhenov N.A. and Kalmurzaev B.S. On dark computably enumerable equivalence relations // Siberian Mathematical Journal. – 2018. – Vol. 59. – No. 1. – P. 22–30.Bazhenov N.A. and Kalmurzaev B.S. On dark computably enumerable equivalence relations // Siberian Mathematical Journal. – 2018. – Vol. 59. – No. 1. – P. 22–30.

The authors declare that there are no conflicts of interest present.