Seja
uma função.
Se
é sobrejetiva e
é enumerável, então
é enumerável? Justifique.
Se
Passo 1
O enunciado diz que temos uma função
sobrejetiva (isto é, para todo
existe pelo menos um
com
) e que
é enumerável (ou seja, finito ou com mesma cardinalidade de
). Pergunta-se se isso obriga
a ser enumerável.
Passo 2
Lembre que uma função sobrejetiva
implica, em termos de cardinalidade, que
. Isto é,
tem “tamanho” pelo menos tão grande quanto
. Se
é enumerável então
, mas isso não impede
de ser estritamente maior (por exemplo, não enumerável).
Passo 3
Basta um contraexemplo clássico. Tome
e defina
de modo que para cada
haja algum real que seja enviado em
(por exemplo, faça
restringido a um conjunto apropriado ou use escolha para construir uma sobrejeção). Então
é enumerável,
é sobrejetiva, mas
não é enumerável.
Passo 4
Concluímos que a existência de uma sobrejeção de
sobre um conjunto enumerável
não obriga
a ser enumerável. O que essa sobrejeção garante é apenas
, e um conjunto pode ter cardinalidade maior que a de
.
Resposta
Não. Uma sobrejeção
com
enumerável só garante
, mas pode ocorrer
. Por exemplo,
não enumerável sobrejetando em
.