Mostre que se X é um conjunto infinito enumerável, então P(X) não enumerável.
Dica: Mostre que existe uma bijeção de P(X) e P(N) e use o exercício anterior.

Passo 1

Vamos começar entendendo o que a questão está pedindo. Temos um conjunto X que é infinito e enumerável, ou seja, seus elementos podem ser listados como os números naturais N = 1, 2, 3, dots . Queremos mostrar que o conjunto das partes de X , denotado por P(X) , não é enumerável. Para resolver isso, vamos precisar entender conceitos como bijeção (uma correspondência perfeita entre dois conjuntos), conjuntos enumeráveis e a ideia de que alguns conjuntos são não enumeráveis.

Passo 2

A dica nos orienta a encontrar uma bijeção entre P(X) e P(N) . Primeiro, como X é enumerável, existe uma bijeção f: X to N . Isso significa que cada elemento de X pode ser associado a um único número natural e vice-versa.

Passo 3

Agora, vamos usar essa bijeção f para construir uma nova função g: P(X) to P(N) . Definimos g da seguinte maneira:
g(A) = f(A) = f(a) mid a in A
Ou seja, para cada subconjunto A de X , g(A) é o conjunto dos números naturais correspondentes aos elementos de A através da função f .

Passo 4

Vamos verificar que g é uma bijeção:
  • Injetora: Se g(A) = g(B) , então f(a) mid a in A = f(b) mid b in B . Como f é uma bijeção, isso implica que A = B .
  • Sobrejetora: Para qualquer subconjunto S de N , existe A = f^-1(S) que é um subconjunto de X tal que g(A) = S .
Portanto, g é uma bijeção entre P(X) e P(N) .

Passo 5

Sabemos de um exercício anterior (ou pelo Teorema de Cantor) que P(N) não é enumerável. Como acabamos de mostrar que P(X) e P(N) têm o mesmo tamanho (são bijetores), concluímos que P(X) também não é enumerável.

Resposta

Portanto, se X é um conjunto infinito enumerável, então P(X) não é enumerável.

Exercícios relacionados