Seja f:1,2, ldots, m 1,2, ldots, n uma função. Prove que:
Se f injetiva então m <= n.

Passo 1

Beleza, vamos lá! O problema fala sobre funções injetivas, que são aquelas onde cada elemento do conjunto de partida é mapeado para um elemento único no conjunto de chegada, sem repetições. Aqui, temos uma função que vai de para . O que precisamos provar é que, se essa função é injetiva, então o número de elementos no conjunto de partida não pode ser maior que o número de elementos no conjunto de chegada . Vamos resolver isso passo a passo!

Passo 2

Primeiro, vamos entender o que significa uma função ser injetiva. Uma função é injetiva se, para todo , sempre que , então . Isso quer dizer que não há dois elementos diferentes em que são mapeados para o mesmo elemento em .

Passo 3

Agora, vamos pensar em termos de contagem. Se é injetiva, cada elemento de é mapeado para um elemento distinto em . Ou seja, cada um dos elementos da primeira coleção precisa de um lugar único entre os elementos da segunda coleção.

Passo 4

Mas aqui está o ponto crucial: para que cada um dos elementos tenha um lugar único em posições, o número de posições disponíveis tem que ser pelo menos igual ao número de elementos . Se fosse maior que , não teríamos posições suficientes para todos os elementos sem repetir algum, o que violaria a injetividade da função.

Passo 5

Em outras palavras, se , não conseguiríamos atribuir um elemento distinto de para cada elemento de sem repetir algum, o que contraria a definição de função injetiva.

Resposta

Portanto, se é injetiva, então .

Exercícios relacionados