×

The category of equivalence relations. (English. Russian original) Zbl 1515.18004

Algebra Logic 60, No. 5, 295-307 (2021); translation from Algebra Logika 60, No. 4, 451-470 (2021).
Summary: 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}\left({\Sigma}_1^0\right)\) of computably enumerable equivalence relations (called ceers), the category \(\mathbb{E}\mathrm{q}\left({\Pi}_1^0\right)\) of co-computably enumerable equivalence relations, and the category \(\mathbb{E}\mathrm{q}(\text{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}\left({\Sigma}_1^0\right)\) the epimorphisms coincide with the onto morphisms, but in \(\mathbb{E}\mathrm{q}\left({\Pi}_1^0\right)\) there are epimorphisms that are not onto. Moreover, \( \mathbb{E}\mathrm{q}\), \( \mathbb{E}\mathrm{q}\left({\Sigma}_1^0\right)\), and \(\mathbb{E}\mathrm{q}(\text{Dark}^*)\) are closed under finite products, binary coproducts, and coequalizers, but we give an example of two morphisms in \(\mathbb{E}\mathrm{q}\left({\Pi}_1^0\right)\) whose coequalizer in \(\mathbb{E}\mathrm{q}\) is not an object of \(\mathbb{E}\mathrm{q}\left({\Pi}_1^0\right)\).

MSC:

18B10 Categories of spans/cospans, relations, or partial maps
03D25 Recursively (computably) enumerable sets and degrees
03D45 Theory of numerations, effectively presented structures
Full Text: DOI

References:

[1] Yu. L. Ershov, Theory of Numerations [in Russian], Nauka, Moscow (1977).
[2] S. Mac Lane, Categories for the Working Mathematician, Grad. Texts Math., 5, Springer, New York (1971). · Zbl 0232.18001
[3] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), New York: McGraw-Hill, New York · Zbl 0183.01401
[4] Ershov, YL, Positive equivalences, Algebra and Logic, 10, 6, 378-394 (1971) · Zbl 0276.02024 · doi:10.1007/BF02218645
[5] U. Andrews, S. Badaev, and A. Sorbi, “A survey on universal computably enumerable equivalence relations,” in Lect. Notes Comput. Sci., 10010, Springer, Cham (2017), pp. 418-451. · Zbl 1485.03146
[6] Shavrukov, VY, Remarks on uniformly finitely precomplete positive equivalences, Math. Log. Q., 42, 1, 67-82 (1996) · Zbl 0852.03021 · doi:10.1002/malq.19960420107
[7] Andrews, U.; Sorbi, A., Joins and meets in the structure of ceers, Computability, 8, 3-4, 193-241 (2019) · Zbl 1454.03048 · doi:10.3233/COM-180098
[8] Bernardi, C.; Sorbi, A., Classifying positive equivalence relations, J. Symb. Log., 48, 3, 529-538 (1983) · Zbl 0528.03030 · doi:10.2307/2273443
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.