8
$\begingroup$

$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$?

2 Answers 2

13

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|$.

  • 2
    There is some use of AC in this post because indeed $M\simeq M\times2$ requires some use of choice.2012-11-30
7

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.

  • 0
    Thanks for your information.I will try to prove.2012-11-16