Congruence relation

In mathematics, a congruence relation, also known as a congruence, is an equivalence relation defined on the carrier set of an algebraic structure that is compatible with the structure's operations, meaning it preserves the results of those operations when applied to equivalent elements.^[1] This compatibility ensures that if elements $a_1 \equiv b_1, \dots, a_n \equiv b_n$ under the congruence, then for any $n$-ary operation $f$ of the algebra, $f(a_1, \dots, a_n) \equiv f(b_1, \dots, b_n)$.^[2] Congruences generalize the familiar notion of congruence modulo $n$ on the integers, where two integers $a$ and $b$ are congruent modulo a positive integer $n$, denoted $a \equiv b \pmod{n}$, if $n$ divides $a - b$, partitioning the integers into equivalence classes known as residue classes.^[3] As an equivalence relation, every congruence satisfies reflexivity ($a \equiv a$), symmetry (if $a \equiv b$ then $b \equiv a$), and transitivity (if $a \equiv b$ and $b \equiv c$ then $a \equiv c$).^[3] In the context of universal algebra, congruences enable the construction of quotient algebras, where the equivalence classes serve as the new carrier set, and operations are defined naturally on these classes via a canonical surjective homomorphism.^[1] The set of all congruences on a given algebra forms a complete lattice under inclusion, ordered by refinement, which facilitates the study of algebraic varieties and homomorphic images.^[1] Congruence relations appear prominently in various algebraic domains: in group theory, they correspond to normal subgroups, yielding quotient groups; in ring theory, they align with ideals, producing quotient rings; and in lattice theory or order theory, they respect partial orders or meets and joins.^[1] For instance, in the integers under addition and multiplication, the principal congruence modulo $n$ is generated by the pairs $(kn, 0)$ for integers $k$, forming the ring of integers modulo $n$, $\mathbb{Z}/n\mathbb{Z}$.^[1] These relations are fundamental to solving linear congruences, analyzing Diophantine equations, and understanding modular arithmetic, with applications extending to cryptography, coding theory, and computational number theory.^[3]

Core Concepts

Definition

In universal algebra, a congruence relation on an algebra $A$ of type $F$ is defined as an equivalence relation $\theta$ on the carrier set (universe) $A$ that satisfies a compatibility condition with respect to the operations specified by $F$.^[4] Formally, $\theta$ is a congruence if, for every $n$-ary operation symbol $f \in F$ and all tuples $(a_1, \dots, a_n), (b_1, \dots, b_n) \in A^n$ such that $a_i \theta b_i$ for each $i = 1, \dots, n$, it holds that

$$f_A(a_1, \dots, a_n) \theta f_A(b_1, \dots, a_n),$$

where $f_A$ denotes the interpretation of $f$ in $A$. This compatibility property ensures that the algebraic structure is preserved under the equivalence.^[4] For binary operations, such as a multiplication $*$ on $A$, the condition specializes to: if $a \theta a'$ and $b \theta b'$, then $a * b \theta a' * b'$. Congruences are typically denoted by $\theta$ or $\sim$, distinguishing them from arbitrary equivalence relations by their structure-preserving nature, which allows the formation of well-defined quotient algebras $A/\theta$.^[4]

Properties

