Denotamos por P(X) o conjunto das partes de X, ou seja, o conjunto dos subconjuntos de X. Mostre que P(N) é não enumerável. com calculos

Passo 1

O enunciado pede para provar que o conjunto das partes de ℕ, denotado por P(N), 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 P(N). Em outras palavras, existe uma função bijetora hipotética f:NtoP(N) que lista todos os subconjuntos de (\mathbb{N}).

Passo 3

Usando f, vamos construir um subconjunto especial de N que não pode aparecer em nenhuma posição da lista. Definimos o conjunto diagonal
D = ninN : nnotin f(n)

Passo 4

Argumentamos que D não está na imagem de f. Se existisse kinN tal que f(k)=D, então teríamos duas possibilidades:
  • Se kin D, pela definição de D isso implicaria knotin f(k)=D, contradição.
  • Se knotin D, então pela definição de D teria kin f(k)=D, também contradição.

Passo 5

Como ambos os casos levam a contradição, concluímos que não existe k tal que f(k)=D. Isso demonstra que D não está listável por f, contrariando a hipótese de que f enumera P(N).

Resposta

Portanto, não existe enumeração de P(N), isto é, P(N) é não enumerável.

Exercícios relacionados