Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
2  
Can you show that the union of countably many finite sets is countable? –  Mustafa Gokhan Benli Sep 21 '12 at 18:38
1  
@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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.