# Cardinality of symmetric group [duplicate]

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)$?

-

## marked as duplicate by Steve Huntsman, Gjergji Zaimi, Robin Chapman, Martin Brandenburg, Scott Morrison♦Jul 19 '10 at 14:38

$|S_3| = 6 \ne 2^3$. – Steve Huntsman Jul 19 '10 at 13:38
Sorry, I should have mentioned the set was infinite. I edited the question. – ashpool Jul 19 '10 at 13:40

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.