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