О СТРУКТУРЕ МИНИМАЛЬНЫХ ТЕМНЫХ ВЫЧИСЛИМО ПЕРЕЧИСЛИМЫХ ОТНОШЕНИЙ ЭКВИВАЛЕНТНОСТИ

Структура вычислимо перечислимых отношений эквивалентности относительно вычислимой сводимости (коротко – ceers) активно развивается на протяжении последних 25 лет. В обзоре Эндрюса и Сорби было показано множество структурных свойств структуры ceers. Эндрюс и Сорби исследовали существование супремумов и инфимумов. Они разделили структуру на две определимые части: темные (эквивалентности без эффективного трасверсаля) и светлые (с эффективным трансверсалем) эквивалентности и показали существование бесконечного числа минимальных (в том смысле, что строго под ними могут быть только конечные эквивалентности) темных ceers. Минимальные темные эквивалентности имеют следующее свойство: каждая пара классов вычислимо неотделима. Также в теории ceers изучаются слабо предполные эквивалентности (то есть те эквивалентности, для которых не существует вычислимых диагональных функций). Также у данных эквивалентностей каждая пара классов вычислимо неотделима. В связи с этим возникает вопрос о существовании минимальных темных эквивалентностей, не являющихся слабо предполными. В данной статье дается положительный ответ на этот вопрос. Через FS обозначим в.п. отношение эквивалентности все классы которого конечны. Эндрюс, Швебер, Сорби показали существование темных FS экивалентностей. В этой статье доказывается, что над любой темной FS эквивалентностью существует бесконечная антицепь темных FS эквивалентностей.

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).