Dilworth's Theorem - Inductive Proof

Inductive Proof

The following proof by induction on the size of the partially ordered set is based on that of Galvin (1994).

Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of .

By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size . Clearly, for . For, let be the maximal element in that belongs to an antichain of size in, and set . We claim that is an antichain. Let be an antichain of size that contains . Fix arbitrary distinct indices and . Then . Let . Then, by the definition of . This implies that, since . By interchanging the roles of and in this argument we also have . This verifies that is an antichain.

We now return to . Suppose first that for some . Let be the chain . Then by the choice of, does not have an antichain of size . Induction then implies that can be covered by disjoint chains since is an antichain of size in . Thus, can be covered by disjoint chains, as required. Next, if for each, then is an antichain of size in (since is maximal in ). Now can be covered by the chains, completing the proof.