Mostre que se
for uma função de
para
, em que
e
são conjuntos finitos com
, então há elementos
e
em
, tal que
, ou, em outras palavras,
não é injetora.
Passo 1
O enunciado afirma que existe uma função
entre conjuntos finitos tais que
. O objetivo é mostrar que
não pode ser injetora, ou seja, mostrar que existem
com
e
. O conteúdo teórico usado é o princípio da casa dos pombos aplicado a cardinalidades de imagens de funções.
Passo 2
Suponha, por absurdo, que
seja injetora. Então elementos distintos de
têm imagens distintas em
. Em particular, o tamanho da imagem de
, definido por
satisfaz
pois cada um dos
elementos de
gera uma imagem diferente.
Passo 3
Por outro lado, como
, segue-se que
Combinando as duas desigualdades temos
o que contradiz a hipótese
.
Passo 4
Da contradição obtida, conclui-se que a suposição de que
é injetora está errada. Logo,
não é injetora, isto é, necessariamente existem pelo menos dois elementos distintos
tais que
Resposta
Existem
em
tais que
, logo
não é injetora.