Zorn's lemma

Every vector space has a basis

Zorn's lemma can be used to show that every vector space V has a basis.^[14]

If V = {0}, then the empty set is a basis for V. Now, suppose that V ≠ {0}. Let P be the set consisting of all linearly independent subsets of V. Since V is not the zero vector space, there exists a nonzero element v of V, so P contains the linearly independent subset {v}. Furthermore, P is partially ordered by set inclusion (see inclusion order). Finding a maximal linearly independent subset of V is the same as finding a maximal element in P.

To apply Zorn's lemma, take a chain T in P (that is, T is a subset of P that is totally ordered). If T is the empty set, then {v} is an upper bound for T in P. Suppose then that T is non-empty. We need to show that T has an upper bound, that is, there exists a linearly independent subset B of V containing all the members of T.

Take B to be the union of all the sets in T. We wish to show that B is an upper bound for T in P. To do this, it suffices to show that B is a linearly independent subset of V.

Suppose otherwise, that B is not linearly independent. Then there exists vectors v₁, v₂, ..., v_k ∈ B and scalars a₁, a₂, ..., a_k, not all zero, such that

${\displaystyle a_{1}\mathbf {v} _{1}+a_{2}\mathbf {v} _{2}+\cdots +a_{k}\mathbf {v} _{k}=\mathbf {0} .}$

Since B is the union of all the sets in T, there are some sets S₁, S₂, ..., S_k ∈ T such that v_i ∈ S_i for every i = 1, 2, ..., k. As T is totally ordered, one of the sets S₁, S₂, ..., S_k must contain the others, so there is some set S_i that contains all of v₁, v₂, ..., v_k. This tells us there is a linearly dependent set of vectors in S_i, contradicting that S_i is linearly independent (because it is a member of P).

The hypothesis of Zorn's lemma has been checked, and thus there is a maximal element in P, in other words a maximal linearly independent subset B of V.

Finally, we show that B is indeed a basis of V. It suffices to show that B is a spanning set of V. Suppose for the sake of contradiction that B is not spanning. Then there exists some v ∈ V not covered by the span of B. This says that B ∪ {v} is a linearly independent subset of V that is larger than B, contradicting the maximality of B. Therefore, B is a spanning set of V, and thus, a basis of V.

Remark: While less common, it is possible to construct a basis somehow more directly using transfinite recursion, still assuming the axiom of choice. For that, see for example Transfinite recursion theorem § Example: a basis construction as a comparison.

Every nontrivial ring with unity contains a maximal ideal

Zorn's lemma can be used to show that every nontrivial ring R with unity contains a maximal ideal.

Let P be the set consisting of all proper ideals in R (that is, all ideals in R except R itself). Since R is non-trivial, the set P contains the trivial ideal {0}. Furthermore, P is partially ordered by set inclusion. Finding a maximal ideal in R is the same as finding a maximal element in P.

To apply Zorn's lemma, take a chain T in P. If T is empty, then the trivial ideal {0} is an upper bound for T in P. Assume then that T is non-empty. It is necessary to show that T has an upper bound, that is, there exists an ideal I ⊆ R containing all the members of T but still smaller than R (otherwise it would not be a proper ideal, so it is not in P).

Take I to be the union of all the ideals in T. We wish to show that I is an upper bound for T in P. We will first show that I is an ideal of R. For I to be an ideal, it must satisfy three conditions:

1. I is a nonempty subset of R,
2. For every x, y ∈ I, the sum x + y is in I,
3. For every r ∈ R and every x ∈ I, the product rx is in I.

#1 - I is a nonempty subset of R.

Because T contains at least one element, and that element contains at least 0, the union I contains at least 0 and is not empty. Every element of T is a subset of R, so the union I only consists of elements in R.

#2 - For every x, y ∈ I, the sum x + y is in I.

Suppose x and y are elements of I. Then there exist two ideals J, K ∈ T such that x is an element of J and y is an element of K. Since T is totally ordered, we know that J ⊆ K or K ⊆ J. Without loss of generality, assume the first case. Both x and y are members of the ideal K, therefore their sum x + y is a member of K, which shows that x + y is a member of I.

#3 - For every r ∈ R and every x ∈ I, the product rx is in I.

