You are here
Homepartitions form a lattice
Primary tabs
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 nonempty 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\;\;(\mathop{{\rm mod}}E)$ iff there is a finite sequence $a=c_{1},\ldots,c_{n}=b$ such that
$\displaystyle c_{k}\equiv c_{{k+1}}\;\;(\mathop{{\rm mod}}E_{{i(k)}})\qquad% \mbox{ for }k=1,\ldots,n1.$ (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\;\;(\mathop{{\rm mod}}E)$. Then we get a finite sequence $c_{k}$ as described by (1) above, so $c_{k}\equiv c_{{k+1}}\;\;(\mathop{{\rm mod}}F)$ for each $k\in\{1,\ldots,n1\}$. Hence $a\equiv b\;\;(\mathop{{\rm mod}}F)$ also.
Mathematics Subject Classification
06B20 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