A congruence relation on an algebra is fundamentally an equivalence relation, meaning it satisfies the properties of reflexivity, symmetry, and transitivity.^[5][6] The congruence classes induced by a congruence $\theta$ on $A$ are the sets $[a]_\theta = \{ b \in A \mid (a, b) \in \theta \}$, which partition $A$. Specifically, for any operation $f$ of arity $n$ and elements $a_1, \dots, a_n \in A$, if each $a_i \in [b_i]_\theta$, then $f(a_1, \dots, a_n) \in [f(b_1, \dots, b_n)]_\theta$. This ensures that operations are well-defined on the quotient set.^[5][6] The quotient set $A / \theta$, consisting of these congruence classes, inherits the structure of an algebra with operations defined componentwise: for an $n$-ary operation $f$, the induced operation is $f_{A/\theta}([a_1]_\theta, \dots, [a_n]_\theta) = [f(a_1, \dots, a_n)]_\theta$. This well-definedness follows from the compatibility condition, and the quotient algebra $A / \theta$ satisfies all equations that $A$ does, preserving the variety of the original algebra. The canonical projection $\pi_\theta: A \to A / \theta$ is a homomorphism witnessing this structure.^[5][6] The collection of all congruences on an algebra $A$, denoted $\mathrm{Con}(A)$, ordered by inclusion, forms a complete lattice. The meet of any family of congruences is their intersection, which is again a congruence as it inherits compatibility and equivalence properties. The join is the congruence generated by the union, obtained via the transitive closure under relational products, ensuring $\mathrm{Con}(A)$ is closed under arbitrary infima and suprema. The trivial congruence $\Delta_A = \{(a,a) \mid a \in A\}$ (the equality relation) is the least element, and the full relation $\nabla_A = A \times A$ is the greatest. This lattice structure is algebraic, with compact elements corresponding to finitely generated congruences.^[5][6]

Examples

Modular Arithmetic

A fundamental example of a congruence relation arises in the integers $\mathbb{Z}$ under the relation of congruence modulo $n$, where $n$ is a positive integer. Two integers $a$ and $b$ are congruent modulo $n$, denoted $a \equiv b \pmod{n}$, if and only if $n$ divides $a - b$, meaning there exists an integer $k$ such that $a - b = kn$.^[7][8] This relation partitions the integers into equivalence classes known as residue classes. The residue class of an integer $a$ modulo $n$ consists of all integers that differ from $a$ by multiples of $n$, formally $[a] = \{ \dots, a - 2n, a - n, a, a + n, a + 2n, \dots \}$.^[7][9] The congruence relation modulo $n$ is compatible with the operations of addition and multiplication on the integers. Specifically, if $a \equiv b \pmod{[n](/page/N+)}$ and $c \equiv d \pmod{[n](/page/N+)}$, then $a + c \equiv b + d \pmod{[n](/page/N+)}$ and $ac \equiv bd \pmod{[n](/page/N+)}$.^[7] This compatibility ensures that the set of residue classes forms a ring under the induced operations, denoted $\mathbb{Z}/[n](/page/N+)\mathbb{Z}$, where addition and multiplication are performed modulo $[n](/page/N+)$.^[7] In this quotient ring, each element is a residue class, and the structure captures the arithmetic of integers "wrapped around" every $[n](/page/N+)$ units.^[9] The concept of congruence modulo $n$ was introduced by Carl Friedrich Gauss in his 1801 work Disquisitiones Arithmeticae, where he developed it as a tool for investigating properties of integers and Diophantine equations.^[10][11]

Groups

