forked from planetmath/08_General_algebraic_systems
-
Notifications
You must be signed in to change notification settings - Fork 0
/
08A30-CongruenceLattice.tex
115 lines (102 loc) · 7.47 KB
/
08A30-CongruenceLattice.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{CongruenceLattice}
\pmcreated{2013-03-22 17:06:31}
\pmmodified{2013-03-22 17:06:31}
\pmowner{CWoo}{3771}
\pmmodifier{CWoo}{3771}
\pmtitle{congruence lattice}
\pmrecord{8}{39407}
\pmprivacy{1}
\pmauthor{CWoo}{3771}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{08A30}
\pmdefines{lattice of congruences}
\endmetadata
\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% 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}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newtheorem{stp}{Step}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}
\newcommand{\Con}[1]{\operatorname{Con}(#1)}
\begin{document}
\begin{thm} The set $\operatorname{Con}(A)$ of all congruences on an algebraic system $A$ is a complete lattice that is a sublattice (called the \emph{congruence lattice} of $A$) of the lattice of equivalence relations on $A$.
\end{thm}
\begin{proof}
It is not hard to see that $\Con A$ is a topped intersection structure. As a result, $\Con A$ is a complete lattice. Since it is also a subset of the lattice $E(A)$ of equivalence relations on $A$, the only remaining item to show is that it is a sublattice of $E(A)$. In other words, we need to show that if $\mathcal{C}$ is a family of congruence relations on $A$, so is $\Theta:=\bigvee \mathcal{C}$.
For convenience, let us introduce some notational devices:
\begin{itemize}
\item $\mathbf{n}:=\lbrace 1,\ldots,n\rbrace$;
\item for any $a_k,b_k\in A$ and $\Theta_k\in\Con A$, where $k\in \mathbf{n}$, we mean $$(a_1,\ldots,a_n)\equiv (b_1,\ldots, b_n)\pmod{(\Theta_1,\ldots,\Theta_n)}$$ by $a_k\equiv b_k\pmod {\Theta_k}$, for each $k\in \mathbf{n}$;
\item $(a_1,\ldots,a_n)\equiv (b_1,\ldots, b_n)\pmod{\Theta}$ means $a_k\equiv b_k\pmod \Theta$, for each $k\in \mathbf{n}$;
\item Finally, when $c_k\equiv c_{k+1}\pmod {\Theta_k}$, where $k\in \mathbf{n-1}$, we write $$c_1\stackrel{\Theta_1}{\equiv} c_2\stackrel{\Theta_2}{\equiv} \cdots \stackrel{\Theta_{n-1}}{\equiv }c_n.$$
Let us call this an \PMlinkescapetext{\emph{equivalence chain}} (of \PMlinkescapetext{length} $n$).
\end{itemize}
Back to the proof. Let $\omega$ be an $n$-ary operator on $A$ and $(a_1,\ldots,a_n)\equiv (b_1,\ldots,b_n)\pmod \Theta$. We want to show that $\omega(a_1,\ldots,a_n)\equiv \omega(b_1,\ldots,b_n)\pmod \Theta$.
The proof now breaks up into two main steps:
\begin{stp} For each $i\in \mathbf{n}$, $a_i\equiv b_i\pmod \Theta$ means we have a finite \PMlinkescapetext{equivalence chain}
$$a_i=c_1\stackrel{F_1}{\equiv} c_2\stackrel{F_2}{\equiv} \cdots \stackrel{F_{p-1}}{\equiv }c_p=b_i,$$
where each $F_i$ is a congruence in $\mathcal{C}$, and each $c_i\in A$. Now the lengths of the sequences may vary by $i$. The idea is to show that we can in fact pick the sequences so that they all have the same length. \end{stp}
To see this, take the first two pairs of congruent elements $a_1\equiv b_1\pmod \Theta$ and $a_2\equiv b_2\pmod \Theta$, and expand them into two finite \PMlinkescapetext{equivalence chains}
\begin{enumerate}
\item $a_1=c_1\stackrel{F_1}{\equiv} c_2\stackrel{F_2}{\equiv} \cdots \stackrel{F_{p-1}}{\equiv }c_p=b_1$, and
\item $a_2=d_1\stackrel{G_1}{\equiv} d_2\stackrel{G_2}{\equiv} \cdots \stackrel{G_{q-1}}{\equiv }d_q=b_2$,
\end{enumerate}
where $c_i,d_j\in A$ and $F_i,G_j\in \mathcal{C}$. If $q<p$, we may lengthen the second chain so it has the same length as the first one:
$$a_2=d_1\stackrel{G_1}{\equiv} d_2 \cdots \stackrel{G_{q-1}}{\equiv }d_q \stackrel{G_q}{\equiv} d_{q+1}\stackrel{G_{q+1}}{\equiv} \cdots \stackrel{G_{p-1}}{\equiv }d_p,$$
where $G_{q-1}=G_q=\cdots =G_{p-1}$ and $d_q=\cdots=d_p=b$.
The above argument and an induction step on $n$ show that we can indeed make all the ``expanded'' \PMlinkescapetext{equivalence chains} the same length. As a result, without loss of generality, we assume that all the expanded chains have the same length, say $r+1$.
\begin{stp} Complete the proof. \end{stp}
Instead of writing all $n$ chains, let us use our notational device, and we have the following \emph{single} \PMlinkescapetext{equivalence chain} (again, we may write it in this fashion because all chains are now assumed to have the same finite length of $r+1$):
$$\xymatrix{
(c_{11},\ldots,c_{1n})\ar@3{-}[rr]^-{(F_{11},\ldots,F_{1n})} && (c_{21},\ldots,c_{2n})\ar@3{-}[rr]^-{(F_{21},\ldots,F_{2n})} && \cdots\ar@3{-}[rr]^-{(F_{r1},\ldots,F_{rn})} && (c_{r+1,1},\ldots,c_{r+1,n})
}$$
where each $c_{ij}\in A$, each $F_{ij}\in\mathcal{C}$, with $(i,j)\in (\mathbf{r+1})\times \mathbf{n}$, and that $(a_1,\ldots,a_n)=(c_{11},\ldots,c_{1n})$ and $(c_{r+1,1},\ldots,c_{r+1,n})=(b_1,\ldots,b_n)$.
Look at the first congruence pair $\xymatrix{(c_{11},\ldots,c_{1n})\ar@3{-}[rr]^-{(F_{11},\ldots,F_{1n})} && (c_{21},\ldots,c_{2n})}$. This can be expanded into an \PMlinkescapetext{equivalence chain} of length $n$ as follows:
$$\xymatrix{
(c_{11},c_{12},\ldots,c_{1n})\ar@3{-}[r]^-{F_{11}} & (c_{21},c_{12},\ldots,c_{1n})\ar@3{-}[r]^-{F_{12}} & \cdots \ar@3{-}[r]^-{F_{1n}} & (c_{21},c_{22},\ldots,c_{2n})
}$$
The idea is to replace the coordinates one at a time, in sequence, from the first to the last, until all $n$ coordinates are completely replaced from $(c_{11},\ldots, c_{1n})$ to $(c_{21},\ldots,c_{2n})$.
Now, since each $F_{1j}$ is a congruence, apply $\omega$ to each $n$-tuple to get a new \PMlinkescapetext{equivalence chain}
$$\xymatrix{
\omega(c_{11},c_{12},\ldots,c_{1n})\ar@3{-}[r]^-{F_{11}} & \omega(c_{21},c_{12},\ldots,c_{1n})\ar@3{-}[r]^-{F_{12}} & \cdots \ar@3{-}[r]^-{F_{1n}} & \omega(c_{21},c_{22},\ldots,c_{2n})
}.$$
But this chain implies that $\omega(a_1,\ldots,a_n)=\omega(c_{11},\ldots,c_{in})\equiv \omega(c_{21},\ldots,c_{2n})\pmod \Theta$. So what we have shown is that the images of the first congruence pair are congruent modulo $\Theta$. But this process can be easily applied to subsequent congruence pairs, so that we end up with
$$\xymatrix{
\omega(a_1,\ldots,a_2)\ar@3{-}[r]^-{\Theta} & \omega(c_{21},\ldots,c_{2n})\ar@3{-}[r]^-{\Theta} & \cdots \ar@3{-}[r]^-{\Theta} & \omega(b_1,\ldots,b_n)
}.$$ As $\Theta$ is an equivalence relation, $\omega(a_1,\ldots,a_2)\equiv \omega(b_1,\ldots,b_n)\pmod \Theta$, completing the proof.
\end{proof}
\textbf{Remarks}.
\begin{itemize}
\item
Furthermore, it can be shown that $\Con A$ is an algebraic lattice. The compact elements of $\Con A$ are finite joins of so-called \emph{principal congruences}.
\item
Conversely, it can be shown (by Gr\"{a}tzer) that every algebraic lattice is isomorphic to the congruence lattice of some algebraic system.
\item
If $A$ is a lattice, then $\Con A$ is distributive. The converse statement, that every distributive algebraic lattice is isomorphic to a congruence lattice, has recently been proven to be false by F. Wehrung.
\end{itemize}
\begin{thebibliography}{6}
\bibitem{gg} G. Gr\"{a}tzer: {\em Universal Algebra}, 2nd Edition, Springer, New York (1978).
\bibitem{fw} F. Wehrung: {\em \PMlinkexternal{A Solution to Dilworth's Congruence Lattice Problem}{http://hal.archives-ouvertes.fr/docs/00/11/93/14/PDF/CLP.pdf}}, (2005).
\end{thebibliography}
%%%%%
%%%%%
\end{document}