Zorn's lemma can be used to show that every
graph has a
spanning tree. The set of all subgraphs that are trees is ordered by inclusion, and the union of a chain is an upper bound. Zorn's lemma says that a maximal tree must exist, which is a spanning tree. Zorn's lemma is not needed for finite graphs, such as the one pictured here.
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:
Suppose a partially ordered set P has the property that every chain (i.e. totally ordered subset) has an upper bound in P. Then the set P contains at least one maximal element.
It is named after the mathematicians Max Zorn and Kazimierz Kuratowski.
Contents

Background 1

Example 2

Sketch of proof 3

History 4

Equivalent forms of Zorn's lemma 5

Notes 6

References 7

External links 8
Background
The terms used in the statement of the lemma are defined as follows. Suppose (P,≤) is a partially ordered set. A subset T is totally ordered if for any s, t in T we have s ≤ t or t ≤ s. Such a set T has an upper bound u in P if t ≤ u for all t in T. Note that u is an element of P but need not be an element of T. An element m of P is called a maximal element (or nondominated) if there is no element x in P for which m < x.
Note that P is not explicitly required to be nonempty. However, the empty set is a chain (trivially), hence is required to have an upper bound, thus exhibiting at least one element of P. An equivalent formulation of the lemma is therefore:
Suppose a nonempty partially ordered set P has the property that every nonempty chain has an upper bound in P. Then the set P contains at least one maximal element.
The distinction may seem subtle, but proofs involving Zorn's lemma often involve taking a union of some sort to produce an upper bound. The case of an empty chain, hence empty union is a boundary case that is easily overlooked.
Zorn's lemma is equivalent to the wellordering theorem and the axiom of choice, in the sense that any one of them, together with the Zermelo–Fraenkel axioms of set theory, is sufficient to prove the others. 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 every nonzero ring has a maximal ideal and that every field has an algebraic closure.
Example
Zorn's lemma can be used to show that every nontrivial ring R with unity contains a maximal ideal. In the terminology above, the set P consists of all (twosided) ideals in R except R itself, which is not empty since it contains at least the trivial ideal {0}. This set is partially ordered by set inclusion. Finding a maximal ideal is the same as finding a maximal element in P. The ideal R was excluded because maximal ideals by definition are not equal to R.
To apply Zorn's lemma, take a nonempty totally ordered subset T of P. It is necessary to show that T has an upper bound, i.e. that 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. 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 condition of Zorn's lemma has been checked, and thus there is a maximal element in P, in other words a maximal ideal in R.
Note that the proof depends on the fact that our ring R has a multiplicative unit 1. Without this, the proof wouldn't work and indeed the statement would be false. For example, the ring with \Q as additive group and trivial multiplication (i. e. a b=0 for all a,b) has no maximal ideal (and of course no 1): Its ideals are precisely the additive subgroups. The factor group \Q/A by a proper subgroup A is a divisible group, hence certainly not finitely generated, hence has a proper nontrivial subgroup, which gives rise to a subgroup and ideal containing A.
Sketch of proof
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 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_{0} < a_{1} < a_{2} < a_{3} < ... 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_{0} 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 wellfounded definition.
This proof shows that actually a slightly stronger version of Zorn's lemma is true:
If P is a poset in which every wellordered 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.
History
The Hausdorff maximal principle is an early statement similar to Zorn's lemma.
K. Kuratowski proved in 1922^{[1]} a version of the lemma close to its modern formulation (it applied to sets ordered by inclusion and closed under unions of wellordered chains). Essentially the same formulation (weakened by using arbitrary chains, not just wellordered) was independently given by Max Zorn in 1935,^{[2]} who proposed it as a new axiom of set theory replacing the wellordering 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".^{[3]} 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:

Hausdorff maximal principle

Axiom of choice

Wellordering theorem.
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 Hamel basis, a result from linear algebra (to which it is equivalent^{[4]})

Every commutative unital ring has a maximal ideal, a result from ring theory

Tychonoff's theorem in topology (to which it is also equivalent^{[5]})
In this sense, we see how Zorn's lemma can be seen as a powerful tool, especially in the sense of unified mathematics.
Notes

^ 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).

^ Zorn, Max (1935). "A remark on method in transfinite algebra". Bulletin of the American Mathematical Society 41 (10): 667–670.

^ Campbell 1978, p. 82.

^ Blass, Andreas (1984). "Existence of bases implies the Axiom of Choice". Contemp. Math. 31: 31–33.

^ Kelley, John L. (1950). "The Tychonoff product theorem implies the axiom of choice". Fundamenta mathematica 37: 75–76.
References

Campbell, Paul J. (February 1978). "The Origin of ‘Zorn's Lemma’". Historia Mathematica 5 (1): 77–89.

Ciesielski, Krzysztof (1997). Set Theory for the Working Mathematician. Cambridge University Press.
External links

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.)
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.