Published on 2019-12-27
Warning: this is not very rigorous, I just want to provide an intuitive explanation.
I have seen a lot of different proofs on why the set of languages over an alphabet is uncountable, however the one I'm about to show you now is the simplest in my opinion. It involves using Cantor's diagonalisation argument and forming a couple of bijections.
Firstly, we can see that if we prove that the set of languages over the alphabet denoted by is uncountable, then the set of languages over any non-empty alphabet is uncountable, as we can just take a one element subset of the alphabet, form a bijection to , and as the set of languages with that subset is uncountable, and this set is a subset of all languages possible from the alphabet, then the set of languages for the whole alphabet must be uncountable. Thus it is sufficient to prove that the set of languages over the alphabet is uncountable.
Ok, first of all, let us observe the set of all possible finite-length strings formed from the alphabet . will just be strings of a finite number of 0s concatenated i.e.,
As is countable, we can assign a unique natural number to each element of , i.e., we can say that is of the form
Now, we want to prove that is uncountable. We will do this using a proof by contradiction. Let us assume that is countable. This means that there must be some enumeration of elements in where we assign a unique natural number to each element of . Let us take one such enumeration.
For this enumeration, we can create a similar representation in terms of 0s and 1s for all the :
Email a comment to the public inbox!