The Ascent to the Top: A Guide to Zorn's Lemma and its Equivalence to the Axiom of Choice

Zorn's Lemma is a fundamental principle in mathematics that provides a powerful criterion for guaranteeing the existence of 'maximal' elements. It states that if a non-empty partially ordered set has the property that every chain (a totally ordered subset) has an upper bound within the set, then the set must contain at least one maximal element. A maximal element is one that cannot be strictly 'less than' any other element in the set. The lemma is celebrated for its ability to handle infinite sets where simple induction fails. The true significance of Zorn's Lemma lies in its relationship with the Axiom of Choice (AC), a foundational axiom of set theory. Zorn's Lemma, the Axiom of Choice, and the Well-Ordering Theorem are all logically equivalent. This means that assuming any one of them allows you to prove the other two. This equivalence provides mathematicians with a versatile toolkit; they can choose the principle that is most elegantly applied to the problem at hand. Zorn's Lemma is often the most convenient tool for proofs in algebra and analysis. Its utility is best demonstrated through applications, the most famous of which is proving that every vector space has a basis. By constructing a poset of linearly independent sets, Zorn's Lemma guarantees the existence of a maximal such set, which can then be shown to be a basis. This non-constructive proof—it proves existence without providing a method of construction—is a hallmark of Zorn's Lemma and the Axiom of Choice, and while once a source of philosophical debate, it is now an indispensable part of the standard framework (ZFC) of modern mathematics.

1. Introduction: The Power of Choice

In the foundational landscape of modern mathematics, a few principles stand out for their profound and far-reaching consequences. One of the most famous, and historically controversial, is the Axiom of Choice (AC). It seems intuitively obvious: if you have a collection of non-empty bins, you can pick one item from each bin. However, when this collection is infinite, the act of 'choosing' becomes non-trivial. The Axiom of Choice asserts that such a simultaneous choice is always possible, even without a rule to specify the choice.

While powerful, the Axiom of Choice can be awkward to apply directly. Fortunately, it has several equivalent formulations that are often more convenient in practice. The most celebrated of these is Zorn's Lemma (ZL). This lesson will demystify Zorn's Lemma, explain the prerequisite concepts, demonstrate its power through a cornerstone proof in linear algebra, and finally, explore its deep connection to the Axiom of Choice.

2. The Building Blocks: Posets, Chains, and Maximal Elements

To understand Zorn's Lemma, we first need to define the stage on which it operates: the partially ordered set.

• Partially Ordered Set (Poset): A poset is a pair (P, ≤), where P is a set and ≤ is a binary relation on P that is:

1. Reflexive: For all a ∈ P, a ≤ a. 2. Antisymmetric: For all a, b ∈ P, if a ≤ b and b ≤ a, then a = b. 3. Transitive: For all a, b, c ∈ P, if a ≤ b and b ≤ c, then a ≤ c.

Example: Let S = {1, 2, 3}. The power set of S, denoted P(S), is the set of all subsets of S. (P(S), ⊆) is a poset, where ⊆ is the subset relation. For example, {1} ⊆ {1, 2}, but {1} and {2, 3} are not comparable.

• Chain: A subset C of a poset P is a chain if it is totally ordered. This means for any two elements a, b ∈ C, either a ≤ b or b ≤ a.

• Upper Bound: Let S be a subset of a poset P. An element u ∈ P is an upper bound for S if s ≤ u for all s ∈ S. Note that the upper bound u does not have to be in S itself.

• Maximal Element: An element m ∈ P is a maximal element if there is no other element x ∈ P such that m ≤ x and m ≠ x. In other words, you cannot go 'higher' than m. A poset can have many maximal elements. This is distinct from a maximum element, which would be an element M such that x ≤ M for all x ∈ P.

3. The Statement of Zorn's Lemma

With the terminology in place, we can now state the lemma:

Zorn's Lemma (ZL): If a non-empty partially ordered set P has the property that every chain in P has an upper bound in P, then P has at least one maximal element.

This is a powerful existence theorem. It doesn't tell you how to find the maximal element; it just guarantees that one exists if the condition is met. The core idea is that the 'every chain has an upper bound' condition prevents you from climbing forever without reaching a 'top'.

4. Application: Every Vector Space Has a Basis

One of the most famous applications of Zorn's Lemma is proving that every vector space V (even infinite-dimensional ones) has a basis. A basis is a linearly independent set that spans the entire space.

