Best bijection between $\mathbb{N}^\mathbb{N}$ and $[0,1] \subset \mathbb{R}$.

Question

Cantor's diagonal argument proves as a special case that the set of functions from $\mathbb{N}$ to $\{0,1\}$ has the same cardinality as the interval $[0,1].$ There is an 'obvious' mapping from functions to real numbers that almost provides a bijection, except very few pairs of functions happen to map to the same reals. This can then be dealt with by using the Cantor-Bernstein-Schröder Theorem to prove the existence of a bijection. For an application in number theory I would like to apply similar bijections between $\mathbb{N}^\mathbb{N}$ and $[0,1].$ The construction which is 'obvious' is to use dove-tailing, as follows. Let $M$ be a matrix with rows and columns indexed by $\mathbb{N}$ so that if $f$ is a function, then the binary representation of $f(n)$ is contained in the $n$'th row of $M.$ Now let $f$ correspond to the real number which has as its binary digits the entries (0,0),(0,1),(1,1),(0,2),(1,1),(2,0),(0,3) etc. of $M.$ Clearly each function produces a unique real number between $0$ and $1.$ Again it may be necessary to apply the Cantor-Bernstein-Schröder Theorem to eliminate double occurrences of real numbers. In my particular application I do not worry about this, since all my functions map only a finite number of natural numbers to zero. But my question is whether other bijections are also known, other than this 'obvious' one.

Answer 1

Assuming you're talking about $\Bbb{N}$ starting at $1$ rather than $0$, the bijection I like best is $$(n_1, n_2, n_3, ...) \mapsto \frac{1}{2^{n_1}} + \frac{1}{2^{n_1 + n_2}} + \frac{1}{2^{n_1 + n_2 + n_3}} + ...$$ The first number of the sequence tells me how many digits after the binary point to count to see the first $1$ in the binary expansion of $x$, and every number after that counts the number of binary digits to the next $1$. Although $0$ is not in the image of this map as a result, it is a true bijection of $\Bbb{N}^{\Bbb{N}}$ with $(0, 1]$--nothing gets double counted because this function can never output an infinite tail of zeroes.

Answer 2

The function provided in the answer by Rivers McForge can be slightly modified to include $0$: \begin{equation} f(n_1,n_2,n_3,...) = \begin{cases} 0, & n_i = 1\\ g(n_1 -1, n_2, n_3,...),&n_1 >1, ~ n_{i>1}=1\\ g(n_1, n_2, n_3, ...), & \text{otherwise} \end{cases} \end{equation} where \begin{equation} g(n_1,n_2,n_3,...) = \frac1{2^{n_1}}+\frac1{2^{n_1+n_2}}+\frac1{2^{n_1+n_2+n_3}}+... \end{equation}

This works by "making some space" when $n_i = 1$ for $i>1$ by shifting the function in $n_1$ in the sense of Hilbert's paradox of the Grand Hotel, which leaves an "empty space" at $n_i=1$ for all $i \in \mathbb N$. This "empty space" is then used to assign the value $0$ for $f(1,1,1,...)$, which makes $f(n_1,n_2,n_3,...)$ the bijection between $\mathbb N^{\mathbb N}$ and $[0,1]$, as requested in the question.

In general, a bijection $h: S \to S \cup \{a\}$, where $S$ is an infinite set, can be constructed by defining a sequence $(s_n)$ in $S$ with no repeating members to define the function $h(x)$ in the following way: \begin{equation} h(x) = \begin{cases} a, & x= s_1 \\ s_{n-1}, & x=s_n, ~n>1 \\ x, & x \notin (s_n) \end{cases} \end{equation} In the above example $S=(0, 1]$, $a=0$ and $s_n = 2^{-(n-1)}$ in order to have $f(n_1,n_2,n_3,...) = h(g(n_1,n_2,n_3,...))$.