1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is a "countably infinite string"? $\endgroup$ – fade2black Dec 5 '17 at 9:03
  • $\begingroup$ An infinite string over the alphabet that can be counted. Hence, can be sorted in an ascending order. $\endgroup$ – Anwar Saiah Dec 5 '17 at 9:05
  • $\begingroup$ The fact of the matter is that the order doesn't even have to be ascending, any order will do. $\endgroup$ – Anwar Saiah Dec 5 '17 at 9:08
  • $\begingroup$ 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. $\endgroup$ – fade2black Dec 5 '17 at 9:09
  • 1
    $\begingroup$ @DavidRicherby I got you. Thanks for references. $\endgroup$ – fade2black Dec 5 '17 at 13:16
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Anwar Saiah Dec 5 '17 at 9:29
  • $\begingroup$ 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. $\endgroup$ – fade2black Dec 5 '17 at 9:37
  • $\begingroup$ Yes, now I see what you ment by easily proved. $\endgroup$ – Anwar Saiah Dec 5 '17 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.