For the theorem, "Let A and B be sets and let $f : A \rightarrow B$ be a function. Then $f : A \rightarrow B$ is $surjective$ $iff$ there exists a function $g : B \rightarrow A$ such that $f \circ g = I_B$. "

The theorem implies Axiom of choice.

I proved the statement, but I want to know whether my proof is right or not.


Suppose the theorem. Let A be a set and $Q_R$=$\text{{(R,r)|$r\in R$}}$ for all $R\in \mathscr P'(A)$ . Let $Q = \cup_{R\in\mathscr P'(A)} Q_R$.

Let $f: Q \rightarrow \mathscr P'(A)$ where $(R,r) \mapsto R$. Then, $\exists (R,r)\in Q$ for $\forall R \in \mathscr P'(A)$. So $f$ is surjective. By theorem, $\exists g: \mathscr P'(A) \rightarrow Q $ such that $f \circ g = I_B$. Then, $g(R) = (R,r)$ for some $ r\in R$.

So, let $\gamma : \mathscr P'(A) \rightarrow A$ such that $\gamma(R) = r$ where $\gamma(R) \in R$ for all $R \in \mathscr P'(A).$ Hence, Axiom of choice holds.

  • 1
    $\begingroup$ Yep, that does the trick. Good job! $\endgroup$ – Stefan Mesken May 26 '17 at 13:59

Your proof is mostly fine. Note that you can define $Q$ more clearly as $$\{(R,r)\mid r\in R\subseteq A\},$$ or if you prefer a more explicit statement, $$\{(R,r)\mid R\subseteq A\text{ and }r\in R\}.$$

In the last line, however, you messed up a little bit. You just claimed that a choice function $\gamma$ exists. This requires proof, all that you know is that there is a function $g$ which is the inverse of $f$. You need to use that to define $\gamma$. In this case, $\gamma(R)=r$ if and only if $g(R)=(R,r)$.

Now you need to argue that $\gamma$ is a choice function indeed, which is not difficult from the way we picked $f$, and what we know about $g$.


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.