In group theory, a congruence relation on a group $G$ is an equivalence relation $\sim$ that respects the group operation, meaning if $g_1 \sim h_1$ and $g_2 \sim h_2$, then $g_1 g_2 \sim h_1 h_2$. Such relations on groups are in one-to-one correspondence with the normal subgroups of $G$. Specifically, every normal subgroup $N \trianglelefteq G$ determines a congruence via $g \sim h$ if and only if $g^{-1} h \in N$, and conversely, every congruence arises this way from the normal subgroup consisting of elements equivalent to the identity. $$] ^[2][12] The equivalence classes for this congruence are the left cosets of $N$ in $G$, denoted $gN = \{gn \mid n \in N\}$ for $g \in G$. These cosets partition $G$ and form a group structure under the induced operation $(gN)(hN) = (gh)N$, which is well-defined because $N$ is normal (ensuring that the product of cosets depends only on the cosets themselves, not on choices of representatives). This group is called the quotient group $G/N$, with identity coset $N$ and inverse $(gN)^{-1} = g^{-1}N$.[$$ ^[13][14] Two prominent examples illustrate this construction. The trivial congruence corresponds to $N = G$, the entire group as a normal subgroup, where every element is equivalent to every other, yielding a single coset $G$ and the trivial quotient group $\{G\}$ with one element. The discrete congruence arises from $N = \{e\}$, the trivial subgroup (which is always normal), where $g \sim h$ holds only if $g = h$, so the cosets are singletons $\{g\}$ and the quotient $G/\{e\} \cong G$ is isomorphic to the original group. $$] ^[2][12] Importantly, not every subgroup of $G$ induces a congruence relation; only normal subgroups do, as non-normal subgroups fail to produce an equivalence that is compatible with the group multiplication (the induced relation would not satisfy the compatibility condition for all pairs of elements).[$$ ^[2][1]

Rings

In ring theory, a congruence relation on a ring $R$ is determined by an ideal $I$ of $R$, where two elements $a, b \in R$ satisfy $a \sim b$ if and only if $a - b \in I$.^[15] This relation is an equivalence relation because $I$ is an additive subgroup of $R$, ensuring reflexivity, symmetry, and transitivity, while the ideal property guarantees compatibility with the ring operations.^[16] The equivalence classes under this congruence are the left (or right, since ideals are two-sided) cosets of $I$ in $R$, denoted $a + I = \{a + i \mid i \in I\}$.^[15] These cosets form the quotient ring $R/I$, equipped with well-defined addition and multiplication: $(a + I) + (b + I) = (a + b) + I$ and $(a + I)(b + I) = ab + I$.^[16] The operations are well-defined precisely because $I$ absorbs multiplication by elements of $R$, preventing ambiguity in representatives./16:_Rings/16.05:_Ring_Homomorphisms_and_Ideals) A concrete example arises in polynomial rings: the quotient $\mathbb{R}[x]/(x^2 + 1)\mathbb{R}[x]$ is isomorphic to the field of complex numbers $\mathbb{C}$, where the isomorphism sends the coset of $x$ to $i = \sqrt{-1}$, allowing polynomials to be reduced modulo $x^2 + 1$ to linear forms $a + bi$ with $a, b \in \mathbb{R}$.^[17] More generally, every ideal $I$ of a ring $R$ serves as the kernel of the canonical projection homomorphism $\pi: R \to R/I$, and conversely, the kernel of any ring homomorphism is an ideal./16:_Rings/16.05:_Ring_Homomorphisms_and_Ideals) This correspondence underscores the role of congruences in constructing quotient structures that preserve ring operations.^[18]

Structural Connections

Homomorphisms

