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.


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

  • $\begingroup$ I still don't get it. Sorry. Is there any chance you can elaborate? $\endgroup$ – Galush Balush Feb 7 '18 at 17:16
  • $\begingroup$ @GalushBalush I've given two small examples. I'll add one more. $\endgroup$ – Arthur Feb 7 '18 at 17:18
  • $\begingroup$ How can I be sure that I don't get the same value twice? $\endgroup$ – Galush Balush Feb 7 '18 at 17:26
  • $\begingroup$ 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. $\endgroup$ – Arthur Feb 7 '18 at 17:35
  • $\begingroup$ 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? $\endgroup$ – Galush Balush Feb 7 '18 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.