Zorn's Lemma implies Axiom of Choice

Theorem

Let Zorn's Lemma be accepted.

Then the Axiom of Choice holds.

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

This article, or a section of it, needs explaining. In particular: Check the chain condition (and nonemptiness of $\FF$) You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

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

This article, or a section of it, needs explaining. In particular: How does this prove the hypothesis? You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Sources

• 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 16$: Zorn's Lemma: Exercise