{"history":[],"article":{"id":"97a2587c-dded-411f-adab-55e2288bb1be","title":"Zorn's lemma","slug":"zorn-s-lemma","content":":::summary\n:::\n\n# \n**Zorn's lemma**, also known as the **Kuratowski–Zorn lemma**, is a proposition of [set theory](https://bliptext.com/articles/set-theory).\nIt states that a [preorder](https://bliptext.com/articles/preorder) containing [upper bounds](https://bliptext.com/articles/upper-bound) for every [chain](https://bliptext.com/articles/chain-order-theory) (that is, every [totally ordered](https://bliptext.com/articles/total-order) [subset](https://bliptext.com/articles/subset)) [necessarily](https://bliptext.com/articles/necessity-and-sufficiency) contains at least one [maximal element](https://bliptext.com/articles/maximal-element).\nThe [lemma](https://bliptext.com/articles/lemma-mathematics) was proved (assuming the [axiom of choice](https://bliptext.com/articles/axiom-of-choice)) by [Kazimierz Kuratowski](https://bliptext.com/articles/kazimierz-kuratowski) in 1922 and independently by [Max Zorn](https://bliptext.com/articles/max-august-zorn) in 1935.\nIt occurs in the proofs of several theorems of crucial importance, for instance the [Hahn–Banach theorem](https://bliptext.com/articles/hahn-banach-theorem) in [functional analysis](https://bliptext.com/articles/functional-analysis), the theorem that every [vector space](https://bliptext.com/articles/vector-space) has a [basis](https://bliptext.com/articles/basis-linear-algebra), [Tychonoff's theorem](https://bliptext.com/articles/tychonoff-s-theorem) in [topology](https://bliptext.com/articles/topology) stating that every product of [compact spaces](https://bliptext.com/articles/compact-space) is compact, and the theorems in [abstract algebra](https://bliptext.com/articles/abstract-algebra) that in a [ring](https://bliptext.com/articles/ring-algebra) with identity every proper ideal is contained in a [maximal ideal](https://bliptext.com/articles/maximal-ideal) and that every [field](https://bliptext.com/articles/field-mathematics) has an [algebraic closure](https://bliptext.com/articles/algebraic-closure).\nZorn's lemma is equivalent to the [well-ordering theorem](https://bliptext.com/articles/well-ordering-theorem) and also to the [axiom of choice](https://bliptext.com/articles/axiom-of-choice), in the sense that within ZF ([Zermelo–Fraenkel set theory](https://bliptext.com/articles/zermelo-fraenkel-set-theory) without the [axiom of choice](https://bliptext.com/articles/axiom-of-choice)) any one of the three is sufficient to prove the other two.\nAn earlier formulation of Zorn's lemma is the [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle), which states that every chain is contained in a maximal chain.\n# [Zorn's lemma can be used to show that every connected graph has a 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. Zorn's lemma is not needed for finite graphs, such as the one pictured here. | upload.wikimedia.org/wikipedia/commons/d/d4/4x4///grid///spanning///tree.svg]\n\n# Motivation\nTo prove the existence of a mathematical object that can be viewed as a maximal element in some [preorder](https://bliptext.com/articles/preorder) in some way, one can try proving the existence of such an object by assuming there is no maximal element and using [transfinite induction](https://bliptext.com/articles/transfinite-induction) and the assumptions of the situation to get a contradiction.\nZorn'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.\n\"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.\"\n- William Timothy Gowers\n\n# Statement of the lemma\nPreliminary notions:\nZorn's lemma can then be stated as:\nVariants of this formulation are sometimes used, such as requiring that the set P and its chains be non-empty.\nAlthough 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.\nThen the empty subset of P is a chain, as it satisfies the definition [vacuously](https://bliptext.com/articles/vacuous-truth); 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.\nConversely, 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).\nThe 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.\nSo, many authors prefer to verify the non-emptiness of the set P rather than deal with the empty chain in the general argument.\n\n# Example applications\n\n## Every vector space has a basis\nZorn's lemma can be used to show that every [vector space](https://bliptext.com/articles/vector-space) V has a [basis](https://bliptext.com/articles/basis-linear-algebra).\nIf V = {**0**}, then the empty set is a basis for V.\nNow, suppose that V ≠ {**0**}.\nLet P be the set consisting of all [linearly independent](https://bliptext.com/articles/linear-independence) subsets of V.\nSince V is not the zero ****v****ector space, there exists a nonzero element ****v**** of V, so P contains the linearly independent subset {****v****}.\nFurthermore, P is preordered by [set inclusion](https://bliptext.com/articles/subset) (see [inclusion order](https://bliptext.com/articles/inclusion-order)).\nFinding a maximal linearly independent subset of V is the same as finding a maximal element in P.\nTo apply Zorn's lemma, take a chain T in P (that is, T is a subset of P that is totally ordered).\nIf T is the empty set, then {**v**} is an upper bound for T in P.\nSuppose then that T is non-empty.\nWe 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.\nTake B to be the [union](https://bliptext.com/articles/union-set-theory) of all the sets in T.\nWe wish to show that B is an upper bound for T in P.\nTo do this, it suffices to show that B is a linearly independent subset of V.\nSuppose otherwise, that B is not linearly independent.\nThen there exists ******v******ectors ******v******1, ******v******2, ..., ******v******k ∈ B and [scalars](https://bliptext.com/articles/scalar-mathematics) a1, a2, ..., ak, not all zero, such that\nSince B is the union of all the sets in T, there are some sets S1, S2, ..., Sk ∈ T such that **v**i ∈ Si for e**v**ery i = 1, 2, ..., k.\nAs 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 ******v******1, ******v******2, ..., ******v******k. This tells us there is a linearly dependent set of ******v******ectors in Si, contradicting that Si is linearly independent (because it is a member of P).\nThe 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.\nFinally, we show that B is indeed a basis of V.\nIt suffices to show that B is a [spanning set](https://bliptext.com/articles/linear-span) of V.\nSuppose for the sake of contradiction that B is not spanning.\nThen there exists some **v** ∈ V not co**v**ered by the span of B.\nThis says that B ∪ {**v**} is a linearly independent subset of V that is larger than B, contradicting the maximality of B.\nTherefore, B is a spanning set of V, and thus, a basis of V.\n\n## Every nontrivial ring with unity contains a maximal ideal\nZorn's lemma can be used to show that every nontrivial [ring](https://bliptext.com/articles/ring-mathematics) R with [unity](https://bliptext.com/articles/unital-ring) contains a [maximal ideal](https://bliptext.com/articles/maximal-ideal).\nLet P be the set consisting of all proper [ideals](https://bliptext.com/articles/ideal-ring-theory) in R (that is, all [ideals](https://bliptext.com/articles/ideal-ring-theory) in R except R itself).\nSince R is non-trivial, the set P contains the trivial ideal {0}.\nFurthermore, P is preordered by set inclusion.\nFinding a maximal ideal in R is the same as finding a maximal element in P.\nTo apply Zorn's lemma, take a chain T in P.\nIf T is empty, then the trivial ideal {0} is an upper bound for T in P.\nAssume then that T is non-empty.\nIt 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).\nTake I to be the union of all the ideals in T.\nWe wish to show that I is an upper bound for T in P.\nWe will first show that I is an ideal of R.\nFor I to be an ideal, it must satisfy three conditions:\n#1 - I is a nonempty subset of R.\nBecause T contains at least one element, and that element contains at least 0, the union I contains at least 0 and is not empty.\nEvery element of T is a subset of R, so the union I only consists of elements in R.\n#2 - For every x, y ∈ I, the sum x + y is in I.\nSuppose x and y are elements of I.\nThen there exist two ideals J, K ∈ T such that x is an element of J and y is an element of K.\nSince T is totally ordered, we know that J ⊆ K or K ⊆ J.\n[Without loss of generality](https://bliptext.com/articles/without-loss-of-generality), assume the first case.\nBoth 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.\n#3 - For every r ∈ R and every x ∈ I, the product rx is in I.\nSuppose x is an element of I.\nThen there exists an ideal J ∈ T such that x is in J.\nIf r ∈ R, then rx is an element of J and hence an element of I.\nThus, I is an ideal in R.\nNow, we show that I is a proper ideal.\nAn ideal is equal to R [if and only if](https://bliptext.com/articles/if-and-only-if) it contains 1.\n(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.\nThe 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.\n\n# Proof sketch\nA sketch of the proof of Zorn's lemma follows, assuming the [axiom of choice](https://bliptext.com/articles/axiom-of-choice).\nSuppose the lemma is false.\nThen there exists a proset 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.\nFor 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.\nTo actually define the [function](https://bliptext.com/articles/function-mathematics) b, we need to employ the axiom of choice (explicitly: let, that is, the set of upper bounds for T. The axiom of choice furnishes ).\nUsing the function b, we are going to define elements a0 < a1 < a2 < a3 < ... < aω < aω+1 <…, in P.\nThis uncountable sequence is **really long**: the indices are not just the [natural numbers](https://bliptext.com/articles/natural-number), but all [ordinals](https://bliptext.com/articles/ordinal-number).\nIn fact, the sequence is too long for the set P; there are too many ordinals (a [proper class](https://bliptext.com/articles/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.\nThe ai are defined by [transfinite recursion](https://bliptext.com/articles/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}).\nBecause the av are totally ordered, this is a well-founded definition.\nThe above proof can be formulated without explicitly referring to ordinals by considering the initial segments {av : v < w} as subsets of P.\nSuch sets can be easily characterized as well-ordered chains S ⊆ P where each x ∈ S satisfies x = b({y ∈ S : y < x}).\nContradiction 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).\nThis proof shows that actually a slightly stronger version of Zorn's lemma is true:\nAlternatively, one can use the same proof for the [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle).\nThis is the proof given for example in Halmos' [Naive Set Theory](https://bliptext.com/articles/naive-set-theory) or in below.\n\n# Proof\nThe basic idea of the proof is to reduce the proof to proving the following weak form of Zorn's lemma:\n(Note that, strictly speaking, (1) is redundant since (2) implies the empty set is in F.) Note the above is a weak form of Zorn's lemma since Zorn's lemma says in particular that any set of subsets satisfying the above (1) and (2) has a maximal element.\nThe point is that, conversely, Zorn's lemma follows from this weak form.\nIndeed, let F be the set of all chains in P. Then it satisfies all of the above properties (it is nonempty since the empty subset is a chain.) Thus, by the above weak form, we find a maximal element C in F; i.e., a maximal chain in P. By the hypothesis of Zorn's lemma, C has an upper bound x in P. Then this x is a maximal element since if y \\ge x, then is larger than C and so.\nThus, y = x.\nThe proof of the weak form is given in [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle).\nIndeed, the existence of a maximal chain is exactly the assertion of the Hausdorff maximal principle.\nThe same proof also shows the following equivalent variant of Zorn's lemma:\nIndeed, trivially, Zorn's lemma implies the above lemma.\nConversely, the above lemma implies the aforementioned weak form of Zorn's lemma, since a union gives a least upper bound.\n\n# Zorn's lemma implies the axiom of choice\nA proof that Zorn's lemma implies the axiom of choice illustrates a typical application of Zorn's lemma.\n(The structure of the proof is exactly the same as the one for the [Hahn–Banach theorem](https://bliptext.com/articles/hahn-banach-theorem).)\nGiven a set X of nonempty sets and its union (which exists by the [axiom of union](https://bliptext.com/articles/axiom-of-union)), we want to show there is a function\nsuch that f(S) \\in S for each S \\in X. For that end, consider the set\nIt is preordered by extension; i.e., f \\le g if and only if f is the restriction of g. If is a chain in P, then we can define the function f on the union by setting when x \\in X_i.\nThis is well-defined since if i < j, then f_i is the restriction of f_j.\nThe function f is also an element of P and is a common extension of all f_i's. Thus, we have shown that each chain in P has an upper bound in P. Hence, by Zorn's lemma, there is a maximal element f in P that is defined on some.\nWe want to show X' = X. Suppose otherwise; then there is a set.\nAs S is nonempty, it contains an element s. We can then extend f to a function g by setting g|_{X'} = f and g(S) = s. (Note this step does not need the axiom of choice.) The function g is in P and f < g, a contradiction to the maximality of f. \\square\nEssentially the same proof also shows that Zorn's lemma implies the [well-ordering theorem](https://bliptext.com/articles/well-ordering-theorem): take P to be the set of all well-ordered subsets of a given set X and then shows a maximal element of P is X.\n\n# History\nThe [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle) is an early statement similar to Zorn's lemma.\n[Kazimierz Kuratowski](https://bliptext.com/articles/kazimierz-kuratowski) proved in 1922 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).\nEssentially the same formulation (weakened by using arbitrary chains, not just well-ordered) was independently given by [Max Zorn](https://bliptext.com/articles/max-august-zorn) in 1935, who proposed it as a new [axiom](https://bliptext.com/articles/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](https://bliptext.com/articles/axiom) of choice in another paper, which never appeared.\nThe name \"Zorn's lemma\" appears to be due to [John Tukey](https://bliptext.com/articles/john-tukey), who used it in his book Convergence and Uniformity in Topology in 1940.\n[Bourbaki](https://bliptext.com/articles/nicolas-bourbaki)'s Théorie des Ensembles of 1939 refers to a similar maximal principle as \"le théorème de Zorn\".\nThe name \"[Kuratowski–Zorn lemma](https://bliptext.com/articles/pl-lemat-kuratowskiego-zorna)\" prevails in Poland and Russia.\n\n# Equivalent forms of Zorn's lemma\nZorn's lemma is equivalent (in [ZF](https://bliptext.com/articles/zermelo-fraenkel-set-theory)) to three main results:\nA well-known joke alluding to this equivalency (which may defy human intuition) is attributed to [Jerry Bona](https://bliptext.com/articles/jerry-bona):\n\"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?\"\nZorn's lemma is also equivalent to the [strong completeness theorem](https://bliptext.com/articles/strong-completeness-theorem) of first-order logic.\nMoreover, Zorn's lemma (or one of its equivalent forms) implies some major results in other mathematical areas.\nFor example,\nIn this sense, Zorn's lemma is a powerful tool, applicable to many areas of mathematics.\n\n## Analogs under weakenings of the axiom of choice\nA 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](https://bliptext.com/articles/axiom-of-dependent-choice)).\nZorn'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.\nAs a result, any proset with exclusively finite chains must have a maximal element.\nMore generally, strengthening the axiom of dependent choice to higher ordinals allows us to generalize the statement in the previous paragraph to higher cardinalities.\nIn 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.\n\n# In popular culture\nThe 1970 film [Zorns Lemma](https://bliptext.com/articles/zorns-lemma-film) is named after the lemma.\nThe lemma was referenced on [The Simpsons](https://bliptext.com/articles/the-simpsons) in the episode \"[Bart's New Friend](https://bliptext.com/articles/bart-s-new-friend)\".","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T17:42:48.968Z","updated_at":"2025-01-25T17:42:48.968Z","search_vector":"'lemma':3 'zorn':1","search_content":" \n \n\n# \n**Zorn's lemma**, also known as the **Kuratowski–Zorn lemma**, is a proposition of [set theory](https://bliptext.com/articles/set-theory).\nIt states that a [preorder](https://bliptext.com/articles/preorder) containing [upper bounds](https://bliptext.com/articles/upper-bound) for every [chain](https://bliptext.com/articles/chain-order-theory) (that is, every [totally ordered](https://bliptext.com/articles/total-order) [subset](https://bliptext.com/articles/subset)) [necessarily](https://bliptext.com/articles/necessity-and-sufficiency) contains at least one [maximal element](https://bliptext.com/articles/maximal-element).\nThe [lemma](https://bliptext.com/articles/lemma-mathematics) was proved (assuming the [axiom of choice](https://bliptext.com/articles/axiom-of-choice)) by [Kazimierz Kuratowski](https://bliptext.com/articles/kazimierz-kuratowski) in 1922 and independently by [Max Zorn](https://bliptext.com/articles/max-august-zorn) in 1935.\nIt occurs in the proofs of several theorems of crucial importance, for instance the [Hahn–Banach theorem](https://bliptext.com/articles/hahn-banach-theorem) in [functional analysis](https://bliptext.com/articles/functional-analysis), the theorem that every [vector space](https://bliptext.com/articles/vector-space) has a [basis](https://bliptext.com/articles/basis-linear-algebra), [Tychonoff's theorem](https://bliptext.com/articles/tychonoff-s-theorem) in [topology](https://bliptext.com/articles/topology) stating that every product of [compact spaces](https://bliptext.com/articles/compact-space) is compact, and the theorems in [abstract algebra](https://bliptext.com/articles/abstract-algebra) that in a [ring](https://bliptext.com/articles/ring-algebra) with identity every proper ideal is contained in a [maximal ideal](https://bliptext.com/articles/maximal-ideal) and that every [field](https://bliptext.com/articles/field-mathematics) has an [algebraic closure](https://bliptext.com/articles/algebraic-closure).\nZorn's lemma is equivalent to the [well-ordering theorem](https://bliptext.com/articles/well-ordering-theorem) and also to the [axiom of choice](https://bliptext.com/articles/axiom-of-choice), in the sense that within ZF ([Zermelo–Fraenkel set theory](https://bliptext.com/articles/zermelo-fraenkel-set-theory) without the [axiom of choice](https://bliptext.com/articles/axiom-of-choice)) any one of the three is sufficient to prove the other two.\nAn earlier formulation of Zorn's lemma is the [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle), which states that every chain is contained in a maximal chain.\n# [Zorn's lemma can be used to show that every connected graph has a 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. Zorn's lemma is not needed for finite graphs, such as the one pictured here. | upload.wikimedia.org/wikipedia/commons/d/d4/4x4///grid///spanning///tree.svg]\n\n# Motivation\nTo prove the existence of a mathematical object that can be viewed as a maximal element in some [preorder](https://bliptext.com/articles/preorder) in some way, one can try proving the existence of such an object by assuming there is no maximal element and using [transfinite induction](https://bliptext.com/articles/transfinite-induction) and the assumptions of the situation to get a contradiction.\nZorn'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.\n\"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.\"\n- William Timothy Gowers\n\n# Statement of the lemma\nPreliminary notions:\nZorn's lemma can then be stated as:\nVariants of this formulation are sometimes used, such as requiring that the set P and its chains be non-empty.\nAlthough 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.\nThen the empty subset of P is a chain, as it satisfies the definition [vacuously](https://bliptext.com/articles/vacuous-truth); 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.\nConversely, 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).\nThe 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.\nSo, many authors prefer to verify the non-emptiness of the set P rather than deal with the empty chain in the general argument.\n\n# Example applications\n\n## Every vector space has a basis\nZorn's lemma can be used to show that every [vector space](https://bliptext.com/articles/vector-space) V has a [basis](https://bliptext.com/articles/basis-linear-algebra).\nIf V = {**0**}, then the empty set is a basis for V.\nNow, suppose that V ≠ {**0**}.\nLet P be the set consisting of all [linearly independent](https://bliptext.com/articles/linear-independence) subsets of V.\nSince V is not the zero ****v****ector space, there exists a nonzero element ****v**** of V, so P contains the linearly independent subset {****v****}.\nFurthermore, P is preordered by [set inclusion](https://bliptext.com/articles/subset) (see [inclusion order](https://bliptext.com/articles/inclusion-order)).\nFinding a maximal linearly independent subset of V is the same as finding a maximal element in P.\nTo apply Zorn's lemma, take a chain T in P (that is, T is a subset of P that is totally ordered).\nIf T is the empty set, then {**v**} is an upper bound for T in P.\nSuppose then that T is non-empty.\nWe 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.\nTake B to be the [union](https://bliptext.com/articles/union-set-theory) of all the sets in T.\nWe wish to show that B is an upper bound for T in P.\nTo do this, it suffices to show that B is a linearly independent subset of V.\nSuppose otherwise, that B is not linearly independent.\nThen there exists ******v******ectors ******v******1, ******v******2, ..., ******v******k ∈ B and [scalars](https://bliptext.com/articles/scalar-mathematics) a1, a2, ..., ak, not all zero, such that\nSince B is the union of all the sets in T, there are some sets S1, S2, ..., Sk ∈ T such that **v**i ∈ Si for e**v**ery i = 1, 2, ..., k.\nAs 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 ******v******1, ******v******2, ..., ******v******k. This tells us there is a linearly dependent set of ******v******ectors in Si, contradicting that Si is linearly independent (because it is a member of P).\nThe 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.\nFinally, we show that B is indeed a basis of V.\nIt suffices to show that B is a [spanning set](https://bliptext.com/articles/linear-span) of V.\nSuppose for the sake of contradiction that B is not spanning.\nThen there exists some **v** ∈ V not co**v**ered by the span of B.\nThis says that B ∪ {**v**} is a linearly independent subset of V that is larger than B, contradicting the maximality of B.\nTherefore, B is a spanning set of V, and thus, a basis of V.\n\n## Every nontrivial ring with unity contains a maximal ideal\nZorn's lemma can be used to show that every nontrivial [ring](https://bliptext.com/articles/ring-mathematics) R with [unity](https://bliptext.com/articles/unital-ring) contains a [maximal ideal](https://bliptext.com/articles/maximal-ideal).\nLet P be the set consisting of all proper [ideals](https://bliptext.com/articles/ideal-ring-theory) in R (that is, all [ideals](https://bliptext.com/articles/ideal-ring-theory) in R except R itself).\nSince R is non-trivial, the set P contains the trivial ideal {0}.\nFurthermore, P is preordered by set inclusion.\nFinding a maximal ideal in R is the same as finding a maximal element in P.\nTo apply Zorn's lemma, take a chain T in P.\nIf T is empty, then the trivial ideal {0} is an upper bound for T in P.\nAssume then that T is non-empty.\nIt 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).\nTake I to be the union of all the ideals in T.\nWe wish to show that I is an upper bound for T in P.\nWe will first show that I is an ideal of R.\nFor I to be an ideal, it must satisfy three conditions:\n#1 - I is a nonempty subset of R.\nBecause T contains at least one element, and that element contains at least 0, the union I contains at least 0 and is not empty.\nEvery element of T is a subset of R, so the union I only consists of elements in R.\n#2 - For every x, y ∈ I, the sum x + y is in I.\nSuppose x and y are elements of I.\nThen there exist two ideals J, K ∈ T such that x is an element of J and y is an element of K.\nSince T is totally ordered, we know that J ⊆ K or K ⊆ J.\n[Without loss of generality](https://bliptext.com/articles/without-loss-of-generality), assume the first case.\nBoth 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.\n#3 - For every r ∈ R and every x ∈ I, the product rx is in I.\nSuppose x is an element of I.\nThen there exists an ideal J ∈ T such that x is in J.\nIf r ∈ R, then rx is an element of J and hence an element of I.\nThus, I is an ideal in R.\nNow, we show that I is a proper ideal.\nAn ideal is equal to R [if and only if](https://bliptext.com/articles/if-and-only-if) it contains 1.\n(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.\nThe 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.\n\n# Proof sketch\nA sketch of the proof of Zorn's lemma follows, assuming the [axiom of choice](https://bliptext.com/articles/axiom-of-choice).\nSuppose the lemma is false.\nThen there exists a proset 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.\nFor 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.\nTo actually define the [function](https://bliptext.com/articles/function-mathematics) b, we need to employ the axiom of choice (explicitly: let, that is, the set of upper bounds for T. The axiom of choice furnishes ).\nUsing the function b, we are going to define elements a0 < a1 < a2 < a3 < ... < aω < aω+1 <…, in P.\nThis uncountable sequence is **really long**: the indices are not just the [natural numbers](https://bliptext.com/articles/natural-number), but all [ordinals](https://bliptext.com/articles/ordinal-number).\nIn fact, the sequence is too long for the set P; there are too many ordinals (a [proper class](https://bliptext.com/articles/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.\nThe ai are defined by [transfinite recursion](https://bliptext.com/articles/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}).\nBecause the av are totally ordered, this is a well-founded definition.\nThe above proof can be formulated without explicitly referring to ordinals by considering the initial segments {av : v < w} as subsets of P.\nSuch sets can be easily characterized as well-ordered chains S ⊆ P where each x ∈ S satisfies x = b({y ∈ S : y < x}).\nContradiction 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).\nThis proof shows that actually a slightly stronger version of Zorn's lemma is true:\nAlternatively, one can use the same proof for the [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle).\nThis is the proof given for example in Halmos' [Naive Set Theory](https://bliptext.com/articles/naive-set-theory) or in below.\n\n# Proof\nThe basic idea of the proof is to reduce the proof to proving the following weak form of Zorn's lemma:\n(Note that, strictly speaking, (1) is redundant since (2) implies the empty set is in F.) Note the above is a weak form of Zorn's lemma since Zorn's lemma says in particular that any set of subsets satisfying the above (1) and (2) has a maximal element.\nThe point is that, conversely, Zorn's lemma follows from this weak form.\nIndeed, let F be the set of all chains in P. Then it satisfies all of the above properties (it is nonempty since the empty subset is a chain.) Thus, by the above weak form, we find a maximal element C in F; i.e., a maximal chain in P. By the hypothesis of Zorn's lemma, C has an upper bound x in P. Then this x is a maximal element since if y \\ge x, then is larger than C and so.\nThus, y = x.\nThe proof of the weak form is given in [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle).\nIndeed, the existence of a maximal chain is exactly the assertion of the Hausdorff maximal principle.\nThe same proof also shows the following equivalent variant of Zorn's lemma:\nIndeed, trivially, Zorn's lemma implies the above lemma.\nConversely, the above lemma implies the aforementioned weak form of Zorn's lemma, since a union gives a least upper bound.\n\n# Zorn's lemma implies the axiom of choice\nA proof that Zorn's lemma implies the axiom of choice illustrates a typical application of Zorn's lemma.\n(The structure of the proof is exactly the same as the one for the [Hahn–Banach theorem](https://bliptext.com/articles/hahn-banach-theorem).)\nGiven a set X of nonempty sets and its union (which exists by the [axiom of union](https://bliptext.com/articles/axiom-of-union)), we want to show there is a function\nsuch that f(S) \\in S for each S \\in X. For that end, consider the set\nIt is preordered by extension; i.e., f \\le g if and only if f is the restriction of g. If is a chain in P, then we can define the function f on the union by setting when x \\in X_i.\nThis is well-defined since if i < j, then f_i is the restriction of f_j.\nThe function f is also an element of P and is a common extension of all f_i's. Thus, we have shown that each chain in P has an upper bound in P. Hence, by Zorn's lemma, there is a maximal element f in P that is defined on some.\nWe want to show X' = X. Suppose otherwise; then there is a set.\nAs S is nonempty, it contains an element s. We can then extend f to a function g by setting g|_{X'} = f and g(S) = s. (Note this step does not need the axiom of choice.) The function g is in P and f < g, a contradiction to the maximality of f. \\square\nEssentially the same proof also shows that Zorn's lemma implies the [well-ordering theorem](https://bliptext.com/articles/well-ordering-theorem): take P to be the set of all well-ordered subsets of a given set X and then shows a maximal element of P is X.\n\n# History\nThe [Hausdorff maximal principle](https://bliptext.com/articles/hausdorff-maximal-principle) is an early statement similar to Zorn's lemma.\n[Kazimierz Kuratowski](https://bliptext.com/articles/kazimierz-kuratowski) proved in 1922 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).\nEssentially the same formulation (weakened by using arbitrary chains, not just well-ordered) was independently given by [Max Zorn](https://bliptext.com/articles/max-august-zorn) in 1935, who proposed it as a new [axiom](https://bliptext.com/articles/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](https://bliptext.com/articles/axiom) of choice in another paper, which never appeared.\nThe name \"Zorn's lemma\" appears to be due to [John Tukey](https://bliptext.com/articles/john-tukey), who used it in his book Convergence and Uniformity in Topology in 1940.\n[Bourbaki](https://bliptext.com/articles/nicolas-bourbaki)'s Théorie des Ensembles of 1939 refers to a similar maximal principle as \"le théorème de Zorn\".\nThe name \"[Kuratowski–Zorn lemma](https://bliptext.com/articles/pl-lemat-kuratowskiego-zorna)\" prevails in Poland and Russia.\n\n# Equivalent forms of Zorn's lemma\nZorn's lemma is equivalent (in [ZF](https://bliptext.com/articles/zermelo-fraenkel-set-theory)) to three main results:\nA well-known joke alluding to this equivalency (which may defy human intuition) is attributed to [Jerry Bona](https://bliptext.com/articles/jerry-bona):\n\"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?\"\nZorn's lemma is also equivalent to the [strong completeness theorem](https://bliptext.com/articles/strong-completeness-theorem) of first-order logic.\nMoreover, Zorn's lemma (or one of its equivalent forms) implies some major results in other mathematical areas.\nFor example,\nIn this sense, Zorn's lemma is a powerful tool, applicable to many areas of mathematics.\n\n## Analogs under weakenings of the axiom of choice\nA 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](https://bliptext.com/articles/axiom-of-dependent-choice)).\nZorn'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.\nAs a result, any proset with exclusively finite chains must have a maximal element.\nMore generally, strengthening the axiom of dependent choice to higher ordinals allows us to generalize the statement in the previous paragraph to higher cardinalities.\nIn 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.\n\n# In popular culture\nThe 1970 film [Zorns Lemma](https://bliptext.com/articles/zorns-lemma-film) is named after the lemma.\nThe lemma was referenced on [The Simpsons](https://bliptext.com/articles/the-simpsons) in the episode \"[Bart's New Friend](https://bliptext.com/articles/bart-s-new-friend)\".","revisionCount":0},"hasMore":false,"nextCursor":null}