Mirsky's theorem

Remarks

A chain meets an antichain in at most one element, so a chain with $h$ elements needs $h$ different antichains to cover it. For the other half, let $f(x)$ be the largest number of elements of a chain whose greatest element is $x$. If $x < y$, then a chain ending at $x$ extends by $y$, so $f(x) < f(y)$. Thus each level set $\set{x \in P : f(x) = k}$ is an antichain, and the values of $f$ are $1, \ldots, h$. Example: in the divisors of $12$ ordered by divisibility, the chain $1, 2, 4, 12$ has $4$ elements, and the levels $\set{1}$, $\set{2, 3}$, $\set{4, 6}$, $\set{12}$ are $4$ antichains that cover the set. The same proof works for an infinite partially ordered set of finite height. The theorem is the dual of Dilworth's theorem, which exchanges the roles of chains and antichains, but its proof is much easier.

Going deeper

For a student

The proof gives an explicit partition: put each element into the level given by the longest chain that ends at it. This is the layering used in scheduling and in drawing directed acyclic graphs. In the language of graphs, the comparability graph of a poset has chromatic number equal to its clique number. The same holds for each induced subgraph, so comparability graphs are perfect. Together with Dilworth's theorem it gives the Erdős–Szekeres theorem on monotone subsequences.