Dado um conjunto finito
, prove que uma função
é injetora se, e somente se, é sobrejetora (e, portanto, uma bijeção).
Passo 1
O enunciado pede para mostrar que, sendo
um conjunto finito, uma função
é injetora exatamente quando é sobrejetora.
Conteúdo: teoria de relações entre injeção, sobrejeção e cardinalidade de conjuntos finitos. Vamos precisar usar que, se , então uma aplicação que envia
elementos em imagens todas distintas força a imagem a ter tamanho
, e vice-versa.
Conteúdo: teoria de relações entre injeção, sobrejeção e cardinalidade de conjuntos finitos. Vamos precisar usar que, se
Passo 2
Seja
. Suponha que
seja injetora. Por definição de injeção, elementos distintos do domínio têm imagens distintas. Então os
elementos de
geram
valores diferentes em
. Logo
Por outro lado,
e
. A única forma de um subconjunto de
ter mesma cardinalidade é ser igual a
. Portanto
o que significa que
é sobrejetora.
Passo 3
Agora suponha que
seja sobrejetora, isto é,
. Se
não fosse injetora, existiriam
em
tais que
. Então o número de valores distintos atingidos por
seria no máximo
, pois duas entradas colapsam numa única imagem. Isso impediria
de ter cardinalidade
e, consequentemente, de coincidir com
. Contradição com a sobrejeção. Logo
deve ser injetora.
Resposta
Dessa forma, numa aplicação de um conjunto finito em si mesmo, injeção e sobrejeção são equivalentes, e ambas implicam bijeção.