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

-

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! – Allison Cameron 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

## 3 Answers

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

-

So the set of words of all possible lengths n must also be finite? – Allison Cameron Sep 21 '12 at 18:40
@AllisonCameron No. The set of all possible lengths is countably infinite. It's $1, 2, \ldots$ (or $\mathbb{N}$). So the set of all words of all possible lengths is the union of countably many finite sets. – Ayman Hourieh Sep 21 '12 at 18:41

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9343360662460327, "perplexity_flag": "head"}