Seja
uma função sobrejetiva. Prove que se
é enumerável então
é enumerável.
Passo 1
Beleza, vamos lá! A questão diz que temos uma função
que é sobrejetiva, ou seja, todo elemento de
tem pelo menos um elemento em
que mapeia para ele. Queremos provar que se
é enumerável (ou seja, tem a mesma quantidade de elementos que os números naturais, podendo ser contado), então
também é enumerável. Vamos precisar usar conceitos de funções sobrejetivas e conjuntos enumeráveis para resolver isso.
Passo 2
Primeiro, lembrando o que é um conjunto enumerável: um conjunto
é enumerável se podemos listar seus elementos em uma sequência
. Como
é enumerável, vamos assumir que ela pode ser listada dessa forma.
Passo 3
Agora, considerando que
é sobrejetiva, para cada elemento
em
, existe pelo menos um elemento
em
tal que
. Ou seja, a função
“cobre” todo o conjunto
.
Passo 4
Como
é enumerável e
é uma função, podemos associar cada elemento de
com um número natural através de sua posição na lista
. Isso significa que podemos pensar em
como uma sequência de imagens:
.
Passo 5
Para provar que
é enumerável, precisamos mostrar que podemos listar seus elementos sem faltar nenhum. Como
é sobrejetiva, cada elemento de
aparece pelo menos uma vez na sequência
.
Passo 6
Podemos então criar uma nova lista para
escolhendo, para cada
em
, o menor índice
tal que
. Assim, garantimos que cada elemento de
aparece exatamente uma vez nessa nova lista.
Passo 7
Dessa forma, concluímos que há uma correspondência um a um entre os números naturais e os elementos de
, o que significa que
é enumerável.
Resposta
Portanto, se
é enumerável e
é uma função sobrejetiva, então
também é enumerável.