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