Lemma. For sets $X, Y$ with $|X|=|Y|=m \in \mathbb{N}$ there exists exactly $m! = 1 \cdot 2 \cdot \ldots \cdot m$ pairwise distinct bijective maps between $X$ and $Y$.
Proof is left as an exercise.
Attempt: Prove Lemma.
(1) Show true for $m=1$. $X=\{1\}$, $Y=\{a\}$. Number of possible arrangements $1!$, arrangements: (1,a).
(2) Assume true for $m=k$. $X = \{1,2 \ldots , k_X \}$, $Y=\{a, b \ldots k_Y \}$. Number of possible arrangements $k!$. Note that $k! \implies m!$
(3) Show true for $m=k+1$. $X = \{1,2, \ldots, k_X, k_X+1\}$, $Y = \{a,b, \ldots, k_Y, k_Y+1\}$. Number of possible arrangements $(k+1)!$
$(k+1)! = m!$
$m! = k!$ (from step (2))
(4) $\therefore$ by the process of mathematical induction, for $m$ elements there exists $m!$ pairwise distinct bijective maps between $X$ and $Y$.
I'd like to know if I have been redundant in some step or wrote some nonsense along the way.
Liesen, J., Mehrmann, V. 2015. Linear Algebra. Berlin, Germany.: Springer.
Best Answer
In step (2), I would denote the sets as $X=\{x_1,x_2,\dots,x_k\}$ and $Y=\{y_1,y_2,\dots,y_k\}$.
For the induction step (3), it doesn't really make sense to say $(k+1)!=m!$ and $m!=k!$ as you did. I would say that the first element of $X=\{x_1,x_2,\dots,x_{k+1}\}$ is mapped to any of the $k+1$ elements of $Y$, and by the induction hypothesis there are $k!$ possible arrangements for the remaining $k$ elements of $X$ to be mapped to the remaining $k$ elements of $Y$, so by the multiplication principle there are $(k+1)k!=(k+1)!$ possible bijective maps from $X$ to $Y$.