Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. 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 proven (assuming the axiom of choice) by Kazimierz Kuratowski in 1922 and independently by Max Zorn in 1935. It 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 in a ring with identity every proper ideal is contained in a maximal ideal and that every field has an algebraic closure.
Zorn's lemma is equivalent to the well-ordering theorem and also to the axiom of choice, in the sense that within ZF (Zermelo–Fraenkel set theory without the axiom of choice) any one of the three is sufficient to prove the other two. An earlier formulation of Zorn's lemma is the Hausdorff maximal principle which states that every totally ordered subset of a given partially ordered set is contained in a maximal totally ordered subset of that partially ordered set.
Motivation
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.
Statement of the lemma Preliminary notions: Partially ordered set A set P equipped with a binary relation ≤ that is reflexive ( for every x), antisymmetric (if both and hold, then ), and transitive (if and then ) is said to be (partially) ordered by ≤. Given two elements x and y of P with x ≤ y, y is said to be greater than or equal to x. The word "partial" is meant to indicate that not every pair of elements of a partially ordered set is required to be comparable under the order relation, that is, in a partially ordered set P with order relation ≤ there may be elements x and y with neither x ≤ y nor y ≤ x. An ordered set in which every pair of elements is comparable is called totally ordered. Chain Every subset S of a partially ordered set P can itself be seen as partially ordered by restricting the order relation inherited from P to S. A subset S of a partially ordered set P is called a chain (in P) if it is totally ordered in the inherited order. Maximal element An element m of a partially ordered set P with order relation ≤ is maximal (with respect to ≤) if there is no other element of P greater than m, that is, there is no s in P with s ≠ m and m ≤ s. Depending on the order relation, a partially ordered set may have any number of maximal elements. However, a totally ordered set can have at most one maximal element. Upper bound Given a subset S of a partially ordered set P, an element u of P is an upper bound of S if it is greater than or equal to every element of S. Here, S is not required to be a chain, and u is required to be comparable to every element of S but need not itself be an element of S.
Zorn's lemma can then be stated as:
In fact, property (1) is redundant, since property (2) says, in particular, that the empty chain has an upper bound in , implying is nonempty. However, in practice, one often checks (1) and then verifies (2) only for nonempty chains, since the case of the empty chain is taken care of by (1).
In the terminology of Bourbaki, a partially ordered set is called inductive if each chain has an upper bound in the set (in particular, the set is then nonempty). Then the lemma can be stated as:
For some applications, the following variant may be useful.
Indeed, let with the partial ordering from . Then, for a chain in , an upper bound in is in and so satisfies the hypothesis of Zorn's lemma and a maximal element in is a maximal element in as well.
Remark: Zorn's lemma can fail for a partially ordered class, not a set. Indeed, let P be the class of all ordinals. Then it satisfies the hypothesis of the lemma (it can be shown that the union of a chain of ordinals is again an ordinal; roughly, initial segments glue). However, has no maximal element: if is a maximal ordinal, the successor of it is strictly larger. (The fact that the class of ordinals is not a set is known as the Burali-Forti paradox.)
Example applications Every vector space has a basis Zorn's lemma can be used to show that every vector space V has a basis.
If V = {0}, then the empty set is a basis for V. Now, suppose that V ≠ {0}. Let P be the set consisting of all linearly independent subsets of V. Since V is not the zero vector space, there exists a nonzero element v of V, so P contains the linearly independent subset {v}. Furthermore, P is partially ordered by set inclusion (see inclusion order). 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). If T is the empty set, then {v} is an upper bound for T in P. Suppose then that T is non-empty. 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. Then there exists vectors v1, v2, ..., vk ∈ B and scalars a1, a2, ..., ak, not all zero, such that
Since B is the union of all the sets in T, there are some sets S1, S2, ..., Sk ∈ T such that vi ∈ Si for every i = 1, 2, ..., k. As T is totally ordered, one of the sets S1, S2, ..., Sk must contain the others, so there is some set Si that contains all of v1, v2, ..., vk. This tells us there is a linearly dependent set of vectors in Si, contradicting that Si is linearly independent (because it is a member of P).
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. Then there exists some v ∈ V not covered by the span of B. This says that B ∪ {v} is a linearly independent subset of V that is larger than B, contradicting the maximality of B. Therefore, B is a spanning set of V, and thus, a basis of V.
Remark: While less common, it is possible to construct a basis somehow more directly using transfinite recursion, still assuming the axiom of choice. For that, see for example as a comparison.
Every nontrivial ring with unity contains a maximal ideal
Zorn's lemma can be used to show that every nontrivial ring R with unity contains a maximal ideal.
Let P be the set consisting of all proper ideals in R (that is, all ideals in R except R itself). Since R is non-trivial, the set P contains the trivial ideal {0}. Furthermore, P is partially ordered by set inclusion. 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 necessary to show that T has an upper bound, that is, there exists an ideal I ⊆ R containing all the members of T but still smaller than R (otherwise it would not be a proper ideal, so it is not in P).
Take I to be the union of all the ideals in T. We wish to show that I is an upper bound for T in P. We will first show that I is an ideal of R. For I to be an ideal, it must satisfy three conditions:
I is a nonempty subset of R, For every x, y ∈ I, the sum x + y is in I, For every r ∈ R and every x ∈ I, the product rx is in I.
#1 - I is a nonempty subset of R.
Because T contains at least one element, and that element contains at least 0, the union I contains at least 0 and is not empty. Every element of T is a subset of R, so the union I only consists of elements in R.
#2 - For every x, y ∈ I, the sum x + y is in I.
Suppose x and y are elements of I. Then there exist two ideals J, K ∈ T such that x is an element of J and y is an element of K. Since T is totally ordered, we know that J ⊆ K or K ⊆ J. Without loss of generality, assume the first case. Both x and y are members of the ideal K, therefore their sum x + y is a member of K, which shows that x + y is a member of I.
#3 - For every r ∈ R and every x ∈ I, the product rx is in I.
Suppose x is an element of I. Then there exists an ideal J ∈ T such that x is in J. If r ∈ R, then rx is an element of J and hence an element of I. Thus, I is an ideal in R.
Now, we show that I is a proper ideal. An ideal is equal to R if and only if it contains 1. (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 proof of Tychonoff's theorem Zorn's lemma implies the ultrafilter lemma, which in turn implies Tychonoff's theorem (together with the axiom of choice). However, it is also possible to prove Tychonoff's theorem directly from Zorn's lemma as follows (by using an ultrafilter implicitly).
Let be a family of compact spaces, not necessarily Hausdorff. We shall show that a family of closed subsets of with the finite intersection property has nonempty intersection. Let be the collection of all the families of subsets of with the finite intersection property (not necessarily closed subsets). We let be ordered by set inclusion. If is a chain, then clearly the union of has the finite intersection property; so, the union is in . Thus, by Zorn's lemma, there is a maximal element in containing . We shall show that the intersection of all the closed sets in has nonempty intersection; a fortiori, has nonempty intersection.
For each finite subset , since is nonempty, is nonempty for the projection Thus, for each , the set
has nonempty intersection since it has the finite intersection property and is compact. We note If is a finite subset, is in . For an open set intersecting , we have is in . Indeed, (1) holds since by maximality, as the set on the right has the finite intersection property. Similarly, for a finite subset , since is in , or . Thus, the set has the finite intersection property and (2) follows by the maximality of .
Now, by the axiom of choice, we can find an element in . We claim this is in each closed set in . Since is closed, it is enough to show is in the closure of ; i.e., each basic neighborhood of intersects . A basic neighborhood of has the form . But by the property (2) above, we have , which gives the claim by the finite intersection property.
Remark: The ultrafilter lemma is strictly weaker than the axiom of choice; it is equivalent to the boolean prime ideal theorem. On the other hand, somehow surprisingly, Tychonoff's theorem implies (thus is equivalent to) the axiom of choice. Hence, the use of AC above cannot be eliminated. (If are compact Hausdorff, then the use of AC can be eliminated; indeed, each above has exactly one point in that case.)