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 .
Dada , prove:
Se for infinito e se for injetora, então, é infinito.
Dada , prove:
Se for infinito e se for sobrejetora, então, é infinito.