cardinality of $S_{\mathbb{N}}$

Question

When I am proving something, I got a doubt. what is the cardinality of $S_{\mathbb{N}}$, the set of all bijections from $\mathbb{N}$ to $\mathbb{N}$? I hope it is countable, because that will make my life easier.

Thanks in Advance.

Answer 1

It is not countable: it is $2^{\aleph_0}=\mathfrak{c}$, the cardinality of $\Bbb R$, the real line, and of $\wp(\Bbb N)$.

To see that it is at least this big, let $A$ be any subset of $\Bbb N$. We can define a bijection $f_A\in S_{\Bbb N}$ as follows:

$$f_A:\Bbb N\to\Bbb N:n\mapsto\begin{cases} n+1,&\text{if }n\in 2A\\ n-1,&\text{if }n\in 2A+1\\ n,&\text{otherwise}\;. \end{cases}$$

Here $2A=\{2n:n\in A\}$, and $2A+1=\{2n+1:n\in A\}$. As an example, if $A=\{1,4\}$, then $2A=\{2,8\}$, $2A+1=\{3,9\}$, and $f_A$ is the bijection that interchanges $2$ and $3$ and interchanges $8$ and $9$ while leaving every other natural number alone. It’s not hard to check that if $A,B\subseteq\Bbb N$, and $A\ne B$, then $f_A\ne f_B$.