# Any injection $f: A \to A$ is surjective if $A$ is finite

elementary-set-theoryfunctionssolution-verification

I am trying to prove that if $$A$$ is a finite set, then any injective function $$f: A \to A$$ is surjective. I have a few alternative proofs of this written. I'm not sure if any of these contain errors or are preferable to another, so I was hoping someone could take a look.

Proof 1.

As $$f$$ is injective, then there exists a bijection $$A \stackrel{\sim}{\to} \mathrm{Im}(f)$$, so $$|A| = |\mathrm{Im}(f)|$$. But since $$\mathrm{Im}(f) \subset A$$ and $$A$$ is finite, we must have $$\mathrm{Im}(f) = A$$.

Proof 2

Let $$f$$ be injective. As $$A$$ is finite, there are only $$|A|!$$ injective maps $$A \to A$$, so there exists $$n \in \mathbb{N}$$ such that $$f^n = f$$. If $$n = 2$$, then $$f^2 = f$$. As $$f$$ is injective, it has a left inverse, so $$f = \mathrm{id}_A$$, which is surjective, so we can suppose $$n > 2$$. Composing on the left with $$g: A \to A$$, the left inverse of $$f$$, we obtain $$f^{n-1} = \mathrm{id}_A$$. In particular, given $$a \in A$$, we have $$f(f^{n-1} (a)) = \mathrm{id}_A (a) = a$$. So given $$a \in A$$, there exists $$x := f^{n-1} (a) \in A$$ such that $$f(x) = a$$, so $$f$$ is surjective.

If $$f:A \rightarrow A$$ is injective but not surjective, then pick $$a\in A$$ that is not in the image of $$f$$, we show that $$a, f(a), f(f(a)), \cdots$$ are pairwise distinct, therefore $$A$$ is not finite.
We show $$f^{(n)}(a)\not=f^{(m)}(a), \forall m>n$$ by indution on $$n$$. When $$n=0$$, as $$a$$ is not in the image of $$f$$, $$a\not=f^{(m)}(a)$$ for any $$m>0$$. In general for $$n\ge 1$$, if $$f^{(n)}(a)=f^{(m)}(a)$$, then $$f^{(n-1)}(a) = f^{(m-1)}(a)$$ by injectivity, but this contradicts the induction hypothesis.