a surjection between finite sets of the same cardinality is bijectiveASurjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective2005-07-12 23:23:232005-07-13 10:05:59Resultan injection between two finite sets of the same cardinality is bijective% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here\newtheorem*{theorem}{Theorem}
\begin{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.
\end{theorem}
\begin{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.
\end{proof}