Cardinality of the permutations of an infinite set If you have an infinite set X of cardinality k, then what is the cardinality of Sym(X) - the group of permutations of X ?
 A: Here is another solution: $X$ is infinite and so there are two elements $x_1$ and $x_2$. Let $X'=X\setminus \lbrace x_1,x_2\rbrace$. I have that $|X|=|X'|$ and so $|P(X)|=|P(X')|$. Let $A$ be a subset of $X'$ and so $|X\setminus A|\ge 2$. Then there exist a permutation $f:X\setminus A \to X\setminus A$ without fixed points. Then I extend $f$ to $X$ leaving fixed the elements of $A$. The set of the points fixed by $f$ is then $A$. So I have a surjection $Sym(X) \to P(X')$. Hence $|Sym(X)| \ge |P(X')|=|P(X)|$. That $|Sym(X)| \le |P(X)|$ is easy.
A: $k^k$.
Easy that it's an upper bound. For lower bound split $X$ into two equinumerous
subsets; there are $\ge k^k$ permutations swapping the two subsets.
A: As already mentioned, we have $$2^k\le k^k\le(2^k)^k=2^{kk}=2^k,$$ and thus $2^k=k^k$. The inequality $k!\le k^k$ is obvious. To check $2^k\le k!$, note that $2^k$ subsets of $X$ are the set of fixed points of some permutation. Conclusion: $k!=2^k$. 
(I don't understand Robin Chapman's argument.) 
A: Since the comments on Steve0078's answer raise issues concerning the axiom of choice, let me point out that John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice.  (Slogan: Without choice, nothing can be proved about those two cardinals.)  The reference for this is "Factorials of Infinite Cardinals" in Fundamenta Mathematicae 93 (1976) pp. 186-195 (Math Reviews volume 55 #7779).
