Cardinality of infinite words from finite alphabet is the same as that of $\mathbb{R}$

121 Views Asked by At

Let $[n]$ denote the set $\{0, 1,2, \ldots, n\}$. I want to show that $[n]^{\mathbb{N}} \simeq \mathbb{R}$. I am aware you could do this with base $n$-ary expansions of reals, but that seems a bit clunky to me. Is there a way to prove this by avoiding such expansions?

I can do this one way for $n = 1$ by enumerating the rationals, associating each real number it's "cut" of rational numbers less than it, and setting the $n$th digit of the sequence associated with $x$ to be $1$ if $r_n < x$. This gives an injection from $\mathbb{R}$ to $[1]^{\mathbb{N}}$. Can this be generalized? And what about the other direction (for Schroder Bernstein)?

1

There are 1 best solutions below

5
On BEST ANSWER

I'll write $\{0,1,\ldots,n-1\}^{\mathbb N}=:W_n$ for short.

You have provided an injection $\phi:\>{\mathbb R}\to W_2$. For an injection $\psi$ in the other direction use some Cantor set construction, e.g., $$\psi(x):=\sum_{k=1}^\infty{2x_k\over3^k}\ .$$ On the other hand it is obvious that $W_n\subset W_m$ if $n<m$. Furthermore the sets $W_n$ and $W_{n^2}$ can be bijectively related by re-encoding: For $x\in W_n$ put $$y_k:=n x_{2k-1}+x_{2k}\qquad(k\geq1)\ .$$ Then $$\chi:\quad W_n\to W_{n^2},\qquad x\mapsto y$$ is a bijection. In this way we have shown that all $W_n$, $n\geq2$, have the same cardinality.