Zorn's Lemma Implies Axiom of Choice

From ProofWiki
Jump to navigation Jump to search

Theorem

If Zorn's Lemma is true, then so must the Axiom of Choice be.


Proof

Let $X$ be a set.

Let $\FF$ be the set of partial choice functions defined as:

$f \in \FF \iff \begin{cases} \Dom f \subseteq \powerset X & \ \\ \Img f \subseteq X & \ \\ \forall A \in \Dom f: \map f A \in A & \ \end{cases}$

Let $\preceq$ be the relation defined on $\FF$ as:

$\forall f_1, f_2 \in \FF: f_1 \preceq f_2 \iff f_2$ is an extension of $f_1$.

Straightforwardly, $\preceq$ is a partial ordering on $\FF$.

We can also see that the Empty Mapping is an element of $\FF$.


Let $C \subseteq \FF$ be a non-empty chain in $\FF$.

Let $U$ be the union of all domains of mappings in $C$.

Furthermore, let $f$ be the union of all graphs of mappings in $C$.

For each $x \in U$, all mappings $g \in C$ with $x \in \Dom g$ have the same value at $x$.

Thus there is a unique $y \in X$ such that $\tuple {x, y} \in f$.

Hence $f: U \rightarrow X$ is a mapping.

By construction, we also have $\map f x \in x$ for all $x \in \Dom f = U$.


That is, every non-empty chain in $\FF$ has an upper bound.


Suppose Zorn's Lemma holds.

Then there exists a maximal element of $\FF$.



We then show by contraposition that if $g$ is such a maximal element, then:

$\Dom g = \powerset X \setminus \O$

In that case, we will have constructed a choice function $\powerset X \setminus \set \O \rightarrow X$.


Suppose that $\Dom g \ne \powerset X \setminus \O$.

Then there is an $A \in \paren {\powerset X \setminus \O} \setminus \Dom g$.

Let $x \in A$.

We can then define the mapping $\hat g: \set A \cup \Dom g$ by defining:

$\forall S \in \Dom g: \forall \map {\hat g} A = x: \map {\hat g} S = \map g S$

That way, we clearly have $\hat g \ne g$ and $\hat g \preceq g$.

Thus $g$ is not maximal in $\FF$.




Sources