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

  • 0
    It seems that in the second paragraph of your argument you must use the axiom of choice to ensure that "swap" is legal.2012-11-16
  • 0
    Why would that require AC?2012-11-16
  • 0
    @IttayWeiss I am wrong……2012-11-16
  • 1
    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.2012-11-16
  • 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