congruence relation on an algebraic system

Let $(A,O)$ be an algebraic system. A congruence relation, or simply a congruence $ℭ$ on $A$

1. is an equivalence relation on $A$; if $(a,b)\in ℭ$ we write $a\equiv b(modℭ)$, and

2. respects every $n$-ary operator on $A$: if ${\omega }_A$ is an $n$-ary operator on $A$ ($\omega \in O$), and for any $a_i,b_i\in A$, $i=1,\mathrm{\dots },n$, we have

   $$a_i\equiv b_i(modℭ)\mathit{\hspace{1em}\hspace{1em}}\text{ implies }\mathit{\hspace{1em}\hspace{1em}}{\omega }_A(a_1,\mathrm{\dots },a_n)\equiv {\omega }_A(b_1,\mathrm{\dots },b_n)(modℭ).$$

For example, $A^2$ and ${\mathrm{\Delta }}_A:=\{(a,a)\mid a\in A\}$ are both congruence relations on $A$. ${\mathrm{\Delta }}_A$ is called the trivial congruence (on $A$). A proper congruence relation is one not equal to $A^2$.

Remarks.

• $ℭ$ is a congruence relation on $A$ if and only if $ℭ$ is an equivalence relation on $A$ and a subalgebra of the product (http://planetmath.org/DirectProductOfAlgebras) $A\times A$.

• The set of congruences of an algebraic system is a complete lattice. The meet is the usual set intersection. The join (of an arbitrary number of congruences) is the join of the underlying equivalence relations (http://planetmath.org/PartitionsFormALattice). This join corresponds to the subalgebra (of $A\times A$) generated by the union of the underlying sets of the congruences. The lattice of congruences on $A$ is denoted by $\mathrm{Con}(A)$.

• (restriction)If $ℭ$ is a congruence on $A$ and $B$ is a subalgebra of $A$, then ${ℭ}_B$ defined by $ℭ\cap (B\times B)$ is a congruence on $B$. The equivalence of ${ℭ}_B$ is obvious. For any $n$-ary operator ${\omega }_B$ inherited from $A$’s ${\omega }_A$, if $a_i\equiv b_i(mod{ℭ}_B)$, then ${\omega }_B(a_1,\mathrm{\dots },a_n)={\omega }_A(a_1,\mathrm{\dots },a_n)\equiv {\omega }_A(b_1,\mathrm{\dots },b_n)={\omega }_B(b_1,\mathrm{\dots },b_n)(modℭ)$. Since both ${\omega }_B(a_1,\mathrm{\dots },a_n)$ and ${\omega }_B(b_1,\mathrm{\dots },b_n)$ are in $B$, ${\omega }_B(a_1,\mathrm{\dots },a_n)\equiv {\omega }_B(b_1,\mathrm{\dots },b_n)(mod{ℭ}_B)$ as well. ${ℭ}_B$ is the congruence restricted to $B$.

• (extension)Again, let $ℭ$ be a congruence on $A$ and $B$ a subalgebra of $A$. Define $B^{ℭ}$ by $\{a\in A\mid (a,b)\in ℭ\text{ and }b\in B\}$. In other words, $a\in B^{ℭ}$ iff $a\equiv b(modℭ)$ for some $b\in B$. We assert that $B^{ℭ}$ is a subalgebra of $A$. If ${\omega }_A$ is an $n$-ary operator on $A$ and $a_1,\mathrm{\dots },a_n\in B^{ℭ}$, then $a_i\equiv b_i(modℭ)$, so ${\omega }_A(a_1,\mathrm{\dots },a_n)\equiv {\omega }_A(b_1,\mathrm{\dots },b_n)(modℭ)$. Since ${\omega }_A(b_1,\mathrm{\dots },b_n)\in B$, ${\omega }_A(a_1,\mathrm{\dots },a_n)\in B^{ℭ}$. Therefore, $B^{ℭ}$ is a subalgebra. Because $B\subseteq B^{ℭ}$, we call it the extension of $B$ by $ℭ$.

• Let $B$ be a subset of $A\times A$. The smallest congruence $ℭ$ on $A$ such that $a\equiv b(modℭ)$ for all $a,b\in B$ is called the congruence generated by $B$. $ℭ$ is often written $⟨B⟩$. When $B$ is a singleton $\{(a,b)\}$, then we call $⟨B⟩$ a principal congruence, and denote it by $⟨(a,b)⟩$.

Quotient algebra

Given an algebraic structure $(A,O)$ and a congruence relation $ℭ$ on $A$, we can construct a new $O$-algebra $(A/ℭ,O)$, as follows: elements of $A/ℭ$ are of the form $[a]$, where $a\in A$. We set

$$[a]=[b]\text{ iff }a\equiv b(modℭ).$$

Furthermore, for each $n$-ary operator ${\omega }_A$ on $A$, define ${\omega }_{A/ℭ}$ by

$${\omega }_{A/ℭ}([a_1],\mathrm{\dots },[a_n]):=\left[{\omega }_A(a_1,\mathrm{\dots },a_n)\right].$$

It is easy to see that ${\omega }_{A/ℭ}$ is a well-defined operator on $A/ℭ$. The $O$-algebra thus constructed is called the quotient algebra of $A$ over $ℭ$.

Remark. The bracket $[\cdot ]:A\to A/ℭ$ is in fact an epimorphism, with kernel (http://planetmath.org/KernelOfAHomomorphismBetweenAlgebraicSystems) $\ker ([\cdot ])=ℭ$. This means that every congruence of an algebraic system $A$ is the kernel of some homomorphism from $A$. $[\cdot ]$ is usually written ${[\cdot ]}_{ℭ}$ to signify its association with $ℭ$.