I'm trying to prove that, for a finite set $A$, if the map $f: A\rightarrow A$ is a surjection, then it's an injection. I've looked at this post: Surjectivity implies injectivity but the arguments there seem very round-about, proving that injectivity implies surjectivity first. I think I've seen other proofs, too, but they all sound kind of flimsy. They tend to go something like "If the function is surjective then no two arguments can go to the same image, since that would require some element of the range not being the image of any element." While that's true and I see what the argument has in mind, it's no more convincing than the statement of the claim that we're trying to prove! Without a more rigorous proof, both seem to rely on the intuition that everything has to go to one and only one thing, but we're supposed to be proving that.
But I've been trying to develop a more thorough and direct proof, and haven't been able to. I've tried induction:
The theorem holds trivially if $|A|=0$. Suppose the theorem holds up to $n=|X|$, and let $|A|=n+1$ and $f:A\rightarrow A$ be a surjection. Then let $x\in A$ and $f^{-1}(x)$ be the set of all elements $y\in A$ such that $f(y)=x$…
But at this stage I want to restrict my function, but that has the disadvantage that if $f(y)$ has more than one element in it, when I pluck it out of $A$ as the domain and pluck $x$ out of $A$ as the range, then I may not be dealing with a function mapping from a set to itself and so I don't get to use the inductive hypothesis.
Any other proofs you know about?
Best Answer
Let $f: A\to A$ be any function. For each $a\in A$, let $N(a)$ be the number of elements in $A$ that are mapped to $a$. Then $\sum_a N(a) = n = |A|$ because every element of $A$ is mapped to some element of $A$. (This is the statement that the fibers of $f$ partition $A$.)
If $f$ is surjective, then $N(a)\ge 1$ for all $a$. If $f$ is not injective, then $N(a_0)>1$ for some $a_0$. But then $\sum_a N(a) > n$, a contradiction.
This same technique works for the dual statement:
If $f$ is injective, then $N(a)\le 1$ for all $a$. If $f$ is not surjective, then $N(a_0)<1$ for some $a_0$. But then $\sum_a N(a) < n$, a contradiction.