[Math] Show that, if $f:A\to B$ is a function, with $A$ and $B$ being finite sets, and $|A|=|B|$, then $f$ is one to one iff $f$ is onto.

discrete mathematics

I'm a little stuck with this proof. Not sure where to go. I was thinking that I could first assume that $f$ is one to one and prove that it's onto, and then assume it's onto and prove that it's one to one… but I'm not sure what to do with the knowledge that $|A|=|B|=m\in\mathbb{Z}\geq 0$.

I've tried to start by defining what it means for $f$ to be one-to-one, and going from there…

\begin{align*}
f\text{ is one-to-one}&\Longrightarrow f=\{(a,b)\in A\times B\mid b=f(a)\wedge f^{-1}(b)=a\}\\
&\Longrightarrow \dots\\
&\Longrightarrow \text{$f$ is onto}
\end{align*}

but not sure where to go from there… I have a feeling that my definition is too presumptuous to begin with, since I'm trying to show that $f$ is onto… not assume that it is.

Best Answer

If $f$ is not one-to-one, then there are distinct $a_1, a_2 \in A$ such that $f(a_1) = f(a_2) \in B$. As a result,

$$ \left| f(A) \right| < |A|.$$

So there must be some $b \in B$ with no preimage. Hence, $f$ is not onto.

For the converse, just run the arguments in reverse.

Related Question