# 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.

This holds for any countably infinite word length.

• The question says "set of all countably infinite strings...". Doesnt that mean the set is already known to be countably infinite (and we have nothing to prove) ? Am I missing something and sounding stupid? – anir Dec 1 '19 at 14:36
• @anir The strings have countably infinite length; the question is how many of these strings exist. – David Richerby Dec 1 '19 at 18:10
• ohh so its "strings of countably infinite length", but not "countably infinite number of strings"! (Q1) What does countable means in "countably infinite length". (Length is single value not an infinite set whose elements we can count.) (Q2) I guess all languages on non-singleton alphabet with infinite length strings are uncountable, right? – anir Dec 1 '19 at 18:56

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.

• Thanks, you know what I don't like about easily proved diagonalization arguments? It's that their ease is a matter of perspective. What's easy there is not so easy here! Any way I was thinking to prove it this way: Since we cannot order the sets in any manner, then they are uncountable.If we take two strings s1 and s2 when s2>s1 we can plot a string s3 that will be between them by simply adding characters to s1or removing them from s2.. So how about that diagonal argument of yours? – Anwar Saiah Dec 5 '17 at 9:29
• 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
• Yes, now I see what you ment by easily proved. – Anwar Saiah Dec 5 '17 at 9:39