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

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.

## 1 Answer

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

• I still don't get it. Sorry. Is there any chance you can elaborate? – Galush Balush Feb 7 '18 at 17:16
• @GalushBalush I've given two small examples. I'll add one more. – Arthur Feb 7 '18 at 17:18
• How can I be sure that I don't get the same value twice? – Galush Balush Feb 7 '18 at 17:26
• From my last example, can you not see how that's obvious? If that's not clear enough, then I don't think I'm capable of explaining it to you. Instead, I really recommend that you take out a pen and a piece of paper, come up with some random $g$, and work through, one by one, what $f(g)(n)$ is for, say, $n=0,1,2,3,4,5,6,7$. The fact of the matter is that the construction of $f$ is really simple, but it's a bit difficult to convey in writing. I don't know what else to do. You will just have to try it on your own. – Arthur Feb 7 '18 at 17:35
• I think I'm starting to get it. So basically it's just taking the identity function and permutate it. Is there a formal way to prove that the output is a bijection? – Galush Balush Feb 7 '18 at 17:36