one-to-one function from onto function

Theorem.

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\to B$ is onto, and define $ℱ=\{f^{-1}(\{b\}):b\in B\}$; that is, $ℱ$ is the set containing the pre-image of each singleton subset of $B$. Since $f$ is onto, no element of $ℱ$ is empty, and since $f$ is a function, the elements of $ℱ$ 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 $𝒞:ℱ\to \bigcup ℱ$ be a choice function, noting that $\bigcup ℱ=A$, and define $g:B\to A$ by $g(b)=𝒞\left(f^{-1}(\{b\})\right)$. 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$𝒞\left(f^{-1}(\{b_1\})\right)=𝒞\left(f^{-1}(\{b_2\})\right)$, but since the elements of $ℱ$ 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$.∎