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?

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.

• That's very nice! – Asaf Karagila Oct 24 '14 at 13:10
• This is the pigeonhole principle mildly disguised. – Pedro Tamaroff Oct 24 '14 at 13:58
• To me, this is the pigeonhole principle. There is no disguise. This is a nice proof! – Hugh Denoncourt Oct 24 '14 at 15:39
• i have a question: can this proof be extended to any finite sets A,B with |A|=|B|? – SAJW Oct 29 '16 at 12:59
• @saturatedexpo, sure, just compose with a bijection $A \to B$. – lhf Oct 29 '16 at 14:13

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.

• Ah, nice. By the way, little type there: "is injective, and therefore $g$ is injective." Thank you! – Addem Oct 24 '14 at 13:08
• I don't see the typo. – Asaf Karagila Oct 24 '14 at 13:09
• Sorry, was confused about what was being said, no typo. But now I'm thinking, how do we know the restriction of $g$ is injective? Presumably by the inductive hypothesis using the fact that the restriction is surjective. But how do we know the restriction is well-defined? It seems that, at this point in the proof, it is possible that some two elements mapped to $n$ so that there is some $p\ne n$ for which $g(p) = n$ and then if the range is restricted then $g$ will no longer be defined for $p$. – Addem Oct 24 '14 at 13:31
• Oh, that's correct. But that's quite easy to fix, hang on. – Asaf Karagila Oct 24 '14 at 13:32
• I see the change but I can't say that I see how it fixes the problem. It still seems to me that, in $g$, some element other than $n$ could map to $n$. For instance, perhaps in $f$ there were two things that mapped to $n$--you just exchanged one of them for $n$ but the other remains. – Addem Oct 24 '14 at 13:42

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.

Method 1:

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.

Method 2:

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.

Let $f\colon A\to A$ be a surjective map. Let $$\mathcal A=\{\,X\subseteq A\mid f|_X\colon X\to A\text{ is injective}\,\}.$$ Then $\mathcal A$ is not empty because $f|_\emptyset$ is injective. Let $B\in\mathcal A$ be maximal (how?). Then $f|_B$ is onto as otherwise we'd find $b\in A$ with $f(b)\notin f(B)$ and then $B\cup\{b\}$ would conflict with $B$'s maximality. Thus we have found a subset $B\subseteq A$ that is in bijection with $A$. Now we use that $A$ is finite: It implies that $B$ cannot be a proper subset, i.e. $A=B\in\mathcal A$.

• I like how we have to use Zorn's lemma here! (Although, to be fair, if the partial order is finite, we can just prove Zorn's lemma directly. :-P) – Asaf Karagila Oct 24 '14 at 15:34
• @AsafKaragila That's why I invoked finiteness of $A$ only later, to have more fun – Hagen von Eitzen Oct 24 '14 at 15:57
• Hi @AsafKaragila, 1. Since there is no element in $\emptyset$, how can $f|_\emptyset :\emptyset \to A$ be injective? 2. Which order is set $\mathcal A$ ordered by? (I don't see it explicitly mentioned) 3. The author use Zorn's lemma, so his proof equivalently appeal to Axiom of Choice (in the form of Zorn's lemma), while lhf 's proof does not need to do so. Is it true that lhf 's proof need fewer axioms then Hagen von Eitzen's one? Thank you for your clarifying! – MadnessFor MATH Apr 7 '18 at 4:15
• Hi @AsafKaragila, after searching MSE, I found that $f|_\emptyset :\emptyset \to A$ is indeed an injection. math.stackexchange.com/questions/650384/… . But it still seem strange to me. :) – MadnessFor MATH Apr 7 '18 at 4:27
• From your comment, I know that $A$ is finite set, so we don't need to appeal to the full Zorn's lemma :) – MadnessFor MATH Apr 7 '18 at 5:10