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)$?
Why does the symmetric group on an infinite set X have the cardinality of the power set ${\cal P}(X)$? 

marked as duplicate by Steve Huntsman, Gjergji Zaimi, Robin Chapman, Martin Brandenburg, Scott Morrison♦ Jul 19 '10 at 14:38This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question. 


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. 

