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:
-
$\langle\mathcal F,\leq\rangle\\$ is a partially order relation.
-
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.
-
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
Best Answer
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$).