Mostre que se
é um conjunto infinito enumerável, então
não enumerável.
Dica: Mostre que existe uma bijeção de
e
e use o exercício anterior.
Passo 1
Vamos começar entendendo o que a questão está pedindo. Temos um conjunto
que é infinito e enumerável, ou seja, seus elementos podem ser listados como os números naturais
. Queremos mostrar que o conjunto das partes de
, denotado por
, 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
e
. Primeiro, como
é enumerável, existe uma bijeção
. Isso significa que cada elemento de
pode ser associado a um único número natural e vice-versa.
Passo 3
Agora, vamos usar essa bijeção
para construir uma nova função
. Definimos
da seguinte maneira:
Ou seja, para cada subconjunto
de
,
é o conjunto dos números naturais correspondentes aos elementos de
através da função
.
Passo 4
Vamos verificar que
é uma bijeção:
-
Injetora: Se
, então . Como é uma bijeção, isso implica que . -
Sobrejetora: Para qualquer subconjunto
de , existe que é um subconjunto de tal que .
Portanto,
é uma bijeção entre
e
.
Passo 5
Sabemos de um exercício anterior (ou pelo Teorema de Cantor) que
não é enumerável. Como acabamos de mostrar que
e
têm o mesmo tamanho (são bijetores), concluímos que
também não é enumerável.
Resposta
Portanto, se
é um conjunto infinito enumerável, então
não é enumerável.