Prove o Princípio das Casas de Pombo: Se
, então, não existe uma função injetora
.
Passo 1
Beleza, vamos lá! O enunciado pede para provar o Princípio das Casas de Pombo, que é uma forma de dizer que se você tem mais pombos do que casas, não dá para colocar cada pombo em uma casa diferente sem que pelo menos duas fiquem na mesma casa. Aqui, estamos lidando com funções injetoras entre conjuntos com tamanhos diferentes. Para resolver isso, vamos precisar entender o que é uma função injetora e como os tamanhos dos conjuntos influenciam essa possibilidade.
Passo 2
Primeiro, vamos entender o que significa uma função injetora. Uma função
é chamada de injetora se, para cada elemento diferente de
, a imagem também é diferente em
. Em outras palavras, nenhum elemento de
recebe mais de um elemento de
.
Passo 3
Agora, vamos olhar para os conjuntos
e
. Aqui,
representa um conjunto com
elementos e
um com
elementos. O enunciado diz que
, ou seja, o conjunto
tem mais elementos do que
.
Passo 4
Suponhamos, para tentar chegar a uma contradição, que existe uma função injetora
. Se
, isso significa que temos mais elementos em
do que em
.
Passo 5
Como a função
é injetora, cada elemento de
teria que ser mapeado para um elemento único em
. Mas como
tem menos elementos que
, inevitavelmente alguns elementos de
teriam que ser mapeados para o mesmo elemento de
, o que viola a injetividade da função.
Passo 6
Essa contradição mostra que nossa suposição inicial de que existe uma função injetora
quando
está errada. Portanto, não existe tal função injetora.
Resposta
Assim, provamos que se
, não existe uma função injetora
.
Exercícios relacionados
Prove que todo conjunto finito não-vazio
de números naturais contém um elemento máximo (isto é, existe
tal que
).
Sejam
e
dois conjuntos.
Determine o número de sobrejeções possíveis de em
.
Determine o número de sobrejeções possíveis de
Dada
, prove:
Se for infinito e se
for injetora, então,
é infinito.
Se
Dada
, prove:
Se for infinito e se
for sobrejetora, então,
é infinito.
Se