Cardinality of the set of all natural sequences is $2^{\aleph_0}$

This question already has an answer here:

  • What's the cardinality of all sequences with coefficients in an infinite set?

    4 answers

Solutions Collecting From Web of "Cardinality of the set of all natural sequences is $2^{\aleph_0}$"

For every number $n\in\Bbb N$ let $\sigma_n$ be the binary sequence of $1$’s of length $n$ and then a $0$, this is – if you want to think of it that way – a representation of $n$ in base $1$. With a zero afterwards.

Now given a sequence $a=\langle a_n\mid n\in\Bbb N\rangle$ where $a_n$ is a natural number, we define the following binary sequence by induction.

  1. $b_0$ is the empty sequence.
  2. If $b_n$ was defined, $b_{n+1}$ is the concatenation of $b_n$ with $\sigma_{a_n}$. That is we write $b_n$, and then $\sigma_{a_n}$.

$b$ is the sequence we have at the end of the induction process. Then $b\in 2^{\Bbb N}$, which is easy to see, as it is an infinite sequence of $0$-$1$ digits.

And I claim that the map sending $a$ to $b$ (where $a$ is a sequence of natural numbers, and $b$ is a sequence defined as above from $a$) is a bijection.

For this we just observe that the function decoding sequences of $1$’s between $0$’s is an inverse function. It’s a bit harder to write down formally, but I’ll try.

Let $b=\langle b_n\mid n\in\Bbb N\rangle$ be an infinite binary sequence. We define a sequence of integers.

  1. $a_0=\min\{k\mid b_n=0\}$.
  2. If $a_0,\ldots,a_n$ were defined, let $t$ be the least $k$ such that $b_k=0$ and $k\geq\sum (a_i+1)$ then $a_n=t-\sum (a_i+1)$.

I might be off with the indices in that second part, but that’s the general idea. We find out how to decompose $b$ into pieces looking like $\sigma_k$, then we take the $k$ from each piece.