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

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

• One way to (almost) construct such a function is to use the facts that there is (almost) a nice bijection between $2^{\Bbb N}$ and $[0,1]$ (binary decimal expansion), and there is also (almost) a nice bijection between $\Bbb N^{\Bbb N}$ and $[0,1]$ (continued fractions). Aug 4, 2021 at 17:04

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.

• What topologies are you putting on $2^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}}$? Aug 4, 2021 at 17:26
• @Dionel Jaime For the set $A^\mathbb{N}$, I'm giving $A$ the discrete topology and $A^\mathbb{N}$ the product topology $\prod\limits_{n \in \mathbb{N}} A$. Aug 4, 2021 at 17:27
• Ok, so you're using Tychonoff? Very interesting. I am curious about this fact about a constructive map having to be continuous. Aug 4, 2021 at 17:30
• @DionelJaime You should look into Brouwer's version of real analysis with constructive logic. He basically adds two axioms. The first is that $2^\mathbb{N}$ is compact. The second is that every function $\mathbb{N}^\mathbb{N} \to \mathbb{N}$ is continuous. Any constructive function can be defined solely using constructive logic, hence can be defined using constructive logic + Brouwer's two axioms. And it turns out that in models of Brouwer's intuitionism, every definable function $\mathbb{N}^\mathbb{N} \to \mathbb{N}$ actually is continuous. Aug 4, 2021 at 17:35
• @DionelJaime I know there's a classic result in Bishop-style constructive mathematics that 'every function is continuous' (see e.g. mathoverflow.net/questions/164694/… ); I presume the argument is some variation on that. Aug 4, 2021 at 17:36

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.