Showing cardinality of all infinite sequences of natural numbers is the same as the continuum.

Question

So I'm trying to show that these two sets have the same cardinality, i.e. there is a possible bijection between the two. I'm trying to use the Cantor-Schroeder-Bernstein theorem as I can't explicitly think of a bijection that will work. For this I need to find an injective map each way. I can find an injective mapping between $R$ and the set of infinite sequences of natural numbers. E.g., for each real number $x$, I can associate it with the sequence $S$, where the first element is $2^{n}$ (where $n$ is the greatest integer less than or equal to $x$) if x is nonnegative, and $3^{n}$ if x is negative. Then the rest of the sequence can be the decimal expansion of x in single digits. E.g. the sequence associated with pi through the function would be $(2^{3}, 1,4, etc)$. This is injective, so the first half of Cantor-Schroeder-Bernstein is satisfied. If I can find an injective function going the other way then I am done.

I first thought of something involving turning the digits of the sequence into a real number, but that failed to be injective as my function would not be able to differentiate between the sequences $(1,0,1,0,1,0,...)$ and $(10,10,10,...)$.

Any hints or help? I'm trying to figure it out without resorting to proofs based on cardinal arithmetic or related to the power set of N.

Answer 1

You need a separator to cure the problem you identified. One way is to write all the numbers in the sequence in binary and put a $2$ between them, so $4,3,5,1,9$ would become $10021121012121001$. Put a decimal point in front and you are done.

Answer 2

Every real number in $[0,1)$ can be written uniquely as $\sum_{i=1}^{\infty}\frac{a_i}{2^i}$ where each $a_i\in\{0,1\}$ and there are infinitely many $i$ with $a_i=0$.

Let $i_{n}(\alpha)$ be the index of the $n$th zero in that expansion for $\alpha\in[0,1)$.

Then define $$\alpha\mapsto \left\{i_1(\alpha)-1,i_2(\alpha)-i_1(\alpha)-1,i_3(\alpha)-i_2(\alpha)-1,\dots,i_{n+1}(\alpha)-i_{n}(\alpha)-1,\dots\right\}$$

Show that this is one-to-one and onto.

(This assumes natural numbers include $0$, but if they don't, then you can remove all the $-1$s.)

Basically, we are representing a sequence $\{1,2,0,1,3,\dots\}$ as the base $2$ expression:

$$0.101100101110\dots_2$$

Answer 3

We know $(0,1)$ has the cardinality of the continuum. Each $x\in (0,1)$ has a decimal expansion $.x_1 x_2 \dots $ The map $x = .x_1 x_2 x_3 \, \dots \to x_1,x_2, x_3,\dots$ is then an injection of $(0,1)$ into $\mathbb N^{\mathbb N}.$

For an injection going the other way: if $n_1, n_2 , \dots \in \mathbb N^{\mathbb N},$ we can map it to the decimal expansion that starts with $n_1$ $1$'s, followed by one $0,$ then followed by $n_2$ $1$'s, followed by one $0,$ etc. For example, $2, 5, 3, 1, 4, 2, \dots$ goes to $.1 1 0 1 1 1 1 1 0 1 1 1 0 1111 0 11 0\dots$

Answer 4

Alternate Approach:

For now, let's assume that $0\not\in\mathbb{N}$ - I'll mention a little more about this later.

Recall the following fact about continued fractions: Infinite continued fractions are in bijective correspondence with irrational numbers.

Therefore, one can associate each sequence of natural numbers with an irrational number. By the uniqueness, this is a bijection and so there is an injective map from the infinite sequences to the set of irrational numbers and there are many more irrational numbers than rational numbers.

Notes:

1. If you typically assume that $0\in\mathbb{N}$, then just let $\mathbb{N}^+$ be the set of positive natural numbers and there is a bijection between the sequences from $\mathbb{N}$ and $\mathbb{N}^+$ where a sequence $\{a_i\}$ in $\mathbb{N}$ corresponds to the sequence $\{a_i+1\}$ in $\mathbb{N}^+$.

2. If you don't want to use that there are more irrational numbers than rational numbers, you can just see that this gives an injection from the set of sequences of natural numbers to the continuum of numbers. One can also get a surjection from the sequences of natural numbers to positive real numbers, by mapping a sequence $\{a_i\}$ to the real number $\sum a_i2^{-i}$.