# A question about the cardinality of the set of all the bijections from $M$ to itself

$M$ is a set.We denote the set of all the bijections from $M$ to itself by $K$.Is the cardinality of $K$ larger than the cardinality of $M$?

-

Sure it is, unless $|M|$ is $1$ or $2$. If $M$ is finite, this simply means that $|M|!>|M|$. If $M$ is infinite, then $M \simeq M \times \{0,1\}$. Let us look at bijections from $M \times \{0,1\}$ to itself.

There are at least as many of them as there are subsets of $M$. Indeed, if $A \subset M$, then you can build a bijection $\varphi\colon M \times \{0,1\} \to M \times \{0,1\}$ such that it fixes pairs $(m,0)$ and $(m,1)$ for every $m \in A$ and swaps pairs $(m,0)$ and $(m,1)$ for every $m \not \in A$.

This proves that the cardinality of the set of bijections from $M$ to itself is greater or equal to the cardinality of the power set of $M$, which is in turn strictly greater than $|M|$.

-
It seems that in the second paragraph of your argument you must use the axiom of choice to ensure that "swap" is legal. –  Luqing Ye Nov 16 '12 at 11:21
Why would that require AC? –  Ittay Weiss Nov 16 '12 at 11:22
@IttayWeiss I am wrong…… –  Luqing Ye Nov 16 '12 at 11:26
To tell you the truth, I have almost no experience working without AC, and I suspect its implicit use everywhere. For instance, I don't even see how to prove that $M \simeq M \times \{0,1\}$ without AC. –  Dan Shved Nov 16 '12 at 14:49
There is some use of AC in this post because indeed $M\simeq M\times2$ requires some use of choice. –  Asaf Karagila Nov 30 '12 at 9:44
In general for a cardinality $\kappa$ the cardinality of the set you describe can be written as $\kappa !$. For finite $\kappa$ the cardinality $\kappa !$ is given by the usual factorial. For infinite $\kappa$ one has $\kappa ! = 2^\kappa$. It is not difficult to prove using Cantor-Schroeder-Bernstein.