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$.