Notes - Set Theory HT25, Zorn's lemma

A subset $C \subseteq X$ which is totally ordered by $<$.

An upper bound for $A \subseteq X$ is an element $u \in X$ such that $u \ge a$ for all $a \in A$.

1. If $(X, <)$ is a partially ordered set in which every chain has an upper bound, then $(X, <)$ has a maximal element.
2. If a set $X$ is closed under unions of non-empty chains, meaning $\bigcup C \in X$ for any $C \subseteq X$ which is totally ordered by inclusion, then $X$ has a maximal element with respect to inclusion. (Note that this isn’t saying that $X$ is closed under the union of two chains, it’s saying that the union of any chain is still in $X$)

(1) implies (2):

Let $(X, <)$ be a partial order in which every chain has an upper bound. Since the axiom of choice is equivalent to the well-ordering principle, it follows that there exists a bijection $\theta : \alpha \to X$ for some ordinal $\alpha$.

Define an increasing sequence of chains by transfinite recursion:

• $C _ 0 := \emptyset$
• $C _ {\beta^+} := \begin{cases}C _ \beta \cup \{\theta(\beta)\} &\text{if } \beta \in \alpha \text{ and } \theta(\beta) > x \text{ for all }x \in C _ \beta \\ C _ \beta &\text{otherwise}\end{cases}$
• $C _ \eta := \bigcup _ {\beta \in \eta} C _ \beta$ if $\eta$ is a limit ordinal

Then by transfinite induction, $C _ \beta \subseteq C _ \gamma$ if $\beta \le \gamma$, and each $C _ \beta$ is a chain.

In particular, $C _ \alpha$ is a chain. Then let $u \in X$ be an upper bound for $C _ \alpha$. Suppose $u$ is not maximal, say $x > u$. Then let $\beta = \theta^{-1}(x) \in \alpha$. Then $x = \theta(\beta) \in C _ {\beta^+} \subseteq C _ \alpha$ by definition of $C _ {\beta^+}$, contradicting $u$ being an upper bound for $C _ \alpha$. Hence $u$ is a maximal element and Zorn’s lemma holds.

(2) implies (3):

Suppose $X$ is closed under unions of chains. Then every chain $C$ in the partial order $(X, \subseteq)$ has $\bigcup C$ as an upper bound, so by Zorn’s lemma there is a maximal element.

(3) implies (1):

Let $X$ be a set and let $P’ := \mathcal P(X) \setminus \{\emptyset\}$. Say $h \subseteq P’ \times X$ is a partial choice function for $X$ if it is a function with $\text{dom}(h) \subseteq P’$ such that $h(A) \in A$ for all $A \in \text{dom}(h)$. Then the set of partial choice functions for $X$ is closed under unions of chains. So by (3), a maximal partial choice function $h$ exists.

Now we show that $h$ is a choice function for $X$, i.e. that $\text{dom}(h) = P’$. Suppose not, say $A \in P’ \setminus \text{dom}(h)$. Then $A \ne \emptyset$ by definition of $P’$, so say $a \in A$. But then $h \cup \{\langle A, a\rangle\}$ is a partial choice function properly extending $h$, contradicting the maximality of $h$.