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
Canonical name	PartitionsFormALattice
Date of creation	2013-03-22 16:45:22
Last modified on	2013-03-22 16:45:22
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	6
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 06B20
Defines	lattice of equivalence relations