Let $S$ be a finite set. Let $f$ be a surjective function from $S$ to $S$.
How do I prove that it is injective?
$\endgroup$ 23 Answers
$\begingroup$Let $S$ be a finite set, and $f : S \to S$ a function. Then the following are equivalent:
- $f$ is injective.
- $f$ is surjective.
- $f$ is bijective.
This is really just a counting argument. First, suppose $f$ is injective. If $S$ has $n$ elements, by our assumption, this means the image of $f$ has at least $n$ elements. But the image of $f$ is contained in $S$, so it has at most $n$ elements; so the image of $f$ contains exactly $n$ elements and is therefore the whole of $S$, i.e. $f$ is surjective.
Next, suppose $f$ is surjective. So, for each $y$ in $S$, there is an $x$ in $S$ such that $y = f(x)$; we choose one such $x$ for each $y$ and define a function $g : S \to S$ so that $g(y) = x$. By construction, $f(g(y)) = y$, so $g$ must be injective, and hence, must be surjective by the above argument. So $g$ is a bijection, and $f$ is a left inverse for $g$. But a left inverse for a bijection is also a right inverse, so this implies $f$ is a bijection, and a fortiori an injection.
Notice that the very first part of the argument fails when $S$ is not finite. For example, let us consider the function $f : \mathbb{N} \to \mathbb{N}$ defined by $f(x) = x + 1$. This function is certainly injective but is not surjective. Similarly, the function $g : \mathbb{N} \to \mathbb{N}$ defined by $f(0) = 0$ and $f(x + 1) = x$ is surjective, but not injective.
$\endgroup$ 6 $\begingroup$Suppose that $f$ is an injective function and not surjective, i.e. there is point $y\in S$ such that there is no point $x\in S$ with $f(x)=y$. Since $f$ is a function, every $x\in S$ must work as abscissa in the relation $f$. Hence we must have some $x_1 \ne x_2$ with $f(x_1)=f(x_2)$, which gives a contradiction. Therefore $f$ must be onto.
$\endgroup$ $\begingroup$The purpose of this answer is to supply proof details for the first paragraph of Zhen Lin's answer.
For any $k \in \Bbb N$ let $[k]$ represent the set $\{0,\ldots,k-1\}$.
Lemma 1: A function $\sigma: [n] \to [n-1]$ can't be injective.
Proof
To get a contradiction assume we can write
$\tag 1 \sigma: [n] \to [n-1] \quad \text{is an injection with } n-1 \ge 1$
If necessary we can apply a transposition
$\quad \big(n-2 \;\; \sigma(n-1) \big) \circ \sigma$
and therefore claim the existence of another injection
$\tag 2 \sigma_{|}: [n-1] \to [n-2] \quad \text{is an injection with } n-2 \ge 1$
Using the method of infinite descent we conclude that the lemma must be true. $\quad \blacksquare$
Proposition 2: An injective function $f: S \to S$ on a finite set $S$ must also be a surjection.
Proof
To get a contradiction assume $a \in S$ is not in the range of $f$. We can put $S$ into a bijective correspondence
$\tag 3 \kappa: S \to [n] \quad \text{where } \kappa(a) = n-1$
The injective function $\kappa \circ f \circ \kappa^{-1}: [n] \to [n]$ doesn't have $n-1$ in its range, and by applying lemma 1 we arrive at the contradiction. $\quad \blacksquare$
$\endgroup$
