Zorn’s Lemma

Some objects are built one piece at a time: an injection one pair at a time, a set of representatives one class at a time, a total order one comparison at a time. When the pieces can be listed, induction finishes the job, one step for each natural number. When they cannot, as for the elements of $\mathbb{R}$ , the words “and so on” stand in for a step that is never given, and that is not a proof. Zorn’s lemma is the principle that replaces them. If every unfinished partial object can be enlarged, and every growing chain of partial objects has a partial object above it, then there is one that cannot be enlarged, and it is complete.

The chapter states the lemma and says why it is not proved here: it is equivalent to the axiom of choice of Chapter 3, and this volume proves only the half that gives choice. It turns the lemma into a single method of proof, the maximality template, and runs the template four times. The third run settles the question Section 3.4 left open: any two sets are comparable in size.

What you need. Logic and Proof, Chapters 1–8, in particular the rule $\mathrm{\exists E}$ (Logic and Proof, Definition 5.6.1) and the catalogue of what is not allowed (Logic and Proof, Example (What is not allowed)), above all (N13), “an ‘and so on’ needs its step”. From this volume: Section 4.3 on orders (Definition 4.3.1, Example (Inclusion is a partial order, rarely total), Definition 4.3.2, Definition 4.3.3, Definition 4.3.4, Proposition 4.3.2, Example (Maximal elements that are not greatest), Proposition 4.3.1); Section 4.2 on equivalence relations (Definition 4.2.1, Definition 4.2.2, Theorem 4.2.1, Example (The reals modulo the integers)); Chapter 3 on sizes and choice (Axiom 3.2.1, Section 3.2’s method box Example (Method: name the choice), Definition 3.4.1, Theorem 3.4.3, Proposition 3.4.2, Proposition 3.1.4, Proposition 3.1.5, Theorem 3.3.4); Section 2.5 on finite sets (Proposition 2.5.6, Example (Hilbert’s Hotel), Proposition 2.5.5, Corollary 2.5.3, Proposition 2.5.1); Sections 2.1–2.2 (Theorem 2.1.3, Theorem 2.2.1); Chapter 1 (Definition 1.1.2, Definition 1.4.3, Definition 1.5.1). Proof methods: proof by contradiction (Example (Method: choosing direct, contrapositive or contradiction), Chapter 2) and disproof by counterexample (Example (Method: disproof by counterexample, proof by example), Chapter 1).

Time. About 10 hours on the core track (all of A, one B and one C per section, the exit checks); about 15 hours for everything.

Roadmap

Chains and Zorn’s lemma. A pair-by-pair matching that cannot finish; chains in a partially ordered set, and why finitely many elements of the union of a chain of sets lie in one member; Zorn’s lemma, why each hypothesis is needed, and why it is stated and not proved; the axiom of choice from Zorn’s lemma, as the first run of the maximality template; a set of representatives for any equivalence relation.
Using Zorn’s lemma. Any two sets are comparable, so sizes satisfy trichotomy; every partial order extends to a total order, one added comparison at a time; and, in an optional last subsection, how the same template gives every vector space a basis (Linear Algebra, Section 1.8).

Named moves

The maximality template (Example (Method: the maximality template)). Partial objects ordered by extension; the union of a chain is again a partial object, since each defining condition mentions finitely many elements and these lie in one member of the chain (Lemma 6.1.1); Zorn’s lemma gives a maximal one; a maximal one is complete, since a missing piece would give a strictly larger partial object. (Section 6.1)

Threads

Comparing sizes. Section 3.4 asked whether any two sets are comparable. Section 6.1 opens with a pair-by-pair matching that does not finish, and Section 6.2 finishes it with Zorn’s lemma (Theorem 6.2.1).
Choice. Chapter 3 stated the axiom of choice. Section 6.1 derives it from Zorn’s lemma (Theorem 6.1.3), and Axiomatic Set Theory, Chapter 4 proves the converse.

Summary

A chain is a subset of a partially ordered set on which the order is total (Definition 6.1.1), and finitely many elements of the union of a chain of sets lie in one member (Lemma 6.1.1). Zorn’s lemma (Theorem 6.1.2): a non-empty partially ordered set in which every non-empty chain has an upper bound has a maximal element, usually one of many and not a greatest one. It is stated without proof; it implies the axiom of choice (Theorem 6.1.3), and the converse belongs to Axiomatic Set Theory, Chapter 4. The maximality template (Example (Method: the maximality template)) gives a set of representatives for any equivalence relation (Example (A set of representatives)), shows that any two sets are comparable in size (Theorem 6.2.1), so that exactly one of $\left| A \right| < \left| B \right|$ , $\left| A \right| = \left| B \right|$ , $\left| B \right| < \left| A \right|$ holds (Corollary 6.2.2), and extends every partial order to a total order (Theorem 6.2.4), by adding one comparison at a time (Lemma 6.2.3).

Every object built in this chapter is shown to exist and none is written down: no formula is known for a set of representatives of $\mathbb{R}$ modulo $\mathbb{Q}$ , for an injection between two arbitrary sets, or for a total order containing $\subseteq$ on $\mathcal{P}\left( \mathbb{R} \right)$ . Where a formula exists, as for divisibility on $\mathbb{N}$ (Example (A total order containing divisibility)), it is the better proof.

Terms

chain: a subset in which any two elements are comparable (Definition 6.1.1).
linear extension: a total order containing a given partial order; “linear order” is a synonym of “total order” (Theorem 6.2.4).
maximality template: partial objects, unions of chains, Zorn’s lemma, completeness of a maximal object (Example (Method: the maximality template)).
partial choice function: a set of pairs $(i, x)$ with $x \in A_i$ , at most one for each index (Theorem 6.1.3).
partial matching: a relation $G \subseteq A \times B$ in which each element of $A$ and of $B$ occurs in at most one pair (Theorem 6.2.1).
set of representatives: a set meeting every equivalence class in exactly one element (Example (A set of representatives)).
Zorn’s lemma: a non-empty partially ordered set in which every non-empty chain has an upper bound has a maximal element (Theorem 6.1.2).