Dado um conjunto finito , prove que uma função é injetiva se, e somente se, é sobrejetiva.
Passo 1
O enunciado pede para provar que, em um conjunto finito , qualquer função é 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 :
Suponha que seja injetiva. Então imagens de elementos distintos são todas distintas, o que implica
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.