In universal algebra, the kernel of a homomorphism $\phi: A \to B$ between two algebras over the same signature is defined as the relation $\ker(\phi) = \{(a, b) \in A \times A \mid \phi(a) = \phi(b)\}$. This kernel is always a congruence on $A$, as it forms an equivalence relation—reflexive because $\phi(a) = \phi(a)$, symmetric because equality is symmetric, and transitive because if $\phi(a) = \phi(b)$ and $\phi(b) = \phi(c)$, then $\phi(a) = \phi(c)$—and it is compatible with the operations of $A$: if $(a_i, b_i) \in \ker(\phi)$ for $i = 1, \dots, n$, then $\phi(f_A(a_1, \dots, a_n)) = f_B(\phi(a_1), \dots, \phi(a_n)) = f_B(\phi(b_1), \dots, \phi(b_n)) = \phi(f_A(b_1, \dots, b_n))$, so $(f_A(a_1, \dots, a_n), f_A(b_1, \dots, b_n)) \in \ker(\phi)$.^[5] The first isomorphism theorem establishes a fundamental connection between this kernel and quotient structures: the quotient algebra $A / \ker(\phi)$ is isomorphic to the image $\operatorname{im}(\phi) = \{\phi(a) \mid a \in A\}$, where the isomorphism is given by the map $[a]_{\ker(\phi)} \mapsto \phi(a)$. This map is well-defined because if $[a]_{\ker(\phi)} = [a']_{\ker(\phi)}$, then $(a, a') \in \ker(\phi)$, so $\phi(a) = \phi(a')$; it is bijective, with inverse $\phi(a) \mapsto [a]_{\ker(\phi)}$; and it preserves operations since $\phi$ is a homomorphism.^[5] Conversely, every congruence $\theta$ on $A$ arises as the kernel of some homomorphism, specifically the natural projection $\pi: A \to A / \theta$ defined by $\pi(a) = [a]_\theta$. Here, $\ker(\pi) = \theta$ because $\pi(a) = \pi(b)$ if and only if $(a, b) \in \theta$, and $\pi$ is a surjective homomorphism that preserves all operations by the definition of the quotient algebra.^[5] A concrete example occurs in the context of modular arithmetic on the integers: the projection homomorphism $\pi: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ given by $\pi(k) = k \mod n$ has kernel $\ker(\pi) = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a \equiv b \pmod{n}\}$, which is precisely the standard congruence relation modulo $n$. By the first isomorphism theorem, $\mathbb{Z} / \ker(\pi) \cong \mathbb{Z}/n\mathbb{Z}$.^[5]

Normal Subgroups and Ideals

In group theory, a congruence relation on a group $G$ is determined by a normal subgroup $N \trianglelefteq G$, where two elements $g_1, g_2 \in G$ are congruent modulo $N$ if $g_1 g_2^{-1} \in N$ (or equivalently, $g_1^{-1} g_2 \in N$), and the congruence classes are the cosets of $N$. This equivalence relation preserves the group operation because $N$ is normal, ensuring that the quotient set $G/N$ forms a group under the induced operation. A subgroup $N$ of $G$ is normal if and only if it is the kernel of some group homomorphism $\phi: G \to H$, where the kernel is defined as $\ker \phi = \{ g \in G \mid \phi(g) = e_H \}$. This correspondence establishes a bijection between the normal subgroups of $G$ and the congruence relations on $G$.^[2]/02%3A_Groups/2.04%3A_Group_homomorphisms) An equivalent characterization of normality is that $N$ is invariant under conjugation: $g N g^{-1} = N$ for all $g \in G$. This condition ensures that left and right cosets coincide, $gN = Ng$, which is necessary for the coset partition to define a congruence compatible with the group multiplication. The kernel property follows directly from this invariance, as homomorphisms preserve the group structure, and conversely, for any normal subgroup $N$, the canonical projection $\pi: G \to G/N$ is a surjective homomorphism with kernel $N$. Thus, normal subgroups unify the notions of kernels and congruences in groups.^[19] In ring theory, congruence relations on a ring $R$ correspond precisely to two-sided ideals $I$ of $R$, where $a \equiv b \pmod{I}$ if $a - b \in I$, and the classes $a + I$ form the quotient ring $R/I$. A subset $I$ of $R$ is a two-sided ideal if it absorbs multiplication from both sides: for all $r \in R$ and $i \in I$, $r i \in I$ and $i r \in I$. Such an ideal $I$ is the kernel of a ring homomorphism $\psi: R \to S$ if and only if it is two-sided, as the homomorphism must preserve both addition and multiplication, requiring the kernel to be compatible with left and right multiplications. Left ideals (absorbing only right multiplication) and right ideals (absorbing only left multiplication) do not generally yield ring congruences unless the ring is commutative, but in the general case, two-sided ideals provide the full correspondence. This bijection between two-sided ideals and congruences mirrors the group case, enabling quotient constructions.^[15][20] In the setting of universal algebra, congruences on an algebra $A$ in a variety are exactly the kernels of homomorphisms from $A$ to other algebras in the variety, where the kernel is the equivalence relation $\theta = \{ (a, b) \in A \times A \mid \phi(a) = \phi(b) \}$ for some $\phi: A \to B$. These kernels are fully invariant under endomorphisms of $A$, meaning that if $(a, b) \in \theta$, then $(\phi(a), \phi(b)) \in \theta$ for any endomorphism $\phi$. The lattice of congruences $\mathrm{Con}(A)$ is algebraic and complete, with a bijection to the closed fully invariant subsets via the term condition or the quotient algebras $A/\theta$. This general framework encompasses groups and rings as special cases, where normal subgroups and two-sided ideals are the specific fully invariant congruence kernels.^[21]

General Frameworks

Universal Algebra

