Exercise A0.V.3.06

⚠️⚠️⚠️

Definition (initial segment)

An order relation $\leq$ is an initial segment of an order relation $\leq'$ if and only if

1. the ground set of $\leq$ is a subset of the ground set of $\leq'$
2. $\leq$ is a restriction of $\leq'$ to $\operatorname{ground}(\leq)$
3. every element of $\operatorname{ground}(\leq)$ precedes under $\leq'$ every element of $\operatorname{ground}(\leq') \setminus \operatorname{ground}(\leq)$

We write $\leq \preceq \leq'$ whenever $\leq$ is an initial segment of $\leq'.$

Lemma L3.1

Let $Z$ be a non-empty set and let $\mathscr{F}$ be a family of well-ordering relations such that for each $\leq \in \mathscr{F},$ $\operatorname{ground}(\leq) \subseteq Z.$ Then the initial segment relation is a partial order on $\mathscr{F}.$

Proof

Each relation is its own initial segment, so $\preceq$ is reflexive. If $\leq_1 \preceq \leq_2$ and $\leq_2 \preceq \leq_1$ then then the two relations have the same ground set and are restrictions of each other, which forces equality. Suppose $\leq_1 \preceq \leq_2$ and $\leq_2 \preceq \leq_3.$

Subset inclusions are transitive, so $\operatorname{ground}(\leq_1) \subseteq \operatorname{ground}(\leq_2) \subseteq \operatorname{ground}(\leq_3)$ implies $\operatorname{ground}(\leq_1) \subseteq \operatorname{ground}(\leq_3).$

Since for each $x_1, x_2 \in \operatorname{ground}(\leq_2)$ it is the case that $x_1 \leq_2 x_2 \iff x_1 \leq_3 x_2,$ and since for each $y_1, y_2 \in \operatorname{ground}(\leq_1),$ $y_1 \leq_1 y_2 \iff y_1 \leq_2 y_2,$ the transitivity of biconditional lets us conclude that $\leq_1$ is a restriction of $\leq_3.$

All elements of $\operatorname{ground}(\leq_1)$ precede under $\leq_3$ all elements of $\operatorname{ground}(\leq_2) \setminus \operatorname{ground}(\leq_1).$ Also, all elements of $\operatorname{ground}(\leq_2)$ precede under $\leq_3$ all elements of $\operatorname{ground}(\leq_3) \setminus \operatorname{ground}(\leq_2).$ Take $x \in \operatorname{ground}(\leq_1)$ and $y \in \operatorname{ground}(\leq_3) \setminus \operatorname{ground}(\leq_1).$

If $y \in \operatorname{ground}(\leq_2),$ then it is also an element of $\operatorname{ground}(\leq_2) \setminus \operatorname{ground}(\leq_1)$ (since it is not an element of $\operatorname{ground}(\leq_1)$) and hence $x$ precedes it. If $y \notin \operatorname{ground}(\leq_2),$ then it is an element of $\operatorname{ground}(\leq_3) \setminus \operatorname{ground}(\leq_2)$ and in this case too $x$ precedes it.

Thus $\leq_1 \preceq \leq_3,$ which is sufficient to demonstrate transitivity.

$\blacksquare$

Lemma L3.2

Let $Z$ be a non-empty set and let $\mathscr{F}$ be a family of well-ordering relations such that for each $\leq \in \mathscr{F},$ $\operatorname{ground}(\leq) \subseteq Z.$ Let $\ell \subseteq \mathscr{F}$ be a $\preceq$-chain. Then a $\preceq$-upper bound of $\ell$ exists and is a well-ordering relation on a subset of $Z.$

Proof

Let $S = \bigcup_{\leq \in \ell}\operatorname{ground}(\leq).$ Define a relation $\leq_{\mathrm{ub}}$ with ground set $S$ as follows: for any $a, b \in S,$ $a \leq_{\mathrm{ub}} b$ if and only if there exists $\leq \in \ell$ such that $a,b \in \operatorname{ground}(\leq)$ and $a \leq b.$

It is immediate that $\leq_{\mathrm{ub}}$ is reflexive and antisymmetric. Suppose $a \leq_{\mathrm{ub}} b$ and $b \leq_{\mathrm{ub}} c.$ Let $\leq_1$ be the element of $\ell$ witnessing $a \leq_{\mathrm{ub}} b,$ and let $\leq_2$ be the element of $\ell$ witnessing $b \leq_{\mathrm{ub}} c.$ If $\leq_1 \preceq \leq_2$ then $a \leq_2 c.$ Suppose instead $\leq_2 \preceq \leq_1.$ Then $a,b,c \in \operatorname{ground}(\leq_1)$ and the restriction condition lets us conclude $a \leq_1 c.$ Thus $\leq_{\mathrm{ub}}$ is transitive.

