Prove que, se
é uma função sobrejetiva e
é enumerável, então
é também enumerável.
Dica: Seja
uma função sobrejetiva. Então, existe uma função
tal que
, onde
denota a função identidade de
em
. Em particular,
é injetiva. Depois use o corolário 1 do Teorema 4 do livro
Dica: Seja
Passo 1
O enunciado afirma que existe uma função sobrejetiva
e que
é enumerável (isto é, ou finito ou equipolente a
). Queremos mostrar que então
também é enumerável. Para isso usaremos o fato (Corolário 1 do Teorema 4) de que, se há uma injeção de um conjunto
em um conjunto enumerável
, então
também é enumerável.
Passo 2
Como
é sobrejetiva, podemos escolher para cada
algum
tal que
. Essa escolha define uma função
tal que
Tomando
e supondo
, aplicamos
dos dois lados e obtemos
Logo
é injetiva.
Passo 3
Agora temos uma função injetiva
e sabemos que
é enumerável. Pelo corolário citado, qualquer conjunto que injeta em um enumerável também é enumerável. Portanto
é enumerável.