Axiom of Choice Implies Zorn's Lemma/Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Acceptance of the Axiom of Choice implies the truth of Zorn's Lemma.


Statement of Zorn's Lemma

Let $\struct {X, \preceq}, X \ne \O$ be a non-empty ordered set such that every non-empty chain in $X$ has an upper bound in $X$.


Then $X$ has at least one maximal element.


Proof

Aiming for a contradiction, suppose that for each $x \in X$ there is a $y \in X$ such that $x \prec y$.

By the Axiom of Choice, there is a mapping $f: X \to X$ such that:

$\forall x \in X: x \prec \map f x$

Let $\mathcal C$ be the set of all chains in $X$.

By the premise, each element of $\mathcal C$ has an upper bound in $X$.

Thus by the Axiom of Choice, there is a mapping $g: \mathcal C \to X$ such that for each $C \in \mathcal C$, $\map g C$ is an upper bound of $C$.

Let $p$ be an arbitrary element of $X$.

Define a mapping $h: \operatorname {Ord} \to X$ by transfinite recursion thus:

\(\displaystyle \map h 0\) \(=\) \(\displaystyle p\)
\(\displaystyle \map h {\alpha^+}\) \(=\) \(\displaystyle \map f {\map h \alpha }\)
\(\displaystyle \map h \lambda\) \(=\) \(\displaystyle \map f {\map g {f \sqbrk \lambda} }\) if $\lambda$ is a limit ordinal



Then $h$ is strictly increasing, and thus injective.



Let $h'$ be the restriction of $h$ to $\operatorname {On} \times \map h {\operatorname{On} }$.

Then ${h'}^{-1}$ is a surjection from $\map h {\operatorname{On} } \subseteq X$ onto $\operatorname{On}$.

By the Axiom of Replacement, $\operatorname{On}$ is a set.

By Burali-Forti Paradox, this is a contradiction.

Thus we conclude that some element of $X$ has no strict successor, and is thus maximal.

$\blacksquare$