3
$\begingroup$

This question already has an answer here:

Can someone please give me feedback on my attempted proof that Zorn's Lemma implies the Axiom of Choice? I have a very good idea how to do it, but need help with some small details.

This is my proof so far... major gaps missing, please help!

Let $X$ be a nonempty set. Let $S = \{f : f \text{ is a choice function on } A \subset \mathcal{P}_{0}{X}\}$. Explain why $S$ nonempty. Declare $f_{1} \leq f_{2}$ if $Dom(f_{1}) \subset Dom(f_{2})$ (Why is this a partial ordering?). Let $T$ be a chain in $S$. Let $F$ be the union on the functions in $T$. (Why is $F$ also a choice function?) Therefore, by Zorn's Lemma, there exists a maximal function $m$. (Why is $m$ a choice function on every $A \subset PX$). Suppose not, then there exists an $A \subset \mathcal{P}_{0}{X}$ such that $m$ is not defined on $A$ (Don't know how to finish this!!) Therefore, $f \in S$ and $m < f$, contradicting $m$ being maximal. Thus, $m$ is a choice function for the entire set $\mathcal{P}{X}$.

$\endgroup$

marked as duplicate by Jack, TastyRomeo, martini, Noah Schweber, Arnaud D. Jan 7 '17 at 22:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Asking Google would be much quicker if you are just looking for a proof: proofwiki.org/wiki/Zorn's_Lemma_Implies_Axiom_of_Choice $\endgroup$ – Jack Jan 7 '17 at 21:40
  • $\begingroup$ I haven't really found an actual proof on google yet which is weird... I've looked at that wikipage, there isn't enough information $\endgroup$ – B. Drennan Jan 7 '17 at 21:41
  • $\begingroup$ In your definition of partial order you should also require that $f_2$ and $f_1$ coincide on the common subdomain. The rest then follows (if $m$ is not defined in all of $X$ you may extend it. This does not rely on the AoC). $\endgroup$ – H. H. Rugh Jan 7 '17 at 21:45
3
$\begingroup$

Fixing your proof:

Let $X$ be a nonempty set.

Let $S = \{\,f : f \text{ is a choice function on } A \subset \mathcal{P}{X}\}$.

$S$ is nonempty, as $f=\big\{(\{a\},a)\big\}\in S$, for all $a\in A$. Here, $\,f=\big\{(\{a\},a)\big\}$ is the choice function $\,f:\{\{a\}\}\to\{a\}$, with $\,f(\{a\})=a$. Note that in Set Theory, functions are identified with their graph, i.e. if $f:A\to B$, then $f=\{(a,f(a)):a\in A\}$.

Next, define the partial order: $$f_{1} \leq f_{2}\quad\text{iff}\quad f_{1}\subset f_{2}. $$ It is a partial ordering, as "$\subset$" is always a partial ordering in $\mathcal PX$.

Let $T$ be a chain in $S$ and $F$ be the union on the functions in $T$. Then $F$ is a function (why?) and hence a choice function.

Therefore, by Zorn's Lemma, there exists a maximal function $f_{max}$.

If the domain of $f_{max}$ is not the whole of $X$, then choose $a\in X\setminus \mathrm{Dom}\,f_{max}$, and set $$ \tilde f=f_{max}\cup\big\{(\mathrm{Dom}\,f_{max}\cup\{a\}),a\big\}. $$ We have extended $f_{max}$ to $\tilde f$ by adding just one more element. Contradiction as $T\cup \{\tilde f\}$ would also be a chain, larger than $T$.

$\endgroup$
  • $\begingroup$ Thank you! Can you please explain in more detail the contradiction. That's the part I'm having the most trouble with $\endgroup$ – B. Drennan Jan 7 '17 at 21:57
  • $\begingroup$ And can you please explain the notation $f = \{(\{a\}, a)\}$ $\endgroup$ – B. Drennan Jan 7 '17 at 21:59
  • $\begingroup$ See my edited answer. $\endgroup$ – Yiorgos S. Smyrlis Jan 7 '17 at 22:07
  • $\begingroup$ Thank you so much! This is all the information I needed! $\endgroup$ – B. Drennan Jan 7 '17 at 22:19

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