| Version 3 |
Version 2 |
| \textbf{Dilworth's Theorem}. If $P$ is a poset with width $w$, then |
\textbf{Dilworth's Theorem}. If $P$ is a non-empty finite |
| there is a collection, with cardinality $w$, of chains in $P$, whose |
poset, then the width of $P$ is the minimum number of chains in $P$ |
| union is $P$. Furthermore, no smaller collection (cardinality $< w$) |
whose union is $P$. |
| of chains exists whose union is $P$. |
|
|
|
| \begin{enumerate} |
\begin{enumerate} |
| \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 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 Any chain can be lengthened to a maximal chain; any antichain can be enlarged to a maximal antichain. |
\item Any chain can be lengthened to a maximal chain; any antichain can be enlarged to a maximal antichain. |
| \end{enumerate} |
\end{enumerate} |
|
|
| \begin{proof} |
\begin{proof} First, note that it is possible to write $P$ as the |
| If $P=\varnothing$, then $w=0$, and the theorem is vacuously true. |
union of chains (take all singleton subsets of $P$). Among all |
| So suppose $P$ is non-empty. First, note that it is possible to |
collections of chains of $P$ whose unions are $P$, take one with the |
| write $P$ as the union of chains (take all singleton subsets of |
least number of chains, so we can write |
| $P$). Among all collections of chains of $P$ whose unions are $P$, |
$$P=C_1\cup\cdots C_m,$$ |
| take one with the smallest cardinality, and write |
where each $C_i$ is a chain in $P$. Note that each $C_i$ has the |
| $$P=\bigcup_{i\in I} C_i,$$ where each $C_i$ is a chain in $P$, and $i$ in some index set $I$. |
following property |
| Next, remove any $C_i$ that can be absorbed into the rest of the |
$$C_i\nsubseteq \bigcup_{j\neq i} C_j,$$ |
| chains: |
for otherwise $\lbrace C_j\mid j\neq i\rbrace$ would form a |
| $$C_i\subseteq \bigcup_{j\neq i} C_j.$$ Note that if the |
collection of chains whose union is $P$. We can enlarge each $C_i$ |
| cardinality of the collection is finite, this step would not have |
to a maximal chain. Of course, the resulting collection of maximal |
| been necessary. We now have a collection of chains with the |
chains would still have the properties that their union is $P$ and |
| properties |
no chain is a subset of the union of the rest. We might as well |
| \begin{enumerate} |
call each $C_i$ maximal. Now, there is $a_i\in C_i$ such that |
| \item their union is $P$, and |
$a_i\notin \cup_{j\neq i} C_j$. Then $A=\lbrace a_1,\ldots, |
| \item no chain is a subset of the union of the rest. |
a_m\rbrace$ is an antichain. For if, say, $a_1\le a_2$, then |
| \end{enumerate} |
$a_1\in C_2$ since $C_2$ is maximal, which is contrary to the choice |
| We can enlarge each $C_i$ to a maximal chain. Of course, the |
of $a_1$. |
| 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 |
Next, among all antichains of $P$ (as remarked earlier: antichains |
|
exist in $P$), pick one, call it $B$, whose cardinality is $w$.
|
exist in $P$), pick one with the largest number of elements $B=
|
| Each $b\in B$ is in some maximal chain $C_i\in\mathcal{C}$. This |
\lbrace b_1,\ldots,b_r\rbrace$. So $m\le r=$ width of $P$. Since $P$ is the |
| implies that there is a function $f$ from $B$ to $\mathcal{C}$, by |
union of the $C_j$, each $b_i$ ($i=1,\ldots,r$) is an element of |
| Axiom of Choice. Furthermore, no two elements of $B$ can be in the |
some $C_j$ ($j=1,\ldots,m$). Furthermore, no more than one $b_i$ |
| same $C_i$. This says that $f$ is one-to-one. As a result, we have |
can be in the same $C_j$, for otherwise they would be comparable. |
| $w\le\mid\mathcal{C}|$. Then, by Schroeder-Bernstein Theorem, |
This implies that the number of $b_i$'s can't exceed the number of |
|
$w=\mid \mathcal{C}|$.
|
$C_j$'s (Pigeonhole principle), so $r\le m$. This shows that $r=m$.
|
| \end{proof} |
\end{proof} |
|
|
| \textbf{Remark}. If $P$ is finite, then the proof is simpler, invoking only the Pigeonhole principle. |
|
