2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Hint: If $f(a)=f(a')=b$, then we could restrict $f$ to $A\setminus \{a'\}$ and have the same range.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Adriano May 10 '13 at 5:19
  • 1
    $\begingroup$ @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$.) $\endgroup$ – Trevor Wilson May 10 '13 at 5:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.