Dilworth's theorem

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. Dilworth's theorem states that there exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A. When this occurs, A must be the largest antichain in the order, for any antichain can have at most one element from each member of P. Similarly, P must be the smallest family of chains into which the order can be partitioned, for any partition into chains must have at least one chain per element of A. The width of the partial order is defined as the common size of A and P.

An equivalent way of stating Dilworth's theorem is that, in any finite partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains. A version of the theorem for infinite partially ordered sets states that, in this case, a partially ordered set has finite width w if and only if it may be partitioned into w chains, but not less.

The following proof by induction on the size of the partially ordered set ${\displaystyle P}$ is based on that of Galvin (1994).

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

...
Wikipedia