The Category of Equivalence Relations

We make some beginning observations about the category Eq 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 Eq, such as the category Eq(Sigma(0)(1)) of computably enumerable equivalence relations (called ceers), the category Eq(Pi(0)(1)) of co-computably enumerable equivalence relations, and the category Eq(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 Eq(Sigma(0)(1)) the epimorphisms coincide with the onto morphisms, but in Eq(Pi(0)(1)) there are epimorphisms that are not onto. Moreover, Eq, Eq(Sigma(0)(1)), and Eq(Dark*) are closed under finite products, binary coproducts, and coequalizers, but we give an example of two morphisms in Eq(Pi(0)(1)) whose coequalizer in Eq is not an object of Eq(Pi(0)(1)).