Rigorous proof that surjectivity implies injectivity for finite sets

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?

Solution 1:

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.

Solution 2:

The trick, when you do this by induction, is that you replace $f$ by a function $g$ which maps the $n+1$-th element to itself. Without loss of generality, we can assume $A=\{0,\ldots,n\}$. And $f\colon A\to A$ is surjective.

First we can assume that $f(n)\neq n$, for if it were then by simply taking $k$ to be some element such that $f(k)=0$ and redefining $f'(n)=f(k)$ and $f'(k)=f(n)$, and $f'(i)=f(i)$ otherwise, we have $f'$ a surjective function with this condition and from $f'$ being injective we can show that $f$ is injective. We now define $g$ as follows:

$$g(i)=\begin{cases} n & i=n\\ f(n) & f(i)=n\\ f(i) &\text{otherwise}\end{cases}$$

Now $g$ is surjective, since if $j\leq n$, then either $j=n$ or $j=m$ and we're done; or there is some $i<n$ such that $f(i)=j$ (we know that $n$ itself is not mapped to $j$ by $f$, since $f(n)=m$). But this $i<n$ and $i\neq k$ either, so $f(i)=g(i)=j$ as wanted.

Now the induction can go through. $g\restriction\{0,\ldots,n-1\}$ is injective, and therefore $g$ is injective. And from this $f$ is also injective by a similar argument.

Solution 3:

I'm gonna provide some elegant direct proofs (without contradiction) that injectivity implies surjectivity and that surjectivity implies injectivity.

First, we introduce some notation as shown below.

$$f^k(x) := \begin{cases} x & \text{if } k = 0 \\[3pt] f(f^{k-1}(x)) & \text{if } k > 0 . \end{cases}$$

Injectivity implies surjectivity

Given any arbitrary $x \in A$, since $A$ is finite, the sequence $$x, f(x), f^2(x), \dotsc , f^k(x)$$ must have duplicate terms. Thus there must exist $m > n \ge 0$ such that $$f^m(x) = f^n(x) .$$ If $n \ge 0$, then, due to the injectivity of $f$, we have $$\begin{align*} f^{m-1}(x) &= f^{n-1}(x) \\ & \:\mathrel{\vdots} \\ f^{m-n}(x) &= x . \end{align*}$$ Let $x' = f^{m-n-1}(x)$, then $f(x') = x$. Since $x$ is arbitrary, the map $f$ is surjective.

Source of the above proof: Kostrikin's Introduction to Algebra.

Surjectivity implies injectivity

Given any arbitrary $x \in A$, since $f$ is surjective, there must exist an $x_1$ such that $$f(x_1) = x .$$ Similarly, there must exist $x_2, x_3, \dotsc , x_k$ such that $$\begin{align*} f(x_2) &= x_1 \\ f(x_3) &= x_2 \\ & \:\mathrel{\vdots} \\ f(x_k) &= x_{k-1} \\ f^2(x_k) &= x_{k-2} \\ & \:\mathrel{\vdots} \\ f^k(x_k) &= x . \end{align*}$$ Since $A$ is finite, the sequence $x_1, x_2, \dotsc , x_k$ must have duplicate terms. Thus there must exist $m > n \ge 0$ such that $$x_m = x_n .$$ Consequently, $$f^{m-n}(x) = f^{m-n}(f^n(x_n)) = f^m(x_n) = f^m(x_m) = x .$$

Applying the above result, we have the following.

Given any arbitrary $x, x' \in A$, there must exist $m > n \ge 0, \bar m > \bar n \ge 0$ such that $$f^{m-n}(x) = x \quad \text{and} \quad f^{\bar m - \bar n}(x') = x' .$$

Consequently, $$f^{(m-n)(\bar m - \bar n)}(x) = x \quad \text{and} \quad f^{(m-n)(\bar m - \bar n)}(x') = x' .$$

Now we have two way to go.

If $x \ne x'$, then $$f^{(m-n)(\bar m - \bar n)}(x) \ne f^{(m-n)(\bar m - \bar n)}(x') .$$ Since $(m-n)(\bar m - \bar n) \ge 1$, $$f(x) \ne f(x') .$$ Thus the map $f$ is injective.

If $f(x) = f(x')$, then, since $(m-n)(\bar m - \bar n) \ge 1$, we have $$\begin{align*} f^{(m-n)(\bar m - \bar n)}(x) &= f^{(m-n)(\bar m - \bar n)}(x') \\ x &= x' . \end{align*}$$ Thus the map $f$ is injective.

Souce of the above proof: After reading Kostrikin's proof, I feel there must exist an equally elegant proof that surjectivity implies injectivity. After spending an afternoon thinking about it, the proof finally comes out of my mind.