computation-theorycountable

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.

Solution

  • 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|