# 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 $\mathcal{F}=\{{f}^{-1}(\{b\}):b\in B\}$; 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 $\mathcal{C}:\mathcal{F}\to \bigcup \mathcal{F}$ be a choice function, noting that $\bigcup \mathcal{F}=A$, and define $g:B\to A$ by $g(b)=\mathcal{C}\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 $\mathcal{C}\left({f}^{-1}(\{{b}_{1}\})\right)=\mathcal{C}\left({f}^{-1}(\{{b}_{2}\})\right)$, 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^{} |