Every injection $f: A \to A$ for finite $A$ is surjective

Question

I cannot prove this rather simple theorem in set theory.

Let $A$ be a finite set. If $f: A \to A$ is injective, then $f$ is also surjective.

My Attempt. Suppose for contradiction that this isnt the case. So there exists a mapping $f: A \to A$ that is not surjective. Then the image of $A$ under $f$ is a proper subset of $A$, i.e., $\text{Im}(f) = C$, where $C \subsetneq A$. Define the mapping $g: C \to A$, where $c \mapsto f^{-1} (\{c\})$. By construction, $g$ is not onto, but since $f$ is injective, it is well-defined, since every $c \in C$ has a unique preimage in $A$. Hence, every $c$ is sent to exactly one $a \in A$. But, if that is the case, $|C| = |A|$, as a function is by definition defined on its entire domain. With this contradiction, we conclude that no such function $f$ can exist.

Answer 1

Your proof is correct, but using a proof by contradiction makes it unnecessarily complicated.

Since $f$ is injective, no two distinct elements of $A$ are mapped to the same element. Hence $|f(A)| = |A|$. As $A$ is finite, $f$ must be surjective.

Answer 2

Take a copy of the set $A$ and name it $B$. Take an arbitrary element $a_1\in A$ and its image $f(a_1)$ and delete it from the corresponding sets. The new sets $A_1$ and $B_1$ satisfy $|A_1| = |A|-1$ and $|B_1| = |B|-1$. Now take $a_2 \in A_1$ and its image $f(a_2)\in B_1$. Since $f$ is injective $f(a_2) \neq f(a_1)$, hence $f(a_2) \in B_1$. Now delete them from corresponding sets. In the $(2\le) k^{th}$ step take $a_k\in A_{k-1}$. Due to injectivity of the map $f(a_{k}) \notin \{f(a_1),\ldots f(a_{k-1}\} = B\setminus B_{k-1}$, hence $f(a_k) \in B_{k-1}$. Delete them, then leftover sets $A_k$ and $B_k$ satisfy $|A_k| = |A_{k-1}| -1 $ and $|B_k| = |B_{k-1}| -1$. After $|A|$ steps you end up with empty set, i.e. $|A_{|A|}| = \emptyset$. If $B_{|A|}$ was not empty then going back the chain one gets $|B|\geq |A| +1$ which contradicts $|A| = |B|$, since $B$ was a copy of $A$.

Answer 3

Let $A$ be a finite set and $f:A\to A$ be injective.

We define the (common) notation $f^m(a)=\underbrace{f\circ\dotso\circ f}_{m-times}(a)$ for $m\in\mathbb{N}$.

Since for an injective function $f: X\to Y$ and a function $g: Y\to X$ the function $f\circ g$ is injective, we have that $f^m$ is injective.

Since $A$ is a finite set it exists a $k\in\mathbb{N}$, $k>1$ (the equality $f^1=f$ is trivial) with $f^k=f$ (which means that $f^k(a)=f(a)$ for every $a\in A$). Without loss of generality we can assume that $k\neq 2$. If $k=2$ then $f$ is the identity map, since $f^2(a)=f(f(a))=f(a)$ for every $a\in A$. In that case there is nothing to show.

Why does such $k$ exist? Well, $A$ is finite. That means there is only a finite number of possible functions that can be constructed by concatenating $f$ with itself, since every element can possibly be only mapped at $|A|$ different elements, which means we can at most have $|A|^{|A|}$ possible functions. So if we just concatenate $f$ as often as necessary, we will end up with $f$ again.

As I said it holds that $f^k(a)=f(a)$ for every $a\in A$. So $f(f^{k-1}(a))=f(a)$. But $f$ is injective, which means that $f^{k-1}(a)=a$.

But then we found for every $a\in A$ a preimage of $a$, which is $f^{k-2}(a)$, since $f(f^{k-2}(a))=f^{k-1}(a)=a$. Here we need our assumption without loss of generality, that $k>2$. Else it is not clear that $k-2$ is an element of $\mathbb{N}$ which would make the expression $f^{k-2}$ pointless.

This proof might not be the easiest to find (or even to understand). I tried to make every step clear, which makes the proof look long and complicated.