Suppose x is an element of I. Then there exists an ideal J ∈ T such that x is in J. If r ∈ R, then rx is an element of J and hence an element of I. Thus, I is an ideal in R.

Now, we show that I is a proper ideal. An ideal is equal to R if and only if it contains 1. (It is clear that if it is R then it contains 1; on the other hand, if it contains 1 and r is an arbitrary element of R, then r1 = r is an element of the ideal, and so the ideal is equal to R.) So, if I were equal to R, then it would contain 1, and that means one of the members of T would contain 1 and would thus be equal to R – but R is explicitly excluded from P.

The hypothesis of Zorn's lemma has been checked, and thus there is a maximal element in P, in other words a maximal ideal in R.

A proof of Tychonoff's theorem

Zorn's lemma implies the ultrafilter lemma, which in turn implies Tychonoff's theorem (together with the axiom of choice). However, it is also possible to prove Tychonoff's theorem directly from Zorn's lemma as follows (by using an ultrafilter implicitly).^[15]

Let ${\displaystyle X_{i}}$ be a family of compact spaces, not necessarily Hausdorff. We shall show that a family ${\displaystyle F}$ of closed subsets of ${\displaystyle X:=\prod _{i}X_{i}}$ with the finite intersection property has nonempty intersection. Let ${\displaystyle P}$ be the collection of all the families of subsets of ${\displaystyle X}$ with the finite intersection property (not necessarily closed subsets). We let ${\displaystyle P}$ be ordered by set inclusion. If ${\displaystyle C\subset P}$ is a chain, then clearly the union of ${\displaystyle C}$ has the finite intersection property; so, the union is in ${\displaystyle P}$. Thus, by Zorn's lemma, there is a maximal element ${\displaystyle M}$ in ${\displaystyle P}$ containing ${\displaystyle F}$. We shall show that the intersection of all the closed sets in ${\displaystyle M}$ has nonempty intersection; a fortiori, ${\displaystyle F}$ has nonempty intersection.

