Demostrar que el conjunto de todos los idiomas más de un alfabeto finito es incontable

Question

Tratar de hacer alguna revisión, pero no estoy seguro en este caso:

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

tengo la sensación de que será necesario utilizar el método Cantor Diagonalization - pero yo' No estoy seguro de cómo lo usaría para este problema.

Answer 1

que he encontrado en mis notas de clase teoría de la computación esta prueba, espero que sea útil para usted

| N | < | idiomas (N) |

Supongamos que | N | > = | idiomas (N) |. Por lo tanto, cada uno de los elementos de los idiomas (N) se puede relacionar con uno de los elementos de N. Por lo tanto, se pueden ordenar:

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

se define un conjunto D como:

D = {N en N/n no en S_n}

D es válida y D es un subconjunto de N, por tanto, pertenece D idiomas (N). Por lo tanto, debe existir un k para el cual D = S_k

1) Si k pertenece a D entonces, por definición de D, k no pertenece a S_k. Y k no pertenece a D Porque D = S_k (encontramos una contradicción)

2) Si k no pertenece a D, entonces: k pertenece a S_k (por definición de D) yk pertenece a D porque D = S_k (Contradicción nuevamente)

Una secuencia como la asumida no puede existir. Por lo tanto, no es posible una función inyectiva que asigna un elemento de N para cada elemento de los idiomas (N). Concluyendo que | idiomas (N) | ! < = | N |, so | idiomas (N) | > | N |