$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$?
Asked
Active
Viewed 752 times
2 Answers
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|$.
Dan Shved
- 15,862
- 39
- 55
-
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
-
1To 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
-
2There 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 09:44
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.
Ittay Weiss
- 79,840
- 7
- 141
- 236