Zorn's lemma

Zorn's Lemma is a lemma in set theory, named after Max Zorn.

Let P be a partially ordered set. Zorn's Lemma states that if every totally ordered subset of P has an upper bound in P, then P has a (not necessarily unique) maximal element.

Here, an "upper bound" is an element in P which is at least as big as every element from the totally ordered subset; it does not have to be a member of that subset. A "maximal element" of P is an element so that no other element of P is bigger.

Like the well-ordering principle, Zorn's Lemma is equivalent to the axiom of choice, in the sense that either one together with the Zermelo-Fraenkel axioms (see set theory) is sufficient to prove the other. It is probably the most useful of all equivalents of the axiom of choice and occurs in the proofs of several theorems of crucial importance, for instance the Hahn-Banach theorem in functional analysis, the theorem that every vector space has a basis, and the theorem that every field has an algebraic closure.

A sketch of the proof follows. Suppose the lemma is false. Then there exists a poset P such that every totally ordered subset has an upper bound, and every element has a bigger one. For every totally ordered subset T we may then define a bigger element b(T), because T has an upper bound, and that upper bound has a bigger element. To actually define the function b, we need to employ the axiom of choice.

Using the function b, we are going to define elements a₀ < a₁ < a₂ < a₃ < ... in P. This sequence is really long: the indices are not just the natural numbers, but all ordinals. In fact, the sequence is too long for the set P; there are too many ordinals, more than there are elements in any set, and the set P will be exhausted before long and then we will run into the desired contradiction.

The a's are defined by transfinite induction: we pick a₀ in P arbitrary and for any other ordinal w we set a_w = b({a_v: v < w}). Because the a_v are totally ordered, this works just fine.

This proof shows that actually a slightly stronger version of Zorn's lemma is true:

If P is a poset in which every well-ordered subset has an upper bound, and if x is any element of P, then P has a maximal element that is greater than or equal to x. That is, there is a maximal element which is comparable to x.