Sejam
e
dois conjuntos finitos com
e
elementos, respectivamente. Se
, então não existe uma função injetora de
em
.
Passo 1
O enunciado dá duas informações claras:
e
são conjuntos finitos com, respectivamente,
e
elementos, e há a condição numérica
. A pergunta implícita é: “Existe uma função injetora
quando
?” Ou seja, precisamos decidir (e provar) se tal função injetora pode existir ou não.
Passo 2
Vamos lembrar com calma o que significa “injetora” e outras noções que usaremos, sem pressa:
- Uma função
é injetora se, sempre que , então . Equivalentemente, elementos distintos de têm imagens distintas em . - A imagem de
por é o conjunto . Por definição temos . - O número de elementos de um conjunto finito
chamamos de cardinalidade e escrevemos . Aqui e .
Essas definições já bastam; eu explico cada passo quando for usá-las.
Passo 3
Estratégia para provar: vamos usar prova por contradição — suponho que existe uma função injetora
e mostro que isso leva a uma contradição com
. Se a suposição leva a contradição, então não pode existir tal função.
Passo 4
Suponha que exista
injetora. Como disse antes, a imagem
é um subconjunto de
:
Além disso, por definição de imagem,
vista como função de
em
é sobrejetora (porque cada elemento de
tem pelo menos um antecessor em
), e como começamos com
injetora, essa mesma restrição é também injetora. Logo, a restrição de
a
é bijetora entre
e
.
Passo 5
Se existe bijeção entre
e
, então conjuntos finitos têm a mesma cardinalidade:
Aqui usei a propriedade básica: bijeção entre conjuntos finitos implica igualdade do número de elementos.
Passo 6
Como
e ambos são finitos, o número de elementos de
é menor ou igual ao número de elementos de
:
Substituindo o resultado do passo anterior, obtemos
Passo 7
Agora temos duas informações conflitantes: da hipótese do enunciado temos
, e da suposição de existência de uma injeção obtivemos
. Essas duas desigualdades não podem ser verdadeiras ao mesmo tempo. Portanto a suposição inicial (que existe uma função injetora
) é falsa. Concluímos que não existe função injetora de
em
quando
.
Passo 8
Interpretação intuitiva (princípio das gavetas/pombos): pense em cada elemento de
como um pombo e cada elemento de
como uma gaveta. Uma função injetora colocaria cada pombo numa gaveta distinta. Se há mais pombos (
) que gavetas (
), com
, sempre haverá pelo menos duas pombas na mesma gaveta — logo, não é possível colocar todos de forma injetora. Esse raciocínio dá a mesma conclusão de forma rápida e visual.
Resposta
A afirmação é verdadeira: não existe função injetora de
em
quando
.