| Version 5 |
Version 4 |
| \textbf{Dilworth's Theorem}. If $P$ is a poset with width $w<\infty$, then $w$ is also the smallest integer such that $P$ can be written as the union of $w$ chains. |
\textbf{Dilworth's Theorem}. If $P$ is a poset with width $w$, then |
|
there is a collection, with cardinality $w$, of chains in $P$, whose |
|
union is $P$. Furthermore, no smaller collection (cardinality $< w$) |
|
of chains exists whose union is $P$. |
|
|
| \textbf{Remark}. If $w$ is infinite, then statement is not true. The proof of Dilworth's Theorem and its couterexample in the infinite case can be found in the reference below. |
Before proving this, we make a few remarks and observations: |
|
\begin{enumerate} |
|
\item singleton subsets of $P$ are both chains and antichains. |
|
\item a maximal chain is a chain which is not properly contained in another chain. Therefore, it is not necessary that a maximal chain is a chain with the largest cardinality in $P$. |
|
\item Maximal antichains are dually defined. |
|
\item Any chain can be lengthened to a maximal chain; any antichain can be enlarged to a maximal antichain. |
|
\end{enumerate} |
|
|
| \begin{thebibliography}{6} |
\begin{proof} |
| \bibitem{jbn} J.B. Nation, ``Lattice Theory", \PMlinkexternal{http://www.math.hawaii.edu/~jb/lat1-6.pdf}{http://www.math.hawaii.edu/~jb/lat1-6.pdf} |
If $P=\varnothing$, then $w=0$, and the theorem is vacuously true. |
| \end{thebibliography} |
So suppose $P$ is non-empty. First, note that it is possible to |
|
write $P$ as the union of chains (take all singleton subsets of |
|
$P$). Among all collections of chains of $P$ whose unions are $P$, |
|
take one with the smallest cardinality, and write |
|
$$P=\bigcup_{i\in I} C_i,$$ where each $C_i$ is a chain in $P$, and $i$ in some index set $I$. |
|
Next, remove any $C_i$ that can be absorbed into the rest of the |
|
chains: |
|
$$C_i\subseteq \bigcup_{j\neq i} C_j.$$ Note that if the |
|
cardinality of the collection is finite, this step would not have |
|
been necessary. We now have a collection of chains with the |
|
properties |
|
\begin{enumerate} |
|
\item their union is $P$, and |
|
\item no chain is a subset of the union of the rest. |
|
\end{enumerate} |
|
We can enlarge each $C_i$ to a maximal chain. Of course, the |
|
resulting collection $\mathcal{C}$ of maximal chains would still |
|
have the two properties just mentioned. We might as well call each |
|
$C_i$ maximal. Now, each $C_i$ contains an element $a_i$ such that |
|
$a_i\notin \cup_{j\neq i} C_j$. Then $A=\lbrace a_i \mid i\in |
|
I\rbrace$ is an antichain. For if, say, $a_i\le a_j$, then $a_i\in |
|
C_j$ as $C_j$ is maximal. But this contradicts the fact that |
|
$a_i\notin C_j$. $\mid\mathcal{C}|=|A| \le w$, the width of $P$. |
|
|
|
Next, among all antichains of $P$ (as remarked earlier: antichains |
|
exist in $P$), pick one with cardinality $w$, and call it $B$. |
|
Each $b\in B$ is in some maximal chain $C_i\in\mathcal{C}$. This |
|
implies that there is a function $f$ from $B$ to $\mathcal{C}$, by |
|
Axiom of Choice. Furthermore, no two elements of $B$ can be in the |
|
same $C_i$ (or else they would be comparable). This says that $f$ is one-to-one. As a result, we have |
|
$w\le\mid\mathcal{C}|$. Then, by Schroeder-Bernstein Theorem, |
|
$w=\mid \mathcal{C}|$. |
|
\end{proof} |
|
|
|
\textbf{Remark}. If $P$ is finite, then the proof is simpler, invoking only the Pigeonhole principle. |