In universal algebra, a congruence relation on an algebra $A$ with a given signature of operations is defined as an equivalence relation $\theta$ on the carrier set of $A$ that is compatible with all the operations, meaning it preserves the algebraic structure under substitution: if $a_i \theta b_i$ for all $i < n_f$, then $f(a_0, \dots, a_{n_f-1}) \theta f(b_0, \dots, b_{n_f-1})$ for every operation $f$ of arity $n_f$. This extends the notion to arbitrary algebraic structures, including those with relations if the signature incorporates them, ensuring the quotient $A/\theta$ forms an algebra of the same type. The set $\operatorname{Con}(A)$ of all congruences on an algebra $A$, ordered by inclusion, forms a complete algebraic lattice, where the meet of congruences is their intersection and the join is the smallest congruence containing their union. This lattice structure captures the hierarchical organization of equivalence classes compatible with the algebra's operations, with the trivial congruences $\Delta_A$ (the equality relation) as the bottom element and $\nabla_A$ (the full relation) as the top. In varieties of algebras—equational classes closed under homomorphic images, subalgebras, and products—specific properties of $\operatorname{Con}(A)$ arise; for instance, a variety is congruence-permutable if congruences $\theta$ and $\phi$ satisfy $\theta \circ \phi = \phi \circ \theta$ for all algebras in the variety, a condition equivalent to the existence of a Mal'cev term $m(x,y,z)$ such that $m(x,x,y) \approx y$ and $m(x,y,y) \approx x$, as in the variety of groups where normal subgroups ensure permutability. Similarly, a variety is congruence-distributive if $\operatorname{Con}(A)$ is distributive for every $A$ in the variety, characterized by primal algebras or discriminator terms, as exemplified by the variety of lattices where congruences correspond to filters and ideals. Principal congruences play a central role in generating $\operatorname{Con}(A)$, with $\theta(a,b)$ denoting the smallest congruence on $A$ such that $a \theta(a,b) b$, obtained as the transitive closure of the relation generated by substituting polynomials or algebraic functions that identify $a$ and $b$. These are finitely generated and compact in the lattice, allowing every congruence to be expressed as a join of principal ones in algebraic lattices. The HSP theorem, fundamental to varieties, states that a class of algebras is a variety if and only if it is closed under the operators H (homomorphic images, via congruences), S (subalgebras), and P (arbitrary products), implying that varieties are precisely the HSP-closures of their subdirectly irreducible members and enabling the representation of any algebra as a subdirect product of simples modulo principal congruences.

Category Theory

In category theory, particularly in categories equipped with pullbacks, a congruence on an object $A$ is defined as an internal equivalence relation, represented by a subobject $R \hookrightarrow A \times A$ equipped with structure maps ensuring reflexivity, symmetry, and transitivity. This subobject gives rise to a pair of parallel arrows $(p_1, p_2): R \rightrightarrows A$, where $p_1$ and $p_2$ are the projections from $R$ to $A$. The coequalizer of this pair, denoted $q: A \to A/\sim$, exists in such categories and yields the quotient object $A/\sim$, where $\sim$ denotes the equivalence relation induced by the congruence.^[22] The quotient object satisfies a universal property: for any morphism $h: A \to B$ that coequalizes the pair $(p_1, p_2)$—meaning $h \circ p_1 = h \circ p_2$—there exists a unique morphism $\overline{h}: A/\sim \to B$ such that $h = \overline{h} \circ q$. This property characterizes the coequalizer and ensures that homomorphisms from $A$ respecting the congruence factor uniquely through the quotient. A congruence is effective if it is the kernel pair of its coequalizer morphism $q$, meaning the pair $(p_1, p_2)$ is precisely the pullback of $q$ along itself.^[23] In the category $\mathbf{Set}$, congruences correspond exactly to ordinary equivalence relations on sets, with the coequalizer $q: A \to A/\sim$ being the canonical surjection onto the set of equivalence classes, and the universal property reducing to the standard fact that functions constant on equivalence classes descend to the quotient set.^[23] In abelian categories, kernels of morphisms are normal monomorphisms, as every monomorphism is the kernel of its cokernel, providing a canonical way to construct normal subobjects. Congruences in this setting manifest as effective equivalence relations, where the kernel pair of any morphism forms a congruence, and the coequalizer yields the corresponding quotient, aligning with the exact structure of the category.^[24]