GENERALIZED NUMBERING FOR LINEAR ORDERS

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 П₃-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 S₀ of c.e. linear preorders such that any c.e. linear preorder lies in lower cone for some c.e. linear order from S₀. 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.

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.