proving that the set of all english words is countble.

Question

This is the question : Prove that the set of all the words in the English language is countble (the set's cardinality is אo) A word is defined as a finite sequence of letters in the English language.

I'm not really sure how to start this. I know that a finite union of countble sets is countble and i think this is the way to start.

Thanks in advance !

Answer 1

There are $26$ letters in the English language.

Consider each letter as one of the digits on base $27$:

• $A=1$
• $B=2$
• $C=3$
• $\dots$
• $Z=26$

Then map each word to the corresponding integer on base $27$, for example:

$\text{BAGDAD}=217414_{27}=2\cdot27^5+1\cdot27^4+7\cdot27^3+4\cdot27^2+1\cdot27^1+4\cdot27^0$.

This mapping yields that the cardinality of your set is $\leq|\mathbb{N}|$, hence this set is countable.

Answer 2

The set $S_n$ of the English words with length $n$ is finite (this is almost obvious). So it's also countable. Why is it finite? The set $A_n$ of all sequences with length $n$ made up of latin characters is finite as it contains $26^n$ elements. Only some of these sequences are meaningful/actual English words. So $S_n \subset A_n$. So $S_n$ is also finite.

The set $T$ for which you have to prove that it is countable is:

$T = S_1 \cup S_2 \cup S_3 \cup ... $

Now you have this theorem:
"A countable union of countable sets is also countable"

Applying it you get that T is also countable.
Thus your statement has been proved.

Answer 3

The easiest way to show a set is countable is to provide a way of counting it - ie a rule to determine the position of any member within the set.

In this case we can start with all 1-letter "words", from a to z - there are 26 of these. Then we can continue with the two-letter words aa, ab, ... az, ba, bb .... zy, zz. There are 26^2 of these. And so on.

Any finite-length word will be assigned a unique position in this sequence, therefore the sequence is countable.