Prove o Princípio das Casas de Pombos (ou Princípio das Gavetas): Se
, então não existe uma função injetiva
, ou seja, quando
, para alojar
pombos em
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.