Proof on surjective functions

I have this assignment:

given a function $f:A\longrightarrow B$ between two sets $A,B$ prove that $f$ is surjective if and only if there exists a function $\psi:B\longrightarrow A$ such that $f\circ\psi=\operatorname{id}_B$.

My thoughts: assume such a $\psi$ exists. Then consider two other functions $$h,k:B\rightrightarrows\left\{0,1\right\}$$ defined by $$h(b)=1\text{ if b}\in f(A)$$ and $$h(b)=0\text{ otherwise}$$ and $$k(b)=1\text{ for every } b$$ Then $h\circ f=k\circ f$, thus $h\circ f\circ\psi=k\circ f\circ \psi$, thus $h=k$ and so $f(A)=B$.

Now viceversa assume that $f$ is surjective. I have to define $\psi$ and I don't know how. I know that since $f$ is surjective, every element of $B$ has a non-empty inverse image, but how can I get out a function from that?

If $\psi:B\to A$ with $f\circ\psi=\text{id}_{B}$ then for every $b\in B$ we have $b=f\left(a\right)$ if $a\in A$ is defined by $a:=\psi\left(f\left(b\right)\right)$. This shows that $f$ is surjective.

If conversely $f:A\to B$ is surjective then for every $b\in B$ some $a_{b}\in A$ exists with $f\left(a_{b}\right)=b$. Then function $\psi:B\to A$ prescribed by $b\mapsto a_{b}$ will satisfy the condition $f\circ\psi=\text{id}_{B}$. Needed here is actually the axiom the choice.

• Can I choose the $a_b$ I want? So $\psi$ is not unique? – Danae Kissinger Jul 23 '16 at 15:32
• Indeed. $\psi$ is not unique in general in this context. If there is uniqueness (special case) then $f$ is bijective. – drhab Jul 23 '16 at 15:34
• Is there no way to avoid AC? – ajotatxe Jul 23 '16 at 15:35
• @ajotatxe No (or more cautious: not that I know of). – drhab Jul 23 '16 at 15:36
• At the end of my answer, I added a proof that AC follows from every surjective function having a right inverse. – Mitchell Spector Jul 23 '16 at 19:42

You're making this much too complicated.

If such a $\psi$ exists, to show that $f$ is surjective, you just need to show that for every $b \in B$, there exists $a \in A$ such that $f(a)=b.$ You can define such an $a$ explicitly using $\psi$ and $b.$

For the implication from left to right, note that you'll need to use the axiom of choice. In fact, that direction is essentially the same as the axiom of choice.

By the way, here's how to see that the axiom of choice is actually needed for the above. Assuming that every surjective function has a right inverse, we'll prove the axiom of choice. (In fact, they're equivalent; @drhab proved the other direction in his or her answer.)

Suppose that $S$ is a set and that $g$ is a function with domain $S$ such that for every $s$ in $S,$ $g(s)$ is a non-empty set. We need to show that there is a choice function for $g.$

Let $A=\lbrace \langle s,x \rangle \; |\; s \in S\text{ and }x \in g(s)\rbrace$.

Let $\pi_1:A \rightarrow S$ be the projection function with domain $A$ defined by setting $\pi_1(\langle s,x\rangle)=s.$ Let $\pi_2$ be the projection function, also with domain $A,$ defined by setting $\pi_2(\langle s,x\rangle)=x.$ Then the definition of $A$ tells us that for any $a \in A,$ we have $$\pi_2(a) \in g(\pi_1(a)).$$

The function $\pi_1:A \rightarrow S$ is surjective. (For any $s \in S,$ $g(s)$ is non-empty; if $x$ is any member of $g(s),$ then $\langle s,x \rangle \in A$ and $\pi_1(\langle s,x\rangle)=s.)$

By our assumption, the surjective function $\pi_1:A \rightarrow S$ must have a right inverse $\psi: S \rightarrow A.$

It follows that $\pi_2 \circ \psi$ is a choice function for $g,$ since for any $s \in S,$ we have:

\begin{align}\pi_2(\psi(s)) \in g(\pi_1(\psi(s))= g(s).\end{align}

• Thanks, @drhab. I didn't want to assume. – Mitchell Spector Jul 24 '16 at 15:36