Sejam
e
dois conjuntos.
Determine o número de sobrejeções possíveis de
em
.
Determine o número de sobrejeções possíveis de
Passo 1
Ok, vamos lá! Temos dois conjuntos:
e
. A pergunta é: quantas funções sobrejetoras (ou seja, que cobrem todo o conjunto
) podemos formar de
para
? Vamos usar conceitos de combinatória para resolver isso.
Passo 2
Primeiro, vamos entender o que é uma função sobrejetora. Uma função
é sobrejetora se, para todo elemento
em
, existe pelo menos um elemento
em
tal que
. Ou seja, todo elemento de
precisa ser “atingido” pela função.
Passo 3
Agora, vamos contar quantas funções possíveis existem de
para
. Como
tem 2 elementos e
tem 3, cada elemento de
pode ser mapeado para qualquer dos 3 elementos de
. Portanto, o número total de funções é
.
Passo 4
Para que uma função seja sobrejetora, todos os elementos de
precisam ser mapeados por elementos de
. Porém, como
só tem 2 elementos e
tem 3, é impossível que todos os 3 elementos de
sejam alcançados por apenas 2 elementos de
.
Passo 5
Vamos confirmar isso: se mapeamos os dois elementos de
para
, no máximo cobrimos 2 dos 3 elementos de
. Sempre haverá pelo menos um elemento de
que não será atingido, tornando a função não sobrejetora.
Resposta
Não há funções sobrejetoras de
para
. O número de sobrejeções possíveis é 0.
Exercícios relacionados
Sejam
e
dois conjuntos.
Determine o número de injeções possíveis de em
.
Determine o número de injeções possíveis de
Suponha que
e
sejam conjuntos finitos tais que
,
,
e que
e
. Prove que
é finito e que
.
Prove que todo conjunto finito não-vazio
de números naturais contém um elemento máximo (isto é, existe
tal que
).
Prove o Princípio das Casas de Pombo: Se
, então, não existe uma função injetora
.