Zorn's lemma in a finite poset

ID: zorn-s-lemma-in-a-finite-poset

Consider the following finite set of subsets, ordered by subset containment:
Every nonempty chain in a partial order has a greatest element within that chain in a partial order, hence an upper bound in . For the empty chain in a partial order, choose . Thus the hypothesis of Zorn's lemma holds. The two maximal elements are and : neither is a proper subset of another member of . There is no greatest element, because it would have to contain both, and no member of contains .
Figure 1.
A finite inclusion poset with two maximal elements and no greatest element
. Lines show immediate upward inclusions; following upward paths gives all other strict comparisons. The blue path is a chain, and the orange nodes are the two maximal elements. Details.
For the chain in a partial order , the member is already an upper bound, although it is not a maximal element of . Both orange members are also upper bounds for . A chain in a partial order need not have a unique upper bound, and the upper bound used to check the hypothesis need not be the eventual maximal element.
The restriction to chains in a partial order matters. The subset has no upper bound in , but its two members are incomparable, so it is not a chain in a partial order. Requiring every subset of to have an upper bound would be much stronger: taking that subset to be itself would force a greatest element.

New to topics? Read the docs here!