Show that if $f\{1,\dots,n\}\to\{1,\dots,n\}$ is surjective then it is also bijective.

Question

Show by induction that if $f:\{1,\dots,n\}\to\{1,\dots,n\}$ is surjective then it is also bijective.

My approach:

Base case $n=1$:

$f:\{1\}\to\{1\}$ is trivially bijective.

Induction hypothesis for a $n\in\mathbb{N}$:

$f:\{1,\dots,n\}\to\{1,\dots,n\}$ is surjective then it is also bijective.

Induction step $n\to n+1$:

Let's consider the surjective function $f:\{1,\dots,n+1\}\to\{1,\dots,n+1\}$. If $f^{-1}(n+1)$ contains only one element, i.e. $f^{-1}(n+1)=:k$, then $g:\{1,\dots,n\}\to\{1,\dots,n\}$ with

$$\begin{align*} g(x):=\begin{cases}f(x),&x\neq k,\\ f(n+1),&x=k\end{cases} \end{align*}$$

is surjective and we can apply the induction hypothesis. Hence, $g$ is bijective. Consequently, $$\begin{align*} f(x):=\begin{cases}g(x),&x\neq k,\\ n+1,&x=k,\\ f(n+1),&x=n+1\end{cases} \end{align*}$$ is bijective.

If $f^{-1}(n+1)$ contains more than one element, WLOG we denote those elements by $f^{-1}(n+1)=:\{1,\dots,k\}$, then $g:\{1,\dots,n\}\to\{1,\dots,n\}$ with

$$\begin{align*} g(x):=\begin{cases}f(x),&x\notin \{1,\dots,k\},\\ f(n+1),&x\in\{1,\dots,k\}\end{cases} \end{align*}$$ is surjective and we can apply the induction hypothesis. Hence, $g$ is bijective. Consequently, $$\begin{align*} f(x):=\begin{cases}g(x),&x\notin \{1,\dots,k\},\\ n+1,&x\in \{1,\dots,k\},\\ f(n+1),&x=n+1\end{cases} \end{align*}$$ is bijective.

Is this correct? It seems a bit odd to conclude bijectivity as we have $f(n+1)$ for all $x\in\{1,\dots,k\}$.

---

EDIT:

As $f:\{1,\dots,n+1\}\to\{1,\dots,n+1\}$ is surjective we know that $f^{-1}(n+1)\neq\emptyset$ and define $S:=f^{-1}(n+1)$. We consider two cases:

If $n+1\notin S$, then we define $g:\{1,\dots,n\}\to\{1,\dots,n\}$ by $$\begin{align*} g(x):=\begin{cases}f(x),&x\notin S,\\ f(n+1),&x\in S.\end{cases} \end{align*}$$ We take an arbitrary $y\in\{1,\dots,n\}$ and by surjectivity of $f$ there exists a $x\in\{1,\dots,n+1\}$ such that $f(x)=y$.

1.) Either $x=n+1$ so that any $z\in S$ yields $g(z)=f(n+1)=y$,

2.) or $x<n+1$ and because of $y< n+1$ we know that $x\notin S$ which yields $g(x)=f(x)=y$.

Consequentially, $g$ is surjective and we can apply the induction hypothesis so that $g$ must be bijective. This means that $S$ contains exactly one element which we denote by $s$. Now we can represent $f:\{1,\dots,n+1\}\to\{1,\dots,n+1\}$ equivalently by $$\begin{align*} f(x):=\begin{cases}g(x),&x\in\{1,\dots,n\}\setminus\{s\}\\ n+1,&x=s\\f(n+1),&x=n+1.\end{cases} \end{align*}$$ We know that $g$ is bijective so $f(n+1)\neq g(x)$ for all $x\in\{1,\dots,n\}\setminus\{s\}$. Also $n+1\neq f(n+1)$ by assumption and $g(x)\neq n+1$ for all $x\in\{1,\dots,n\}$ because $g$ maps to $\{1,\dots,n\}$. Bearing this in mind we check for injectivity of $f$. If $f(x)=f(y)$ then this could only be possible if $x=y=s$, $x=y=n+1$ or $x,y\in\{1,\dots,n\}$. But as $g$ is bijective the third possibility also delivers $x=y$. So $f$ is injective and hence bijective.

