# 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\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$. ∎

 Title one-to-one function from onto function Canonical name OnetooneFunctionFromOntoFunction Date of creation 2013-03-22 16:26:55 Last modified on 2013-03-22 16:26:55 Owner mathcam (2727) Last modified by mathcam (2727) Numerical id 8 Author mathcam (2727) Entry type Definition Classification msc 03E25 Related topic function Related topic ChoiceFunction Related topic AxiomOfChoice Related topic set Related topic onto Related topic SchroederBernsteinTheorem Related topic AnInjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective Related topic ASurjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective Related topic Set Related topic Surjective