congruence relation

A congruence is an equivalence relation that ‘respects’ the operations, so that you may safely work with classes instead of individual elements. The model to keep in mind is arithmetic mod n: if a ≡ a' and b ≡ b' modulo n, then a + b ≡ a' + b' and a·b ≡ a'·b', so addition and multiplication descend to the residue classes. A congruence generalizes exactly this ‘compatibility with operations’ to any algebra.

Formally, a congruence on a Σ-algebra A is an equivalence relation θ on A that is compatible with every operation: for each f of arity n, whenever a_i θ b_i for i = 1, ..., n, one has f^A(a_1, ..., a_n) θ f^A(b_1, ..., b_n). Equivalently θ, viewed as a subset of A × A, is a subalgebra of the product algebra A × A that is also an equivalence relation. Congruences are what make quotients possible: only when the relation is compatible can the induced operations on classes be well-defined.

Congruences play the role for general algebras that normal subgroups play for groups and ideals play for rings — indeed congruences of a group correspond bijectively to its normal subgroups, and congruences of a ring to its (two-sided) ideals. The set Con(A) of all congruences on A, ordered by inclusion, is a complete lattice (the congruence lattice), and its shape — distributive, modular, simple — encodes deep structural information about A.