Prove that the set of all languages over a finite alphabet is uncountable
Trying to do some revision but not sure on this one:
Prove that the set of all languages over a finite alphabet is uncountable.
I have a feeling it will require using the Cantor Diagonalization method - but I'm not sure how you would use it for this problem.
Answer
I've found in my computation theory class notes this proof, I hope it's useful for you
|N| < |languages(N)|
Supose that |N| >= |languages(N)|. Therefore, each of the elements of languages(N) can be related to one of the elements of N. So they can be put into order:
languages(N) = {S_1 , S_2, S_3, ...}
We define a set D like:
D = {n in N / n not in S_n}
D is valid and D is a subset of N, therefore D belongs languages(N). So, there must exist a k for which D = S_k
1) If k belongs to D then by definition of D, k doesn't belong to S_k. And k doesn't belong to D Because D = S_k(We find a contradiction)
2) If k doesn't belong to D then: k belongs to S_k(by definition of D) and k belongs to D because D = S_k(Contradiction again)
A sequence like the one assumed can't exist. Therefore an injective function that assigns an elemnt of N for each element of languages(N) is not possible. Concluding that |languages(N)| !<= |N|, so |languages(N)| > |N|