Now we assume $n+1\in S$ and define $g:\{1,\dots,n\}\to\{1,\dots,n\}$ by $$\begin{align*} g(x):=\begin{cases}f(x),&x\notin S,\\ 1,&x\in S.\end{cases} \end{align*}$$ Let's take an arbitrary $y\in\{1,\dots,n\}$, then by surjectivity of $f$ there exists a $x\in\{1,\dots,n+1\}$ such that $f(x)=y$. As $y\leq n$ the corresponding $x$ satisfies $x\notin S$ so that $f(x)=g(x)=y$. Hence, $g$ is bijective by induction hypothesis. This means, that $S\cap\{1,\dots,n\}=\emptyset$ because otherwise $g$ couldn't be injective. So $S$ contains only one element, namely $n+1$. Now we can represent $f:\{1,\dots,n+1\}\to\{1,\dots,n+1\}$ equivalently by $$\begin{align*} f(x):=\begin{cases}g(x),&x\in\{1,\dots,n\}\setminus\{n+1\}\\ n+1,&x=n+1.\end{cases} \end{align*}$$ In this case we directly see that $f$ must be injective. Hence, $f$ is bijective.

Answer 1

Write $$\{1,2,\dots,n\}\supseteq f^{-1}(\{1,2,\dots,n\})=\bigcup_{k=1}^nf^{-1}(\{k\})$$

and note that

1. the $f^{-1}(\{k\})$ are disjoint

2. $f^{-1}(\{k\})$ has at least one element (because $f$ is surjective)

Now, taking cardinalities

$$n=|\{1,2,\dots,n\}|\ge |f^{-1}(\{1,2,\dots,n\})|=\sum_{k=1}^n|f^{-1}(\{k\})|\ge\sum_{k=1}^n 1=n$$ which implies that $f^{-1}(\{k\})$ has precisely one element for any $k$. This is the very definition of injectivity: if $f(a)=f(b)=k$ then $$a,b\in f^{-1}(\{k\})$$ so it must be the case $a=b$ is the only element of $f^{-1}(\{k\})$

Answer 2

Your argument is correct, but I'll provide another proof here. We shall prove the generalisation of the question: "Show that if $f:\{a_1, a_2, \dots, a_n\}\to\{a_1, a_2, \dots, a_n\}$ is surjective, then it is also bijective, where $\{a_1, a_2, \dots, a_n\}$ are distinct". Let $P(n)$ denote this statement for the case of $n$.

Base case: $P(1)$ is clearly true.

Induction hypothesis: $P(1), P(2), \dots, P(k)$ are all true, where $k\in\mathbb{Z}+$.

Inductive step: We claim that $P(k+1)$ is true.

First if there exists $i$ such that $f(a_i)=a_i$, then we can "remove" $a_i$ and we are left with $k$ elements. Since $P(k)$ is true, we know that $P(k+1)$ is true.

Now suppose $\forall i, f(a_i)\neq a_i$. Define the sequence $\{b_i\}_{i=1}^{k+1}$ by $b_0=a_1$ and $b_i=f(b_{i-1})$ for $i\geq1$. Since $b_i\in\{a_1, a_2, \dots, a_n\}$, the sequence must be periodic. Let $m>0$ be the first element such that $b_m=b_0$.

First note that $m<n$ because, since $f(x)$ is surjective, $\{b_0, b_1, \dots, b_{n-1}\}\subseteq\{a_1, a_2, \dots a_n\}$, so $m\leq n-1\implies m<n$. Second note that since $\{a_1, a_2, \dots, a_n\}$ is distinct, $\{b_0, b_1, \dots, b_{n-1}\}$ is distinct. Hence, we can "remove" $b_0, b_1, \dots, b_{m-1}$ and we are left with $k+1-m$ elements. Since $P(k+1-m)$ is true, we know that $P(k+1)$ is true.

This completes the induction.