# a surjection between finite sets of the same cardinality is bijective

###### Theorem.

Let $A$ and $B$ be finite sets^{} of the same cardinality. If $f\mathrm{:}A\mathrm{\to}B$ is a surjection then $f$ is a bijection.

###### Proof.

Let $A$ and $B$ be finite sets with $|A|=|B|=n$. Let $C=\{{f}^{-1}\left(\{b\}\right)\mid b\in B\}$. Then $\bigcup C\subseteq A$, so $|\bigcup C|\le n$. Since $f$ is a surjection, $|{f}^{-1}\left(\{b\}\right)|\ge 1$ for each $b\in B$. The sets in $C$ are pairwise disjoint because $f$ is a function; therefore, $n\le |\bigcup C|$ and

$$\left|\bigcup C\right|=\sum _{b\in B}|{f}^{-1}\left(\{b\}\right)|.$$ |

In the last equation, $n$ has been expressed as
the sum of $n$ positive integers; thus $|{f}^{-1}\left(\{b\}\right)|=1$ for each $b\in B$, so $f$ is injective^{}.
∎

Title | a surjection between finite sets of the same cardinality is bijective^{} |
---|---|

Canonical name | ASurjectionBetweenFiniteSetsOfTheSameCardinalityIsBijective |

Date of creation | 2013-03-22 15:23:28 |

Last modified on | 2013-03-22 15:23:28 |

Owner | ratboy (4018) |

Last modified by | ratboy (4018) |

Numerical id | 5 |

Author | ratboy (4018) |

Entry type | Result |

Classification | msc 03-00 |

Related topic | OneToOneFunctionFromOntoFunction |