Dado um conjunto finito X, prove que uma função f: X X é injetiva se, e somente se, é sobrejetiva.

Passo 1

O enunciado pede para provar que, em um conjunto finito X, qualquer função fcolon X to X é injetiva se, e somente se, é sobrejetiva. Vamos usar argumentos de cardinalidade e as definições de injeção e sobrejeção.

Passo 2

Prova de injeção implies sobrejeçãoçãçã:
Suponha que f seja injetiva. Então imagens de elementos distintos são todas distintas, o que implica
l|f(X)r| = lvert Xrvert
Mas sempre vale l|f(X)r|<= lvert Xrvert, pois f(X)subseteq X. Como há igualdade de tamanhos, necessariamente f(X)=X, ou seja, f é sobrejetiva.

Passo 3

Prova de sobrejeção implies injeçãoçãçã:
Suponha que f seja sobrejetiva, isto é f(X)=X. Então
l|f(X)r| = lvert Xrvert
Se f não fosse injetiva, existiriam xneq y com f(x)=f(y), o que forçaria l|f(X)r|<lvert Xrvert. Isso contradiz a igualdade anterior, portanto f deve ser injetiva.

Passo 4

Como mostramos ambas as implicações, concluímos que para qualquer conjunto finito X e função fcolon Xto X vale
f é injetivaLong<=ftrightarrow f é sobrejetiva éé

Resposta

Para todo conjunto finito X, uma função fcolon Xto X é injetiva se, e somente se, é sobrejetiva.

Exercícios relacionados