2
$\begingroup$

This question already has an answer here:

The exercise 22 page 158 of Elements of Set Theory by B. Enderton is the following:

Show that the following statement is another equivalent version of the axiom of choice: For any set $A$ there is a function $F$ with $\text{dom }F=\bigcup A$ and such that $x\in F(x)\in A$ for all $x\in\bigcup A$.

The versions of the axiom of choice that I know for the moment are:

enter image description here

(although the Cardinal comparability and Zorn's lemma were stated as well, the author didn't prove yet that they're equivalent to the Axiom of Choice)

and the following form: (Exercise 18 in the same page)

enter image description here

I proved that AC III implies the statement of the exercise as follows:

Let $A$ be a set According to AC III there exists a function $f:\mathcal{P}A\setminus\{\emptyset\}\to A$ such as $\forall X\in\mathcal{P}A\setminus\{\emptyset\},\,f(X)\in X$.

Let

\begin{align*} g:&\bigcup A\,\,\to \mathcal{P}A\setminus\{\emptyset\}\\ &x \quad\quad\mapsto\{a\in A\mid x\in a\} \end{align*}

$g$ is a well defined function/

Let $F=f\circ g$. Then $\text{dom }F=\text{dom }g=\bigcup A$.

Let $x\in\bigcup A$. $F(x)=f(g(x))=f\left(\{a\in A\mid x\in a\}\right)$. Thus $F(x)\in\{a\in A\mid x\in a\}$. Thus $x\in F(x)\in A$.$$\tag*{$\square$}$$

I couldn't prove the other way. I had two ideas:( $F:\bigcup A\to A$ such that $\forall a\in\bigcup A,\,a\in F(a)\in A$)

1) We could try to construct an "inverse" of $F$. But $F$ isn't necessarily injective nor surjective. Thus such a construction would require the axiom of choice.

2) We could consider $f=F\circ g$ where $g:\,A\to \bigcup\bigcup A$ and $F:\,\bigcup\bigcup A\to\bigcup A$ but I couldn't find a suitable $g$.

Could you please help me? Thanks you in advance!

$\endgroup$

marked as duplicate by egreg, Community Jul 10 '16 at 15:36

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$ multiplicative axiom ​ ​ $\endgroup$ – user57159 Jul 9 '16 at 21:37
  • 1
    $\begingroup$ Do you mean that I should prove the multiplicative axiom? I tried to do so but I failed. According to the statement of the exercise there is a function $F:\bigcup_{i\in I}H(i)\to\{H(i)\mid i\in I\}$ that satisfies $x\in F(x)\in\bigcup_{i\in I}H(i)$. However nothing ensures that $F$ is surjective. Even if that was the case, for each $i\in I$, we will have to use the axiom of choice to justify that we can choose an element which image by $F$ is $H(i)$. $\endgroup$ – Scientifica Jul 10 '16 at 10:13
  • $\begingroup$ Yes. ​ You should use Exercise 18, rather than whatever exercise your comment uses. ​ ​ ​ ​ $\endgroup$ – user57159 Jul 10 '16 at 10:46
  • 1
    $\begingroup$ Exercise 18 is the statement "For any set $\mathcal{A}$ whose members are nonempty sets, there is a function $f$ with domain $\mathcal{A}$ such that $f(X)\in X$ for all $X$ in $\mathcal{A}$", so what I tried to prove (as I wrote in my question) is that the statement of exercise 22 implies the statement of exercise 18 but I failed to. $\endgroup$ – Scientifica Jul 10 '16 at 11:17
  • 1
    $\begingroup$ @RickyDemer I'm going to use the trick of IainM in the link where my question has an answer (that trick is powerful!): Let $R$ be a relation. Let $h:\,\text{dom }R\to\mathcal{P}\,\text{ran R}$ such as $h(x)=\{y\in\text{ran }R\mid xRy\}$. Let $S=\{(a,b)\in h(\text{dom }R\times\text{ran }R\mid b\in a\}$ (with $(a,b)=\{\{a\},\{a,b\}\})$. Let $\pi_2:h(\text{dom }R\times\text{ran }R \to\text{ran }R$ such as $\pi_2(a,b)=b$. Let $F$ be the function described in Exercise 22 with range $\bigcup S$. Then let $f:\text{dom }R\to\text{ran }R$ such as $f(x)=\pi_2\circ F(\{h(x)\})$... $\endgroup$ – Scientifica Jul 10 '16 at 18:50