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

Exercícios relacionados