Prove Cardinality of set of Bijections in $\mathbb{N} \to \mathbb{N}$ is $\mathfrak {c}$

Question

I'm asked to prove that the cardinality of the set of all bijections in $\mathbb{N} \to \mathbb{N}$ is $\mathfrak {c}$.

Note: $\mathfrak {c}$ is the cardinality of the real numbers.

I would appreciate some help understanding the following solution:

Let's denote this set as $|A|$. On the one hand, $|A| \subseteq \mathbb{N} \to \mathbb{N}$. Thus, according to CSB theorem, $|A|\le \mathfrak {c}$. This part I understand.

On the other hand, we can define an injective function $f\in \{0,1\}^{\mathbb{N_{even}}}\to A$ as follows:

$f=\lambda g\in \{0,1\}^{\mathbb{N_{even}}}.\lambda n\in \mathbb{N}.\begin{cases} n+1, & \text{if $n\in \mathbb{N}_{even} \land g(n)=1$ } \\[2ex] n-1, & \text{if $n\in \mathbb{N}_{odd} \land g(n-1)=1$} \\[2ex] n, & \text{otherwise } \end{cases}$

Now, I can conclude that $|A|\ge \mathfrak {c}$. Hence, $|A|= \mathfrak {c}$.

I would appreciate if someone could explain why $Im(g)\subseteq A$? Or in other words, why is the output of $g$ necessarily a bijection.

Also, if you think there's an easier way to solve that, I would be glad to see it. Thank you.

Answer 1

$f$ sends $g$ to the bijection $f(g):\Bbb N\to \Bbb N$ given by partitioning $\Bbb N$ into pairs $(0,1),(2,3),\ldots$ and then we swap the two elements of any pair for which $g(n)=1$ where $n$ is the even number in the pair, and we leave all the other pairs untouched.

So for $g_0$ given by $g_0(n)=0$, we have that $f(g_0)$ is the identity, while for $g_1$ given by $g_1(n)=1$, we get that $f(g_1)(2k)=2k+1$ and $f(g_1)(2k+1)=2k$ for all $k\in \Bbb N$.

For a final example, take $g_2$ defined by $g_2(4k)=0$ and $g_2(4k+2)=1$. Then we have

• $f(g_2)(0)=0$ and $f(g_2)(1)=1$ because $g_2(0)=0$
• $f(g_2)(2)=3$ and $f(g_2)(3)=2$ because $g_2(2)=1$
• $f(g_2)(4)=4$ and $f(g_2)(5)=5$ because $g_2(4)=0$

and so on.