congruence relation on an algebraic systemCongruenceRelationOnAnAlgebraicSystem2006-11-29 18:31:222008-08-12 16:17:47Definitioncongruencecongruence relationquotient algebraproper congruencetrivial congruencenon-trivial congruencecongruence restricted to a subalgebraextension of a subalgebra by a congruenceprincipal congruencecongruence generated by\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
\usepackage{psfrag}
% define commands here
\newtheorem{prop}{Proposition}Let $(A,O)$ be an algebraic system. A \emph{congruence relation}, or simply a \emph{congruence} $\mathfrak{C}$ on $A$
\begin{enumerate}
\item is an equivalence relation on $A$; if $(a,b)\in \mathfrak{C}$ we write $a\equiv b\pmod {\mathfrak{C}}$, and
\item 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\pmod {\mathfrak{C}} \qquad\mbox{ implies }\qquad \omega_A(a_1,\ldots,a_n)\equiv \omega_A(b_1,\ldots,b_n) \pmod {\mathfrak{C}}.$$
\end{enumerate}
For example, $A^2$ and $\Delta_A:=\lbrace (a,a)\mid a\in A\rbrace$ are both congruence relations on $A$. $\Delta_A$ is called the \emph{trivial congruence} (on $A$). A \emph{proper} congruence relation is one not equal to $A^2$.
\textbf{Remarks}.
\begin{itemize}
\item
$\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 \PMlinkname{product}{DirectProductOfAlgebras} $A\times A$.
\item
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 \PMlinkname{join of the underlying equivalence relations}{PartitionsFormALattice}. This join corresponds to the subalgebra (of $A\times A$) generated by the union of the underlying sets of the congruences. The \emph{lattice of congruences} on $A$ is denoted by $\operatorname{Con}(A)$.
\item \textbf{(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 \pmod {\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) \pmod {\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) \pmod {\mathfrak{C}_B}$ as well. $\mathfrak{C}_B$ is the congruence \emph{restricted} to $B$.
\item \textbf{(extension)}
Again, let $\mathfrak{C}$ be a congruence on $A$ and $B$ a subalgebra of $A$. Define $B^{\mathfrak{C}}$ by $\lbrace a\in A\mid (a,b)\in \mathfrak{C}\mbox{ and }b\in B\rbrace$. In other words, $a\in B^{\mathfrak{C}}$ iff $a \equiv b \pmod {\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 \pmod {\mathfrak{C}}$, so $\omega_A(a_1,\ldots,a_n)\equiv \omega_A(b_1,\ldots,b_n) \pmod {\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 \emph{extension} of $B$ by $\mathfrak{C}$.
\item
Let $B$ be a subset of $A\times A$. The smallest congruence $\mathfrak{C}$ on $A$ such that $a\equiv b\pmod {\mathfrak{C}}$ for all $a,b\in B$ is called the \emph{congruence generated by} $B$. $\mathfrak{C}$ is often written $\langle B\rangle$. When $B$ is a singleton $\lbrace (a,b)\rbrace$, then we call $\langle B\rangle$ a \emph{principal congruence}, and denote it by $\langle (a,b)\rangle$.
\end{itemize}
\subsubsection*{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\pmod {\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 well-defined operator on $A/\mathfrak{C}$. The $O$-algebra thus constructed is called the \emph{quotient algebra} of $A$ over $\mathfrak{C}$.
\textbf{Remark}. The bracket $[\cdot]:A\to A/\mathfrak{C}$ is in fact an epimorphism, with \PMlinkname{kernel}{KernelOfAHomomorphismBetweenAlgebraicSystems} $\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}$.
\begin{thebibliography}{7}
\bibitem{gg} G. Gr\"{a}tzer: {\em Universal Algebra}, 2nd Edition, Springer, New York (1978).
\end{thebibliography}