Flashcard FC264094
Como o argumento da diagonal de Cantor prova que um conjunto é não enumerável?
Conjuntos
IDECAN · 2021
Como o argumento da diagonal de Cantor prova que um conjunto é não enumerável?
Mostrar resposta e comentário
Resposta
Constrói-se, a partir de uma suposta enumeração, um elemento que difere de cada elemento da lista na coordenada diagonal, gerando contradição.Explicação completa:
Suponha, por absurdo, que exista uma enumeração \(x_1,x_2,x_3,\dots\) do conjunto em questão. Escreva cada \(x_n\) como uma sequência de coordenadas e construa um novo elemento \(y\) escolhendo sua coordenada \(y_n\) diferente da coordenada \(n\)-ésima de \(x_n\). Assim \(y\) não coincide com \(x_n\) em nenhuma coordenada \(n\), logo não está na lista — contradição. Portanto o conjunto é não enumerável.
Exemplo:
Considere o conjunto das partes de \(\mathbb{N}\), \(\mathcal{P}(\mathbb{N})\). Suponha que todas as partes foram listadas: \(A_1,A_2,A_3,\dots\). Defina
\(B=\{\,n\in\mathbb{N}: n\notin A_n\,\}.\)
Por construção, para todo \(n\) temos \(n\in B\) exatamente quando \(n\notin A_n\), portanto \(B\neq A_n\) para todo \(n\). Assim \(B\) não aparece na lista, contradizendo a enumeração — logo \(\mathcal{P}(\mathbb{N})\) é não enumerável.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/261456
Conteúdo do catálogo FC Concursos · Atualizado em