# partitions form a lattice

Let $S$ be a set. Let $\operatorname{Part}(S)$ be the set of all partitions on $S$. Since each partition is a cover of $S$, $\operatorname{Part}(S)$ is partially ordered by covering refinement relation, so that $P_{1}\preceq P_{2}$ if for every $a\in P_{1}$, there is a $b\in P_{2}$ such that $a\subseteq b$. We say that a partition $P$ is finer than a partition $Q$ if $P\preceq Q$, and coarser than $Q$ if $Q\preceq P$.

###### Proposition 1.

$\operatorname{Part}(S)$ is a complete lattice

###### Proof.

For any set $\mathcal{P}$ of partitions $P_{i}$ of $S$, the intersection $\bigcap\mathcal{P}$ is a partition of $S$. Take the meet of $P_{i}$ to be this intersection. Next, let $\mathcal{Q}$ be the set of those partitions of $S$ such that each $Q\in\mathcal{Q}$ is coarser than each $P_{i}$. This set is non-empty because $S\times S\in\mathcal{Q}$. Take the meet $P^{\prime}$ of all these partitions which is again coarser than all partitions $P_{i}$. Define the join of $P_{i}$ to be $P^{\prime}$ and the proof is complete. ∎

Remarks.

• The top element of $\operatorname{Part}(S)$ is $S\times S$ and the bottom is the diagonal relation on $S$.

• Correspondingly, the partition lattice of $S$ also defines the lattice of equivalence relations $\Delta$ on $S$.

• Given a family $\{E_{i}\mid i\in I\}$ of equvialence relations on $S$, we can explicitly describe the join $E:=\bigvee E_{i}$ of $E_{i}$, as follows: $a\equiv b\pmod{E}$ iff there is a finite sequence $a=c_{1},\ldots,c_{n}=b$ such that

 $\displaystyle c_{k}\equiv c_{k+1}\pmod{E_{i(k)}}\qquad\mbox{ for }k=1,\ldots,n% -1.$ (1)

It is easy to see this definition makes $E$ an equivalence relation. To see that $E$ is the supremum of the $E_{i}$, first note that each $E_{i}\leq E$. Suppose now $F$ is an equivalence relation on $S$ such that $E_{i}\leq F$ and $a\equiv b\pmod{E}$. Then we get a finite sequence $c_{k}$ as described by (1) above, so $c_{k}\equiv c_{k+1}\pmod{F}$ for each $k\in\{1,\ldots,n-1\}$. Hence $a\equiv b\pmod{F}$ also.

Title partitions form a lattice PartitionsFormALattice 2013-03-22 16:45:22 2013-03-22 16:45:22 CWoo (3771) CWoo (3771) 6 CWoo (3771) Derivation msc 06B20 lattice of equivalence relations