Zorns lemma

Zorn's Lemma, a lemma? in set theory named after Max Zorn, states that, if P is a partially ordered set such that 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 of 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, Tychonoff's theorem in topology stating that every product of compact spaces is compact, and the theorems in abstract algebra that every commutative ring has a [prime ideal]? and that every field has an [algebraic closure]?.

A sketch of the proof of Zorn's lemma follows. Suppose the lemma is false. Then there exists a partially ordered set, or 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.