The Proof Strategy: We will construct a poset where the maximal elements are precisely the bases of the vector space. Zorn's Lemma will then guarantee the existence of such a maximal element.

1. Define the Poset: Let V be a vector space over a field F. Let P be the set of all linearly independent subsets of V. We order P by set inclusion, ⊆. So (P, ⊆) is our poset.

1. Verify the ZL Hypothesis:

- P is non-empty: The empty set ∅ is linearly independent, so ∅ ∈ P. (If V is not the zero vector space, any set {v} with v ≠ 0 is also in P). - Let C be any chain in P. C is a collection of linearly independent subsets of V, {S_i}, such that for any S_i, S_j ∈ C, either S_i ⊆ S_j or S_j ⊆ S_i. - We need an upper bound for C in P. Let U = ⋃_{S_i ∈ C} S_i (the union of all sets in the chain). By definition, S_i ⊆ U for all S_i ∈ C, so U is an upper bound. But is U in P? We must show U is linearly independent. - Take any finite set of vectors {v_1, ..., v_n} ⊆ U and scalars {c_1, ..., c_n} ⊆ F such that c_1v_1 + ... + c_nv_n = 0. Each v_k comes from some set S_{i_k} in the chain C. Since there are finitely many such sets and C is a chain, one of them, say S_L, must contain all the others. Therefore, {v_1, ..., v_n} ⊆ S_L. Since S_L is in P, it is linearly independent, which means all scalars c_k must be zero. This proves U is linearly independent, so U ∈ P.

1. Apply Zorn's Lemma: The hypothesis holds. Zorn's Lemma tells us that P must have a maximal element. Let's call it B.

1. Show the Maximal Element is a Basis: We know B is a maximal element of P, which means it is a linearly independent set that cannot be extended to a larger linearly independent set by adding another vector from V.

- B is linearly independent by definition of P. - We must show B spans V. Suppose, for contradiction, that it doesn't. Then there exists a vector w ∈ V such that w is not in the span of B. This implies that the set B' = B ∪ {w} is linearly independent. But this is a contradiction! B' is a linearly independent set and B is a proper subset of B'. This contradicts the fact that B is a maximal element in P. - Therefore, our assumption was wrong. B must span V.

Since B is linearly independent and spans V, B is a basis for V.

5. Equivalence with the Axiom of Choice

Zorn's Lemma does not exist in a vacuum. It is one of the 'big three' equivalent statements that dominate this area of set theory, all of which are provable from each other (within ZF set theory).

1. The Axiom of Choice (AC): For any collection C of non-empty sets, there exists a function f (a 'choice function') such that for each set S ∈ C, f(S) ∈ S.
2. The Well-Ordering Theorem (WOT): Every set can be well-ordered. (A well-ordering is a total ordering where every non-empty subset has a least element).
3. Zorn's Lemma (ZL): As stated above.

AC ⇔ ZL ⇔ WOT

The proof of AC ⇒ ZL is quite complex and is a staple of graduate-level set theory courses. However, the proof of ZL ⇒ AC is more accessible and elegantly demonstrates the utility of the lemma.

Sketch of Proof: Zorn's Lemma ⇒ Axiom of Choice

• Goal: Given a collection of non-empty sets {X_i}_{i∈I}, we want to prove the existence of a choice function f: I → ⋃X_i with f(i) ∈ X_i.
• Setup: Consider the set P of all 'partial choice functions'. A function g is in P if its domain is a subset of I, and for every j in its domain, g(j) ∈ X_j.
• Poset: We order P by function extension. g ≤ h if dom(g) ⊆ dom(h) and g(j) = h(j) for all j ∈ dom(g). This is a partial order.
• Verify ZL Hypothesis: Given a chain C of partial choice functions in P, their 'union' (a function whose graph is the union of their graphs) is a well-defined partial choice function and is an upper bound for the chain.
• Apply ZL: Zorn's Lemma guarantees a maximal partial choice function, f_max.
• Conclusion: The domain of f_max must be all of I. If not, say k ∈ I is not in its domain, we could create a new, larger partial choice function by picking an element from the non-empty set X_k and adding the pair (k, x_k) to f_max. This would contradict the maximality of f_max. Therefore, dom(f_max) = I, and f_max is the desired total choice function.

Browse public study notes