08A30-CongruenceRelationOnAnAlgebraicSystem.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{CongruenceRelationOnAnAlgebraicSystem}
\pmcreated{2013-03-22 16:26:23}
\pmmodified{2013-03-22 16:26:23}
\pmowner{CWoo}{3771}
\pmmodifier{CWoo}{3771}
\pmtitle{congruence relation on an algebraic system}
\pmrecord{33}{38594}
\pmprivacy{1}
\pmauthor{CWoo}{3771}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{08A30}
\pmrelated{Congruence3}
\pmrelated{Congruence2}
\pmrelated{CongruenceInAlgebraicNumberField}
\pmrelated{PolynomialCongruence}
\pmrelated{QuotientCategory}
\pmrelated{CategoryOfAdditiveFractions}
\pmdefines{congruence}
\pmdefines{congruence relation}
\pmdefines{quotient algebra}
\pmdefines{proper congruence}
\pmdefines{trivial congruence}
\pmdefines{non-trivial congruence}
\pmdefines{congruence restricted to a subalgebra}
\pmdefines{extension of a subalgebra by a congruence}
\pmdefines{principal congruence}
\pmdefines{congruence generated by}

\endmetadata

\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}
\begin{document}
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}
%%%%%
%%%%%
\end{document}