Prouver que l'ensemble de toutes les langues sur un alphabet fini est indénombrable
-
09-10-2019 - |
Question
Essayer de faire une révision, mais pas sûr de celui-ci:
Prouver que l'ensemble de toutes les langues sur un alphabet fini est fi indénombrable.
J'ai le sentiment qu'il faudra en utilisant la méthode Cantor Diagonalisation de - mais je suis ne sais pas comment vous l'utiliser pour ce problème.
La solution
Je l'ai trouvé dans mes notes de cours théoriques de calcul cette preuve, je l'espère, il est utile pour vous
| N | <| Langues (N) |
Supose que | N | > = | Langues (N) |. Par conséquent, chacun des éléments de langues (N) peuvent être liés à l'un des éléments de N. Ils peuvent être mis en ordre:
langues (N) = {S_1, S_2, S_3, ...}
Nous définissons un ensemble D comme:
D = {n en N / n pas dans S_n}
D est valide et D est un sous-ensemble de N, donc D appartient langues (N). Donc, il doit exister un k pour lesquels D = S_k
1) Si k appartient à D par définition de D, k ne appartiennent à S_k. Et k ne appartiennent à D = D Parce que S_k (Nous trouvons une contradiction)
2) Si k ne pas appartenir à D alors: k appartient à S_k (par définition de D) et k appartient à D parce que D = S_k (Contradiction nouveau)
Une séquence comme celle supposée ne peut pas exister. Par conséquent, une fonction injective qui attribue un elemnt de N pour chaque élément de langues (N) est impossible. Concluant que | langues (N) | ! <= | N |, donc | langues (N) | > | N |