МИНИМАЛ ҚАРАҢҒЫ ЕСЕПТЕЛІМДІ САНАЛЫМДЫ ЭКВИВАЛЕНТ ҚАТЫНАСТАРДЫҢ ҚҰРЫЛЫМЫ ЖАЙЫНДА

Есептелімді көшіруге қатысты есептелімді саналымды эквиваленттік қатынастардың (қысқаша ceers) құрылымы соңғы 25 жылда белсенді түрде зерттелуде. Эндрюс пен Сорбидің шолу еңбектері ceers құрылымына тән көптеген құрылымдық қасиеттерді ашып көрсетті. Олар супремум мен инфимумның бар-жоғын зерттей отырып, құрылымды анықталымды екі бөлікке бөлді: қараңғы (яғни, тиімді трансверсалі жоқ) және жарық (тиімді трансверсалі бар) эквиваленттіліктер. Сонымен қатар, Эндрюс пен Сорби минималды қараңғы есептелімді саналымды эквиваленттік қатынастардың (бұдан әрі – минималды қараңғы ceers) шексіз саны бар екенін дәлелдеді. Мұндағы минималдылық – бұл қатынастардың төменгі конусында тек кластар саны шектеулі болатын эквиваленттіктер ғана жатуы мүмкін деген мағынада. Мұндай минималды қараңғы эквиваленттіктердің маңызды қасиеті – кластардың кез келген жұбы есептелімді түрде ажыратылмайды. Сондай-ақ, ceers теориясында әлсіз жартылай толық эквиваленттік қатынастар да зерттелуде. Бұл есептелімді диагонал функциясы жоқ эквиваленттіктер. Аталған қатынастарда да кластардың кез келген жұбы есептелімді түрде ажыратылмайды. Осыған байланысты әлсіз жартылай толық, минималды қараңғы эквиваленттік қатынастардың бар-жоғы туралы сұрақ туындайды. Бұл мақалада аталған сұраққа оң жауап беріліп отыр. FC арқылы барлық класы ақырлы болатын есептелімді саналымды эквиваленттік қатынас белгіленсін. Эндрюс, Швебер және Сорби қараңғы FC эквиваленттіктерінің бар екенін көрсеткен болатын. Ал бұл зерттеуде біз кез келген қараңғы FC эквиваленттік қатынасының үстінде қараңғы FC эквиваленттік қатынастардан тұратын шексіз антитізбек (антишынжыр) бар екенін дәлелдейміз.

1. Ershov, Y. L. Positive equivalences. Algebra and Logic, 10(6), 378–394 (1971).

2. Bernardi, C. On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica, 40, 29–37 (1981).

3. Bernardi, C., Sorbi, A. Classifying positive equivalence relations. The Journal of Symbolic Logic, 48(3), 529–538 (1983).

4. Andrews, U., Lempp, S., Miller, J. S., Ng, K. M., San Mauro, L., Sorbi, A. Universal computably enumerable equivalence relations. The Journal of Symbolic Logic, 79(1), 60–88 (2014).

5. Andrews, U., Badaev, S., Sorbi, A. A survey on universal computably enumerable equivalence relations. In Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 418–451). Cham: Springer International Publishing (2016).

6. Andrews, U., Sorbi, A. The complexity of index sets of classes of computably enumerable equivalence relations. The Journal of Symbolic Logic, 81(4), 1375–1395 (2016).

7. Bazhenov, N. A., Kalmurzaev, B. S. On dark computably enumerable equivalence relations. Siberian Mathematical Journal, 59, 22–30 (2018).

8. Ng, K. M., Yu, H. On the degree structure of equivalence relations under computable reducibility. Notre Dame J. Formal Logic, 60(4), 733–761 (2019).

9. Andrews, U., Badaev, S. A. On isomorphism classes of computably enumerable equivalence relations. The Journal of Symbolic Logic, 85(1), 61–86 (2020).

10. Andrews, U., Schweber, N., Sorbi, A. Self-full ceers and the uniform join operator. Journal of Logic and Computation, 30(3), 765–783 (2020).

11. Andrews, U., Sorbi, A. Effective inseparability, lattices, and preordering relations. The Review of Symbolic Logic, 14(4), 838–865 (2021).

12. Delle Rose, V., San Mauro, L., Sorbi, A. A note on the category of equivalence relations. Algebra and Logic, 60(5), 295–307 (2021).

13. Andrews, U., Belin, D. F., San Mauro, L. On the structure of computable reducibility on equivalence relations of natural numbers. The Journal of Symbolic Logic, 88(3), 1038–1063 (2023).

14. Ershov Yu. L. The Theory of Enumerations, Nauka, Moscow (1977). [Russian].

15. Badaev S. A. On weakly pre-complete positive equivalences, Sib. Math. J., 32 (2), 321–323 (1991).

16. Badaev, S.A., Sorbi, A. Weakly precomplete computably enumerable equivalence relations. Math. Log. Quart. 62, No. 1–2, 111–127 (2016).

17. Badaev, S.A., Bazhenov, N.A., Kalmurzayev, B.S., Mustafa, M. On diagonal functions for equivalence relations. Archive for Mathematical Logic. 63, 259–278 (2023).

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

19. Gao, S., Gerdes, P. Computably enumerable equivalence relations. Studia Logica, 27–59 (2001).

20. Badaev, S. A., Kalmurzaev, B. S., Mukash, N. K., Khamitova, A. A. Special classes of positive preorders. Sib. Elektron. Mat. Izv., 18:2, 1657–1666 (2021).

21. Andrews, U., Schweber, N., Sorbi, A. The theory of ceers computes true arithmetic. Ann. Pure Appl. Logic. (171:8), 102811 (2020).

22. Soare R. Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, SpringerVerlag, Berlin (1987).