- (Q1-ITA/2017) Sejam X e Y dois conjuntos finitos com
e
. Considere as seguintes afirmações:
I. Existe uma bijeção
.
II. Existe uma função injetora
.
III.O número de funções injetoras
é igual ao número de funções sobrejetoras
.
I. Existe uma bijeção
II. Existe uma função injetora
III.O número de funções injetoras
Passo 1
O enunciado dá duas partes: conjuntos finitos
e
tais que
e
. Vou anotar o que isso implica em termos de tamanhos:
- Seja
e . Como e não são iguais, temos (ambos inteiros não negativos, mas com ).
As perguntas do enunciado são avaliar a veracidade das três afirmações:
I. Existe uma bijeção.
II. Existe uma função injetora.
III. O número de funções injetorasé igual ao número de funções sobrejetoras .
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 injetarpombos em caixas com 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
.”
- Uma bijeção entre
e exigiria . - Mas do enunciado temos
. - Logo não pode existir bijeção
.
Conclusão: a afirmação I é falsa.
Passo 4
Avaliação da afirmação II: “Existe uma função injetora
.”
- Uma injeção
exigiria . - Mas temos
. - 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
é igual ao número de funções sobrejetoras
.”
Vou contar cada tipo explicitamente e depois mostrar que, em geral, não são iguais.
Vou contar cada tipo explicitamente e depois mostrar que, em geral, não são iguais.
Contagem de funções injetoras
quando
e
com
:
- Para definir uma injeção, escolhe-se uma imagem distinta em
para cada um dos elementos de . - O número é o fatorial decrescente (produto em cascata):
Contagem de funções sobrejetoras
:
- O número de funções sobrejetoras de um conjunto de tamanho
para um conjunto de tamanho é dado por
onde
é o número de Stirling de segunda espécie (número de maneiras de particionar um conjunto de
elementos em
blocos não vazios). Essa fórmula vem de: primeiro particionar os
elementos em
classes não vazias (há
maneiras), depois rotular as
classes com os
elementos de
(fator
).
Agora um contraexemplo simples mostra que essas quantidades nem sempre são iguais. Tome
e
(isso respeita
,
):
- Número de injeções
: . - Número de sobrejeções
: há exatamente uma função que manda os dois elementos de para o único elemento de , então o número é .
Como, as quantidades diferem neste caso específico.
Portanto a igualdade da afirmação III não vale em geral (pode ocorrer para alguns paresespeciais, 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
impede bijeção). - II: falsa (não se pode injetar conjunto maior em conjunto menor).
- III: falsa (contagens em geral diferentes; contraexemplo
dá injeções vs sobrejeção).
Resposta
I. Falsa
II. Falsa
III. Falsa
II. Falsa
III. Falsa