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.

## Best Answer

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.