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 Axiom of Choice

For every set of non-empty sets, it is possible to provide a mechanism for choosing one element of each element of the set.

$\ds \forall s: \paren {\O \notin s \implies \exists \paren {f: s \to \bigcup s}: \forall t \in s: \map f t \in t}$

That is, one can always create a choice function for selecting one element from each element of the set.


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 $\CC$ be the set of all chains in $X$.

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

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


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

Define a mapping $h: \On \to X$ by transfinite recursion thus:

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

when $h \sqbrk \lambda$ is the image set of $\lambda$ under $h$.



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



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

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

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

By the Burali-Forti Paradox, this is a contradiction.

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

$\blacksquare$