0
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, that is very nice. $\endgroup$ – Tommy R. Jensen Jan 24 at 23:09
0
$\begingroup$

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

$\endgroup$

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.