Let $T \subseteq S$ be non-empty. Take $t \in T$ and let $\leq \in \ell$ be such that $t \in \operatorname{ground}(\leq).$ Let $m$ be the $\leq$-minimal element of $T' = T \cap \operatorname{ground}(\leq).$ Suppose $m' \in T.$ If $m' \in \operatorname{ground}(\leq)$ then $m' \in T'$ and hence $m \leq m'.$ Otherwise, $m'$ has to come from the ground set of some other relation $\leq' \in \ell.$ It cannot be that $\leq' \preceq \leq,$ since in that case $m' \in \operatorname{ground}(\leq') \subseteq \operatorname{ground}(\leq).$ Since $\ell$ is a chain, it must be $\leq \preceq \leq'.$ Then the third condition of initial segment relation forces $m \leq' m'.$ In both cases, $m \leq_{\mathrm{ub}} m'.$

Thus, $\leq_{\mathrm{ub}}$ is a well-ordering.

So $\leq_{\mathrm{ub}}$ is in $\mathscr{F}.$ Let $\leq \in \ell.$ Then $\operatorname{ground}(\leq) \subseteq S,$ and the restriction of $\leq_{\mathrm{ub}}$ to $\operatorname{ground}(\leq)$ agrees with $\leq,$ since whenever $\leq$ holds, $\leq_{\mathrm{ub}}$ holds by definition. Suppose $a, b \in \operatorname{ground}(\leq)$ and $a \leq_{\mathrm{ub}} b,$ then there exists $\leq'$ such that $a,b \in \mathrm{ground}(\leq')$ and $a \leq' b.$ If $\leq \preceq \leq'$ then $\leq'$ restricts to $\leq$ and hence $a \leq b.$ Otherwise, if $\leq' \preceq \leq$ then $\leq'$ restricts to $\leq$ and $a \leq b.$ Finally, suppose $x \in \operatorname{ground}(\leq)$ and $y \in \operatorname{ground}(\leq_{\mathrm{ub}}) \setminus \operatorname{ground}(\leq).$ Let $\leq'$ be such that $y \in \operatorname{ground}(\leq').$ It cannot be that $\leq' \preceq \leq,$ since this would violate ground set inclusion, therefore $\leq \preceq \leq'$ and hence $x \leq' y.$

Thus, $\leq \preceq \leq_{\mathrm{ub}}.$

$\blacksquare$

Lemma L3.3

Let $Z$ be a set, let $S \subsetneq Z,$ and let $\leq$ be a well-ordering relation on $S.$ Let $a \in Z \setminus S.$ Then there exists a well-ordering relation $\leq'$ such that $\operatorname{ground}(\leq') = S \cup \{a\}$ and for all $z \in S,$ $z \leq' a.$ Furthermore, $\leq \preceq \leq'.$

Proof

Define $\leq'$ as $u \leq' v$ if and only if either

1. $u, v \in S$ and $u \leq v$, or
2. $v = a.$

We only need to check that $\leq'$ is a partial order when one of the arguments is $a,$ since otherwise this follows from $\leq$ being a partial order. Clearly $a \leq' a.$ The only way $a \leq' u$ could hold is when $u = a,$ so $\leq'$ is antisymmetric. Suppose $u \leq' v$ and $v \leq' a.$ It is always the case that $u \leq' a.$ If, instead, we have either $a \leq' u \leq' v$ or $u \leq' a \leq' v,$ then $v = a$ and necessarily $u \leq' a.$ Thus $\leq'$ is transitive.

Suppose $T \subseteq S \cup \{a\}$ is non-empty. If $T = \{a\}$ then $a$ is $\leq'$-least element of $T.$ If $a \notin T,$ then $\leq'$ agrees with $\leq$ on $T$ and gives the $\leq'$-least element of $T.$ If $T$ is not a singleton and it contains $a,$ $a$ cannot be the $\leq'$-least element of $T,$ since any element of $T \setminus \{a\}$ is lesser than $a.$ Thus we take the $\leq$-least element of $T \setminus \{a\}$ which is automatically the $\leq'$-least.

Observe that $\operatorname{ground}(\leq) \subseteq \operatorname{ground}(\leq')$ and, by construction, forgetting about $a \in \operatorname{ground}(\leq')$ leaves us with a relation identical to $\leq,$ thus $\leq'$ restricts to $\leq.$ Finally, since $a$ is the maximal element of $\leq',$ it sits above every element of $\operatorname{ground}(\leq).$ Thus $\leq \preceq \leq'.$

$\blacksquare$

Proposition

Zorn’s lemma implies the well-ordering principle.

Proof

Let $Z$ be a non-empty set and let $\mathscr{F}$ be a set of all well-orderings $\leq$ such that $\operatorname{ground}(\leq) \subseteq Z.$ Since singletons are always well-ordered, $\mathscr{F}$ is non-empty.

By lemma 3.1, the initial segment relation $\preceq$ is a partial order on $\mathscr{F}.$ By lemma 3.2, every $\preceq$-chain has an upper bound, which is a well-ordering of a subset of of $Z.$

By Zorn’s lemma, there exists a $\preceq$-maximal element $\leq_M$ of $\mathscr{F}.$

Suppose $S = \operatorname{ground}(\leq_M)$ is a proper subset of $Z.$ Then we can extend $\leq_M$ with $a \in Z \setminus S$ using lemma 3.3, which results in a $\preceq$-greater well-ordering $\leq_M'.$

This contradicts $\preceq$-maximality of $\leq_M.$

$\blacksquare$