|
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...? |
|||||||||||||||||
|
|
@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. |
|||
|
|
|
Hint: The number of words of length $n$ is finite. Now consider the set of words of all possible lengths $n \in \mathbb{N}$. |
|||||
|
|
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. |
|||
|
|
