Chapter 3 Zorns Lemma and its Applications

In this chapter we introduce a primary tool for dealing with in\u85nite preordered sets. This is the Axiom of Choice, or its order-theoretic reformulation, Zorns Lemma. We begin with an intuitive discussion of these (equivalent) axioms, and then point to some of their surprising, if not paradoxical, consequences. We then deduce from Zorns Lemma the Hausdor¤Maximal Principle and the Well-Ordering Principle. (These are, in fact, none other than equivalent reformulations of the Axiom of Choice.) The remainder of the chapter aims to deduce some major results of order theory by using Zorns Lemma. In particular, we prove Szpilrajns Theorem on completing a partial order, which naturally leads to the notion of order-dimension, and establish a number of (topological) results on the existence of maximal elements of a preordered set. Finally, we prove the Dilworth Decomposition Theorem for \u85nite posets, and then use Zorns Lemma to extend this result to the context of an arbitrary poset. We also consider here some interesting applications of Dilworths Theorem. 1. The Axiom of Choice Consider the following seemingly innocent question: Given a collection A of nonempt