1
$\begingroup$

Q: Let the alphabet A be a finite set of $n$ letters such that A=${a_1, a_2,...,a_n}$ and let W be the set of all possible words written from this finite alphabet (here a word is a finite concatenation of letters). Show that W is countable.

I don't know how to do this...?

  • 0
    That question has nothing to do with real analysis, and has a lot more to do with elementary set theory.2012-09-21

2 Answers 2

3

@William has already given a construction using the standard proof that the countable unions of countable sets are countable, but I would like to also present a direct proof for completeness.

Given $A=\{a_1,\dots,a_n\}$ and $W=\{\text{Words of finite length}\}$, where a word is a concatenation of elements from $A$, let $W_m$ denote the set of words of length $m$. The number of elements of $W_m$ is precisely $n^m$, hence finite. We can now rewrite $W$ in the following way.

$ W=\bigcup_{m=1}^\infty W_m $

We can form a bijection (one-to-one mapping) between the natural numbers in the following way. Assign to the elements of $W_1$ the numbers $\{1,2,\dots,n\}$ in a non-repeating way. To the elements of $W_2$ assign the numbers $\{n+1,n+2,\dots,n+n^2\}$ in a non-repeating way. Now supposing that we have assigned to sets $W_1,\dots,W_k$ the numbers $\{1,2,\dots,\sum_{i=1}^k n^i\}$, assign to the elements of $W_{k+1}$ the numbers $\{1+\sum_{i=1}^k n^i,2+\sum_{i=1}^k n^i,\dots,n^{k+1}+\sum_{i=1}^k n^i\}$.

The above construction shows the existence of a bijection between $W$ and the natural numbers, which are countable. Therefore, $W$ is countable.

2

If $A$ is a finite alphabet of size $k$. Let $B_n$ denote the words of length $n$. Then the size of $B_n$ is $k^n$. The set of all words in $A$ is $\bigcup_{n \in \mathbb{N}} B_n$. Countable union of countable sets (finite sets) are countable. Hence the set of all words are countable.