Another proof of Dilworth's decomposition theorem (Q1252854): Difference between revisions

This note gives a new proof of Dilworth's famous Theorem: ``If a partially ordered set \(S\) has maximal sized antichains with \(n\) elements, then \(S\) can be covered by \(n\) chains''. The proof differs from earlier ones in that the chains are constructed one by one. A method is described that starting with a minimal element of the set successively adjoins one element at a time to construct a sequence of chains that has the property that each maximal sized antichain that does not intersect \(C\) contains an element lying above all elements of \(C\). The maximal chain \(C\) thus constructed intersects all antichains of maximal size and so its removal reduces the width of \(S\).