The equivalence of "Every surjection has a right inverse" and the Axiom of Choice

This is a problem from Tao's Analysis I.

We are asked to show that the axiom of choice is equivalent to the statement that for any sets $A$ and $B$ for which a surjection $g:B\to A$ exists, an injection $f:A\to B$ exists.

I have proven that the axiom of choice implies the statement , but I am having difficulty with the other implication. The hint given in the book is to use the previous exercise, which says that the axiom of choice is equivalent to the statement that if $I$ is a set, $\forall\alpha\in I$ $X_\alpha$ is a non-empty-set and $\forall \alpha,\beta\in I, \alpha\neq \beta\implies X_\alpha\cap X_\beta=\emptyset$, then there exists a set $Y$ with $\forall \alpha\in I ,|Y\cap X_\alpha|=1$.

To use the previous exercise we need disjoint sets, so we consider the sets $\{\alpha\}\times X_\alpha$ instead of just $X_\alpha$. I think then we should find a set $Y$ with $\forall \alpha \in I,|Y\cap(\{\alpha\}\times X_\alpha)|=1$, perhaps by using that there is some surjection between two sets and so by assumption some injection which goes the other way, whose image is suitable as a set $Y$. I think that is the idea, but I can't figure out exactly what these functions should be.

If I am incorrect, please correct me. Any help is appreciated.

Solution 1:

The problem's statement would be correct if $f$ were required to be a right inverse of $g$, i.e., for each $a\in A$, $f(a)$ selects an element from the fiber $g^{-1}(\{a\})$. Without this additional requirement, the statement is not known to be equivalent to the axiom of choice, nor is it known to be strictly weaker. This open problem is sometimes called the "map on map in" problem.

Solution 2:

Let $\{X_\alpha:\alpha\in I\}$ be a family of pairwise disjoint non-empty sets indexed by a set $I$. Let $X=\bigcup_{\alpha\in I}X_\alpha$, and define $g:X\to I$ by setting $g(x)=\alpha$ iff $x\in X_\alpha$. Then $g$ is a surjection, so by hypothesis there is an injection $f:I\to X$ such that $f(\alpha)\in X_\alpha$ for each $\alpha\in I$. (Note: I’m assuming that you inadvertently omitted that last bit in stating the problem. If not, the following argument doesn’t work, and I’m not sure that the result is even true.) Let $Y=f[I]$; then $|Y\cap X_\alpha|=1$ for each $\alpha\in I$. By the previous exercise, the axiom of choice holds.