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.

  • $\begingroup$ 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$. $\endgroup$ – Andreas Blass Oct 27 '18 at 20:16
  • $\begingroup$ @AndreasBlass Yes, I did forget it hypothesis. It is fixed $\endgroup$ – Gödel Oct 27 '18 at 20:58
  • $\begingroup$ Could you mention the source of the statement that you are proving equivalent to choice? @Gödel $\endgroup$ – Carl Mummert Oct 28 '18 at 1:29
  • $\begingroup$ @Carl: It's a fairly well-known version. I couldn't even tell you who proved that equivalence. $\endgroup$ – Asaf Karagila Oct 28 '18 at 8:51
  • $\begingroup$ @Asaf: it's pretty clearly equivalent to AC, too :). The OP must have found it somewhere - that source might be interesting for others. $\endgroup$ – 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\}$.

  • $\begingroup$ It makes sense to me. $\endgroup$ – Gödel Oct 27 '18 at 17:34
  • $\begingroup$ Is it not necessary delet $\emptyset$ from $E$? $\endgroup$ – Gödel Oct 27 '18 at 17:38
  • $\begingroup$ No, because it is not in the domain of $G$. $\endgroup$ – Asaf Karagila Oct 27 '18 at 18:31
  • $\begingroup$ Of course I see it $\endgroup$ – Gödel Oct 27 '18 at 18:44

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.