# Unable to prove that a statement is an equivalent form of the Axiom of Choice [duplicate]

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:

(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)

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

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

• 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)$. – Scientifica Jul 10 '16 at 10:13
• 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. – Scientifica Jul 10 '16 at 11:17
• @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)\})$... – Scientifica Jul 10 '16 at 18:50