For each finite subset ${\displaystyle M'\subset M}$, since ${\displaystyle \cap M'}$ is nonempty, ${\displaystyle \cap p_{i}(M')}$ is nonempty for the projection ${\displaystyle p_{i}:X\to X_{i}.}$ Thus, for each ${\displaystyle i}$, the set

${\displaystyle N_{i}:=\left\{{\overline {p_{i}(A)}}\mid A\in M\right\}}$

has nonempty intersection since it has the finite intersection property and ${\displaystyle X_{i}}$ is compact. We note

1. If ${\displaystyle M'\subset M}$ is a finite subset, ${\displaystyle \cap M'}$ is in ${\displaystyle M}$.
2. For an open set ${\displaystyle U_{i}}$ intersecting ${\displaystyle \cap N_{i}}$, we have ${\displaystyle p_{i}^{-1}(U_{i})}$ is in ${\displaystyle M}$.

Indeed, (1) holds since ${\displaystyle M=M\cup \{\cap M'\}}$ by maximality, as the set on the right has the finite intersection property. Similarly, for a finite subset ${\displaystyle M'\subset M}$, since ${\displaystyle A=\cap M'}$ is in ${\displaystyle M}$, ${\displaystyle U_{i}\cap p_{i}(A)\neq \emptyset }$ or ${\displaystyle p_{i}^{-1}(U_{i})\cap A\neq \emptyset }$. Thus, the set ${\displaystyle M\cup \{p_{i}^{-1}(U_{i})\}}$ has the finite intersection property and (2) follows by the maximality of ${\displaystyle M}$.

Now, by the axiom of choice, we can find an element ${\displaystyle m}$ in ${\displaystyle \prod _{i}(\cap N_{i})}$. We claim this ${\displaystyle m}$ is in each closed set ${\displaystyle A}$ in ${\displaystyle M}$. Since ${\displaystyle A}$ is closed, it is enough to show ${\displaystyle m}$ is in the closure of ${\displaystyle A}$; i.e., each basic neighborhood of ${\displaystyle m}$ intersects ${\displaystyle A}$. A basic neighborhood of ${\displaystyle m}$ has the form ${\displaystyle \cap _{j=1}^{r}p_{i_{j}}^{-1}(U_{i_{j}})}$. But by the property (2) above, we have ${\displaystyle \left\{A,p_{i_{j}}^{-1}(U_{i_{j}})\mid j=1,\dots ,r\right\}\subset M}$, which gives the claim by the finite intersection property. ${\displaystyle \square }$

Remark: The ultrafilter lemma is strictly weaker than the axiom of choice; it is equivalent to the boolean prime ideal theorem. On the other hand, somehow surprisingly, Tychonoff's theorem implies (thus is equivalent to) the axiom of choice. Hence, the use of AC above cannot be eliminated. (If ${\displaystyle X_{i}}$ are compact Hausdorff, then the use of AC can be eliminated; indeed, each ${\displaystyle \cap p_{i}(M)}$ above has exactly one point in that case.)

An alternative (perhaps more standard) proof of Tychonoff's theorem is to first prove Alexander's subbase lemma, but the proof of that lemma typically uses Zorn's lemma.

Proof by transfinite recursion

Suppose Zorn's 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 (explicitly: let ${\displaystyle B(T)=\{b\in P:\forall t\in T,b>t\}}$, which is non-empty by the argument above. The axiom of choice furnishes ${\displaystyle b:b(T)\in B(T)}$).

Using the function b, we are going to define elements a₀ < a₁ < a₂ < a₃ < ... < a_ω < a_ω+1 <…, in P. This uncountable 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 (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_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.^{[clarification needed]} (See also Transfinite recursion theorem § Example: a proof of Zorn's lemma for more details on this recursive construction.)

The above proof can be formulated without explicitly referring to ordinals by considering the initial segments {a_v : 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), an argument originally due to Kneser.^[19][20] (cf. Bourbaki–Witt theorem § Proof 3)

This proof shows that actually a slightly stronger version of Zorn's lemma is true:

Proof from the Hausdorff maximal principle

The Hausdorff maximal principle is an alternative formulation of Zorn's lemma asserting that every partially ordered set ⁠${\displaystyle P}$⁠ has a maximal chain ⁠${\displaystyle C\subseteq P}$⁠ with respect to set inclusion. (In fact, the usual form of the Hausdorff maximal principle is slightly stronger, stating that for every chain ⁠${\displaystyle C_{0}\subseteq P}$⁠ there exists a maximal chain ⁠${\displaystyle C}$⁠ such that ⁠${\displaystyle C_{0}\subseteq C}$⁠.)

The usual form of Zorn's lemma follows from the Hausdorff maximal principle, since if ⁠${\displaystyle P}$⁠ satisfies the hypothesis of Zorn's lemma, then its maximal chain ⁠${\displaystyle C}$⁠ also has an upper bound ⁠${\displaystyle x}$⁠ in ⁠${\displaystyle P}$⁠. This ⁠${\displaystyle x}$⁠ is a maximal element since if ⁠${\displaystyle y>x}$⁠, then ⁠${\displaystyle {\widetilde {C}}=C\cup \{y\}}$⁠ is a strictly larger chain than ⁠${\displaystyle C}$⁠, contradicting the maximality of ⁠${\displaystyle C}$⁠.^[21]

Conversely, the Hausdorff maximal principle also follows from Zorn's lemma by regarding the set of admissible chains (chains that contain ⁠${\displaystyle C_{0}}$⁠) as a partially ordered set ordered by set inclusion. In fact, this specific case only needs the following weak form of Zorn's lemma:^[22]

Or the following even weaker form:

(Note that, strictly speaking, (1) is redundant since (2) implies the empty set is in ${\displaystyle F}$.) This is a weaker form since that the union of each chain of ⁠${\displaystyle F}$⁠ is a least upper bound of that chain. This cycle of implications (Zorn's lemma ⇒ Lemma 1 ⇒ Lemma 2 ⇒ Hausdorff maximal principle ⇒ Zorn's lemma) shows that all these forms are in fact equivalent.

Lemma 2 can be directly proved from the axiom of choice, as shown in Hausdorff maximal principle § Proof 1.

The Bourbaki–Witt theorem can also be used to give a proof of the Hausdorff maximal principle; see Hausdorff maximal principle § Proof 2.

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.^[33]

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