You are here
Homecongruence lattice
Primary tabs
congruence lattice
Theorem 1.
The set $\operatorname{Con}(A)$ of all congruences on an algebraic system $A$ is a complete lattice that is a sublattice (called the congruence lattice of $A$) of the lattice of equivalence relations on $A$.
Proof.
It is not hard to see that $\operatorname{Con}(A)$ is a topped intersection structure. As a result, $\operatorname{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:

$\mathbf{n}:=\{1,\ldots,n\}$;

for any $a_{k},b_{k}\in A$ and $\Theta_{k}\in\operatorname{Con}(A)$, where $k\in\mathbf{n}$, we mean
$(a_{1},\ldots,a_{n})\equiv(b_{1},\ldots,b_{n})\;\;(\mathop{{\rm mod}}(\Theta_{% 1},\ldots,\Theta_{n}))$ by $a_{k}\equiv b_{k}\;\;(\mathop{{\rm mod}}\Theta_{k})$, for each $k\in\mathbf{n}$;

$(a_{1},\ldots,a_{n})\equiv(b_{1},\ldots,b_{n})\;\;(\mathop{{\rm mod}}\Theta)$ means $a_{k}\equiv b_{k}\;\;(\mathop{{\rm mod}}\Theta)$, for each $k\in\mathbf{n}$;

Finally, when $c_{k}\equiv c_{{k+1}}\;\;(\mathop{{\rm mod}}\Theta_{k})$, where $k\in\mathbf{n1}$, we write
$c_{1}\stackrel{\Theta_{1}}{\equiv}c_{2}\stackrel{\Theta_{2}}{\equiv}\cdots% \stackrel{\Theta_{{n1}}}{\equiv}c_{n}.$ Let us call this an equivalence chain (of length $n$).
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})\;\;(\mathop{{\rm mod}}\Theta)$. We want to show that $\omega(a_{1},\ldots,a_{n})\equiv\omega(b_{1},\ldots,b_{n})\;\;(\mathop{{\rm mod% }}\Theta)$.
The proof now breaks up into two main steps:
Step 1.
For each $i\in\mathbf{n}$, $a_{i}\equiv b_{i}\;\;(\mathop{{\rm mod}}\Theta)$ means we have a finite equivalence chain
$a_{i}=c_{1}\stackrel{F_{1}}{\equiv}c_{2}\stackrel{F_{2}}{\equiv}\cdots% \stackrel{F_{{p1}}}{\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.
To see this, take the first two pairs of congruent elements $a_{1}\equiv b_{1}\;\;(\mathop{{\rm mod}}\Theta)$ and $a_{2}\equiv b_{2}\;\;(\mathop{{\rm mod}}\Theta)$, and expand them into two finite equivalence chains
1. $a_{1}=c_{1}\stackrel{F_{1}}{\equiv}c_{2}\stackrel{F_{2}}{\equiv}\cdots% \stackrel{F_{{p1}}}{\equiv}c_{p}=b_{1}$, and
2. $a_{2}=d_{1}\stackrel{G_{1}}{\equiv}d_{2}\stackrel{G_{2}}{\equiv}\cdots% \stackrel{G_{{q1}}}{\equiv}d_{q}=b_{2}$,
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_{{q1}}}{\equiv}d_{q% }\stackrel{G_{q}}{\equiv}d_{{q+1}}\stackrel{G_{{q+1}}}{\equiv}\cdots\stackrel{% G_{{p1}}}{\equiv}d_{p},$ 
where $G_{{q1}}=G_{q}=\cdots=G_{{p1}}$ 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” 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$.
Step 2.
Complete the proof.
Instead of writing all $n$ chains, let us use our notational device, and we have the following single 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 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 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}})\;\;(\mathop{{\rm mod}}\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})\;\;(\mathop{{\rm mod% }}\Theta)$, completing the proof. ∎
Remarks.

Furthermore, it can be shown that $\operatorname{Con}(A)$ is an algebraic lattice. The compact elements of $\operatorname{Con}(A)$ are finite joins of socalled principal congruences.

Conversely, it can be shown (by Grätzer) that every algebraic lattice is isomorphic to the congruence lattice of some algebraic system.

If $A$ is a lattice, then $\operatorname{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.
References
 1 G. Grätzer: Universal Algebra, 2nd Edition, Springer, New York (1978).
 2 F. Wehrung: A Solution to Dilworth’s Congruence Lattice Problem, (2005).
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
 Corrections