# Set of all countably infinite strings over a finite alphabet >1

Is the set of all countably infinite strings over a finite alphabet that contains more than one letter countably infinite?

• What is a "countably infinite string"? – fade2black Dec 5 '17 at 9:03
• An infinite string over the alphabet that can be counted. Hence, can be sorted in an ascending order. – Anwar Saiah Dec 5 '17 at 9:05
• The fact of the matter is that the order doesn't even have to be ascending, any order will do. – Anwar Saiah Dec 5 '17 at 9:08
• You say "over a finite alphabet" which already implies that your underlying alphabet is countable. So, no need to use the word "countably" (which may be confusing), simply "infinite strings" would be enough. – fade2black Dec 5 '17 at 9:09
• @DavidRicherby I got you. Thanks for references. – fade2black Dec 5 '17 at 13:16

Take the alphabet $\Sigma = \{0,1\}$ and consider strings whose positions are indexed by $\mathbb{N}$ (also known as $\omega$-words). There is a one-to-one correspondence between these strings and subsets of $\mathbb{N}$ given by $x_0x_1x_2\dots \leftrightarrow \{i\in\mathbb{N}\mid x_i=1\}$. Therefore, there are as many $\omega$-words as there are subsets of $\mathbb{N}$, and this is an uncountable number.
Consider an alphabet $\Sigma = \{0,1\}$ and the set of all infinite length strings over $\Sigma$. Then this set is of course infinite, but uncountable which can be easily proved by the diagonalization argument.
• Assume that this set is countable, i.e., its elements (strings) can be enumerated as $s_1, s_2,\dots$. Then you can construct a new infinite string $s$ which differs from each $s_i$ in $i$-th position by the following rule: if $i$th symbol of $s_i$ is $0$ then let $i$-th symbol of $s$ be $1$, and let $i$-th symbol of $s$ be $0$ otherwise. – fade2black Dec 5 '17 at 9:37