Seja f: X Y uma função.
Se f é sobrejetiva e Y é enumerável, então X é enumerável? Justifique.

Passo 1

O enunciado diz que temos uma função fcolon Xto Y sobrejetiva (isto é, para todo yin Y existe pelo menos um xin X com f(x)=y) e que Y é enumerável (ou seja, finito ou com mesma cardinalidade de N). Pergunta-se se isso obriga X a ser enumerável.

Passo 2

Lembre que uma função sobrejetiva fcolon Xto Y implica, em termos de cardinalidade, que lvert Yrvert<=lvert Xrvert. Isto é, X tem “tamanho” pelo menos tão grande quanto Y. Se lvert Yrvert é enumerável então lvert Xrvert>=a<=ph0, mas isso não impede lvert Xrvert de ser estritamente maior (por exemplo, não enumerável).

Passo 3

Basta um contraexemplo clássico. Tome
X=R, Y=N,
e defina fcolonRtoN de modo que para cada ninN haja algum real que seja enviado em n (por exemplo, faça f(x)=lfloor xrfloor restringido a um conjunto apropriado ou use escolha para construir uma sobrejeção). Então Y é enumerável, f é sobrejetiva, mas R não é enumerável.

Passo 4

Concluímos que a existência de uma sobrejeção de X sobre um conjunto enumerável Y não obriga X a ser enumerável. O que essa sobrejeção garante é apenas lvert Xrvert>=lvert Yrvert, e um conjunto pode ter cardinalidade maior que a de N.

Resposta

Não. Uma sobrejeção fcolon Xto Y com Y enumerável só garante lvert Xrvert>=a<=ph0, mas pode ocorrer lvert Xrvert>a<=ph0. Por exemplo, R não enumerável sobrejetando em N.

Exercícios relacionados