My very first post. Checked this site and MathOverflow for answer but did not find.
Statement: If A and B are finite sets with |A| = |B| = n , then there are n! bijective functions from A to B.
A proof by induction:
Let $A = \{ a_1,a_2,\ldots,a_n\}$ and $B = \{b_1,b_2,\ldots,b_n\}$.
Induction hypothesis: A and B being finite sets with $|A| = |B| = n$ there are n! bijective functions $f: A \rightarrow B$.
Consider $A' = A \cup \{a_{n+1}\}$ and $B' = B \cup \{b_{n+1}\}$. For any $a_i \in A'$ there are $n+1$ choices for the image of $a_i$ in $B$ under a function $f$. Fix $a_i = a \in A'$ . If f is bijective then $f:A' \; \backslash \; \{a\} \rightarrow B' \; \backslash \; \{f(a)\}$ is also bijective. By the induction hypothesis there are n! such bijective functions. So there are $(n+1)n! = (n+1)!$ bijective functions $f: A' \rightarrow B'$. Q.E.D.
Is the above proof correct?
Best Answer
For the inductive step it might be better to write it something like this:
Let $A$ and $B$ be sets with $|A|=|B|=n+1$. Consider any $a\in A$. For any given $b\in B$, we have by the inductive hypothesis that there are $n!$ bijective functions from $A\setminus \{a\}$ to $B\setminus \{b\}$. Since there are $n+1$ choices of $b$, there are $(n+1)n!=(n+1)!$ bijective functions from $A$ to $B$.