Exercício 11. Sejam A um conjunto finito e f: A A uma função. Mostre que:
(a) Se f injetora, então também é sobrejetora.
(b) Se f sobrejetora, então também é injetora.
(c) Os itens anteriores, em geral, são verdadeiros se A é um conjunto infinito

Passo 1

O enunciado pede para A finito e fcolon Ato A mostrar que
( 1) se f é injetora então é sobrejetora,
( 2) se f é sobrejetora então é injetora,
e em ( 3) observar que para A infinito essas implicações, em geral, falham.
Aqui usamos noções de injeção, sobrejeção e cardinalidade de conjuntos finitos: se f é injetora, então lvert f(A)rvert=lvert Arvert, e como f(A)subseteq A, decorre f(A)=A. O caso sobrejetor toinjetor é análogo.

Passo 2

Prova de (a): suponha f injetora. Então a imagem f(A) tem lvert f(A)rvert=lvert Arvert. Por outro lado, f(A)subseteq A implica lvert f(A)rvert<=lvert Arvert. Da igualdade de cardinalidades concluímos f(A)=A, logo f é sobrejetora.

Passo 3

Prova de (b): suponha f sobrejetora. Então f(A)=A e lvert f(A)rvert=lvert Arvert. Como f é de A em A, domínio e contradomínio têm mesma cardinalidade finita; a existência de colisões (ou seja, f(a)=f(a') com ane a') reduziria lvert f(A)rvert para menos que lvert Arvert, contradizendo a sobrejeção. Logo não há colisões, isto é, f é injetora.

Passo 4

Contraexemplos para A infinito:
– Considere fcolonNtoN dada por
,f(n)=n+1.
Esta f é injetora, mas não atinge 1, logo não é sobrejetora.
– Considere gcolonNtoN dada por
g(1)=1, g(n)=n-1 para n>1
Então g é sobrejetora (todo m tem pré-imagem m+1), mas não é injetora pois g(1)=g(2).

Resposta

(a) Se f é injetora em conjunto finito A, então lvert f(A)rvert=lvert Arvert e f(A)subseteq A implicam f(A)=A, logo f é sobrejetora.
(b) Se f é sobrejetora em conjunto finito A, então lvert f(A)rvert=lvert Arvert e a ausência de colisões é necessária, logo f é injetora.
(c) Para A infinito as implicações falham em geral: por exemplo, f(n)=n+1 em N é injetora não sobrejetora, e g acima é sobrejetora não injetora.

Exercícios relacionados