Udowodnić, że zbiór wszystkich językach ponad alfabetem fi nite jest niezliczona

Question

Próbując zrobić jakieś zmiany, ale nie wiem, na tym jednym:

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

Mam wrażenie, będzie to wymagało stosując metodę Cantor Diagonalization - ale jestem nie jestem pewien, w jaki sposób użyłbyś go do tego problemu.

Answer 1

Znalazłem w mojej teorii obliczeń klasy notatek Dowód ten, mam nadzieję, że to przydatne dla Ciebie

| N | < | języki (N) |

Załóżmy | N | > = | języki (N) |. Dlatego każdy z elementów języków (N) może być powiązany z jednym z elementów N. Można więc je uporządkować:

języki (N) = {S_1, S_2, S_3, ...}

Zdefiniujmy zestaw D jak:

D = {n, w n/n nie s_n}

D jest ważne, a D jest podzbiór n zatem D przynależy języków (n). więc musi istnieć k dla którego D = S_k

1) Jeśli k należy do D następnie przez definicji D, K nie należy do S_k. I k nie należy do D Ponieważ D = S_k (Znaleźliśmy sprzeczność)

2) Jeśli k nie należy do D, to: k należy do S_k (z definicji D), a k do D, ponieważ D = S_k (Sprzeczność ponownie)

Nie można znaleźć sekwencji podobnej do przyjętej. Dlatego funkcja iniekcyjna, która przypisuje element N dla każdego elementu języka (N), nie jest możliwa. Wniosek, że | języki (N) | ! < = | N |, więc | języki (N) | > | N |