Rel, bicategory of relations, allegory
left and right euclidean;
extensional, well-founded relations.
In Euclidean geometry, by congruence one means the equivalence relation on the collection of subsets of a Euclidean space which regards two of these as equivalent if one is carried into the other by an isometry (of the ambient Euclidean space).
Similarly, in algebra, by a congruence one means certain equivalence relations on elements of algebraic structures, such as groups or rings (cf. e.g. the multiplicative group of integers modulo n).
Therefore, in category theory the term congruence is used in the broad generality of equivalence relations on (the generalized elements of) any object internal to any finitely complete category.
In a category $C$ with pullbacks, a congruence on an object $X$ is an internal equivalence relation on $X$ (i.e.: an internal groupoid — hence an internal category with all morphisms being isomorphisms — but with no non-identity automorphisms).
This means that it consists of a subobject
of the Cartesian product of $X$ with itself, equipped with the following morphisms:
internal reflexivity: $r \colon X \to R$ which is a section both of $p_1$ and of $p_2$, i.e., $p_1 r = p_2 r = 1_X$;
internal symmetry: $s \colon R \to R$ which interchanges $p_1$ and $p_2$, i.e., $p_1\circ s = p_2$ and $p_2\circ s = p_1$;
internal transitivity:
$t \,\colon\, R \times_X R \to R$
(where on the left we have the fiber product of $R \hookrightarrow X \times X \overset{p_2}{\to} X$ with $R \hookrightarrow X \times X \overset{p_1}{\to} X$, i.e. the subobject of pairs of composable pairs in relation)
which factors the left/right projection map $R \times_X R \to X \times X$ through $R$, i.e., the following diagram commutes
where $q_1$ and $q_2$ are the projections defined by the pullback diagram
Since $i$ is a monomorphism, the maps $r$, $s$, and $t$ are necessarily unique if they exist.
Equivalently, a congruence on $X$ is an internal category with $X$ the object of objects, such that the (source,target)-map is a monomorphism and such that if there is a morphism $x_1 \to x_2$ then there is also a morphism $x_2 \to x_1$ (internally).
We can equivalently define a congruence $R$ as (a representing object of) a representable sub-presheaf of $\hom(-, X \times X)$ so that for each object $Y$, the composite of $R(Y) \hookrightarrow \hom(Y, X \times X) \cong \hom(Y, X) \times \hom(Y, X)$ exhibits $R(Y)$ as an equivalence relation on the set $\hom(Y, X)$. The upshot of this definition is that it makes sense even when $C$ is not finitely complete.
The coequalizer of a congruence is called a quotient object.
The quotient of an effective congruence is called an effective quotient.
A regular category is called an exact category if every congruence is effective.
An effective congruence, def. , is always the kernel pair of its quotient, def. , if that quotient exists.
Every diagonal morphism on an object is a congruence and has a quotient object isomorphic to the original object.
Every kernel pair is a congruence.
An equivalence relation is precisely a congruence in Set.
The eponymous example is congruence modulo $n$ (for a fixed natural number $n$), which can be considered a congruence on $\mathbb{N}$ in the category of rigs, or on $\mathbb{Z}$ in the category of rings.
A quotient group by a normal subgroup $K \hookrightarrow G$ is the quotient of the congruence $R = \{(x,y) : xy^{-1} \in K \}$.
Alternatively, a quotient group by a normal subgroup $K \hookrightarrow G$ is the quotient of the congruence $G \times K \stackrel{(p_1,p_2)}{\hookrightarrow} G \times G$, where $p_1$ is projection on the first factor and $p_2$ is multiplication in $G$ (these are source and target maps in the action groupoid $G \sslash K$).
A special case of this is that of a quotient module.
The notions of regular category and exact category can naturally be formulated in terms of congruences. A “higher arity” version, corresponding to coherent categories and pretoposes is discussed at familial regularity and exactness.
A Mal'cev category is a finitely complete category in which every internal relation satisfying reflexivity is thereby actually a congruence.
Higher-categorical generalizations are that of a 2-congruence and of a groupoid object in an (∞,1)-category. See also (n,r)-congruence.
Wikipedia, Congruence (geometry)
Wikipedia, Congruence relation
References using terminology as above:
Jiri Adamek, Horst Herrlich, George Strecker, p. 195 of: Abstract and Concrete Categories, John Wiley and Sons, New York (1990) reprinted as: Reprints in Theory and Applications of Categories 17 (2006) 1-507 [tac:tr17, book webpage]
Francis Borceux, Exp. 2.10.3.b in: Handbook of Categorical Algebra Vol. 1 Basic Category Theory, Encyclopedia of Mathematics and its Applications 50, Cambridge University Press (1994) [doi:10.1017/CBO9780511525858]
Francis Borceux, Exps. 2.5.6 in: Handbook of Categorical Algebra Vol. 2 Categories and Structures, Encyclopedia of Mathematics and its Applications 50, Cambridge University Press (1994) [doi:10.1017/CBO9780511525865]
Marek A. Bednarczyk, Andrzej M. Borzyszkowski, Wieslaw Pawlowski, Generalized congruences – epimorphisms in $\mathcal{C}at$, Theory and Applications of Categories 5 11 (1999) 266-280 [tac:5-11, dml:120226]
…
But, for what it’s worth, a different use of the term “congruence” in category theory appears in Def. 3.5.1 on p. 89 in:
Last revised on July 30, 2024 at 13:47:01. See the history of this page for a list of all contributions to it.