The category of equivalence relations

V. Delle Rose ; L. San Mauro ; A. Sorbi

Algebra i logika, Tome 60 (2021) no. 5, pp. 451-470.

Résumé

We make some beginning observations about the category $\mathbb{E}\mathrm{q}$ of equivalence relations on the set of natural numbers, where a morphism between two equivalence relations $R$ and $S$ is a mapping from the set of $R$-equivalence classes to that of $S$-equivalence classes, which is induced by a computable function. We also consider some full subcategories of $\mathbb{E}\mathrm{q}$, such as the category $\mathbb{E}\mathrm{q}(\Sigma^0_1)$ of computably enumerable equivalence relations (called ceers), the category $\mathbb{E}\mathrm{q}(\Pi^0_1)$ of co-computably enumerable equivalence relations, and the category $\mathbb{E}\mathrm{q}(\mathrm{Dark}^*)$ whose objects are the so-called dark ceers plus the ceers with finitely many equivalence classes. Although in all these categories the monomorphisms coincide with the injective morphisms, we show that in $\mathbb{E}\mathrm{q}(\Sigma^0_1)$ the epimorphisms coincide with the onto morphisms, but in $\mathbb{E}\mathrm{q}(\Pi^0_1)$ there are epimorphisms that are not onto. Moreover, $\mathbb{E}\mathrm{q}$, $\mathbb{E}\mathrm{q}(\Sigma^0_1)$, and $\mathbb{E}\mathrm{q}(\mathrm{Dark}^*)$ are closed under finite products, binary coproducts, and coequalizers, but we give an example of two morphisms in $\mathbb{E}\mathrm{q}(\Pi^0_1)$ whose coequalizer in $\mathbb{E}\mathrm{q}$ is not an object of $\mathbb{E}\mathrm{q}(\Pi^0_1)$.

Détail

Keywords: category of equivalence relations on set of natural numbers, category of ceers, category of coceers, category of dark ceers and finite ceers.

Bibliographie

[1] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977

[2] S. Mac Lane, Categories for the working mathematician, Grad. Texts Math., 5, Springer-Verlag, New York-Heidelberg-Berlin, 1971 | Zbl

[3] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 ; Kh. Rodzhers, Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | Zbl

[4] Yu. L. Ershov, “Pozitivnye ekvivalentnosti”, Algebra i logika, 10:6 (1971), 620–650

[5] U. Andrews, S. Badaev, A. Sorbi, “A survey on universal computably enumerable equivalence relations”, Computability and complexity, Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday, Lect. Notes Comput. Sci., 10010, eds. A. Day et al., Springer, Cham, 2017, 418–451 | DOI | Zbl

[6] V. Yu. Shavrukov, “Remarks on uniformly finitely precomplete positive equivalences”, Math. Log. Q, 42:1 (1996), 67–82 | DOI | Zbl

[7] U. Andrews, A. Sorbi, “Joins and meets in the structure of ceers”, Computability, 8:3/4 (2019), 193–241 | DOI | Zbl

[8] C. Bernardi, A. Sorbi, “Classifying positive equivalence relations”, J. Symb. Log., 48:3 (1983), 529–538 | DOI | Zbl