Is symmetric group on natural numbers countable?

Here's a very silly argument to show $|S_\mathbb{N}| \geq 2^\mathbb{N}$.

A fact from calculus tells us that a non-absolutely convergent series whose terms converge to zero can be reordered to take the value of any real. So, for each real $\alpha$, there is a permutation such that $$ \sum\frac{(-1)^{n_i}}{n_i}= \alpha $$

So there must be at least as many permutations as reals!

We can do a diagonal argument directly, too: Let $(\sigma_0,\sigma_1,\sigma_2,\ldots)$ be an infinite sequence of bijections $\mathbb N\to\mathbb N$. We wish to find a bijection $f$ that's not in the sequence:

Let $f$ be the bijection such that for each $k$, $f$ swaps $2k$ and $2k+1$ if $\sigma_k(2k)=2k$ and leaves them alone otherwise.

By construction $f$ is a bijection, and different from each of the $\sigma_i$s.

(Note that this argument shows less than the other answers: it only cloncludes that the cardinality of $S_{\mathbb N}$ is larger than $\aleph_0$, not that it equals $2^{\aleph_0}$.)

Note that unlike in the finite case, the group generated by all single transpositions is not the entire permutation group. Instead it is the group of all permutations "with finite support", which is countable.

$S_{\Bbb N}$ is simply the set of bijections from $\Bbb N$ to itself, which has cardinality $2^\omega=\mathfrak{c}$. (In particular, it’s uncountable.)

It’s clear that $|S_{\Bbb N}|\le\omega^\omega=2^\omega$. For the other direction, let $A$ be any infinite subset of $\Bbb N$, and enumerate $A=\{a_k:k\in\Bbb N\}$ in increasing order. Let

$$\sigma_A:\Bbb N\to\Bbb N:n\mapsto\begin{cases} a_{2k+1},&\text{if }n=a_{2k}\text{ for some }k\in\Bbb N\\ a_{2k},&\text{if }n=a_{2k+1}\text{ for some }k\in\Bbb N\\ n,&\text{if }n\in\Bbb N\setminus A\;. \end{cases}$$

$\Bbb N$ has $2^\omega$ infinite subsets, and $\sigma_A=\sigma_B$ iff $A=B$, so $|S_{\Bbb N}|\ge 2^\omega$. Thus, $|S_{\Bbb N}|=2^\omega$.

A similar argument to Brian's, but maybe slightly easier: given a set $S\subseteq\mathbb{N}$, let $\pi_S$ be the permutation which swaps $2n$ and $2n+1$ for each $n\in S$, and leaves all other numbers fixed. Then $\pi_S=\pi_{S'}\iff S=S'$, so $\vert S_\mathbb{N}\vert=2^\omega$.

What about generalizations to arbitrary infinite sets - that is, for which $A$ can we conclude that $S_A$ has cardinality $2^A$? (Assume choice fails badly, so this is nontrivial.)

• My argument above works with any infinite set $A$ which can be put into bijection with its double $A\sqcup A$.

• Brian's answer requires us to assume that each infinite subset of A can be written as a disjoint union of pairs. This need not be the case, e.g. if $A=X\times\omega$ for an amorphous set $X$ - one of the "rows" equal to $X$ need not be splittable into pairs (note that this $A$ can be put in bijection with $A\sqcup A$). (As written, it also requires $2^A$ to have the same cardinality as the set of infinite subsets of $A$, which is not always true, but this is easily fixable: for $X$ finite, have the associated permutation fix exactly the elements not in $X$.)

• Moreover, Brian's argument merely produces a surjection from $S_A$ onto $2^A$, while the argument above yields an injection going the other way; in general, this is stronger. (The issue with Brian's argument is that one must choose a way of writing a given infinite $X\subseteq A$ as a disjoint union of pairs.)

• On the other hand, the relationship between Brian's and my hypotheses is not clear. Certainly mine does not imply Brian's, but the converse may be true as well.

The set of fixed points of any permutation $\pi\colon\mathbb{N}\to\mathbb{N}$ (i.e., the set $\{x\mid \pi(x)=x\}$) can be any subset of $\mathbb{N}$ except ones of the form $\mathbb{N}\setminus\{n\}$ for some $n$. So there are at least as many permutations as there are such subsets and there are uncountably many subsets.

_{Thanks to Henning Makholm for pointing out an error in the original version of this answer.}