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.
2021
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1175461