Proving conjunto de línguas finitas vs todas as línguas sobre o alfabeto finito para ser contável / incontável

Question

Eu me deparei com os seguintes fatos:

.

.
1. conjunto de línguas finitas sobre um alfabeto finito é contável.
2. Conjunto de idiomas sobre o alfabeto finito é incontável.
   Eu acredito que a prova disso será semelhante ao número abaixo do fato 3.
3. conjunto de idiomas sobre {0,1} é incontável.

Eu me deparei com a prova de facto 1 Aqui e do fato 3 Aqui .

Resumo do fato 1 Prova:

.

Deixe seu alfabeto finito ser $ Σ= {a_1, ..., A_ℓ} $ e deixe $ \ # $ < / Span> Seja algum caractere não em $ Σ $ . Deixe $ l= {w_1, ..., w_n} $ ser uma linguagem finita sobre $ Σ $ . Em seguida, a string $ \ # w_1 \ # w_2 \ # ... \ #w_n $ mapas diferentes $ l $ para inteiro diferente.

Resumo do fato 3 Prova:

.

Deixe $ l $ Conjunto de todas as cadeias de comprimento finito sobre $ \ {0,1} $ . Podemos gerar um mapeamento um-para-um da $ l $ para $ \ mathbb {n} $ : Basta adicionar um 1 na frente de cada string em w e interpretar as strings resultantes como números binários. Então $ l $ é contável. Agora, deixe $ l _ {\ {0,1 \}} $ é contável, onde $ l \ {0,1 \ }={L_1, l_2, l_3, ... \} $ com cada $ l_i $ ser um idioma sobre $ \ {0,1 \} $ . Dado que cada $ l_i $ é um conjunto cujos elementos são strings de $ l $ e desde que $ l $ é contável, podemos construir uma tabela cujos índices de linha são índices de linguagem e cujos índices de coluna são índices de string da seguinte forma: Para cada célula de tabela com índice de linha $ i $ e índice de coluna $ J $ , escreva 1 se a linguagem $ L_i $ contém a string $ s_j $ ou 0 caso contrário.

Nós vílimos o valor de cada célula diagonal na tabela acima, colecionamos todas as strings $ s_j $ tal que a célula diagonal na coluna da $ s_j $ tem um 1 após a folga:
Vamos chamá-lo $ l_ {diag}= {s_2, s_3, ...} $ .
$ l_ {diag} $ é um idioma com uma propriedade especial: é diferente de todas as linguagens $ l_i∈l _ {\ {0,1 \}} $ . Isso implica $ l_ {diag} ≠ l_i $ para todos $ l_i∈l $ {{0,1 }} e, portanto, $ l_ {diag} ∉l _ {\ {0,1 \}} $ . No entanto, como $ l $ é um conjunto de seqüências de caracteres que estão em $ l $ , $ l_ {diag} $ é um idioma sobre {0,1} e, portanto, $ l_ {diag} ∈l _ {\ {0,1 \}} $ , uma contradição. Portanto, $ l _ {\ {0,1 \}} $ não pode ser contável.

dúvidas

Eu recebo as provas, mas eu não entendo por que as abordagens seguidas em cada uma delas não podem ser usadas para provar outro fato incorreto. Isto é:

.

1. Por que eu não posso usar o fato 1 Abordagem de prova para provar que o fato 3 está incorreto, isto é "conjunto de idiomas sobre {0,1} é contável". Não posso formar uma cadeia de string semelhante $ \ # w_1 \ # w_2 \ # ... \ #w_n $ Para diferentes idiomas para mapeá-los para diferentes inteiros?

2. Por que eu não posso usar a abordagem de prova de fatos 3 para provar que o fato 1 está incorreto, isto é "conjunto de linguagens finitas sobre um alfabeto finito é incontável"?

   Não posso formar tabela semelhante para linguagens finitas e, em seguida, formulário $ l_ {diag} $ que não pertencem ao conjunto de línguas finitas?

Answer 1

.

1. Se o idioma for infinito, a palavra $ \ # w_1 \ # w_2 \ ldot $ seria infinito, e assim não mapear para uminteiro de qualquer maneira significativa.

2. Aplicar o argumento diagonal no conjunto de todos os idiomas finitos pode (de fato, vontade) resultar em uma linguagem infinita.