# Finite strings from infinite alphabet

Is the set of all strings of finite length $\Sigma^*$ from a infinite alphabet $\Sigma$ uncountable?

The usual procedure in these types of proof is that you

list strings of length 1
list strings of length 2
list strings of length 3
.......

.......

.......
and so on


But now even the first line has infinite length so the construction can never stop. What is wrong?

-
Assuming the Axiom of Choice, the set of finite strings from an infinite alphabet has the same cardinality as the alphabet. But your method does not work, because the first "list" never ends, so you never get to the the list of strings of length 2. To show countability in the countable sense, well-order the alphabet, list words of the same length lexicographically, and then imitate the proof that the positive rationals are countable. –  Arturo Magidin Feb 9 '12 at 7:12
@Arturo Magidin if the alphabet was finite then my method would work right? –  user602774 Feb 9 '12 at 7:23
Yes, it would: in that case each line of your table would be finite. –  Brian M. Scott Feb 9 '12 at 7:28
hi could someone please help me out with this proof. Iam stuck ? :(. Help is greatly appreciated. –  user602774 Feb 9 '12 at 7:43
@Arturo: You actually don't need the axiom of choice at all here. If the alphabet is countable then without the axiom of choice you can show that the finite strings form a countable set; if the set was not countable to begin with... well, the result will not be countable. –  Asaf Karagila Feb 10 '12 at 9:39

If the set of letters is uncountable, so is the set of words. For a finite or countably infinite alphabet, one can imitate your argument closely without getting into difficulties.

List the alphabet as $a_0,a_1,a_2,\dots$. Let the complexity $c(w)$ of a word $w$ be the largest integer $i$ such that $a_i$ appears in $w$ plus the number of letters in $w$. It is clear that for any $n$ there are only finitely many words $w$ such that $c(w)=n$.

Write down the word(s) of complexity $0$ (there is only one, the empty word). Next down the word(s) of complexity $1$, in lexicographic order. Then write down the words of complexity $2$, in lexicographic order. And so on.

We conclude that if the set of letters is non-empty and finite or countably infinite, then the set of words is countably infinite.

-

If your alphabet is countably infinite and ordered then you can

• List all strings of length $m$ using letters up and including the $n$th where $m+n=2$
• List all strings of length $m$ using letters up and including the $n$th where $m+n=3$
• etc.

Each of the sublists is finite (you can use your suggestion within each sublist) and so the overall list is countable.

-

You have succumbed to a common fallacy: one proof does not generalise but that does not mean there is no other proof. The technique you use fails here but can easily be fixed.

Assume your alphabet is countable, i.e. $\Sigma = \{a_0, a_1, a_2, \dots\}$. The idea is that you can (recursively) enumerate the set $\Sigma^n = \{w \in \Sigma^* \mid |w| = n\}$ for any fixed $n \in \mathbb{N}$ and then interleave all these (countably infinitely many) enumerations.

In order to enumerate $\Sigma^n$, consider the following construction (note that $\Sigma^1 = \Sigma$ serves as an anchor) which interleaves the enumerations of $\Sigma$ and $\Sigma^{n-1}$, concatenating their elements to the words of $\Sigma^n$:

$\qquad \Sigma^n = \{\ \Sigma_0\Sigma^{n-1}_0,\quad \Sigma_0\Sigma^{n-1}_1, \Sigma_1\Sigma^{n-1}_0,\quad \Sigma_0\Sigma^{n-1}_2, \Sigma_1\Sigma^{n-1}_1, \Sigma_2\Sigma^{n-1}_0,\quad \dots \ \}$

By continuing this scheme, you enumerate whole $\Sigma^n$ (in a computable way).

Now, $\Sigma^*$ can be enumerated in the very same way:

$\qquad \Sigma^* = \{\ \varepsilon, \quad \Sigma^1_0, \quad \Sigma^1_1, \Sigma^2_0, \quad\Sigma^1_2, \Sigma^2_1, \Sigma^3_0,\quad \dots\ \}$

The technique used is often called dovetailing. If you write the whole space as a table, you can see that it closely resembles the canonical scheme for enumerating the rationals.

Note that if $\Sigma$ is uncountable $\Sigma^*$ is trivially uncountable, too.

-

$\Sigma^*$ is countably infinite. Recall,

$$\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n$$

for every value $n \in \mathbb{N}$, the set $\Sigma^n$ is countable, therefore, $\Sigma^*$ is a countable union of countable sets, thus it is countable.

Proof:

We must provide a bijection, a mapping of every element in $\Sigma^*$ to a unique element in $\mathbb{N}$, that is, a function which is one-to-one and onto.

Let $\Sigma = \{0, 1\}$ and $f:\Sigma^* \rightarrow \mathbb{N}$ be our bijection.

Now we start by writing down all the strings in $\Sigma^*$ in increasing order. First all strings of length $0$, then all strings of length $1$, all strings of length $2$, all strings of length $3$, so and and so forth.

$$\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 110, 101, 111, ...\}\\ \mathbb{N} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... \}$$

Upon inspection of the above, we clearly have a bijection $f:\Sigma^* \rightarrow \mathbb{N}$, that is a function that maps every element of our alphabet to a unique element of the natural numbers. Therefore, $\Sigma^*$ is countably infinite. $\square$

-