Sejam
com
não-enumerável. Demonstre que se existir uma função sobrejetiva de
em
, então
é não-enumerável.
Passo 1
O enunciado (como dado) é: sejam
com
não-enumerável e exista uma função sobrejetiva de
em
. O que se pede: demonstrar que
é não-enumerável.
Observação importante (para evitar confusão): se realmente
então
seria enumerável (subconjunto de conjunto enumerável é enumerável), o que contradiz a hipótese de
não-enumerável. Vou então interpretar o enunciado da forma habitualmente usada neste tipo de exercício:
e
são conjuntos quaisquer (não repetir a hipótese impossível), com
não-enumerável, e existe uma função sobrejetiva
. Essas são as informações que vou usar.
Passo 2
Definições e resultados que usarei (explicados de forma clara).
- Definição de sobrejetiva: uma função
é sobrejetiva se, para todo , existe pelo menos um tal que . Em símbolos:
- Definição de enumerável (aqui uso a definição prática e comum): um conjunto
é enumerável (ou contável, no sentido “pelo menos enumerável”) se existe uma função sobrejetiva . Essa definição inclui conjuntos finitos e conjuntos equiparáveis a . - Composição preserva sobrejetividade: se
é sobrejetiva e é sobrejetiva então a composição é sobrejetiva. Vou provar isso explicitamente no próximo passo.
Passo 3
Prova por contradição (estrutura padrão e simples de aplicar em provas de conjunto).
Suponha, para chegar a uma contradição, que seja enumerável. Pela definição anterior, existe uma função sobrejetiva
Suponha, para chegar a uma contradição, que
Também, pelo enunciado, existe uma função sobrejetiva
Passo 4
Construção da composição e verificação de que ela é sobrejetiva (a peça chave).
Defina a composição por
para todo
.
Defina a composição
Mostro que
é sobrejetiva: tome qualquer elemento
. Como
é sobrejetiva, existe
tal que
. Como
é sobrejetiva, existe
tal que
. Então
Como o
escolhido era arbitrário em
, concluímos que para todo
existe
com
. Logo
é sobrejetiva.
Passo 5
Contradição e conclusão.
Ter sobrejetiva significa que
é enumerável (pela definição usada). Mas isso contradiz a hipótese de que
é não-enumerável. A única hipótese que assumimos e que pode ser falsa é a suposição de que
é enumerável. Portanto essa suposição é falsa, e concluímos que
é não-enumerável.
Ter
Comentário final rápido e amigável: a ideia prática é simples e muito usada em provas — se uma função surjetiva leva de
para
, então
não pode ser “maior” em cardinalidade do que
. Se
é não-enumerável,
também tem de ser não-enumerável; caso contrário, comporíamos uma enumeração de
com a sobrejeção e enumeraríamos
, o que dá contradição.