A NOTE ON THE STRUCTURE OF MINIMAL DARK CEERS

The structure of computably enumerable equivalence relations under computable reducibility (commonly referred to as ceers) has been actively developed over the past 25 years. A comprehensive survey by Andrews and Sorbi presented numerous structural properties of ceers, most notably investigating the existence of joins and meets in the degree structure of ceers. They divided the structure into two definable parts: dark ceers (ceers without an effective transversal) and light ceers (ceers with an effective transversal). They also showed the existence of an infinite number of minimal dark ceers (modulo equivalence relations with finitely many classes). Minimal dark ceers exhibit the distinctive property that every pair of classes is computably inseparable. Furthermore, the classes of weakly precomplete equivalence relations (i.e. those that lack a computable diagonal functions) are also computably inseparable. In this context, a natural question arises: do minimal dark equivalence relations exist that are not weakly precomplete? This paper provides an affirmative answer to this question. Moreover, we establish the existence of an infinite family of non-weakly precomplete minimal dark ceers that avoids lower cone of a given non-universal ceer. We denote by FC the set of ceers consisting of only finite classes. Andrews, Schweber, Sorbi showed the existence of dark FC equivalences. In this paper, we prove that over any dark FC ceer, there exists an infinite antichain of dark FC ceers.

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