Inductive Proof
The following proof by induction on the size of the partially ordered set is based on that of Galvin (1994).
Let be a finite partially ordered set. The theorem holds trivially if is empty. So, assume that has at least one element, and let be a maximal element of .
By induction, we assume that for some integer the partially ordered set can be covered by disjoint chains and has at least one antichain of size . Clearly, for . For, let be the maximal element in that belongs to an antichain of size in, and set . We claim that is an antichain. Let be an antichain of size that contains . Fix arbitrary distinct indices and . Then . Let . Then, by the definition of . This implies that, since . By interchanging the roles of and in this argument we also have . This verifies that is an antichain.
We now return to . Suppose first that for some . Let be the chain . Then by the choice of, does not have an antichain of size . Induction then implies that can be covered by disjoint chains since is an antichain of size in . Thus, can be covered by disjoint chains, as required. Next, if for each, then is an antichain of size in (since is maximal in ). Now can be covered by the chains, completing the proof.
Read more about this topic: Dilworth's Theorem
Famous quotes containing the word proof:
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)