Zorn's Lemma

Prove that every nonempty finite poset has a maximal element (the finite version of Zorn's lemma — no choice axiom needed).

P \ne \varnothing\ \text{finite poset} \ \Rightarrow\ \exists\, m \in P\ \text{maximal}

The divisor poset with the chain

C_0 = \{1, 2, 4, 12\}

highlighted: in this finite poset the proof's "keep climbing" stops at 12.

Show proof

Let $P$ be a nonempty finite poset. Pick any $x_0 \in P$ . If $x_0$ is maximal, we are done. Otherwise some $x_1 \in P$ with $x_0 < x_1$ exists (that is exactly what " $x_0$ is not maximal" means).
Repeat: if $x_k$ is not maximal, pick $x_{k+1}$ with $x_k < x_{k+1}$ . The terms of $x_0 < x_1 < x_2 < \cdots$ are all distinct (antisymmetry and transitivity give $x_i < x_j$ for $i < j$ ). But $P$ is finite, so infinitely many distinct elements cannot be drawn.
Hence the process must stop — some $x_k$ is maximal. Finiteness making "climbing forever" impossible is the entire proof; for infinite posets this argument breaks, and Zorn's lemma (with the axiom of choice) is needed.

In $P = \{1, 2, 3, 4, 6, 12\}$ ordered by divisibility, verify directly that every chain has an upper bound in $P$ , and find all maximal elements.

C\ \text{chain} \ \Rightarrow\ \max C\ \text{exists and bounds}\ C, \qquad \text{maximal}(P) = \{12\}

The chain

C_1 = \{1, 2, 6, 12\}

is highlighted: its only upper bound is

\{12\}

, and 12 is the unique maximal element of the whole poset.

Show proof

Let $C \subseteq P$ be any chain. Since $P$ has only 6 elements, $C$ is finite, and a finite chain has a greatest element $\max C$ (a finite totally ordered subset). Every $c \in C$ satisfies $c \mid \max C$ , so $\max C \in P$ is an upper bound of $C$ . Every chain has an upper bound in $P$ .
Concretely, for the three maximal chains: $C_0 = \{1,2,4,12\}$ has upper bounds $\{12\}$ , $C_1 = \{1,2,6,12\}$ has $\{12\}$ , $C_2 = \{1,3,6,12\}$ has $\{12\}$ (an upper bound of a chain containing 12 must be a multiple of 12, and the only multiple of 12 in $P$ is 12). Shorter chains work the same way: e.g. $\{1, 2\}$ has upper bounds $\{2, 4, 6, 12\}$ and $\{1, 3\}$ has $\{3, 6, 12\}$ .
Maximal elements: $x \in P$ is maximal if no element of $P$ is strictly above it (in divisibility). Since $1 \mid 2$ , $2 \mid 4$ , $3 \mid 6$ , $4 \mid 12$ , $6 \mid 12$ , none of $1, 2, 3, 4, 6$ is maximal. The only multiple of 12 in $P$ is 12 itself, so 12 is maximal — and unique. Exactly as Zorn's lemma promises.

Prove Zorn's lemma implies the axiom of choice: for a family $(X_i)_{i \in I}$ of nonempty sets, apply Zorn's lemma to the poset of partial choice functions. (The converse AC $\Rightarrow$ Zorn is not proved here — it needs transfinite recursion, an idea-level argument.)

P = \{f : \operatorname{dom} f \subseteq I,\ f(i) \in X_i\}, \quad f \le g \iff g\ \text{extends}\ f

The chain

C_2 = \{1, 3, 6, 12\}

is highlighted: Zorn's lemma says "if every chain has an upper bound, a maximal element exists", and the proof below applies exactly this to the problem of finding a choice function.

Show proof

Fix a family $(X_i)_{i \in I}$ of nonempty sets. Order the set $P = \{f : \operatorname{dom} f \subseteq I,\ f(i) \in X_i\}$ of partial choice functions by extension: $f \le g$ means $\operatorname{dom} f \subseteq \operatorname{dom} g$ and $g$ agrees with $f$ on $\operatorname{dom} f$ . $P$ is nonempty (the empty function belongs to it).
For any chain $\mathcal{C}$ in $P$ , let $u = \bigcup \mathcal{C}$ . The chain condition makes $u$ a function: if $f, g \in \mathcal{C}$ are both defined at $i$ , the larger extends the smaller, so $f(i) = g(i)$ . With $\operatorname{dom} u = \bigcup_{f \in \mathcal{C}} \operatorname{dom} f$ and $u(i) \in X_i$ , we get $u \in P$ and $f \le u$ for all $f \in \mathcal{C}$ — $u$ is an upper bound of the chain.
By Zorn's lemma, $P$ has a maximal element $m$ . We show $\operatorname{dom} m = I$ : otherwise some $i_0 \in I \setminus \operatorname{dom} m$ exists, and since $X_{i_0} \ne \varnothing$ , picking $x_0 \in X_{i_0}$ extends $m$ to $m'$ with $m'(i_0) = x_0$ . Then $m < m'$ , contradicting maximality. So $m$ is a choice function defined on all of $I$ — the axiom of choice holds.
Note: the converse (AC $\Rightarrow$ Zorn) needs transfinite recursion along ordinals to grow a chain into a maximal one; it stays an idea-level statement here — the Zorn $\Rightarrow$ AC direction above is proved completely.

Examples & Exercises