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^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)$.
Download