0

Suppose that we have a written language consisting of all 26 letters of the English alphabet. Words are formed in this language by constructing finite strings of integers. a) Prove that the set of all words W, in this language is a denumerable set b) if we allow words to be of infinite(denumerable) length, show that W is uncountable

I tried doing part a but I can't really think about how i'd find a bijection from the natural numbers. I assume part b would be proven by contradiction using part a somehow, but i'm not exactly sure.

Owen
  • 1

2 Answers2

1

Define $W_n$ to be the words of length $n$. Then one has $\#W_n < +\infty$ (why?). Let $W$ be the set of all possible words. Then $W = \cup_{n \in \mathbb{N}} W_n$. Therefore $W$ is a countable union of at most countable sets, yielding that $W$ is countable.

If we allow words of infinite length, one concludes that $W$ is uncountable by using Cantor's diagonal argument.

Hermès
  • 2,647
0

Hint: the integers $\mathbb Z$ are nothing but the finite strings of an alphabet with 10 letters... For part b consider the real numbers in a similar way or use the Cantor diagonal process proving that the set is uncountable by contradiction.

Bargabbiati
  • 2,271