Encode each $n_1,n_2,n_3,...∈N^N$ by an infinite sequence of 0s and 1s with infinitely many 0s, and give a proof that $N^N$ is equinumerous with $R$.

Encode each $n_1,n_2,n_3,...∈N^N$ by an infinite sequence of 0s and 1s with infinitely many 0s, and hence give a proof that $N^N$ is equinumerous with $R$.

Background: Here the set $N^N=N \times N \times N \times N \times...$ is the set of finite sequences of positive integers. Each infinite sequence $n_1,n_2,n_3,...$ of positive integers gives an irrational number (with a infinite continued fraction) between 0 and 1, because each rational has a finite continued fraction. Conversely, each irrational number between 0 and 1 has a continued fraction of the above form, and hence gives an infinite sequence of positive integers. Thus, we immediately have a bijection between $N^N$ and the irrational numbers in (0,1). The latter set is equinumerous with (0,1), and hence with $R$.

So far I tried to encode each n in N^N as either ones and zeros, where comas are represented as zeros. For example <3,2,3,0,1> ---> 1110110111001

TIA

Representation in continued fractions

$\mathbb N^\mathbb N$ represents either the functions from $\mathbb N$ to $\mathbb N$ either the sequences of integers (which by definition are infinite).

A continued fraction is written $[a_0;a_1,a_2,a_3,...]=\displaystyle{a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+...}}}}$ with $(a_i)_i\in\mathbb N^\mathbb N$.

It is true that continued fractions have finite developpement for rationnals and infinite one for irrationnals and that the developpement of such an irrationnal is unique. It is also true than any infinite sequence of integers defines a positive real number.

