Cardinality of symmetric group [duplicate]

Question

Possible Duplicate:
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)$?

Answer 1

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.