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

  • $\begingroup$ 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). $\endgroup$ Aug 4, 2021 at 17:04

2 Answers 2


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.

  • $\begingroup$ What topologies are you putting on $2^{\mathbb{N}}$ and $\mathbb{N}^{\mathbb{N}}$? $\endgroup$ Aug 4, 2021 at 17:26
  • $\begingroup$ @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$. $\endgroup$ Aug 4, 2021 at 17:27
  • $\begingroup$ Ok, so you're using Tychonoff? Very interesting. I am curious about this fact about a constructive map having to be continuous. $\endgroup$ Aug 4, 2021 at 17:30
  • 2
    $\begingroup$ @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. $\endgroup$ Aug 4, 2021 at 17:35
  • $\begingroup$ @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. $\endgroup$ 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .