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