### Corrected proof of Dilworth's lemma

In any partial order on a set $P$ of $n\geq sr+1$ elements, there
exists a chain of length $s+1$ or an antichain of size $r+1$.

**Proof:**
Let $A_i$ be the set of points $x\in P$ such that the *longest* chain
ending in $x$ has $i$ elements. The sets
$A_i$ are clearly disjoint.
Suppose that there is no chain of length $s+1$. Then every $x\in P$ belongs
to some of the $s$ sets $A_1,\ldots,A_s$. We thus have a partition of $P$
into at most $s$ blocks $A_i$. By the pigeonhole principle, at least one of the blocks
$A_i$ must have size $|A|\geq r+1$.
So, it remains to verify that $A_i$ is an antichain. For the sake of contradiction,
assume that $A_i$ contains some two elements $x$ and $y$ such that $x < y$.
Then we can prolong the longest chain to $x$ to a longer chain to $y$,
meaning that $x$ and $y$ cannot both belong to $A_i$, a contradiction. Q.E.D.

Return to
the
home page of the 2nd edition