5
$\begingroup$

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 !

$\endgroup$
8
  • $\begingroup$ This is not the way to start. Look for countability of the set of finite strings. The chosen alphabet is irrelevant as long as it's countable. $\endgroup$
    – AlexR
    Mar 25, 2015 at 19:27
  • $\begingroup$ A countable union of countable sets is also countable. $\endgroup$ Mar 25, 2015 at 19:28
  • $\begingroup$ @AlexR: the chosen alphabet is irrelevant as long as it's countable. $\endgroup$
    – TonyK
    Mar 25, 2015 at 19:30
  • $\begingroup$ @TonyK Thanks I noticed that after reading on my found dupe. Edited within the grace period ;) $\endgroup$
    – AlexR
    Mar 25, 2015 at 19:33
  • 1
    $\begingroup$ The set of all English words is finite, because there is a longest word. $\endgroup$ Mar 25, 2015 at 19:39

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – AlexR
    Mar 25, 2015 at 19:51
  • $\begingroup$ Perfect. Thank you very much ! $\endgroup$
    – NotSure
    Mar 25, 2015 at 20:11
  • $\begingroup$ @MattG: You're welcome :) $\endgroup$ Mar 25, 2015 at 20:12
  • $\begingroup$ Mistake, fixed it $\endgroup$
    – NotSure
    Mar 25, 2015 at 22:09
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .