# Show that this type of function is surjective iff it's injective.

Here's a theorem that I think intuitively makes sense, but I was hoping to prove more rigorously:

Theorem: Suppose $|A|=|B|=n$, where $n\in\mathbb{N}$. Consider the function $f:A \to B$. Then $f$ is onto iff it's one-to-one.

I think I can handle proving this in one direction. That is, I will show that if $f$ is not onto, then it must not be one-to-one.

Suppose $f$ is not onto. Then $∃b^*∈B$ such that $∀a∈A$, $f(a)≠b^*$. Thus, $f$ must map all $n$ elements in $A$ to at most $n-1$ elements in $B$. By the Pigeonhole Principle, it follows that $∃a_1,a_2∈A$ and $∃b'∈B$ such that $f(a_1)=b'=f(a_2)$ yet $a_1≠a_2$. So $f$ is not one-to-one, as desired.

Hopefully that was rigorous. As for the other direction ($f$ is not one-to-one $\implies$ $f$ is not onto), I could use some help. Any suggestions?

Note: I know that this theorem fails if the sets $A$ and $B$ are not finite. So whatever proof used for this direction should somehow take that into account.

Hint: If $f(a)=f(a')=b$, then we could restrict $f$ to $A\setminus \{a'\}$ and have the same range.
• Sorry, I've been staring at your hint for half an hour and I don't really know where to go from there. Here's what I have so far. Suppose $f$ is not one-to-one. Then $∃a_1,a_2∈A$ and $∃b'∈B$ such that $f(a_1 )=b'=f(a_2)$ yet $a_1≠a_2$. Now define the new function $g:A\backslash\{a_2\} \to B$ by $g(a)=f(a)$. Note that $\text{rng}(f) = \text{rng}(g)$. Thus... {insert crucial math step here} ...thus, $∃b^*∈B$ such that $∀a∈A$, $f(a)≠b^*$. So $f$ is not onto, as desired. – Adriano May 10 '13 at 5:19
• @Adriano It follows from the pigeonhole principle that there can be no surjection $f$ from an $(n-1)$-element set to an $n$-element set. (Otherwise we could define an injection $g$ from the $n$-element set to the $(n-1)$-element set by letting $g(y)$ be the least $x$ with $f(x) = y$.) – Trevor Wilson May 10 '13 at 5:37