Dilworth's Theorem

in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements

The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.

The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite

Aiming for a contradiction, suppose there is an $s \in S \setminus \paren {S^+ \cup S^-}$.

For the converse inequality we proceed by induction on the cardinality $\card S$ of $S$.