What is the cardinality of the set of all infinite words formed using a finite alphabet of length > 1?

Question

I am trying to prove that this cardinality is equal to the cardinality of $\mathbb{R}$. I proved that if words are finite, then the set of all words is countable, however I cannot extend that proof to prove this question. Can anyone know how to prove?

Answer 1

Let $a$ and $b$ be two distinct members of the alphabet. For each $S\subseteq\Bbb Z^+$ let $w_S$ be the word $c_1c_2c_3\ldots$ such that

$$c_n=\begin{cases} a,&\text{if }n\in S\\ b,&\text{if }n\notin S\,, \end{cases}$$

and verify that the map that takes $S$ to $w_S$ is an injection from the power set of $\Bbb Z^+$ to the set of infinite words over the given alphabet. This shows that the cardinality of that set of words is at least as big as the cardinality of $\Bbb R$.

To show that the cardinality of that set of words is no bigger than the cardinality of $\Bbb R$, let the alphabet be $\{a_1,a_2,\ldots,a_n\}$, and for each $k$ let $d(a_k)=k$. If $w$ is the word $c_1c_2c_3\ldots$, let

$$x_w=0.d(c_1)d(c_2)d(c_3)\ldots\,,$$

viewed as a number written in the base $n+2$, so that

$$x_w=\sum_{k\ge 1}\frac{d(c_k)}{(n+2)^k}\,.$$

That is, if $n=6$, and $w$ starts $a_3,a_1,a_6$, then $x_w$ starts $0.316$ and is to be interpreted as a number in base $n+2$. Show that the map taking $w$ to $x_w$ is an injection from your set of infinite words to the unit interval $[0,1]$. Taking the base to be $n+2$ is what will let you show that the map is an injection ($1$-to-$1$).

Putting the two pieces together will then give you the desired result.