Seja
uma função injetiva. Prove que se
é enumerável então
é enumerável.
Passo 1
Primeiro, vamos entender o que o enunciado está pedindo. Temos uma função
que é injetiva, ou seja, cada elemento de
é mapeado para um único elemento em
sem repetições. Além disso, sabemos que o conjunto
é enumerável (ou contável), o que significa que podemos listar todos os seus elementos em uma sequência infinita ou que ele é finito. Nosso objetivo é provar que o conjunto
também é enumerável usando essas informações.
Passo 2
Vamos relembrar o que significa uma função ser injetiva. Uma função
é injetiva se, para quaisquer
, sempre que
, então necessariamente
. Isso garante que não há dois elementos diferentes em
que apontam para o mesmo elemento em
.
Passo 3
Como
é enumerável, podemos listar seus elementos de forma que
. Agora, como
é injetiva, cada elemento
corresponde a um elemento único em
. Isso significa que podemos associar cada
a um índice
tal que
.
Passo 4
Para provar que
é enumerável, precisamos mostrar que podemos listar todos os seus elementos em uma sequência
. Como
é injetiva e
está listado como
, podemos definir
como o elemento de
que é mapeado para
por
, ou seja,
.
Passo 5
Isso funciona porque, sendo
injetiva, cada
em
tem no máximo um elemento correspondente
em
. Assim, cada elemento de
pode ser colocado em uma posição específica na sequência baseada na posição de sua imagem em
.
Resposta
Portanto, conseguimos listar todos os elementos de
em uma sequência, demonstrando que
é enumerável.