partitions form a lattice
Let be a set. Let be the set of all partitions on . Since each partition is a cover of , is partially ordered by covering refinement relation, so that if for every , there is a such that . We say that a partition is finer than a partition if , and coarser than if .
is a complete lattice
For any set of partitions of , the intersection is a partition of . Take the meet of to be this intersection. Next, let be the set of those partitions of such that each is coarser than each . This set is non-empty because . Take the meet of all these partitions which is again coarser than all partitions . Define the join of to be and the proof is complete. ∎
The top element of is and the bottom is the diagonal relation on .
Given a family of equvialence relations on , we can explicitly describe the join of , as follows: iff there is a finite sequence such that
It is easy to see this definition makes an equivalence relation. To see that is the supremum of the , first note that each . Suppose now is an equivalence relation on such that and . Then we get a finite sequence as described by (1) above, so for each . Hence also.
|Title||partitions form a lattice|
|Date of creation||2013-03-22 16:45:22|
|Last modified on||2013-03-22 16:45:22|
|Last modified by||CWoo (3771)|
|Defines||lattice of equivalence relations|