$[0;a_1,a_2,a_3,...]\in[0,1]$ when all $a_i\in\mathbb N$ but when $a_0\neq 0$ then it belongs to $[0,+\infty[$.

So it is true that we have a bijection between infinite sequences of natural integers with no trailing zeros and positive irrationnals.

But infinite sequences of natural integers with no trailing zeros are not $\mathbb N^\mathbb N$, they are only a subset of it.

So you have also to consider positive rationnals in this matter.

Unfortunately for such rational numbers there are two possible developpements $[a_0;a_1,a_2,a_3,...,a_n,1,0,...]$ and $[a_0;a_1,a_2,a_3,...,a_n+1,0,...]$ thus preventing continuous fractions to be in bijection with $\mathbb R^+$

We only have an injection from $\mathbb R^+\hookrightarrow\mathbb N^\mathbb N$ (the other way is not injective) and can only say that cardinality of $\mathbb R$ is smaller (in loose sense) than cardinality of $\mathbb N^\mathbb N$ through this argument.

Fortunately the set of all finite subsets of $\mathbb N$ is countable.

The set of sequences of integers with trailing zeros (let's call it $\mathcal N$), is the same than the permutations of all these finite subsets (a subset being unordered) and by the same method countable.

And since we where able to establish a bijection (via continued fractions of positive irrationnal numbers) between $\mathbb N^\mathbb N/\mathcal N$ and $\mathbb R^+/\mathbb Q$ then we can establish that $\mathbb N^\mathbb N$ and $\mathbb R$ are equinumerous.

A bijection between $\mathcal B$ and $\mathbb R$

First note that $[0,1[$ can be mapped one-to-one to $\mathbb R$ via this construction $\require{AMScd}$ \begin{CD} [0,1[ @>\phi>> ]0,1[ @>2x-1>> ]-1,1[ @>\mathrm{argth}>> \mathbb R \end{CD}

With $\begin{cases}\phi(0)=\frac12,\phi(\frac12)=\frac14,\phi(\frac14)=\frac18,..,\phi(\frac1{2^n})=\frac1{2^{n+1}}\quad \mathrm{for}\ n\in\mathbb N \\ \phi(x)=x\quad \mathrm{elsewhere}\end{cases}$

And also that binary sequences with no trailing $1$, namely $(b_n)_n\in\mathcal B\subset\{0,1\}^\mathbb N$

can be mapped one-to-one to $[0,1[$ via the binary developpement $x=\mathtt{0,\overline{b_0b_1b_2...}}$

So our goal is really to find a mapping $\mathbb N^\mathbb N\leftrightarrow\mathcal B$.

$\color{#08F}{Note:}$ the method proposed by Q the Platypus effectively delivers such an element of $\mathcal B$.

Another mapping between $\mathbb N^\mathbb N$ and $\mathcal B$

Let's try to find another method.

For each sequence $(a_n)_n\in\mathbb N^\mathbb N$ we can define $\mathtt{a_0\square a_1\square a_2\square a_3...}$ where $\square$ is a suitable separator. The idea is that the separators allows us to split back the values taken by the original sequence $(a_n)_n$.

To make this a resulting digit sequence let set $\square=0$ and prevent $a_n$ to collide with the separator by writing it in base $9$ and adding $1$.

$a_n=\mathtt{\overline{a_{n,N}..a_{n,2}a_{n,1}a_{n,0}}}$ with $a_{n,i}\in\{1,2,..,9\}$ and such that $a_n=\sum\limits_{i=0}^{N}9^i(a_{n,i}-1)\quad$ ($a_{n,N}\neq 0$).

We also want to have trailing $0$ so if $a_n=0$ we simply encode it with a separator ($0\square$ is encoded not by $\mathtt{\overline{10}}$ but by $\mathtt{\overline{0}}$).

So we have now a one-to-one encoding of $(a_n)_n\in\mathbb N^\mathbb N$ to a sequence of digits $(d_n)_n\in\mathcal D$ with $\mathcal D$ being a subset of $\{0,1,2,..,9\}^\mathbb N$.

This is already astonishing to prove that $\mathbb N^\mathbb N$ is smaller (in loose sense) than $\{0,1,2,..,9\}^\mathbb N$.

Unfortunately this promising idea has a flaw, $\mathcal D$ does not have trailing digits other than zeros, so we cannot map it to the decimal developpement of $x\in[0,1[$, for instance the number $\frac13=\mathtt{\overline{0.3333...}}\notin\mathcal D$.

To remedy to that, one possibility is to restrict $a_{n,i}$ to take only one value, that means $1$. So we have to express a number in $\mathbb N$ by a sequence of $1$.

$\color{#08F}{Note:}$ the solution is then a variant from the one proposed by Einar Rødland

$a_n$ is represented by $\mathtt{\overline{111...1}}$ with $a_n$ times the number $1$.

If $a_n=0$ we still represent it by only a separator $0$.

Finally the following requirements are supported:

• allowing infinite trailing zeros : $\{(X_n)_n,0,0,0,...\}\leftrightarrow(x_n)_n\square\square\square...\leftrightarrow\mathtt{\overline{(x_n)_n000...}}$ where $(X_n)_n$ is the beginning of the sequence and $(x_n)_n$ its encoding.
• allowing leading zeros : $\{(0,0,..,0,(Y_n)_n\}\leftrightarrow\square\square ..\square(y_n)_n\leftrightarrow\mathtt{\overline{00..0(y_n)_n}}$ where $(Y_n)_n$ is the rest of the sequence and $(y_n)_n$ its encoding.
• forbidding trailing ones : this is indeed not possible since it would be mean that some $a_n\in\mathbb N$ is infinite.

This way, the proposed encoding is a one-to-one mapping between $\mathbb N^\mathbb N\leftrightarrow\mathcal B$.

Answer to two questions :

• does the choice of $0$ or $1$ as a separator matters ?
• does the choice of including $0$ in the naturals matters ?

question 1

The choice of $0$ a separator is only to have a valid binary developpement $\mathcal B$ of a real $<1$, it is convenient.

$x=0,0001011101101.....$

If we choose $1$ instead as a separator it is not as straightforward as why this is still working.

For instance $x=\frac14=0,01$ (with infinite trailing zeros) cannot be written in the system.

But considering that $\sum\limits_{k=n_0}^{\infty}2^{-k}=2^{n_0-1}$ then we can give a sense to infinite trailing $1$.

$\frac14$ is now written $0,001111111111...$ (with infinite trailing ones).

And we can show that $\mathcal B'$ the subset of $\{0,1\}^\mathbb N$ with no trailing zeros is also a one-to-one mapping but of $]0,1]$ this time.

question 2

In order to have trailing separators, which is mandatory, we need that exactly one integer is encoded by just a separator.

Let's call the separator $\square$ and the other digit $\blacksquare=1-\square$

In our examples $0$ was chosen for simplicity, but if you exclude it from the naturals then you need to choose another one to play this role. For sake of simplicity you may want to choose $1$ but $17$ or $5764842891113$ can do as well.

But then there would not exists sequences of $\blacksquare$ of length exactly $1$, $17$ or $5764842891113$. This is a hole that need to be fixed in the encoding to make it bijective again.

So let say we have chosen $1$ to be encoded by $\square$.

Then $2$ need to be encoded by $\blacksquare\square$.

Then $3$ need to be encoded by $\blacksquare\blacksquare\square$.

And so on...

Finally you see that we have mapped $\{1,2,3,...\}$ to $\{0,1,2,...\}$.

If we choose $17$ then $\{1,2,3,..,16,17,18,19,...\}$ is mapped to $\{1,2,3,..16,0,17,18,...\}$.

We wanted no $0$ in the naturals but we end up being forced to use it anyway.

One way to do this is to consider $n_{i,j}$ to be the $j$th significant digit of $n_i$. Then you can define your bitstream as $ n_{1,1} n_{2,1} n_{1,2} n_{1,3} n_{2,2} n_{3,1} \dots $

So if you have a sequence $ \langle 0,1,2,\dots \rangle $. You would then transform it into the binary representation. $ \langle 0,1,10,\dots\rangle $. Then write these numbers out in a grid with the least significant digit to the left.

$$ \begin{array}{} 0 & 0 & 0 & \dots\\ 1 & 0 &0 &\dots \\ 0 & 1 & 0 &\dots \end{array}$$

Then you would move along the diagonals of that grid reading off the numbers.

$$ \begin{array}{} \not 0 & 0 & 0 & \dots\\ 1 & 0 &0 &\dots \\ 0 & 1 & 0 &\dots \end{array}$$

$0$

$$ \begin{array}{} \not 0 & 0 & 0 & \dots\\ \not1 & 0 &0 &\dots \\ 0 & 1 & 0 &\dots \end{array}$$

$01$

$$ \begin{array}{} \not 0 & \not 0 & 0 & \dots\\ \not1 & 0 &0 &\dots \\ 0 & 1 & 0 &\dots \end{array}$$

$010$

$$ \begin{array}{} \not 0 & \not 0 & 0 & \dots\\ \not1 & 0 &0 &\dots \\ \not 0 & 1 & 0 &\dots \end{array}$$

$0100$

This way you can encode countable sequence of natural numbers.

A very simple, but not very memory efficient way, is to encode the sequence $n_1, n_2, \ldots$ as a binary sequence on the form: $n_1$ 0s, one 1, $n_2$ 0s, one 1, etc.

Ie the sequence $3,4,1,\ldots$ get encoded as $00010000101\ldots$.

You can easily read off the number of 0s in a row to retrieve $n_1, n_2, \ldots$. On the other hand, you do not get the problem of $\ldots1000000\ldots$ becoming the same real number as $\ldots0111111\ldots$.

There are similar representations that are much shorter. Eg write each $n_i$ in base $m=2^k-1$, represent each base $m$ digit in binary using exactly $k$ bits. Use the binary representation of $m$, which consists of $k$ copies of 1, at the end to mark the end of the number.

Eg using base 3, the number 7, which is $21_3$ in base 3, would be represented as the binary sequence $10\,01\,11$.