A note on the category of equivalence relations

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,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 }_1^0)$ of computably enumerable equivalence relations (called ceers), the category $\mathbb{E}\mathrm{q}({\Pi }_1^0)$ of co-computably enumerable equivalence relations, and the category $\mathbb{E}\mathrm{q}({\mathrm{Dark}}^{\ast })$ 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 }_1^0)$ the epimorphisms coincide with the onto morphisms, but in $\mathbb{E}\mathrm{q}({\Pi }_1^0)$ there are epimorphisms that are not onto. Moreover, $\mathbb{E}\mathrm{q}$, $\mathbb{E}\mathrm{q}({\Sigma }_1^0)$, and $\mathbb{E}\mathrm{q}({\mathrm{Dark}}^{\ast })$ are closed under finite products, binary coproducts, and coequalizers, but we give an example of two morphisms in $\mathbb{E}\mathrm{q}({\Pi }_1^0)$ whose coequalizer in $\mathbb{E}\mathrm{q}$ is not an object of $\mathbb{E}\mathrm{q}({\Pi }_1^0)$.

14 pages, forthcoming in Algebra and Logic