Exercício 11. Sejam
um conjunto finito e
uma função. Mostre que:
(a) Se
injetora, então também é sobrejetora.
(b) Se
sobrejetora, então também é injetora.
(c) Os itens anteriores, em geral, são verdadeiros se
é um conjunto infinito
(a) Se
(b) Se
(c) Os itens anteriores, em geral, são verdadeiros se
Passo 1
O enunciado pede para
finito e
mostrar que
( ) se
é injetora então é sobrejetora,
( ) se
é sobrejetora então é injetora,
e em ( ) observar que para
infinito essas implicações, em geral, falham.
Aqui usamos noções de injeção, sobrejeção e cardinalidade de conjuntos finitos: se é injetora, então
, e como
, decorre
. O caso sobrejetor
injetor é análogo.
(
(
e em (
Aqui usamos noções de injeção, sobrejeção e cardinalidade de conjuntos finitos: se
Passo 2
Prova de (a): suponha
injetora. Então a imagem
tem
. Por outro lado,
implica
. Da igualdade de cardinalidades concluímos
, logo
é sobrejetora.
Passo 3
Prova de (b): suponha
sobrejetora. Então
e
. Como
é de
em
, domínio e contradomínio têm mesma cardinalidade finita; a existência de colisões (ou seja,
com
) reduziria
para menos que
, contradizendo a sobrejeção. Logo não há colisões, isto é,
é injetora.
Passo 4
Contraexemplos para
infinito:
– Considere dada por
.
Esta é injetora, mas não atinge
, logo não é sobrejetora.
– Considere dada por
– Considere
Esta
– Considere
Então
é sobrejetora (todo
tem pré-imagem
), mas não é injetora pois
.
Resposta
(a) Se
é injetora em conjunto finito
, então
e
implicam
, logo
é sobrejetora.
(b) Se é sobrejetora em conjunto finito
, então
e a ausência de colisões é necessária, logo
é injetora.
(c) Para infinito as implicações falham em geral: por exemplo,
em
é injetora não sobrejetora, e
acima é sobrejetora não injetora.
(b) Se
(c) Para