|
This article is cited in 1 scientific paper (total in 1 paper)
The category of equivalence relations
V. Delle Rosea, L. San Maurob, A. Sorbia a Dipartimento di Ingegneria Informatiace e Scienze Matematiche Universitá Degli Studi di Siena, Siena, ITALY
b Institute of Discrete Mathematics and Geometry, Vienna
University of Technology, Vienna, AUSTRIA
Abstract:
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)$.
Keywords:
category of equivalence relations on set of natural numbers, category of ceers, category of coceers, category of dark ceers and finite ceers.
Received: 03.07.2020 Revised: 29.11.2021
Citation:
V. Delle Rose, L. San Mauro, A. Sorbi, “The category of equivalence relations”, Algebra Logika, 60:5 (2021), 451–470; Algebra and Logic, 60:5 (2021), 295–307
Linking options:
https://www.mathnet.ru/eng/al2679 https://www.mathnet.ru/eng/al/v60/i5/p451
|
Statistics & downloads: |
Abstract page: | 162 | Full-text PDF : | 37 | References: | 33 | First page: | 9 |
|