Demostrar que el conjunto de todos los idiomas sobre un alfabeto finito es incontable

Question

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

Demostrar que el conjunto de todos los idiomas sobre un alfabeto finito es incontable.

Tengo la sensación de que requerirá utilizando el método de la Cantor diagonalización - pero estoy no está seguro de cómo le gustaría utilizarlo para este problema.

Answer 1

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

| N | <| Idiomas (N) |

supose que | N | > = | Idiomas (N) |. Por lo tanto, cada uno de los elementos de idiomas (N) puede estar relacionada con uno de los elementos de N. Por lo que se pueden poner en orden:

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

Se define como un conjunto D:

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

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

1) Si k pertenece a D entonces, por definición de D, k no pertenece a S_k. Yk no es de D = D Debido S_k (nos encontramos con una contradicción)

2) Si k no pertenece a D a continuación: k pertenece a S_k (por definición de D) y k pertenece a D porque D = S_k (contradicción de nuevo)

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