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 nonempty $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 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$.

The overall idea is to construct an increasing sequence of chains by inductively extending by an upper bound until you enumerate the whole set. Eventually, we eventually have a chain that contains all the “big” elements of $X$, and so we just take the maximal element in that chain.

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, so by assumption let $u \in X$ be an upper bound for $C _ \alpha$. We aim to show that $u$ is in fact an upper bound for $X$. Suppose $u$ is not maximal, say $u < x$ for some $x \in X$. 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$.

We use the characterisation of Zorn’s lemma that for any non-empty set of sets $A$, if $C \subseteq A$ is a chain then $\bigcup C \in A$.

In this context, let $A$ be the set of all subsets of $S$ of $\mathbb R$ such that

\[S \cup \lbrace \sqrt p \mid p \text{ is prime} \rbrace\]

is linearly independent over $\mathbb Q$; this is indeed a set by comprehension.

$A$ is nonempty, since it contains $\emptyset$ as an element, and the union of any chain is also linearly independent (nontrivial).

Hence $A$ has a maximal element $B$. We must have

\[B \supseteq \lbrace \sqrt p \mid p \text{ is prime} \rbrace\]

or it would not be maximal. If $B$ were not a spanning set and $v$ were not in its span, then $B \cup \lbrace v \rbrace$ would be a bigger linearly independent set, and would be a bigger element of $A$, so $B$ would not be maximal. Hence $B$ is also spanning.

Now there is a unique function $f : \mathbb R \to \mathbb R$ which is a linear transformation when $\mathbb R$ is thought of as a vector space over $\mathbb Q$, and such that $f(\sqrt p) = p$ for all primes $p$ and $f(v) = 0$ for all other elements $v$ of $B$.

@example~ @exam~