Denotamos por
o conjunto das partes de
, ou seja, o conjunto dos subconjuntos de
. Mostre que
é não enumerável. com calculos
Passo 1
O enunciado pede para provar que o conjunto das partes de ℕ, denotado por
, não é enumerável. O conteúdo principal é teoria de conjuntos e usaremos o argumento diagonal de Cantor para chegar à contradição.
Passo 2
Suponha, por absurdo, que exista uma enumeração de
. Em outras palavras, existe uma função bijetora hipotética
que lista todos os subconjuntos de (\mathbb{N}).
Passo 3
Usando
, vamos construir um subconjunto especial de
que não pode aparecer em nenhuma posição da lista. Definimos o conjunto diagonal
Passo 4
Argumentamos que
não está na imagem de
. Se existisse
tal que
, então teríamos duas possibilidades:
- Se
, pela definição de isso implicaria , contradição. - Se
, então pela definição de teria , também contradição.
Passo 5
Como ambos os casos levam a contradição, concluímos que não existe
tal que
. Isso demonstra que
não está listável por
, contrariando a hipótese de que
enumera
.
Resposta
Portanto, não existe enumeração de
, isto é,
é não enumerável.