Dilworth's Theorem - Dual of Dilworth's Theorem (Mirsky's Theorem)

Dual of Dilworth's Theorem (Mirsky's Theorem)

A dual of Dilworth's theorem states that the size of the largest chain in a partial order (if finite) equals the smallest number of antichains into which the order may be partitioned (Mirsky 1971). The proof of this is much simpler than the proof of Dilworth's theorem itself: for any element x, consider the chains that have x as their largest element, and let N(x) denote the size of the largest of these x-maximal chains. Then each set N−1(i), consisting of elements that have equal values of N, is an antichain, and these antichains partition the partial order into a number of antichains equal to the size of the largest chain.