Theorem 1   Given an onto function from a set $A$ to a set $B$ there exists a one-to-one function from $B$ to $A$

Proof. Suppose $f:A\rightarrow B$ is onto, and define $\mathcal{F}=\big\{f^{-1}(\{b\}):b\in B\big\}$ that is, $\mathcal{F}$ is the set containing the pre-image of each singleton subset of $B$ Since $f$ is onto, no element of $\mathcal{F}$ is empty, and since $f$ is a function, the elements of $\mathcal{F}$ are mutually disjoint, for if $a\in f^{-1}(\{b_1\})$ and $a\in f^{-1}(\{b_2\})$ we have $f(a)=b_1$ and $f(a)=b_2$ whence $b_1=b_2$ Let $\mathscr{C}:\mathcal{F}\rightarrow\bigcup\mathcal{F}$ be a choice function, noting that $\bigcup\mathcal{F}=A$ and define $g:B\rightarrow A$ by $g(b)=\mathscr{C}\big(f^{-1}(\{b\})\big)$ To see that $g$ is one-to-one, let $b_1,b_2\in B$ and suppose that $g(b_1)=g(b_2)$ This gives $\mathscr{C}\big(f^{-1}(\{b_1\})\big)=\mathscr{C}\big(f^{-1}(\{b_2\})\big)$ but since the elements of $\mathcal{F}$ are disjoint, this implies that $f^{-1}(\{b_1\})=f^{-1}(\{b_2\})$ and thus $b_1=b_2$ So $g$ is a one-to-one function from $B$ to $A$