3
$\begingroup$

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?

  • 0
    @Arturo: Of course, my remark was merely to suggest that the axiom of choice is not required to show countability or uncountability of this set, since deciding whether or not this set is countable can be deduced directly from the cardinality of the alphabet. If you want to calculate the cardinality the axiom of choice will indeed be useful. :-)2012-02-10

4 Answers 4

4

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.

3

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.

If you wish, you can start with the empty string.

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

2

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.

2

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

\begin{equation} \Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n \end{equation}

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.

\begin{equation} \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, ... \} \end{equation}

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$