Zorn's lemma

Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max Zorn and Kazimierz Kuratowski, 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.

Proved by Kuratowski in 1922 and independently by Zorn in 1935,^[2] this lemma 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,^[3] 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.^[4]

Zorn's lemma is equivalent to the well-ordering theorem and also to the axiom of choice, in the sense that any one of the three, together with the Zermelo–Fraenkel axioms of set theory, is sufficient to prove the other two.^[5] An earlier formulation of Zorn's lemma is Hausdorff's maximum 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.^[6]

Motivation

To prove the existence of a mathematical object that can be viewed as a maximal element in some poset 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.

If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn’s lemma may well be able to help you.
— William Timothy Gowers, "How to use Zorn’s lemma"^[7]

Statement of the lemma

Zorn's lemma can be stated as:

Zorn's Lemma — Suppose a partially ordered set P has the property that every chain in P has an upper bound in P. Then the set P contains at least one maximal element.

Variants of this formulation are sometimes used, such as requiring that the set P and the chains be non-empty.^[8]

Zorn's lemma (for non-empty sets) — Suppose a non-empty partially ordered set P has the property that every non-empty chain has an upper bound in P. Then the set P contains at least one maximal element.

Although this formulation appears to be formally weaker (since it places on P the additional condition of being non-empty, but obtains the same conclusion about P), in fact the two formulations are equivalent. To verify this, suppose first that P satisfies the condition that every chain in P has an upper bound in P. Then the empty subset of P is a chain, as it satisfies the definition vacuously; so the hypothesis implies that this subset must have an upper bound in P, and this upper bound shows that P is in fact non-empty. Conversely, if P is assumed to be non-empty and satisfies the hypothesis that every non-empty chain has an upper bound in P, then P also satisfies the condition that every chain has an upper bound, as an arbitrary element of P serves as an upper bound for the empty chain (that is, the empty subset viewed as a chain).

The difference may seem subtle, but in many proofs that invoke Zorn's lemma one takes unions of some sort to produce an upper bound, and so the case of the empty chain may be overlooked; that is, the verification that all chains have upper bounds may have to deal with empty and non-empty chains separately. So many authors prefer to verify the non-emptiness of the set P rather than deal with the empty chain in the general argument.^[9]

