MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

$|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
up vote 3 down vote accepted

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.