Exercício 0.9 Quantas são as injeções de A=\{a, b\} em B=\{c, d, e, f\} ? E quantas são as sobrejeções de A=\{a, b, c\} em B=\{d, e\} ?

Passo 1

O enunciado faz duas perguntas distintas:
  1. Quantas são as injeções de A=\{a,b\} em B=\{c,d,e,f\} ?
  2. Quantas são as sobrejeções de A=\{a,b,c\} em B=\{d,e\} ?
Informações relevantes fornecidas pelo enunciado:
  • No primeiro item, o conjunto domínio tem |A|=2 elementos e o conjunto contradomínio tem |B|=4 elementos.
  • No segundo item, o conjunto domínio tem |A|=3 elementos e o conjunto contradomínio tem |B|=2 elementos.

Passo 2

Definição e ideia para contar injeções (essa é a parte teórica que vamos usar para o primeiro item).
  • Uma função f\colon A\to B é injetora (injeção) se elementos distintos de A vão para elementos distintos de B. Em outras palavras, não pode haver dois elementos diferentes de A que tenham a mesma imagem em B.
  • Para construir uma injeção de um conjunto de tamanho k para um conjunto de tamanho n (com n\ge k), a ideia prática é: para cada um dos k elementos do domínio escolhemos uma imagem em B, mas sem repetir imagens já escolhidas. Isso é o mesmo que contar arranjos de n elementos tomados k a k.
  • A fórmula geral para o número de injeções quando |A|=k e |B|=n é
\frac{n!}{(n-k)!},
que também se pode pensar como n\cdot(n-1)\cdot\ldots\cdot(n-k+1).
Explicação das notações na fórmula:
  • n! é o fatorial de n, ou seja, n!=n\cdot(n-1)\cdot\ldots\cdot1.
  • (n-k)! é o fatorial de n-k.
  • A razão \dfrac{n!}{(n-k)!} cancela os fatores de (n-k)! e deixa exatamente os k fatores decrescentes que representam as escolhas sem reposição.

Passo 3

Aplicando a ideia de injeção ao primeiro item.
  • Aqui k=|A|=2 e n=|B|=4.
  • Pelo método prático: escolhemos a imagem de a em B. Há 4 escolhas possíveis.
  • Depois escolhemos a imagem de b, que não pode ser igual à de a. Então há 3 escolhas restantes.
  • Multiplicando as escolhas sucessivas obtemos o número total de injeções:
4\cdot 3 = 12.
  • Pela fórmula de arranjos isso seria
\frac{4!}{(4-2)!}=\frac{4\cdot3\cdot2\cdot1}{2\cdot1}=4\cdot3=12.

Passo 4

Definição e ideia para contar sobrejeções (essa é a teoria usada no segundo item).
  • Uma função f\colon A\to B é sobrejetora (sobrejeção) se para todo elemento y\in B existe pelo menos um x\in A com f(x)=y. Ou seja, a imagem de f é todo o conjunto B.
  • Para contar sobrejeções de um conjunto de tamanho m para um conjunto de tamanho n (com m\ge n), existem fórmulas gerais usando números de Stirling ou inclusão-exclusão. Mas quando os conjuntos são pequenos é mais simples raciocinar diretamente.
  • Dois métodos simples que servem aqui:
    1. Contar todas as funções e subtrair as que não são sobrejetoras.
    2. Contar diretamente as distribuições dos elementos do domínio entre as pré-imagens dos elementos do contradomínio, exigindo que cada célula receba pelo menos um elemento.
Vou usar o método 1 por ser direto e prático neste caso.

Passo 5

Aplicando ao segundo item com o método de todas as funções menos as não-sobrejetoras.
  • O domínio tem |A|=3 elementos e o contradomínio tem |B|=2 elementos.
  • Número total de funções f\colon A\to B (sem nenhuma restrição) é 2^{3}, porque cada um dos 3 elementos do domínio tem 2 escolhas independentes de imagem. Logo
2^{3}=8.
  • Agora contamos quantas funções NÃO são sobrejetoras. Essas são exatamente as funções cuja imagem é um único elemento de B, isto é, as funções constantes. Há exatamente 2 funções constantes: a que envia todos os elementos de A para d e a que envia todos para e.
  • Portanto o número de funções sobrejetoras é
2^{3}-2 = 8-2 = 6.

Passo 6

Outra forma de ver (verificação rápida) pelo método das partições:
  • Para ser sobrejetora precisamos que a pré-imagem de d seja um subconjunto não vazio de A e a pré-imagem de e seja o complemento, também não vazio.
  • O número de subconjuntos não vazios e não totais de um conjunto de 3 elementos é
\binom{3}{1}+\binom{3}{2}=3+3=6,
que coincide com o resultado acima. Cada escolha do subconjunto que mapeia para d determina uma sobrejeção única (o resto vai para e).

Resposta

12
6

Exercícios relacionados