(José Igor) Prove que se
é infinito enumerável, o conjunto das partes finitas de
também é (infinito) enumerável.
Passo 1
O enunciado pede para mostrar que, se
é um conjunto infinito enumerável, então o conjunto
também é enumerável (e infinito).
O conteúdo que vamos usar envolve:
– a noção de enumerabilidade (contável) de um conjunto,
– o fato de que produto finito de conjuntos enumeráveis é enumerável,
– que união enumerável de conjuntos enumeráveis é enumerável.
O conteúdo que vamos usar envolve:
– a noção de enumerabilidade (contável) de um conjunto,
– o fato de que produto finito de conjuntos enumeráveis é enumerável,
– que união enumerável de conjuntos enumeráveis é enumerável.
Passo 2
Como
é enumerável infinito, existe uma bijeção
Denotemos
. Assim
Vamos particionar
pelo tamanho dos subconjuntos:
onde
Passo 3
Para cada
, considere o produto cartesiano
Sabemos que
é enumerável e, por indução, qualquer produto finito de conjuntos enumeráveis é enumerável. Logo,
Além disso, existe uma função sobrejetiva
que a uma
-tupla
associa o conjunto
.
Isto mostra que é no máximo enumerável.
Isto mostra que
Passo 4
O caso
é trivial, pois
tem um único elemento.
Assim cada é enumerável (ou finito, no caso
), e
Assim cada
é união contável de conjuntos enumeráveis. Como união contável de enumeráveis é enumerável,
é enumerável.
Passo 5
Para ver que
é infinito, basta notar que, para cada
, o conjunto
pertence a
, e esses são todos distintos. Logo há infinitos elementos em
.
Resposta
O conjunto das partes finitas de
é enumerável infinito.