# Show that the set W is a countable set.

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

-
Do you know that the union of countably many countable sets is countable? If so, you could partition $W$ into sets of words of a fixed length, and show that this makes $W$ a countable union of countable sets. – Manny Reyes Sep 21 '12 at 18:38
Can you show that the union of countably many finite sets is countable? – Mustafa Gokhan Benli Sep 21 '12 at 18:38
@Manny you were 19 seconds faster :) – Mustafa Gokhan Benli Sep 21 '12 at 18:39
That is genius! Thank you both! – user39794 Sep 21 '12 at 18:41
That question has nothing to do with real analysis, and has a lot more to do with elementary set theory. – Asaf Karagila Sep 21 '12 at 19:47

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

-

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.

-