Login
This is a place holder for potential sponsor logos.
a surjection between finite sets of the same cardinality is bijective
Theorem 1 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| \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 \begin{equation*} \\ \left|\bigcup C \right|=\sum_{b\in B}|f^{-1}\left(\{b\}\right)| .\end{equation*} 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. 
a surjection between finite sets of the same cardinality is bijective is owned by ratboy.
None.