1. (Q1-ITA/2017) Sejam X e Y dois conjuntos finitos com X \subset Y e X \neq Y. Considere as seguintes afirmações:
    I. Existe uma bijeção \mathrm{f}: \mathrm{X} \rightarrow \mathrm{Y}.
    II. Existe uma função injetora \mathrm{g}: \mathrm{Y} \rightarrow \mathrm{X}.
    III.O número de funções injetoras f: X \rightarrow Y é igual ao número de funções sobrejetoras \mathrm{g}: \mathrm{Y} \rightarrow \mathrm{X}.

Passo 1

O enunciado dá duas partes: conjuntos finitos X e Y tais que X \subset Y e X \neq Y. Vou anotar o que isso implica em termos de tamanhos:
  • Seja |X|=n e |Y|=m. Como X\subset Y e não são iguais, temos m>n (ambos inteiros não negativos, mas com m>n).
    As perguntas do enunciado são avaliar a veracidade das três afirmações:
    I. Existe uma bijeção f: X \to Y.
    II. Existe uma função injetora g: Y \to X.
    III. O número de funções injetoras f: X \to Y é igual ao número de funções sobrejetoras g: Y \to X.

Passo 2

Definições e fato básico sobre conjuntos finitos (explicado devagar e com intuição):
  • Uma função é bijetora se for injetora e sobrejetora ao mesmo tempo; isso exige que domínio e contradomínio tenham o mesmo número de elementos.
  • Uma função é injetora (injeção) quando elementos distintos do domínio têm imagens distintas — para conjuntos finitos isso só é possível se o tamanho do domínio for menor ou igual ao do contradomínio.
    Intuição (princípio das caixas/pombos): não dá para injetar m pombos em n caixas com m>n sem colocar pelo menos duas pombas na mesma caixa.
  • Uma função é sobrejetora (sobrecção) quando toda elemento do contradomínio é imagem de algo do domínio — para conjuntos finitos isso exige que o tamanho do contradomínio seja menor ou igual ao do domínio.
Esses fatos seguem diretamente das definições e do princípio da casa dos pombos (pigeonhole principle) para conjuntos finitos.

Passo 3

Avaliação da afirmação I: “Existe uma bijeção f: X \to Y.”
  • Uma bijeção entre X e Y exigiria |X|=|Y|.
  • Mas do enunciado temos |Y|=m>|X|=n.
  • Logo não pode existir bijeção f:X\to Y.
    Conclusão: a afirmação I é falsa.

Passo 4

Avaliação da afirmação II: “Existe uma função injetora g: Y \to X.”
  • Uma injeção g:Y\to X exigiria |Y|\le |X|.
  • Mas temos |Y|=m>|X|=n.
  • Pelo princípio das caixas, não é possível mapear injectivamente um conjunto maior para um menor.
    Conclusão: a afirmação II é falsa.

Passo 5

Avaliação da afirmação III: “O número de funções injetoras f: X \to Y é igual ao número de funções sobrejetoras g: Y \to X.”
Vou contar cada tipo explicitamente e depois mostrar que, em geral, não são iguais.
Contagem de funções injetoras f:X\to Y quando |X|=n e |Y|=m com m\ge n:
  • Para definir uma injeção, escolhe-se uma imagem distinta em Y para cada um dos n elementos de X.
  • O número é o fatorial decrescente (produto em cascata):
m\cdot (m-1)\cdot (m-2)\cdots (m-n+1)=\frac{m!}{(m-n)!}.
Contagem de funções sobrejetoras g:Y\to X:
  • O número de funções sobrejetoras de um conjunto de tamanho m para um conjunto de tamanho n é dado por
n!\,S(m,n),
onde S(m,n) é o número de Stirling de segunda espécie (número de maneiras de particionar um conjunto de m elementos em n blocos não vazios). Essa fórmula vem de: primeiro particionar os m elementos em n classes não vazias (há S(m,n) maneiras), depois rotular as n classes com os n elementos de X (fator n!).
Agora um contraexemplo simples mostra que essas quantidades nem sempre são iguais. Tome |X|=n=1 e |Y|=m=2 (isso respeita X\subset Y, m>n):
  • Número de injeções f:X\to Y: \dfrac{m!}{(m-n)!}=\dfrac{2!}{(2-1)!}=2.
  • Número de sobrejeções g:Y\to X: há exatamente uma função g que manda os dois elementos de Y para o único elemento de X, então o número é 1.
    Como 2\neq 1, as quantidades diferem neste caso específico.
    Portanto a igualdade da afirmação III não vale em geral (pode ocorrer para alguns pares (m,n) especiais, mas não para todos).
Conclusão: a afirmação III é falsa em geral (existe contraexemplo).

Passo 6

Resumo final das verificações:
  • I: falsa (porque m>n impede bijeção).
  • II: falsa (não se pode injetar conjunto maior em conjunto menor).
  • III: falsa (contagens em geral diferentes; contraexemplo |X|=1,|Y|=2 2 injeções vs 1 sobrejeção).

Resposta

I. Falsa
II. Falsa
III. Falsa

Exercícios relacionados