congruence relation on an algebraic system
Let $(A,O)$ be an algebraic system. A congruence relation^{}, or simply a congruence^{} $\u212d$ on $A$

1.
is an equivalence relation^{} on $A$; if $(a,b)\in \u212d$ we write $a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)$, 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}\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)\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})\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d).$$
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.

•
$\u212d$ is a congruence relation on $A$ if and only if $\u212d$ 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 $\u212d$ is a congruence on $A$ and $B$ is a subalgebra of $A$, then ${\u212d}_{B}$ defined by $\u212d\cap (B\times B)$ is a congruence on $B$. The equivalence of ${\u212d}_{B}$ is obvious. For any $n$ary operator ${\omega}_{B}$ inherited from $A$’s ${\omega}_{A}$, if ${a}_{i}\equiv {b}_{i}\phantom{\rule{veryverythickmathspace}{0ex}}(mod{\u212d}_{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})\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)$. 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})\phantom{\rule{veryverythickmathspace}{0ex}}(mod{\u212d}_{B})$ as well. ${\u212d}_{B}$ is the congruence restricted to $B$.

•
(extension^{}) Again, let $\u212d$ be a congruence on $A$ and $B$ a subalgebra of $A$. Define ${B}^{\u212d}$ by $\{a\in A\mid (a,b)\in \u212d\text{and}b\in B\}$. In other words, $a\in {B}^{\u212d}$ iff $a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)$ for some $b\in B$. We assert that ${B}^{\u212d}$ is a subalgebra of $A$. If ${\omega}_{A}$ is an $n$ary operator on $A$ and ${a}_{1},\mathrm{\dots},{a}_{n}\in {B}^{\u212d}$, then ${a}_{i}\equiv {b}_{i}\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)$, so ${\omega}_{A}({a}_{1},\mathrm{\dots},{a}_{n})\equiv {\omega}_{A}({b}_{1},\mathrm{\dots},{b}_{n})\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)$. Since ${\omega}_{A}({b}_{1},\mathrm{\dots},{b}_{n})\in B$, ${\omega}_{A}({a}_{1},\mathrm{\dots},{a}_{n})\in {B}^{\u212d}$. Therefore, ${B}^{\u212d}$ is a subalgebra. Because $B\subseteq {B}^{\u212d}$, we call it the extension of $B$ by $\u212d$.

•
Let $B$ be a subset of $A\times A$. The smallest congruence $\u212d$ on $A$ such that $a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d)$ for all $a,b\in B$ is called the congruence generated by $B$. $\u212d$ is often written $\u27e8B\u27e9$. When $B$ is a singleton $\{(a,b)\}$, then we call $\u27e8B\u27e9$ a principal congruence, and denote it by $\u27e8(a,b)\u27e9$.
Quotient algebra
Given an algebraic structure $(A,O)$ and a congruence relation $\u212d$ on $A$, we can construct a new $O$algebra^{} $(A/\u212d,O)$, as follows: elements of $A/\u212d$ are of the form $[a]$, where $a\in A$. We set
$$[a]=[b]\text{iff}a\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(mod\u212d).$$ 
Furthermore, for each $n$ary operator ${\omega}_{A}$ on $A$, define ${\omega}_{A/\u212d}$ by
$${\omega}_{A/\u212d}([{a}_{1}],\mathrm{\dots},[{a}_{n}]):=\left[{\omega}_{A}({a}_{1},\mathrm{\dots},{a}_{n})\right].$$ 
It is easy to see that ${\omega}_{A/\u212d}$ is a welldefined operator on $A/\u212d$. The $O$algebra thus constructed is called the quotient algebra of $A$ over $\u212d$.
Remark. The bracket $[\cdot ]:A\to A/\u212d$ is in fact an epimorphism^{}, with kernel (http://planetmath.org/KernelOfAHomomorphismBetweenAlgebraicSystems) $\mathrm{ker}([\cdot ])=\u212d$. This means that every congruence of an algebraic system $A$ is the kernel of some homomorphism^{} from $A$. $[\cdot ]$ is usually written ${[\cdot ]}_{\u212d}$ to signify its association with $\u212d$.
References
 1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).
Title  congruence relation on an algebraic system 
Canonical name  CongruenceRelationOnAnAlgebraicSystem 
Date of creation  20130322 16:26:23 
Last modified on  20130322 16:26:23 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  33 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 08A30 
Related topic  Congruence3 
Related topic  Congruence2 
Related topic  CongruenceInAlgebraicNumberField 
Related topic  PolynomialCongruence 
Related topic  QuotientCategory 
Related topic  CategoryOfAdditiveFractions 
Defines  congruence 
Defines  congruence relation 
Defines  quotient algebra 
Defines  proper congruence 
Defines  trivial congruence 
Defines  nontrivial congruence 
Defines  congruence restricted to a subalgebra 
Defines  extension of a subalgebra by a congruence 
Defines  principal congruence 
Defines  congruence generated by 