\documentstyle[11pt,amssymb,twoside]{article}
\input{../macros-course}

\addtolength{\topmargin}{-.8in}
\setlength{\textheight}{9in}
\pagestyle{empty}
\setlength{\parskip}{\medskipamount}
%\renewcommand{\text}[1]{\;\mbox{ #1 }\;}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\thm[Dilworth's Theorem]
\noindent
{\bf Dilworth's Theorem} \ 
{\em For any finite poset $P$, if the largest antichain in $P$ has size~$n$, 
then $P$ is the union of $n$ chains.}
%\ethm
\bigskip
\pf
By induction on $|P|$.
If $|P|=1$ then clearly the $P$ is trivially both an antichain 
and a chain of size 1.

Let $C$ be a maximal chain in $P$.  (A chain is {\em maximal\/} if 
for all $x\not\in C$, $C\cup \{x\}$ is no longer a chain.)
If $P-C$ has no antichain of length $n$, then we are done by 
induction:  $P-C$ is a poset of smaller size in which the largest
antichain has size $n-1$ and therefore by the induction hypothesis
is the union of $n-1$ chains, making $P$ a union of $n$ chains
(strictly speaking, this proof is 
actually a double induction on $|P|$ and $n$).

Suppose instead that $P-C$ has an antichain $A=\{a_1,\ldots, a_n\}$.
Define the ``upper half'' of $P$ as 
\[
P^+ = \{ x\in P \,\mid\, a_i \preceq x \,\text{ for some } a_i\in A\}.
\]
Define the ``lower half'' $P^-$ analogously,
$P^- = \{ x\in P \,\mid\, x \preceq a_i \,\text{ for some } a_i\in A\}$,
and note that
\begin{enumerate}
\item $A\subseteq P^+$ and $A\subseteq P^-$ by reflexivity of $\preceq$.
\item $P=P^+\cup P^-$:  Since $A$ is maximal, any $x\not\in A$
is either greater than some element in $A$ or less than some element in $A$.
\item $P^+\subsetneq P$ and $P^-\subsetneq P$:  Since $C$ is maximal,
there is no element of $P$ above the maximum element $c$ of $C$, so 
$c\not\in P^-$; similarly, the minimum element of $C$ is not in $P^+$.
\end{enumerate}
Since $P^+$ and $P^-$ are posets of smaller size in which the largest
antichain has size\footnote{Note that when we write $P-X$, 
we mean the poset containing
the elements $P-X$, with the same relations among these elements.
In particular, if two elements in $P-X$ are related in $P$, 
then they are still related in $P-X$.  It follows that if the largest
antichain in $P$ has size $n$, then the largest antichain in $P-X$
has size at most $n$.  This fact is necessary in order to apply
the inductive hypothesis.} 
$n$, by the induction hypothesis they are each the union of $n$ chains:
\[ 
P^+ = \bigcup_{i=1}^n C^+_i \quad \text{ and }\quad
P^- = \bigcup_{i=1}^n C^-_i.
\]
Since the $a_i$ must clearly be in different chains, index the chains
so $a_i\in C^+_i$ and $a_i\in C^-_i$.

The proof will be complete once we show that for each $i$, 
$a_i$ is the minimum element of $C^+_i$ and the maximum element of $C^-_i$.
For then we have 
\[
\underbrace{x_1 \preceq x_2 \preceq \cdots x_k \preceq \rule[-6pt]{0pt}{11pt}
a_i}_{\textstyle C^-_i}
\hspace*{-4mm}
\overbrace{\makebox[4mm]{}\rule{0pt}{11pt} \preceq y_1 \preceq \cdots 
\preceq y_l}^{\textstyle C^+_i}
\]
which is clearly a chain, and thus $P$ is the union of $n$ chains.
We argue that $a_i$ is the minimum element of $C^+_i$ by contradiction:
if not, then $a_i\preceq x$ for some $x\in C^+_i$, but because $x\in P^+$, 
we have $x\preceq a_j$ for some $j$, which by transitivity implies
$a_i\preceq a_j$, which is false because $A$ is an antichain.
A similar argument shows that $a_i$ is the maximum element of $C^-_i$.
This completes the proof.
\end{proof}

\end{document}



