ЕҢ КІШІ ШЕКТІК ОРДИНАЛҒА ИЗОМОРФТЫ ПУНКТУАЛДЫ СЫЗЫҚТЫ РЕТТЕРДІҢ ҚҰРЫЛЫМЫ

Заманауи әдебиеттерде түрлі құрылымдардың кескіндерінің алгоритмдік күрделілігіне көп көңіл бөлінуде. Аталған күрделіліктерді анықтаудың басты құралы көшірулер. Бұл сигнатура қатынастарын (мысалы, эквиваленттік қатынастар, реттер, т.с.с.) сақтайтын бейнелеу. Мақала ең кіші шектік ординалдың примитивті рекурсивті көшіруге қатысты пунктуалды кескіндерін зерттеуге бағытталған. Бұл құрылымды PR(ω) деп белгілейміз. Атап айтқанда, мақалада ω ординалының есептелімді көшіруге қатысты есептелімді көшірмесі Ω құрылымының және примитивті рекурсивті көшіруге қатысты пунктуалды эквивалент қатынастардан тұратын Peq құрылымының қасиеттерінің орындалуы зерттеледі. Егер(χ, γ) Є L ↔ (ρ(χ), ρ(γ)) Є R шарты орындалатындай P функциясы табылса, L сызықты реті R сызықты ретіне көшіріледі деп атаймыз. Егер көшіруді орындайтын функция есептелімді (примитив рекурсив) болса, бұл көшіру есептелімді (примитив рекурсив) деп аталады. ω ретінің стандартты көшірмесінің деңгейі Ω құрылымында ең кіші болғанымен, PR(ω) құрылымында ең кіші емес екендігі дәлелденді. PR(ω) құрылымында максимал және бас деңгейлер жоқ, сонымен қатар бұл құрылым тығыз емес. Ең кіші жоғарғы шегі бар салыстырылмайтын жұптың мысалы келтірілді.

1. Kalimullin I., Melnikov, A. and Ng K.M. Algebraic structures computable without delay. Theoretical Computer Science, no. 674, 2017, pp. 73–98.

2. Bazhenov N., Ng K.M., San Mauro L. and Sorbi A. Primitive recursive equivalence relations and their primitive recursive complexity. Computability, no.11(3–4), 2022, pp. 187–221.

3. Ershov Y. L. Positive equivalences. Algebra i Logika, 10(6), 1971, 620–650.

4. Bernardi C. and Sorbi A. Classifying positive equivalence relations. J. Symb. Logic, no. 48(3), 1983, pp. 529–538.

5. Gao S. and Gerdes P. Computably enumerable equivalence relations. Studia Logica, no. 67(1), 2011, pp. 27–59.

6. Andrews U. and Sorbi A. Joins and meets in the structure of ceers. Computability, no. 8(3–4), 2019, pp. 193–241.

7. Askarbekkyzy A., Bazhenov N.A. and Kalmurzayev B.S. Computable Reducibility for Computable Linear Orders of Type ω. Journal of Mathematical Sciences, no. 267(4), 2022, pp. 429–443.

8. Bazhenov N.A., Kalmurzayev B.S. and Zubkov M.V. A note on joins and meets for positive linear preorders, Siberian Electronic Mathematical Reports, vol. 20, no. 1, 2023, pp. 1–16.

9. Askarbekkyzy A. and Bazhenov N.A. Index sets of self-full linear orders isomorphic to some standard orders. Herald of the Kazakh-British technical university. 2023;20(2):36–42. https://doi.org/10.55452/19986688-2023-20-2-36-42.

10. Bazhenov N., Downey R., Kalimullin I. and Melnikov A. Foundations of online structure theory. Bulletin of Symbolic Logic, no. 25(2), 2019, pp. 141–181.

11. Kabylzhanova D.K. On positive preorders. Algebra i Logica, no. 57(3), 2018, pp. 279–284 [in Russian].

12. Kuznecov A.V. On primitive recursive functions of large oscillation. Doklady Akademii Nauk SSSR, 71, 1950, pp. 233–236 [in Russian].

13. Paolini L., Piccolo M. and Roversi L. A class of reversible primitive recursive functions. Electronic Notes in Theoretical Computer Science, no. 322, 2016, pp. 227–242.