
> 
> **Possible Duplicate:**  
> 
> [Cardinality of the permutations of an infinite set](https://mathoverflow.net/questions/27785/cardinality-of-the-permutations-of-an-infinite-set) 
> 
> 
> 


Why does the symmetric group on an infinite set X have the cardinality of the power set ${\cal P}(X)$?



Cardinality of symmetric group
I assume you mean an infinite set $X$. You need to use the Axiom of Choice to prove this fact, but I'm not sure to what extent it is necessary.


Since $|X \times X| = |X|$ (uses AC) and $Sym(X) \subseteq \mathcal{P}(X \times X)$, it is clear that $|Sym(X)| \leq 2^{|X \times X|} = 2^{|X|}$.


Since $|X \times 2| = |X|$ (uses AC) we can split $X$ into two disjoint sets $X\_0$ and $X\_1$, each of size $|X|$. Let $a:X\_0 \to X\_1$ be a bijection. For each set $A \subseteq X\_0$ define $\sigma\_A \in Sym(X)$ to be the bijection that exchanges $x$ and $a(x)$ for every $x \in A$ and leaves all other elements unchanged. It is clear that $A \in \mathcal{P}(X\_0) \mapsto \sigma\_A \in Sym(X)$ is an injection. Therefore $|Sym(X)| \geq 2^{|X\_0|} = 2^{|X|}$.


So the equality $|Sym(X)| = 2^{|X|}$ holds unconditionally for all infinite sets such that $|X \times X| = |X|$. The fact that $|X \times X| = |X|$ for all infinite sets $X$ is equivalent to AC by an old result of Tarski.


