RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2021 Volume 60, Number 5, Pages 451–470 (Mi al2679)

This article is cited 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.

UDC: 510.5:512.58

Received: 03.07.2020
Revised: 29.11.2021

DOI: 10.33048/alglog.2021.60.501


 English version:
Algebra and Logic, 2021, 60:5, 295–307

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024