Bijection between $\mathbb N^{\mathbb N}$ and $2^{\mathbb N}$

Question

Let us define $$\mathbb N^{\mathbb N}=\mathbb N\times\mathbb N\times\mathbb N\times\dots$$ I want an explicit bijection between $\mathbb N^{\mathbb N}$ and $2^{\mathbb N}=\mathcal P(\mathbb N)$, i.e., the power set of $\mathbb N$

The fact that this bijection exists in not hard to see. It is very clear that $\mathbb {N^N}$ is the same as $[0,1)$ (with an extra decimal point) which is same as $\mathbb R$ (in terms of infinities of course). And we know that the infinities of $2^{\mathbb N}$ and $\mathbb R$ are same.

Also, it's not hard to see that the map $\{a_1,a_2,\dots a_n\}\to (a_1,a_2,\dots a_n,0,0,\dots)$ and $\{a_1,a_2,\dots\}\to (a_1,a_2,\dots)$ gives an idea of a bijection, only that it's not really a bijection since the order matters in ordered pairs, but not in sets.

Some other ideas are available here as well. But, what I want is a well constructed (nice if possible) bijection between $\mathbb N^{\mathbb N}$ and $2^{\mathbb N}$.

Answer 1

You've already given an example of how to construct a bijection between the two. I will be a bit of a contrarian and show that there is no constructive bijection between the two.

A constructive bijection $f : \mathbb{N}^\mathbb{N} \to 2^\mathbb{N}$ means (roughly) that if I give you a sequence $s \in \mathbb{N}^\mathbb{N}$ and a number $n$, you can actually compute the $n$th element of the sequence $f(s)$. And conversely, you should actually be able to compute the $n$th element of $f^{-1}(t)$ given some $t \in 2^\mathbb{N}$.

The problem here is that it can be shown that any constructive function $\mathbb{N}^\mathbb{N} \to 2^\mathbb{N}$ must be continuous when giving $\mathbb{N}$ and $2$ the discrete topology and taking the $\mathbb{N}$-ary product, and any constructive function $2^\mathbb{N} \to \mathbb{N}^\mathbb{N}$ must also be continuous.

This means that any bijection between the two must be a homeomorphism.

But the problem is that $2^\mathbb{N}$ is well-known to be compact, while $\mathbb{N}^\mathbb{N}$ is not compact.

Thus, there can be no homeomorphism between the two, and hence no constructive bijection.

In fact, there can be no constructive surjection $2^\mathbb{N} \to \mathbb{N}^\mathbb{N}$, since this would be a continuous surjection and therefore $\mathbb{N}^\mathbb{N}$ would be compact.

The intuition behind the continuity requirement is that if I have a continuous function $f : 2^\mathbb{N} \to \mathbb{N}^\mathbb{N}$ and I wish to compute the $n$th element of $f(s)$, I should be able to do so after looking at only a finite number of terms in the sequence $s$. This implies continuity.

Answer 2

One (almost as noted in a comment above) bijection is to go between binary and continued fractions for numbers in $[0,1)$. See Minkowski question-mark function for more information.