Département des langues finies vs toutes les langues sur l'alphabet fini pour être dénombrables / indénombrables

Question

J'ai rencontré des faits suivants:

1. Ensemble de langues finies sur un alphabet fini est comptable.
2. Ensemble de langues sur l'alphabet fini est indénombrable.
   Je pense que la preuve de ce fait sera similaire à celle ci-dessous.
3. ensemble de langues sur {0,1} est indénombrable.

J'ai rencontré une preuve de fait 1 ici et de fait 3 ICI .

Résumé du fait 1 Preuve:

Laissez votre alphabet fini être $ σ= {a_1, ..., a_ℓ} $ et laisse $ \ # $ < / Span> Soyez un personnage non dans $ σ $ . Laissez $ l= {w_1, ..., w_n} $ soit une langue finie sur $ σ $ . Alors la chaîne $ \ # w_1 \ # w_2 \ # ... \ #w_n $ carte différente $ l $ à différents entier.

Résumé du fait 3 Preuve:

let $ l $ soit réglé de toutes les chaînes de longueur finies sur $ \ {0,1 \} $ . Nous pouvons générer un mappage unique de $ l $ à $ \ mathbb {n} $ : Il suffit d'ajouter un 1 devant chaque chaîne dans W et interprétez les chaînes résultantes en tant que nombres binaires. Donc $ l $ est comptable. Maintenant, laissez $ l _ {\ {0,1 \}} $ est comptable, où $ l \ {0,1 \ }={L_1, l_2, l_3, ... \} $ avec chaque $ l_i $ étant une langue sur $ \ {0,1 \} $ . Étant donné que chaque $ l_i $ est un ensemble dont les éléments sont des cordes de $ l $ et depuis $ L $ est comptable, nous pouvons construire une table dont les indices de ligne sont des indices de langue et dont les indices de la colonne sont des indices de chaîne comme suit: Pour chaque cellule de table avec indice de rangée I $ I $ et index de colonne $ j $ , écrire 1 si la langue $ L_i $ contient la chaîne $ s_j $ ou 0 sinon.

Nous retournons la valeur de chaque cellule diagonale sur la table ci-dessus, puis collectez toutes les chaînes $ s_j $ telle que la cellule diagonale sur la colonne de $ S_J $ a un 1 après avoir retourné:
Permet de l'appeler $ l_ {diag}= {s_2, s_3, ...} $ .
$ l_ {diag} $ est une langue avec une propriété spéciale: elle est différente de chaque langue $ l_i∈l _ {\ \ {0,1 \}} $ . Cela implique $ l_ {diag} ≠ l_i $ pour tous $ l_i∈l $ {{0,1 }} et donc $ l_ {diag} ∉l _ {\ {0,1 \}} $ . Cependant, étant donné que $ l $ est un ensemble de chaînes qui sont dans $ l $ , $ l_ {diag} $ est une langue sur {0,1} et donc $ l_ {diag} ∈l _ {\ {0,1 \}} $ , une contradiction. D'où $ l _ {\ \ {0,1 \}} $ ne peut pas être comptable.

doutes

Je reçois les deux preuves, mais je ne comprends pas pourquoi les approches suivies dans chacun d'entre eux ne peuvent pas être utilisées pour prouver d'autres faits incorrects. C'est:

1. Pourquoi je ne peux pas utiliser l'approche de la preuve pour prouver que le fait de prouver est incorrecte, c'est «ensemble de langues sur {0,1} est comptable». Je ne peux pas former une chaîne de chaîne similaire $ \ # w_1 \ # w_2 \ # ... \ #w_n $ Pour différentes langues pour les cartographier à différents entiers?

2. Pourquoi je ne peux pas utiliser l'approche de la preuve pour prouver le fait 1 est incorrecte, c'est-à-dire "un ensemble de langues finies sur un alphabet fini est indénombrable"?

   Je ne peux pas faire une table similaire pour les langages finis, puis former $ l_ {diag} $ qui appartiennent à l'ensemble des langues finies?

Answer 1

1. si la langue est infinie, le mot $ \ # w_1 \ # w_2 \ ldots $ serait infini, et donc ne correspond pas à unEntier de manière significative.

2. Appliquer l'argument diagonal sur l'ensemble de toutes les langues finies pourrait (en effet, volonté) entraîner une langue infinie.