Prove o Princípio das Casas de Pombos (ou Princípio das Gavetas): Se m>n, então não existe uma função injetiva f: Im In, ou seja, quando m>n, para alojar m pombos em n casas é preciso que pelo menos uma casa abrigue mais de um pombo.

Passo 1

O enunciado pede para provar que, se temos m pombos e n casas com m>n, não existe uma função injetiva f: I_m→I_n. O conteúdo é o Princípio das Casas de Pombos, que usa argumentos de contagem de elementos.

Passo 2

Vamos lembrar que uma função f: A→B é injetiva quando, para pombos distintos x,y em A, as imagens f(x) e f(y) em B também são distintas. Além disso, o tamanho (cardinalidade) de um conjunto finito A é o número de seus elementos, que chamamos de |A|.

Passo 3

Façamos uma prova por contradição: suponha que exista uma função injetiva f: I_m→I_n com m>n. Como f é injetiva, todos os m elementos de I_m têm imagens distintas em I_n. Logo, o conjunto imagem f(I_m) tem exatamente m elementos, isto é,

Passo 4

[|f(I_m)| = m]

Passo 5

Por outro lado, f(I_m) é um subconjunto de I_n, então seu número de elementos não pode exceder o de I_n:

Passo 6

[|f(I_m)| \le |I_n| = n]

Passo 7

Daí tiramos que m = |f(I_m)| ≤ n, o que contradiz a hipótese m>n.

Passo 8

Assim, nossa suposição de existência de f injetiva leva a uma contradição, e portanto não pode haver função injetiva de I_m em I_n quando m>n.

Resposta

Não existe função injetiva f: I_m→I_n se m>n, pois qualquer injeção exigiria |f(I_m)|=m ≤n, contradizendo m>n.

Exercícios relacionados