3
$\begingroup$

I am trying to solve an exercize, in which we were asked to prove that Zorn's lemma implies axiom of choic. I am using a guidness 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$ antysimmetry: 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 definde.

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

$\endgroup$
  • $\begingroup$ You should use \langle and \rangle for the tuples symbol rather than < and >. Look at the difference: $$\langle\mathcal F,\leq\rangle\\<\mathcal F,\leq>$$ $\endgroup$ – Asaf Karagila Nov 23 '13 at 10:07
  • $\begingroup$ OK. good to know. thanks! $\endgroup$ – topsi Nov 23 '13 at 20:11
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Got it. Thanks!! $\endgroup$ – topsi Nov 23 '13 at 20:06
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You're right on that well-defined part. $\endgroup$ – Asaf Karagila Nov 23 '13 at 10:26
  • $\begingroup$ OK. I'll think about it. Thanks! $\endgroup$ – topsi Nov 23 '13 at 20:08
  • $\begingroup$ @Shir: The missing part (using $f_2|_{A_1}=f_1$) should be used to show that the upper bound of a chain is indeed well-defined. $\endgroup$ – Asaf Karagila Nov 23 '13 at 20:22
  • $\begingroup$ ok i have used it there. Thank you! $\endgroup$ – topsi Nov 24 '13 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.