Dado um conjunto finito A, prove que uma função f: A A é injetora se, e somente se, é sobrejetora (e, portanto, uma bijeção).

Passo 1

O enunciado pede para mostrar que, sendo A um conjunto finito, uma função fcolon Ato A é 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 lvert Arvert=n, então uma aplicação que envia n elementos em imagens todas distintas força a imagem a ter tamanho n, e vice-versa.

Passo 2

Seja lvert Arvert = n. Suponha que f seja injetora. Por definição de injeção, elementos distintos do domínio têm imagens distintas. Então os n elementos de A geram n valores diferentes em f(A). Logo
lvert f(A)rvert = n
Por outro lado, f(A)subseteq A e lvert Arvert = n. A única forma de um subconjunto de A ter mesma cardinalidade é ser igual a A. Portanto
f(A)=A,
o que significa que f é sobrejetora.

Passo 3

Agora suponha que f seja sobrejetora, isto é, f(A)=A. Se f não fosse injetora, existiriam xneq y em A tais que f(x)=f(y). Então o número de valores distintos atingidos por f seria no máximo n-1, pois duas entradas colapsam numa única imagem. Isso impediria f(A) de ter cardinalidade n e, consequentemente, de coincidir com A. Contradição com a sobrejeção. Logo f 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.

Exercícios relacionados