Para cada
, seja
. Prove que
é enumerável. Conclua que o conjunto
dos subconjuntos finitos de
é enumerável.
Passo 1
Resumo do enunciado e conteúdo
O exercício pede para mostrar que, para cada , o conjunto
O exercício pede para mostrar que, para cada
é enumerável (ou seja, possui bijeção ou injeção em
). Em seguida, devemos concluir que
— o conjunto de todos os subconjuntos finitos de
— também é enumerável.
Para isso, vamos usar dois fatos clássicos:
Para isso, vamos usar dois fatos clássicos:
- O produto cartesiano de conjuntos enumeráveis é enumerável (em particular
é enumerável para todo ). - A união enumerável de conjuntos enumeráveis é enumerável.
Passo 2
Base:
Passo indutivo: suponha que
é produto de dois conjuntos enumeráveis, logo é enumerável.
Por indução, é enumerável para todo
.
Por indução,
Passo 3
Injeção de
em
Dado , escrevemos seus elementos em ordem crescente:
Dado
Definimos
Essa aplicação é injetiva porque a tupla ordenada determina unicamente o conjunto
.
Passo 4
Conclusão de que
é enumerável
Como há uma injeção e
é enumerável (Passo 2), segue que
é, no máximo, enumerável. Além disso,
é não-vazio para todo
, logo é enumerável infinito.
Como há uma injeção
Passo 5
Por definição
Cada
é enumerável (Passo 4) e a união sobre
é união enumerável de conjuntos enumeráveis. Portanto
é enumerável.
Resposta
Para cada
,
é enumerável, e consequentemente o conjunto
dos subconjuntos finitos de
também é enumerável.