INDEX SETS OF SELF-FULL LINEAR ORDERS ISOMORPHIC TO SOME STANDARD ORDERS

The work of Bazhenov N.A., Zubkov M.V., Kalmurzayev B.S. started investigation of questions of the existence of joins and meets of positive linear preorders with respect to computable reducibility of binary relations. In the last section of this work, these questions were considered in the structure of computable linear orders isomorphic to the standard order of natural numbers. Then, the work of Askarbekkyzy A., Bazhenov N.A., Kalmurzayev B.S. continued investigation of this structure. In the last article, the notion of a self-full linear order played important role. A preorder R is called self-full, if for every computable function g(x), which reduces R to R, the image of this function intersects all supp(R)-classes. In this article, we measure exact algorithmic complexities of index sets of all self-full recursive linear orders isomorphic to the standard order of natural numbers and to the standard order of integers. Researching the index sets allows us to measure exact algorithmic complexities of different notions in constructive structures, that we are investigating. We prove that the index set of all self-full computable linear orders isomorphic to the standard order of that we are investigating. We prove that the index set of all self-full computable linear orders isomorphic to the standard order of integers is П3 0-complete.

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