It is not hard to see that is a topped intersection structure. As a result, is a complete lattice. Since it is also a subset of the lattice of equivalence relations on , the only remaining item to show is that it is a sublattice of . In other words, we need to show that if is a family of congruence relations on , so is .
For convenience, let us introduce some notational devices:
for any and , where , we mean
by , for each ;
means , for each ;
Finally, when , where , we write
Let us call this an (of ).
Back to the proof. Let be an -ary operator on and . We want to show that .
The proof now breaks up into two main steps:
For each , means we have a finite
where each is a congruence in , and each . Now the lengths of the sequences may vary by . The idea is to show that we can in fact pick the sequences so that they all have the same length.
where and . If , we may lengthen the second chain so it has the same length as the first one:
where and .
The above argument and an induction step on show that we can indeed make all the “expanded” the same length. As a result, without loss of generality, we assume that all the expanded chains have the same length, say .
Complete the proof.
Instead of writing all chains, let us use our notational device, and we have the following single (again, we may write it in this fashion because all chains are now assumed to have the same finite length of ):
where each , each , with , and that and .
Look at the first congruence pair . This can be expanded into an of length as follows:
The idea is to replace the coordinates one at a time, in sequence, from the first to the last, until all coordinates are completely replaced from to .
Now, since each is a congruence, apply to each -tuple to get a new
But this chain implies that . So what we have shown is that the images of the first congruence pair are congruent modulo . But this process can be easily applied to subsequent congruence pairs, so that we end up with
As is an equivalence relation, , completing the proof. ∎
|Date of creation||2013-03-22 17:06:31|
|Last modified on||2013-03-22 17:06:31|
|Last modified by||CWoo (3771)|
|Defines||lattice of congruences|