Mostre que se f for uma função de S para T, em que S e T são conjuntos finitos com |S|>|T|, então há elementos s_{1} e s_{2} em S, tal que f\left(s_{1}\right)=f\left(s_{2}\right), ou, em outras palavras, f não é injetora.

Passo 1

O enunciado afirma que existe uma função f\colon S\to T entre conjuntos finitos tais que \lvert S\rvert>\lvert T\rvert. O objetivo é mostrar que f não pode ser injetora, ou seja, mostrar que existem s_{1},s_{2}\in S com s_{1}\neq s_{2} e f(s_{1})=f(s_{2}). 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 f seja injetora. Então elementos distintos de S têm imagens distintas em T. Em particular, o tamanho da imagem de f, definido por
f(S)=\{\,f(s)\mid s\in S\},
satisfaz
\lvert f(S)\rvert = \lvert S\rvert,
pois cada um dos \lvert S\rvert elementos de S gera uma imagem diferente.

Passo 3

Por outro lado, como f(S)\subseteq T, segue-se que
\lvert f(S)\rvert \le \lvert T\rvert.
Combinando as duas desigualdades temos
\lvert S\rvert = \lvert f(S)\rvert \le \lvert T\rvert,
o que contradiz a hipótese \lvert S\rvert>\lvert T\rvert.

Passo 4

Da contradição obtida, conclui-se que a suposição de que f é injetora está errada. Logo, f não é injetora, isto é, necessariamente existem pelo menos dois elementos distintos s_{1},s_{2}\in S tais que
f(s_{1}) = f(s_{2}).

Resposta

Existem s_{1}\neq s_{2} em S tais que f(s_{1})=f(s_{2}), logo f não é injetora.

Exercícios relacionados