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\colon A\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|\leq n$. Since $f$ is a surjection, $|f^{-1}\left(\{b\}\right)|\geq 1$ for each $b\in B$. The sets in $C$ are pairwise disjoint because $f$ is a function; therefore, $n\leq|\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  ASurjectionBetweenFiniteSetsOfTheSameCardinalityIsBijective 2013-03-22 15:23:28 2013-03-22 15:23:28 ratboy (4018) ratboy (4018) 5 ratboy (4018) Result msc 03-00 OneToOneFunctionFromOntoFunction