We make some beginning observations about the category $eeq$ 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 $eeq$, such as the category $eeq(Sigma^0_1)$ of computably enumerable equivalence relations (called emph{ceers}), the category $eeq(Pi^0_1)$ of co-computably enumerable equivalence relations, and the category $eeq(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 $eeq(Sigma^0_1)$ the epimorphisms coincide with the onto morphisms, but in $eeq(Pi^0_1)$ there are epimorphisms that are not onto. Moreover, $eeq$, $eeq(Sigma^0_1)$, and $eeq(dark^*)$ are closed under finite products, binary coproducts, and coequalizers. On the other hand, we show that $eeq(Pi^0_1)$ does not always have coequalizers.
DELLE ROSE, V., SAN MAURO, L.F., Sorbi, A. (2021). The category of equivalence relations. ALGEBRA AND LOGIC, 60(5), 295-307 [10.1007/s10469-021-09656-6].
The category of equivalence relations
Delle Rose Valentino
;San Mauro Luca;Sorbi Andrea
2021-01-01
Abstract
We make some beginning observations about the category $eeq$ 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 $eeq$, such as the category $eeq(Sigma^0_1)$ of computably enumerable equivalence relations (called emph{ceers}), the category $eeq(Pi^0_1)$ of co-computably enumerable equivalence relations, and the category $eeq(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 $eeq(Sigma^0_1)$ the epimorphisms coincide with the onto morphisms, but in $eeq(Pi^0_1)$ there are epimorphisms that are not onto. Moreover, $eeq$, $eeq(Sigma^0_1)$, and $eeq(dark^*)$ are closed under finite products, binary coproducts, and coequalizers. On the other hand, we show that $eeq(Pi^0_1)$ does not always have coequalizers.File | Dimensione | Formato | |
---|---|---|---|
categories-(English).pdf
non disponibili
Descrizione: articolo
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
238.49 kB
Formato
Adobe PDF
|
238.49 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1175461