Zeigen Sie, dass die Menge aller Sprachen über ein endliches Alphabet überabzählbar

Question

Der Versuch, eine Revision zu tun, aber nicht sicher, auf diese:

Zeigen Sie, dass die Menge aller Sprachen über ein endliches Alphabet ist unzählbar.

Ich habe das Gefühl, es erfordert unter Verwendung der Cantor Diagonalisierung Methode - aber ich bin nicht sicher, wie Sie es für dieses Problem verwenden würden.

Answer 1

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|