Example application

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 (two-sided) ideals in R except R itself. The ideal R was excluded because maximal ideals by definition are not equal to R. Since R is non-trivial, the set P contains the trivial ideal {0}, and therefore P is non-empty. Furthermore, P is partially ordered by set inclusion (see inclusion order). 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 (that is, T is a subset of P that is totally ordered). If T is the empty set, 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 which is bigger than all members of T but still smaller than R (otherwise it would not be 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, and then that it is a proper ideal of R and so is an element of P. Since every element of T is contained in I, this will show that I is an upper bound for T in P, as required.

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. To prove that I is an ideal, note that if a and b are elements of I, then there exist two ideals J, K ∈ T such that a is an element of J and b is an element of K. Since T is totally ordered, we know that J ⊆ K or K ⊆ J. In the first case, both a and b are members of the ideal K, therefore their sum a + b is a member of K, which shows that a + b is a member of I. In the second case, both a and b are members of the ideal J, and thus a + b ∈ I. Furthermore, if r ∈ R, then ar and ra are elements of J and hence elements of I. Thus, I is an ideal in R.

Now, an ideal is equal to R if and only if it contains 1. (It is clear that if it is equal to R, then it must contain 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.

The proof depends on the fact that the ring R has a multiplicative unit 1. Without this, the proof would not work and indeed the statement would be false. For example, the ring with $\mathbb {Q}$ as additive group and trivial multiplication (i.e. $ab=0$ for all $a,b$ ) has no maximal ideal (and of course no 1): Its ideals are precisely the additive subgroups. The factor group $\mathbb {Q} /A$ by a proper subgroup $A$ is a divisible group, hence certainly not finitely generated, hence has a proper non-trivial subgroup, which gives rise to a subgroup and ideal containing $A$ .

Proof sketch

A sketch of the proof of Zorn's lemma follows, assuming the axiom of choice. 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 that for every element in P there is another element bigger than it. 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 (a proper class), 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_i are defined by transfinite recursion: we pick a₀ 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 a_w = b({a_v : v < w}). Because the a_v are totally ordered, this is a well-founded definition.

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. That is, there is a maximal element which is comparable to x.

History

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

Kazimierz Kuratowski proved in 1922^[10] 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,^[11] 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".^[12] The name "Kuratowski–Zorn lemma" prevails in Poland and Russia.

Equivalent forms of Zorn's lemma

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?"^[13]

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

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

Banach's extension theorem which is used to prove one of the most fundamental results in functional analysis, the Hahn–Banach theorem
Every vector space has a basis, a result from linear algebra (to which it is equivalent^[15]). In particular, the real numbers, as a vector space over the rational numbers, possess a Hamel basis.
Every commutative unital ring has a maximal ideal, a result from ring theory
Tychonoff's theorem in topology (to which it is also equivalent^[16])
Every proper filter is contained in an ultrafilter, a result that yields completeness theorem of first-order logic^[17]

In this sense, we see how Zorn's lemma can be seen as a powerful tool, especially in the sense of unified mathematics^{[clarification needed]}.

Analogs under weakenings of the axiom of choice

A weakened form of Zorn's lemma can be proven from ZF + DC (Zermelo–Fraenkel set theory with the axiom of choice replaced by the axiom of dependent choice). 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.^[18]

More generally, strengthening the axiom of dependent choice to higher ordinals allows us to generalize the statement in the previous paragraph to higher cardinalities.^[18] 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.

In popular culture

The 1970 film, Zorns Lemma, is named after the lemma.

This lemma was referenced on The Simpsons in the episode "Bart's New Friend".^[19]

Notes

^ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23
^ Moore 2013, p. 168
^ Wilansky, Albert (1964). Functional Analysis. New York: Blaisdell. pp. 16–17.
^ Jech 2008, ch. 2, §2 Some applications of the Axiom of Choice in mathematics
^ Jech 2008, p. 9
^ Moore 2013, p. 168
^ https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lemma/
^ For example, Lang, Serge (2002). Algebra. Graduate Texts in Mathematics. Vol. 211 (Revised 3rd ed.). Springer-Verlag. p. 880. ISBN 978-0-387-95385-4., Dummit, David S.; Foote, Richard M. (1998). Abstract Algebra (2nd ed.). Prentice Hall. p. 875. ISBN 978-0-13-569302-5., and Bergman, George M (2015). An Invitation to General Algebra and Universal Constructions. Universitext (2nd ed.). Springer-Verlag. p. 162. ISBN 978-3-319-11477-4..
^ Bergman, George M (2015). An Invitation to General Algebra and Universal Constructions. Universitext (Second ed.). Springer-Verlag. p. 164. ISBN 978-3-319-11477-4.
^ Kuratowski, Casimir (1922). "Une méthode d'élimination des nombres transfinis des raisonnements mathématiques" [A method of disposing of transfinite numbers of mathematical reasoning] (PDF). Fundamenta Mathematicae (in French). 3: 76–108. doi:10.4064/fm-3-1-76-108. Retrieved 24 April 2013.
^ Zorn, Max (1935). "A remark on method in transfinite algebra". Bulletin of the American Mathematical Society. 41 (10): 667–670. doi:10.1090/S0002-9904-1935-06166-X.
^ Campbell 1978, p. 82.
^ Krantz, Steven G. (2002), "The Axiom of Choice", Handbook of Logic and Proof Techniques for Computer Science, Springer, pp. 121–126, doi:10.1007/978-1-4612-0115-1_9, ISBN 978-1-4612-6619-8.
^ J.L. Bell & A.B. Slomson (1969). Models and Ultraproducts. North Holland Publishing Company. Chapter 5, Theorem 4.3, page 103.
^ Blass, Andreas (1984). "Existence of bases implies the Axiom of Choice". Axiomatic Set Theory. Contemporary Mathematics. Vol. 31. pp. 31–33. doi:10.1090/conm/031/763890. ISBN 9780821850268. {{cite book}}: |journal= ignored (help)
^ Kelley, John L. (1950). "The Tychonoff product theorem implies the axiom of choice". Fundamenta Mathematicae. 37: 75–76. doi:10.4064/fm-37-1-75-76.
^ J.L. Bell & A.B. Slomson (1969). Models and Ultraproducts. North Holland Publishing Company.
^ ^a ^b Wolk, Elliot S. (1983), On the principle of dependent choices and some forms of Zorn's lemma, 26 365-367, Canadian Mathematical Bulletin, p. 1
^ "Zorn's Lemma | The Simpsons and their Mathematical Secrets".

References

Campbell, Paul J. (February 1978). "The Origin of 'Zorn's Lemma'". Historia Mathematica. 5 (1): 77–89. doi:10.1016/0315-0860(78)90136-2.
Ciesielski, Krzysztof (1997). Set Theory for the Working Mathematician. Cambridge University Press. ISBN 978-0-521-59465-3.
Jech, Thomas (2008) [1973]. The Axiom of Choice. Mineola, New York: Dover Publications. ISBN 978-0-486-46624-8.
Moore, Gregory H. (2013) [1982]. Zermelo's axiom of choice: Its origins, development & influence. Dover Publications. ISBN 978-0-486-48841-7.

External links

"Zorn lemma", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Zorn's Lemma at ProvenMath contains a formal proof down to the finest detail of the equivalence of the axiom of choice and Zorn's Lemma.
Zorn's Lemma at Metamath is another formal proof. (Unicode version for recent browsers.)

[serre-1] Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23

[2] Moore 2013, p. 168

[3] Wilansky, Albert (1964). Functional Analysis. New York: Blaisdell. pp. 16–17.

[4] Jech 2008, ch. 2, §2 Some applications of the Axiom of Choice in mathematics

[5] Jech 2008, p. 9

[6] Moore 2013, p. 168

[7] ttps://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lemma/

[8] For example, Lang, Serge (2002). Algebra. Graduate Texts in Mathematics. Vol. 211 (Revised 3rd ed.). Springer-Verlag. p. 880. ISBN 978-0-387-95385-4., Dummit, David S.; Foote, Richard M. (1998). Abstract Algebra (2nd ed.). Prentice Hall. p. 875. ISBN 978-0-13-569302-5., and Bergman, George M (2015). An Invitation to General Algebra and Universal Constructions. Universitext (2nd ed.). Springer-Verlag. p. 162. ISBN 978-3-319-11477-4..

[9] Bergman, George M (2015). An Invitation to General Algebra and Universal Constructions. Universitext (Second ed.). Springer-Verlag. p. 164. ISBN 978-3-319-11477-4.

[10] Kuratowski, Casimir (1922). "Une méthode d'élimination des nombres transfinis des raisonnements mathématiques" [A method of disposing of transfinite numbers of mathematical reasoning] (PDF). Fundamenta Mathematicae (in French). 3: 76–108. doi:10.4064/fm-3-1-76-108. Retrieved 24 April 2013.

[11] Zorn, Max (1935). "A remark on method in transfinite algebra". Bulletin of the American Mathematical Society. 41 (10): 667–670. doi:10.1090/S0002-9904-1935-06166-X.

[12] Campbell 1978, p. 82.

[13] Krantz, Steven G. (2002), "The Axiom of Choice", Handbook of Logic and Proof Techniques for Computer Science, Springer, pp. 121–126, doi:10.1007/978-1-4612-0115-1_9, ISBN 978-1-4612-6619-8.

[14] J.L. Bell & A.B. Slomson (1969). Models and Ultraproducts. North Holland Publishing Company. Chapter 5, Theorem 4.3, page 103.

[15] Blass, Andreas (1984). "Existence of bases implies the Axiom of Choice". Axiomatic Set Theory. Contemporary Mathematics. Vol. 31. pp. 31–33. doi:10.1090/conm/031/763890. ISBN 9780821850268. {{cite book}}: |journal= ignored (help)

[16] Kelley, John L. (1950). "The Tychonoff product theorem implies the axiom of choice". Fundamenta Mathematicae. 37: 75–76. doi:10.4064/fm-37-1-75-76.

[17] J.L. Bell & A.B. Slomson (1969). Models and Ultraproducts. North Holland Publishing Company.

[Wolk_1983-18] Wolk, Elliot S. (1983), On the principle of dependent choices and some forms of Zorn's lemma, 26 365-367, Canadian Mathematical Bulletin, p. 1

[19] "Zorn's Lemma | The Simpsons and their Mathematical Secrets".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]