You are here
Homecongruence relation on an algebraic system
Primary tabs
congruence relation on an algebraic system
Let $(A,O)$ be an algebraic system. A congruence relation, or simply a congruence $\mathfrak{C}$ on $A$
1. is an equivalence relation on $A$; if $(a,b)\in\mathfrak{C}$ we write $a\equiv b\;\;(\mathop{{\rm mod}}\mathfrak{C})$, 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,\ldots,n$, we have
$a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\mathfrak{C})\qquad\mbox{ implies }% \qquad\omega_{A}(a_{1},\ldots,a_{n})\equiv\omega_{A}(b_{1},\ldots,b_{n})\;\;(% \mathop{{\rm mod}}\mathfrak{C}).$
For example, $A^{2}$ and $\Delta_{A}:=\{(a,a)\mid a\in A\}$ are both congruence relations on $A$. $\Delta_{A}$ is called the trivial congruence (on $A$). A proper congruence relation is one not equal to $A^{2}$.
Remarks.

$\mathfrak{C}$ is a congruence relation on $A$ if and only if $\mathfrak{C}$ is an equivalence relation on $A$ and a subalgebra of the product $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. 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 $\operatorname{Con}(A)$.

(restriction) If $\mathfrak{C}$ is a congruence on $A$ and $B$ is a subalgebra of $A$, then $\mathfrak{C}_{B}$ defined by $\mathfrak{C}\cap(B\times B)$ is a congruence on $B$. The equivalence of $\mathfrak{C}_{B}$ is obvious. For any $n$ary operator $\omega_{B}$ inherited from $A$’s $\omega_{A}$, if $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\mathfrak{C}_{B})$, then $\omega_{B}(a_{1},\ldots,a_{n})=\omega_{A}(a_{1},\ldots,a_{n})\equiv\omega_{A}(% b_{1},\ldots,b_{n})=\omega_{B}(b_{1},\ldots,b_{n})\;\;(\mathop{{\rm mod}}% \mathfrak{C})$. Since both $\omega_{B}(a_{1},\ldots,a_{n})$ and $\omega_{B}(b_{1},\ldots,b_{n})$ are in $B$, $\omega_{B}(a_{1},\ldots,a_{n})\equiv\omega_{B}(b_{1},\ldots,b_{n})\;\;(\mathop% {{\rm mod}}\mathfrak{C}_{B})$ as well. $\mathfrak{C}_{B}$ is the congruence restricted to $B$.

(extension) Again, let $\mathfrak{C}$ be a congruence on $A$ and $B$ a subalgebra of $A$. Define $B^{{\mathfrak{C}}}$ by $\{a\in A\mid(a,b)\in\mathfrak{C}\mbox{ and }b\in B\}$. In other words, $a\in B^{{\mathfrak{C}}}$ iff $a\equiv b\;\;(\mathop{{\rm mod}}\mathfrak{C})$ for some $b\in B$. We assert that $B^{{\mathfrak{C}}}$ is a subalgebra of $A$. If $\omega_{A}$ is an $n$ary operator on $A$ and $a_{1},\ldots,a_{n}\in B^{{\mathfrak{C}}}$, then $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\mathfrak{C})$, so $\omega_{A}(a_{1},\ldots,a_{n})\equiv\omega_{A}(b_{1},\ldots,b_{n})\;\;(\mathop% {{\rm mod}}\mathfrak{C})$. Since $\omega_{A}(b_{1},\ldots,b_{n})\in B$, $\omega_{A}(a_{1},\ldots,a_{n})\in B^{{\mathfrak{C}}}$. Therefore, $B^{{\mathfrak{C}}}$ is a subalgebra. Because $B\subseteq B^{{\mathfrak{C}}}$, we call it the extension of $B$ by $\mathfrak{C}$.

Let $B$ be a subset of $A\times A$. The smallest congruence $\mathfrak{C}$ on $A$ such that $a\equiv b\;\;(\mathop{{\rm mod}}\mathfrak{C})$ for all $a,b\in B$ is called the congruence generated by $B$. $\mathfrak{C}$ is often written $\langle B\rangle$. When $B$ is a singleton $\{(a,b)\}$, then we call $\langle B\rangle$ a principal congruence, and denote it by $\langle(a,b)\rangle$.
Quotient algebra
Given an algebraic structure $(A,O)$ and a congruence relation $\mathfrak{C}$ on $A$, we can construct a new $O$algebra $(A/\mathfrak{C},O)$, as follows: elements of $A/\mathfrak{C}$ are of the form $[a]$, where $a\in A$. We set
$[a]=[b]\mbox{ iff }a\equiv b\;\;(\mathop{{\rm mod}}\mathfrak{C}).$ 
Furthermore, for each $n$ary operator $\omega_{A}$ on $A$, define $\omega_{{A/\mathfrak{C}}}$ by
$\omega_{{A/\mathfrak{C}}}\big([a_{1}],\ldots,[a_{n}]\big):=\big[\omega_{A}(a_{% 1},\ldots,a_{n})\big].$ 
It is easy to see that $\omega_{{A/\mathfrak{C}}}$ is a welldefined operator on $A/\mathfrak{C}$. The $O$algebra thus constructed is called the quotient algebra of $A$ over $\mathfrak{C}$.
Remark. The bracket $[\cdot]:A\to A/\mathfrak{C}$ is in fact an epimorphism, with kernel $\ker([\cdot])=\mathfrak{C}$. This means that every congruence of an algebraic system $A$ is the kernel of some homomorphism from $A$. $[\cdot]$ is usually written $[\cdot]_{{\mathfrak{C}}}$ to signify its association with $\mathfrak{C}$.
References
 1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).
Mathematics Subject Classification
08A30 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis
Apr 20
new image: informationtheoreticdistributedmeasurementdds.png by rspuzio
new image: informationtheoreticdistributedmeasurement4.2 by rspuzio
new image: informationtheoreticdistributedmeasurement4.1 by rspuzio
new image: informationtheoreticdistributedmeasurement3.2 by rspuzio
new image: informationtheoreticdistributedmeasurement3.1 by rspuzio
new image: informationtheoreticdistributedmeasurement2.1 by rspuzio
Apr 19
new collection: On the InformationTheoretic Structure of Distributed Measurements by rspuzio
Apr 15
new question: Prove a formula is part of the Gentzen System by LadyAnne
Mar 30
new question: A problem about Euler's totient function by mbhatia