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