Sejam O e G dois conjuntos finitos com m e n elementos, respectivamente. Se m>n, então não existe uma função injetora de O em G.

Passo 1

O enunciado dá duas informações claras: O e G são conjuntos finitos com, respectivamente, m e n elementos, e há a condição numérica m>n. A pergunta implícita é: “Existe uma função injetora f:O\to G quando m>n?” 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 f:O\to G é injetora se, sempre que f(x)=f(y), então x=y. Equivalentemente, elementos distintos de O têm imagens distintas em G.
  • A imagem de O por f é o conjunto f(O)=\{f(x)\mid x\in O\}. Por definição temos f(O)\subseteq G.
  • O número de elementos de um conjunto finito A chamamos de cardinalidade e escrevemos |A|. Aqui |O|=m e |G|=n.
    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 f:O\to G e mostro que isso leva a uma contradição com m>n. Se a suposição leva a contradição, então não pode existir tal função.

Passo 4

Suponha que exista f:O\to G injetora. Como disse antes, a imagem f(O) é um subconjunto de G:
f(O)\subseteq G.
Além disso, por definição de imagem, f vista como função de O em f(O) é sobrejetora (porque cada elemento de f(O) tem pelo menos um antecessor em O), e como começamos com f injetora, essa mesma restrição é também injetora. Logo, a restrição de f a f(O) é bijetora entre O e f(O).

Passo 5

Se existe bijeção entre O e f(O), então conjuntos finitos têm a mesma cardinalidade:
|f(O)| = |O| = m.
Aqui usei a propriedade básica: bijeção entre conjuntos finitos implica igualdade do número de elementos.

Passo 6

Como f(O)\subseteq G e ambos são finitos, o número de elementos de f(O) é menor ou igual ao número de elementos de G:
|f(O)| \le |G| = n.
Substituindo o resultado do passo anterior, obtemos
m = |f(O)| \le n.

Passo 7

Agora temos duas informações conflitantes: da hipótese do enunciado temos m>n, e da suposição de existência de uma injeção obtivemos m\le n. Essas duas desigualdades não podem ser verdadeiras ao mesmo tempo. Portanto a suposição inicial (que existe uma função injetora f:O\to G) é falsa. Concluímos que não existe função injetora de O em G quando m>n.

Passo 8

Interpretação intuitiva (princípio das gavetas/pombos): pense em cada elemento de O como um pombo e cada elemento de G como uma gaveta. Uma função injetora colocaria cada pombo numa gaveta distinta. Se há mais pombos ( m) que gavetas ( n), com m>n, 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 O em G quando m>n.

Exercícios relacionados