View source for Zorn's lemma

{{short description|Mathematical proposition equivalent to the axiom of choice}}
[[File:4x4 grid spanning tree.svg|thumb|Zorn's lemma can be used to show that every connected [[Graph (discrete mathematics)|graph]] has a [[Spanning tree|spanning tree]]. The set of all sub-graphs 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 since the graph is connected.<ref name="serre">{{citation|title=Trees|first=Jean-Pierre|last=Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003}}</ref> 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|set theory]]. It states that a [[Partially ordered set|partially ordered set]] containing upper bounds for every chain (that is, every [[Total order|totally ordered]] [[Subset|subset]]) [[Necessity and sufficiency|necessarily]] contains at least one maximal element.

The [[Lemma (mathematics)|lemma]] was proved (assuming the [[Axiom of choice|axiom of choice]]) by [[Biography:Kazimierz Kuratowski|Kazimierz Kuratowski]] in 1922 and independently by [[Biography:Max August Zorn|Max Zorn]] in 1935.<ref>{{harvnb|Moore|2013|p=168}}</ref> It occurs in the proofs of several theorems of crucial importance, for instance the [[Hahn–Banach theorem]] in [[Functional analysis|functional analysis]], the theorem that every [[Vector space|vector space]] has a [[Basis (linear algebra)|basis]],<ref>{{cite book |first=Albert |last=Wilansky |title=Functional Analysis |publisher=Blaisdell |location=New York |year=1964 |pages=16–17 }}</ref> [[Tychonoff's theorem]] in [[Topology|topology]] stating that every product of [[Compact space|compact space]]s is compact, and the theorems in [[Abstract algebra|abstract algebra]] that in a ring with identity every proper ideal is contained in a [[Maximal ideal|maximal ideal]] and that every [[Field (mathematics)|field]] has an algebraic closure.<ref>{{harvnb|Jech|2008|loc=ch. 2, §2 Some applications of the Axiom of Choice in mathematics}}</ref>

Zorn's lemma is equivalent to the [[Well-ordering theorem|well-ordering theorem]] and also to the [[Axiom of choice|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.<ref>{{harvnb|Jech|2008|p=9}}</ref> 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.<ref>{{harvnb|Moore|2013|p=168}}</ref>

==Motivation==

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

{{Quote
|text=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.
|author=[[Biography:Timothy Gowers|William Timothy Gowers]]
}}

==Statement of the lemma==
Preliminary notions:
* A [[Set (mathematics)|set]] ''P'' equipped with a [[Binary relation|binary relation]] ≤ that is [[Reflexive relation|reflexive]] ({{nowrap|''x'' ≤ ''x''}} for every ''x''), [[Antisymmetric relation|antisymmetric]] (if both {{nowrap|''x'' ≤ ''y''}} and {{nowrap|''y'' ≤ ''x''}} hold, then {{nowrap|1=''x'' = ''y''}}), and [[Transitive relation|transitive]] (if {{nowrap|''x'' ≤ ''y''}} and {{nowrap|''y'' ≤ ''z''}} then {{nowrap|''x'' ≤ ''z''}}) is said to be [[Partially ordered set|(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 [[Comparability|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.
* Every subset ''S'' of a partially ordered set ''P'' can itself be seen as partially ordered by [[Binary relation#Restriction|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.
* 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, if 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.
* 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:

{{math theorem
|Suppose a [[Partially ordered set|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.
|name=Zorn's lemma}}

Variants of this formulation are sometimes used, such as requiring that the set ''P''  and the chains be non-empty.<ref>For example, {{cite book|last1=Lang|first1=Serge|title=Algebra|edition=Revised 3rd|publisher=Springer-Verlag|series=Graduate Texts in Mathematics|volume=211|date=2002|isbn=978-0-387-95385-4|page=880}}, {{cite book|last1=Dummit|first1=David S.|last2=Foote|first2=Richard M.|title=Abstract Algebra|edition=2nd|publisher=Prentice Hall|date=1998|isbn=978-0-13-569302-5|page=875}}, and {{cite book|last1=Bergman|first1=George M|author-link1=George Bergman|title=An Invitation to General Algebra and Universal Constructions|edition=2nd|publisher=Springer-Verlag|series=Universitext|date=2015|isbn=978-3-319-11477-4|page=162|url=https://math.berkeley.edu/~gbergman/245/}}.</ref>

{{Math theorem
|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.|name=Zorn's lemma|note=for non-empty sets}}

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 [[Vacuous truth|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.<ref>{{cite book|last1=Bergman|first1=George M|title=An Invitation to General Algebra and Universal Constructions|edition=Second|publisher=Springer-Verlag|series=Universitext|date=2015|isbn=978-3-319-11477-4|page=164|url=https://math.berkeley.edu/~gbergman/245/}}</ref>

== Example applications ==

=== Every vector space has a basis ===

Zorn's lemma can be used to show that every [[Vector space|vector space]] ''V'' has a [[Basis (linear algebra)|basis]].<ref>{{cite web |last1=Smits |first1=Tim |title=A Proof that every Vector Space has a Basis |url=https://www.math.ucla.edu/~tsmits/115B/115A/Zorn's%20Lemma.pdf |access-date=14 August 2022}}</ref>

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 [[Linear independence|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 [[Subset|set inclusion]] (see [[Inclusion order|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 (set theory)|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 '''v'''<sub>1</sub>, '''v'''<sub>2</sub>, ..., '''v'''<sub>k</sub> ∈ ''B'' and [[Scalar (mathematics)|scalars]] ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>k</sub>, not all zero, such that
:<math>a_1\mathbf{v}_1 + a_2\mathbf{v}_2 + \cdots + a_k\mathbf{v}_k = \mathbf{0}.</math>
Since ''B'' is the union of all the sets in ''T'', there are some sets ''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>k</sub> ∈ ''T'' such that '''v'''<sub>i</sub> ∈ ''S''<sub>i</sub> for every ''i'' = 1, 2, ..., ''k''. As ''T'' is totally ordered, one of the sets ''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>k</sub> must contain the others, so there is some set ''S''<sub>i</sub> that contains all of '''v'''<sub>1</sub>, '''v'''<sub>2</sub>, ..., '''v'''<sub>k</sub>. This tells us there is a linearly dependent set of vectors in ''S''<sub>i</sub>, contradicting that ''S''<sub>i</sub> 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 [[Linear span|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''.

=== Every nontrivial ring with unity contains a maximal ideal ===

Zorn's lemma can be used to show that every nontrivial [[Ring (mathematics)|ring]] ''R'' with unity contains a [[Maximal ideal|maximal ideal]].

Let ''P'' be the set consisting of all ''proper'' [[Ideal (ring theory)|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|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 ''r''1 = ''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''.

==Proof sketch==
A sketch of the proof of Zorn's lemma follows, assuming the [[Axiom of choice|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 (mathematics)|function]] ''b'', we need to employ the axiom of choice (explicitly: let <math> B(T) = \{b \in P : \forall t \in T, b \ge t\} </math>, that is, the set of upper bounds for ''T''. The axiom of choice furnishes <math> b: b(T) \in B(T) </math>).

Using the function ''b'', we are going to define elements ''a''<sub>0</sub> < ''a''<sub>1</sub> < ''a''<sub>2</sub> < ''a''<sub>3</sub> < ... < a<sub>ω</sub> < a<sub>ω+1</sub> <…, in ''P''. This uncountable sequence is '''really long''': the indices are not just the [[Natural number|natural number]]s, but all [[Ordinal number|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 (in other words, given any set of ordinals, there exists a larger ordinal), and the set ''P'' will be exhausted before long and then we will run into the desired contradiction.

The ''a<sub>i</sub>'' are defined by transfinite recursion: we pick ''a''<sub>0</sub> 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''<sub>''w''</sub> = ''b''({''a''<sub>''v''</sub> : ''v'' < ''w''}). Because the ''a''<sub>''v''</sub> are totally ordered, this is a well-founded definition.

The above proof can be formulated without explicitly referring to ordinals by considering the initial segments {''a''<sub>''v''</sub> : ''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).<ref>{{cite journal |last1=Lewin |first1=Jonathan W. |date=1991 |title=A simple proof of Zorn's lemma |url=https://digitalcommons.kennesaw.edu/cgi/viewcontent.cgi?article=2161&context=facpubs |journal=The American Mathematical Monthly |volume=98 |issue=4 |pages=353–354 |doi=10.1080/00029890.1991.12000768 }}</ref>

This proof shows that actually a slightly stronger version of Zorn's lemma is true:
{{Math theorem|If ''P'' is a poset in which every [[Well-order|well-order]]ed 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''.|name=Lemma}}

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

[[Biography:Kazimierz Kuratowski|Kazimierz Kuratowski]] proved in 1922<ref>{{cite journal |first=Casimir |last=Kuratowski |title=Une méthode d'élimination des nombres transfinis des raisonnements mathématiques |trans-title=A method of disposing of transfinite numbers of mathematical reasoning |journal=[[Fundamenta Mathematicae]] |volume=3 |year=1922 |pages=76–108 |doi=10.4064/fm-3-1-76-108 |url=http://matwbn.icm.edu.pl/ksiazki/fm/fm3/fm3114.pdf |access-date=2013-04-24 |language=fr|doi-access=free }}</ref> 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 [[Biography:Max August Zorn|Max Zorn]] in 1935,<ref>{{cite journal |first=Max |last=Zorn |title=A remark on method in transfinite algebra |journal=Bulletin of the American Mathematical Society |volume=41 |year=1935 |issue=10 |pages=667–670 |doi=10.1090/S0002-9904-1935-06166-X |doi-access=free }}</ref> who proposed it as a new [[Axiom|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 [[Biography:John Tukey|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".<ref>{{harvnb|Campbell|1978|p=82}}.</ref> The name "Kuratowski–Zorn lemma" prevails in Poland and Russia.


==Equivalent forms of Zorn's lemma==

Zorn's lemma is equivalent (in [[Zermelo–Fraenkel set theory|ZF]]) to three main results:
# [[Hausdorff maximal principle]]
# [[Axiom of choice]]
# [[Well-ordering theorem]].

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?"<ref>{{citation
 | doi = 10.1007/978-1-4612-0115-1_9
 | pages = 121–126
 | publisher = Springer
 | title = Handbook of Logic and Proof Techniques for Computer Science
 | year = 2002| chapter = The Axiom of Choice | isbn = 978-1-4612-6619-8 }}.</ref>

Zorn's lemma is also equivalent to the strong completeness theorem of first-order logic.<ref>J.L. Bell & A.B. Slomson (1969). ''Models and Ultraproducts''. North Holland Publishing Company. Chapter 5, Theorem 4.3, page 103.</ref>

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 (linear algebra)|basis]], a result from linear algebra (to which it is equivalent<ref>{{Cite book
|last = Blass
|first = Andreas
|title = Axiomatic Set Theory
|year = 1984
|chapter = Existence of bases implies the Axiom of Choice
|journal=Contemp. Math.
|volume = 31
|pages = 31–33
|ref=blass
|doi=10.1090/conm/031/763890
|series = Contemporary Mathematics
|isbn = 9780821850268
}}</ref>). 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|maximal ideal]], a result from ring theory known as [[Krull's theorem]], to which Zorn's lemma is equivalent<ref>{{cite journal|last=Hodges|first=W.|year=1979|title=Krull implies Zorn|journal=Journal of the London Mathematical Society|volume=s2-19|issue=2|pages=285–287|doi=10.1112/jlms/s2-19.2.285}}</ref>
# [[Tychonoff's theorem]] in topology (to which it is also equivalent<ref>{{cite journal
|last = Kelley
|first = John L.
|year = 1950
|title= The Tychonoff product theorem implies the axiom of choice
| journal= Fundamenta Mathematicae
| volume = 37
| pages = 75–76
|doi = 10.4064/fm-37-1-75-76
| ref=kelley
|doi-access = free
}}</ref>)
# Every proper filter is contained in an [[Ultrafilter|ultrafilter]], a result that yields the completeness theorem of [[First-order logic|first-order logic]]<ref>J.L. Bell & A.B. Slomson (1969). ''Models and Ultraproducts''. North Holland Publishing Company.</ref>

In this sense, we see how Zorn's lemma can be seen as a powerful tool, applicable to many areas of mathematics.

=== 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|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.<ref name="Wolk 1983">{{citation|title=On the principle of dependent choices and some forms of Zorn's lemma|first=Elliot S.|last=Wolk |journal=[[Canadian Mathematical Bulletin]]|volume=26|issue=3|pages=365–367 |year=1983 | doi=10.4153/CMB-1983-062-5 | doi-access=free }}</ref>

More generally, strengthening the axiom of dependent choice to higher ordinals allows us to generalize the statement in the previous paragraph to higher cardinalities.<ref name="Wolk 1983"/> 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.

The lemma was referenced on ''The Simpsons'' in the episode "Bart's New Friend".<ref>{{cite web| url=http://www.simonsingh.net/Simpsons_Mathematics/zorns-lemma/| title=Zorn's Lemma {{!}} The Simpsons and their Mathematical Secrets}}</ref>

== See also ==

* {{annotated link|Antichain}}
* [[Bourbaki–Witt theorem]]
* [[Chain-complete partial order]] – a partially ordered set in which every chain has a least upper bound
* {{annotated link|Szpilrajn extension theorem}}
* [[Teichmüller–Tukey lemma]] (sometimes named Tukey's lemma)

==Notes==
{{Reflist|30em}}

==References==
* {{cite journal
 | last = Campbell
 | first = Paul J.
 |date=February 1978
 | title = The Origin of 'Zorn's Lemma'
 | journal = Historia Mathematica
 | volume = 5
 | issue = 1
 | pages = 77–89
 | doi = 10.1016/0315-0860(78)90136-2
| doi-access = free
 }}
*{{cite book |title=Set Theory for the Working Mathematician |last=Ciesielski |first=Krzysztof |publisher=Cambridge University Press |year=1997 |isbn=978-0-521-59465-3 }}
* {{cite book
 | isbn = 978-0-486-46624-8
 | orig-year=1973
 | publisher = [[Social:Dover Publications|Dover Publications]]
 | location = Mineola, New York
 | title = The Axiom of Choice
 | year = 2008}}
* {{cite book
 | last1 = Moore | first1 = Gregory H.
 | title = Zermelo's axiom of choice: Its origins, development & influence
 | orig-year = 1982
 | year = 2013
 | publisher = [[Social:Dover Publications|Dover Publications]]
 | isbn=978-0-486-48841-7}}

==External links==

* {{springer|title=Zorn lemma|id=p/z099330}}
* [http://www.apronus.com/provenmath/choice.htm 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.
* [http://us.metamath.org/mpegif/zorn.html Zorn's Lemma] at [[Software:Metamath|Metamath]] is another formal proof.  ([http://us.metamath.org/mpeuni/zorn.html Unicode version] for recent browsers.)

{{Mathematical logic}}

{{DEFAULTSORT:Zorn's Lemma}}

[[Category:Axiom of choice]]
[[Category:Order theory]]

{{Sourceattribution|Zorn's lemma}}