Questão 44 Suponha que
seja uma função, onde
é um conjunto nãoenumerável e
seja enumerável. Mostre que existe
tal que
seja um conjunto não-enumerável.
Passo 1
O que o enunciado dá e o que pede.
- Dado: uma função
. - Dado:
é um conjunto não-enumerável (ou seja, não é contável). - Dado:
é enumerável (ou seja, é finito ou contável infinito). - Definição útil que vem no enunciado (vou usá-la): para
, a pré-imagem é o conjunto . - Pedido: mostrar que existe
tal que seja não-enumerável.
Passo 2
Explicar e fixar claramente o significado de “enumerável” e uma propriedade-chave que usarei.
- Vou entender “enumerável” como sinônimo de “contável” (ou seja, finito ou equipotente a
). - Uma propriedade fundamental que vou usar e que preciso justificar é:
Isto é: se
é uma sequência de conjuntos, cada
contável, então
é contável.
Vou agora explicar por que essa propriedade é verdadeira (a prova é uma ferramenta padrão e muito útil em provas deste tipo).
Passo 3
Prova (intuitiva e construtiva) de que a união contável de conjuntos contáveis é contável.
- Como cada
é contável, existe uma enumeração (possivelmente finita) para cada um. Isto é, para todo podemos escrever uma lista (com possíveis repetições) , onde a lista pode ser finita (então só alguns existem) ou infinita. - Agora pense nas pares
com . Os pares são contáveis (há uma enumeração padrão dos pares, por exemplo pela enumeração diagonal de Cantor). Assim existe uma bijeção ou enumeração que percorre todos os pares. - Compose essa enumeração com as listagens dos elementos: para
escreva e considere o termo . Assim obtemos uma sequência que contém todos os elementos de , possivelmente com repetição. - Retirando repetições (ignorando já vistos quando aparecem de novo) obtemos uma enumeração sem repetições de
. Isso mostra que é, no máximo, contável. - Conclusão: a união contável de conjuntos contáveis é contável.
(Dica prática: na prova é suficiente referir esta propriedade e, se pedirem, esboçar a enumeração diagonal ou o argumento de composição acima.)
Passo 4
Argumento por contradição aplicado ao enunciado.
- Suponha, visando Contradição, que para todo
a pré-imagem seja enumerável (contável). - Como
é enumerável, existe uma enumeração (se for finito, a sequência termina, mas o argumento abaixo também vale). - Observe que todo elemento de
pertence à pré-imagem de algum elemento de ; em símbolos:
- Pela hipótese de contradição, cada conjunto
é contável. Logo é união contável de conjuntos contáveis, e pelo resultado do Passo 3 conclui-se que é contável (enumerável). - Isso contraria a hipótese do enunciado de que
é não-enumerável. - Portanto a suposição de que todas as pré-imagens
fossem contáveis é falsa.
Passo 5
Conclusão final e intuição.
- Conclui-se que existe pelo menos um
tal que não é enumerável. - Intuição: a função
“particiona” em fibras . Se todas essas fibras fossem pequenas (contáveis) e há apenas contavelmente muitas fibras, então a união seria contável — impossível porque é grande (não-contável). Logo alguma fibra tem que ser grande (não-contável).
Resposta
Existe
tal que
é não-enumerável.