Dada
, prove:
Se
for infinito e se
for injetora, então,
é infinito.
Se
Passo 1
Então, a gente tem uma função
e precisa provar que se o conjunto
é infinito e a função
é injetora (ou seja, não repete elementos), então o conjunto
também tem que ser infinito. Vamos usar conceitos de teoria dos conjuntos e funções injetoras para resolver isso.
Passo 2
Primeiro, vamos lembrar o que significa a função ser injetora. Uma função
é injetora se, para todo
, se
então
. Isso significa que cada elemento de
é mapeado para um elemento único em
.
Passo 3
Agora, como
é infinito, vamos considerar que não há um número finito de elementos em
. Se
é injetora, cada um desses elementos infinitos de
tem que ser mapeado para um elemento distinto em
.
Passo 4
Se
fosse finito, digamos que tem
elementos, então só poderíamos mapear no máximo
elementos de
para
sem repetir, o que contraria o fato de
ser infinito e
ser injetora. Isso não é possível porque estamos tentando mapear infinitos elementos para um conjunto finito de formas únicas.
Passo 5
Portanto, para que cada elemento de
tenha um destino único em
sem repetições,
também precisa ter infinitos elementos. Caso contrário, não daria para manter a injetividade.
Resposta
Assim, provamos que se
é infinito e
é injetora, então
deve ser infinito.
Exercícios relacionados
Prove o Princípio das Casas de Pombo: Se
, então, não existe uma função injetora
.
Prove que todo conjunto finito não-vazio
de números naturais contém um elemento máximo (isto é, existe
tal que
).
Dada
, prove:
Se for infinito e se
for sobrejetora, então,
é infinito.
Se
Sejam
um conjunto finito e
um conjunto infinito. Prove que:
Existe uma função injetora .
Existe uma função injetora