# Show that $f$ is one-to-one if and only if it is onto.

Suppose that $f$ is a function from A to B, where A and B are finite sets with $| A |= |B|$. Show that $f$ is one-to-one if and only if it is onto.

How should I begin?

• @JessicaK, isn't $f$ is a function from $A$ to $B$, so $b \in A$, not in $B$ for $f$ to be evaluated there? Commented Apr 16, 2015 at 15:13
• @Ilham Opps, I'll fix that. Commented Apr 16, 2015 at 15:14
• Do you know what the definition of 1-1 and onto are? First suppose $f$ is 1-1, (i.e., for $a_{1}, a_{2}\in A$ $f(a_{1}) = f(a_{2})$ implies $a_{1} = a_{2}$. Note that $f(a_{1}), f(a_{2})\in B$.) and show that $f$ is onto using this definition and the hypothesis of the question. Then use the definition of onto and show $f$ must be 1-1. Commented Apr 16, 2015 at 15:17

Use the pigeonhole principle, to see that you can't have the $|B|$ pigeonholes of $B$ having only one "pigeon" of $A$ in them without filling them all up since $|B| = |A|$. Thus injectivity implies surjectivity.
The other direction is a dual statement. Now let for each $b \in B$, let $g(b)$ be the number of distinct elements of $A$ mapped to $b$ by $f$. Since $f$ is surjective, each $g(b)$ is at least one. Suppose for contradiction $f$ is not injective, then at least one of these $g(b)$ is greater than 1. So their sum is greater than $|B|$, and hence greater than $|A|$. Is that possible, considering any function from $A \to B$ maps exactly one element of $B$ to each element of $A$?