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