Proving that Zorn's Lemma implies the axiom of choice

Question

I am trying to solve an exercise, in which we were asked to prove that Zorn's lemma implies axiom of choice. I am using a guidance that was given that said we should use a set $\mathcal{F}$ which i'll define throughout the proof:

Proof: Given a set of nonempty sets $F$, define the set $\mathcal{F}$ to be: $\mathcal{F}=\{f \mid f \space is \space a \space choice \space function \space on \space a \space subset \space of \space F\}$. ($\mathcal{F}$ is not empty since on subsets of $F$, that contain only one set, one can easily define a choice function). Define a relation $\leq$ on $\mathcal{F}$ in the following way: given $f_1,f_2\in\mathcal{F}$ which are choice functions on $\mathcal{A_1},\mathcal{A_2} \subseteq F$, we say that $f_1 \leq f_2$ if $\mathcal{A_1} \subseteq \mathcal{A_2}$ and $f_2|_{\mathcal{A_1}}=f_1$. We will show that:

1. $\langle\mathcal F,\leq\rangle\\$ is a partially order relation.

2. Every chain in $\langle \mathcal{F},\leq \rangle$, has an upper bound in $\mathcal{F}$, and therefor, by Zorn's lemma, $\langle\mathcal{F},\leq \rangle$ has a maximal element.

3. This maximal element is a choice function on $F$.

Proof of 1:

reflexivity: $(f_1,f_1) \in \leq$, since, of course, $f_1|_{\mathcal{A_1}}=f_1$ antisymmetry: given $f_1 \leq f_2$ and $f_2 \leq f_1$, we get that $\mathcal{A_1}=\mathcal{A_2}$, and $f_1|_{\mathcal{A_2}}=f_2$ and $f_2|_{\mathcal{A_1}}=f_1$ which implies $f_1=f_2$. in a similar (rather obvious) way the transitivity can be proved.

Proof of 2:

given a chain $f_1 \leq f_2 \leq ...$ take $f:\bigcup \mathcal{A_i} \rightarrow \bigcup f_i$ to be the function s.t. $f|_{\mathcal{A_i}} = f_i$, for every $i$. Then $f$ is an upper bound for the chain, and $f \in \mathcal{F}$.

Proof of 3: Take $g$, to be the maximal element from 2. we have to show that $g$ is a choice function on all sets in $F$, and that it is well defined.

choice function on all $F$: suppose not, there exists a set $A \in \mathcal{F}$ s.t. $g$, is not defined on $A$. $A$ is not empty, so, take some $a \in A$ and define $h$ to be: $h(X)=\begin{cases} a,&\text{if } X=A\\ g(X),&\text{if } X \neq A \end{cases}$ Then $g < h$ contradicting the fact that $g$ is maximal.

$g$ is well defined: Suppose not, there exists an $A \in \mathcal{F}$ and $a_1,a_2 \in A$ where $a_1 \neq a_2$, such that $g(A)=a_1$ and $g(A)=a_2$. but then, from the construction of $g$, there exists an $f_i$ with domain $\mathcal{A_i}$, which is not well defined, which is also a contradiction. Therefor $g$, is a choice function.

What do you think?

Thank you! Shir

Answer 1

The proof of the first part is fine. You might find it easier to just show that $f_1\leq f_2$ if and only if $f_1\subseteq f_2$.

For the second part using $f_1\leq f_2\leq\ldots$ hints that somehow you are considering countable chains, or even well-ordered chains. While Zorn's lemma holds if we only check well-ordered chains, it is better to write "Suppose $\{f_i\mid i\in I\}$ is a chain" instead. You also haven't shown why $\bigcup f_i$ is a choice function. Have you shown before that the increasing union of functions is a function? If not, it might be worth showing why $f$ is an element of $\cal F$, and why it is an upper bound of the chain.

The last part is also fine (although note that $g$ is necessarily well-defined, since it is an element of $\cal F$).

Answer 2

The part where you show that $g$ is well-defined seems a bit odd. What do you mean by that? In it you also mention the construction of $g$, but there is no construction, the function $g$ is given by Zorn's lemma. Where you might want to show that something is well-defined is in (2) where you define the upper bound of a chain. Also note that except in (1) you nowhere use the condition $f_2|_{A_1}=f_1$. Would the proof work if $\le$ was defined without it?