# Statement that implies axiom of choice

Consider the following statement: for any set $$E$$ and $$G\subseteq E\times E$$, you can to get a function $$f:A\rightarrow B$$ where $$A=dom G$$, $$B=ran G$$ and $$f\subseteq G$$.

I want to show that this implies axiom of choice.

My attempt:I will prove that the statement above implies the existence of a choice function. Indeed, let A an arbitrary set and consider $$E=\mathcal{P}(A)\setminus\{\emptyset\}$$ and take $$G:=\{(B,\{x\})\subseteq E\times E:x\in B\}$$. So, by hypotesis exists a function $$f:E\rightarrow A$$ that it is, in fact, a choice function.

My doubts in the proof is with the set $$G$$, I don't know if in your definition I use axiom of choice, because it seems that I do infinitely many choices.

• Did you intend to require that (the graph of) $f$ is a subset of $G$? Without such a requirement, your statement does not imply the axiom of choice; in fact it's provable from the other axioms of set theory. The reason is that there are functions from any set $A$ to any set $B$ unless $A\neq\varnothing=B$. And that exceptional situation can't occur for you because, if the range of $G$ is empty, then so is $G$ and therefore so is the domain of $G$. – Andreas Blass Oct 27 '18 at 20:16
• @AndreasBlass Yes, I did forget it hypothesis. It is fixed – Gödel Oct 27 '18 at 20:58
• Could you mention the source of the statement that you are proving equivalent to choice? @Gödel – Carl Mummert Oct 28 '18 at 1:29
• @Carl: It's a fairly well-known version. I couldn't even tell you who proved that equivalence. – Asaf Karagila Oct 28 '18 at 8:51
• @Asaf: it's pretty clearly equivalent to AC, too :). The OP must have found it somewhere - that source might be interesting for others. – Carl Mummert Oct 28 '18 at 14:19

Yes, you have a problem there. Specifically, your function returns singletons of elements of $$A$$, not elements of $$A$$.
The obvious way to correct this is to take $$E=A\cup\mathcal P(A)$$ and $$G=\{(B,x)\mid x\in B\subseteq A\}$$.
• Is it not necessary delet $\emptyset$ from $E$? – Gödel Oct 27 '18 at 17:38
• No, because it is not in the domain of $G$. – Asaf Karagila Oct 27 '18 at 18:31