Seja g: A B uma função sobrejetiva. Prove que se A é enumerável então B é 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.

Exercícios relacionados