Beweisen Sie, dass die Menge aller Sprachen über einem endlichen Alphabet ist unzählbar

Question

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

Prove that the set of all languages over a finite alphabet is uncountable. 

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

Answer 1

ich in meiner Berechnung Theorie Klasse Noten dieser Beweis gefunden habe, hoffe ich es für Sie

nützlich ist | N | < | Sprachen (N) |

Zeigen Sie, dass | N | > = | Sprachen (N) |. Daher kann jedes der Elemente von Sprachen (N) mit einem der Elemente von N in Beziehung gesetzt werden. So können sie in die richtige Reihenfolge gebracht werden:

Sprachen (N) = {S_1, S_2, S_3, ...}

Wir definieren eine Menge D wie:

D = {n in N/n nicht in S_n}

D gültig ist, und D ist eine Teilmenge von N, also D gehört Sprachen (N). Also, es muss eine für die k existieren D = S_K

1) Wenn k D gehört dann durch Definition von D, k gehört nicht zu S_K. Und k gehört nicht zu D Weil D = S_k (Wir finden einen Widerspruch)

2) Wenn k nicht zu D gehört dann: k gehört zu S_k (nach Definition von D) und k gehört zu D weil D = S_k (Wiederum Widerspruch)

Eine Sequenz wie die angenommene kann nicht existieren. Daher ist eine injektive Funktion, die ein Element von N für jedes Element von Sprachen (N) zuweist, nicht möglich. Schluss damit, dass | Sprachen (N) | ! < = | N |, so | Sprachen (N) | > | N |