How many elements has S(M,M)?

Question

For two sets $M,N$ let $S(M,N)$ be the set of all bijective functions from $M$ to $N$.

A set $M$ has exactly $n\in \mathbb{N}_0$ elements.

Show that $S(M,M)$ has exactly $n!$ elements.

Induction is strongly suggested.

Now my basecase would be $n=0$.

That holds because there is exactly 1 unique bijective function between the empty set and itself.

But even here I have problems to write that rigorously.

Then the assumption would be: if $M$ has $n$ elements, $S(M,M)$ has $n!$ elements.

Then if $M$ has $(n+1)$ elements, $S(M,M)$ has $(n+1)!$ elements.

But I simply do not know how to write that as a formula that enables me to plug in my assumption. Can you help me?

Answer 1

Remember that $M$ and $N$ are finite sets, then the set of bijections between $M$ and $N$ is nonempty if and only if $|M| = |N| = n$.

So we only need to consider the case where $|M| = |N|$, and we proceed by induction in $n$, where $n = |M| = |N|$.

The base case is $n = 0$. There are a single bijection between $M$ and $N$, namely the function with empty domain and empty range. Since $0! = 1$, we are done here.

For the inductive step, assume that the theorem holds for $n$.

How many bijections are there between $M$ and $N$, if $|M| = |N| = n+1$? Choose an element $x$ in $M$. For each choice of $x$, a bijection $f$ between $M$ and $N$ will consists of associating $x$ with $f(x)$ and a bijection between $M \setminus \{ x \}$ and $N \setminus \{ f(x) \}$. Since $M \setminus \{ x \} = N \setminus \{ f(x) \} = n$, we know from the induction hypothesis that there are $n!$ such bijections. Since $x$ can be chosen in $n+1$ ways, there are $(n+1) \cdot n! = (n+1)!$ bijections between $M$ and $N$.

Answer 2

You can think of a bijection as a two way mapping. Say we have the set $M$ containing $n + 1 \in \mathbb{N}_0$ elements. We want to show that there are $(n +1)!$ bijective functions from $M$ onto $M$ using the inductive hypothesis. Let $M = \{a_1, a_2, \ldots , a_n , a_{n + 1}\} $. We know that $a_{n+1}$ must be mapped to one of the $a_i$ with $1 \leq i \leq n + 1$. Say we map $a_{n+1}$ to $a_j$. After mapping $a_{n+1}$ we are left with $n$ elements in each set. There are $|S(M \setminus \{a_{n+1}\}, M \setminus \{a_j\})|$ ways to complete our bijection. Since $j$ could be any element in $M$ we have \begin{align} |S(M,M)| &= \sum_{j = 1}^{n + 1} |S(M \setminus \{a_{n+1}\}, M \setminus \{a_j\})|\\ &= \sum_{j = 1}^{n + 1} n! && \text{By the Inductive Hypothesis}\\ &= (n+1)n!\\ &= (n + 1)! \end{align} Thus by induction $S(M,M) = n!$ if $|M| = n$.