КЕЙБІР СТАНДАРТ РЕТТЕРГЕ ИЗОМОРФТЫ ӨЗІ ТОЛЫҚ СЫЗЫҚТЫ РЕТТЕРДІҢ ИНДЕКСТІ ЖИЫНДАРЫ

Баженов Н.А., Калмурзаев Б.С., Зубков М.В. жұмыстарында позитивті сызықтық реттердің бинарлы қатынастардың есептелімді көшірілуіне қатысты супремумы мен инфимумының бар болуы туралы сұрақтарын зерттеу басталған болатын. Жұмыстың соңғы тарауында бұл сұрақтар натурал сандардың стандартты ретіне изоморфты болатын есептелімді сызықты реттердің құрылымында қарастырылды. Одан кейін, Асқарбекқызы А., Баженов Н.А., Калмурзаев Б.С. жұмыстарында осы құрылымды зерттеу жалғасын тапты. Соңғы жұмыста өзітолық сызықты реттер ұғымы үлкен рөл ойнады. Егер R жарты ретін R-ге көшіретін кез келген есептелімді g(x) функциясының мәндер жиыны барлық supp(R)-класстарымен қиылысса, R жарты реті өзі толық рет деп аталады. Бұл мақалада натурал сандардың стандарт ретіне және бүтін сандардың стандарт ретіне изоморфты барлық сызықтық реттердің индексті жиындарының алгоритмдік күрделілігі нақты бағаланады. Индексті жиындарды зерттеу қарастырылып отырған конструктивті құрылымдардағы түрлі ұғымдардың нақты күрделілігін бағалауға мүмкіндік береді. Натурал сандардың стандартты ретіне изоморфты болатын өзітолық есептелімді сызықты 

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