Zorn's lemma

It states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.

The lemma was proved (assuming the axiom of choice) by Kazimierz Kuratowski in 1922 and independently by Max Zorn in 1935.

[6] To prove the existence of a mathematical object that can be viewed as a maximal element in some partially ordered set in some way, one can try proving the existence of such an object by assuming there is no maximal element and using transfinite induction and the assumptions of the situation to get a contradiction.

Zorn's lemma tidies up the conditions a situation needs to satisfy in order for such an argument to work and enables mathematicians to not have to repeat the transfinite induction argument by hand each time, but just check the conditions of Zorn's lemma.

Finding a maximal linearly independent subset of V is the same as finding a maximal element in P. To apply Zorn's lemma, take a chain T in P (that is, T is a subset of P that is totally ordered).

We need to show that T has an upper bound, that is, there exists a linearly independent subset B of V containing all the members of T. Take B to be the union of all the sets in T. We wish to show that B is an upper bound for T in P. To do this, it suffices to show that B is a linearly independent subset of V. Suppose otherwise, that B is not linearly independent.

The hypothesis of Zorn's lemma has been checked, and thus there is a maximal element in P, in other words a maximal linearly independent subset B of V. Finally, we show that B is indeed a basis of V. It suffices to show that B is a spanning set of V. Suppose for the sake of contradiction that B is not spanning.

Therefore, B is a spanning set of V, and thus, a basis of V. Zorn's lemma can be used to show that every nontrivial ring R with unity contains a maximal ideal.

Finding a maximal ideal in R is the same as finding a maximal element in P. To apply Zorn's lemma, take a chain T in P. If T is empty, then the trivial ideal {0} is an upper bound for T in P. Assume then that T is non-empty.

(It is clear that if it is R then it contains 1; on the other hand, if it contains 1 and r is an arbitrary element of R, then r1 = r is an element of the ideal, and so the ideal is equal to R.) So, if I were equal to R, then it would contain 1, and that means one of the members of T would contain 1 and would thus be equal to R – but R is explicitly excluded from P. The hypothesis of Zorn's lemma has been checked, and thus there is a maximal element in P, in other words a maximal ideal in R. A sketch of the proof of Zorn's lemma follows, assuming the axiom of choice.

To actually define the function b, we need to employ the axiom of choice (explicitly: let

Using the function b, we are going to define elements a0 < a1 < a2 < a3 < ... < aω < aω+1 <…, in P. This uncountable sequence is really long: the indices are not just the natural numbers, but all ordinals.

The ai are defined by transfinite recursion: we pick a0 in P arbitrary (this is possible, since P contains an upper bound for the empty set and is thus not empty) and for any other ordinal w we set aw = b({av : v < w}).

The above proof can be formulated without explicitly referring to ordinals by considering the initial segments {av : v < w} as subsets of P. Such sets can be easily characterized as well-ordered chains S ⊆ P where each x ∈ S satisfies x = b({y ∈ S : y < x}).

Contradiction is reached by noting that we can always find a "next" initial segment either by taking the union of all such S (corresponding to the limit ordinal case) or by appending b(S) to the "last" S (corresponding to the successor ordinal case).

[14] This proof shows that actually a slightly stronger version of Zorn's lemma is true: Lemma — 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 greater than or equal to x.

(Note that, strictly speaking, (1) is redundant since (2) implies the empty set is in

Essentially the same proof also shows that Zorn's lemma implies the well-ordering theorem: take

[18] The Hausdorff maximal principle is an early statement similar to Zorn's lemma.

Kazimierz Kuratowski proved in 1922[19] a version of the lemma close to its modern formulation (it applies to sets ordered by inclusion and closed under unions of well-ordered chains).

Essentially the same formulation (weakened by using arbitrary chains, not just well-ordered) was independently given by Max Zorn in 1935,[20] who proposed it as a new axiom of set theory replacing the well-ordering theorem, exhibited some of its applications in algebra, and promised to show its equivalence with the axiom of choice in another paper, which never appeared.

The name "Zorn's lemma" appears to be due to John Tukey, who used it in his book Convergence and Uniformity in Topology in 1940.

Bourbaki's Théorie des Ensembles of 1939 refers to a similar maximal principle as "le théorème de Zorn".

Zorn's lemma is equivalent (in ZF) to three main results: A well-known joke alluding to this equivalency (which may defy human intuition) is attributed to Jerry Bona: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?

"[22] Zorn's lemma is also equivalent to the strong completeness theorem of first-order logic.

[23] Moreover, Zorn's lemma (or one of its equivalent forms) implies some major results in other mathematical areas.

For example, In this sense, Zorn's lemma is a powerful tool, applicable to many areas of mathematics.

Zorn's lemma can be expressed straightforwardly by observing that the set having no maximal element would be equivalent to stating that the set's ordering relation would be entire, which would allow us to apply the axiom of dependent choice to construct a countable chain.

As a result, any partially ordered set with exclusively finite chains must have a maximal element.

[28] In the limit where we allow arbitrarily large ordinals, we recover the proof of the full Zorn's lemma using the axiom of choice in the preceding section.