Mostre que um conjunto
é infinito se, e somente se, existir uma função injetiva
que não é sobrejetiva.
Passo 1
O enunciado pede para mostrar a equivalência entre “
é infinito” e “existe
injetiva que não é sobrejetiva”. Vamos usar a definição de conjunto finito:
é finito se existe bijeção entre
e
para algum
; em caso contrário,
é infinito. Também usamos que, em conjuntos finitos, toda função injetiva é sobrejetiva.
Passo 2
Prova de “se existe
injetiva não sobrejetiva então
é infinito”.
Suponha, por absurdo, que seja finito e exista
injetiva. Num conjunto finito, toda injeção é bijeção, logo
seria também sobrejetiva, contradizendo a hipótese de que
não é sobrejetiva. Portanto, se existe
injetiva não sobrejetiva, não pode ser
finito, isto é,
é infinito.
Suponha, por absurdo, que
Passo 3
Prova de “se
- Injetividade: se
para algum
, forçando , ou ambos estão fora do conjunto , caso em que age como identidade e também dá . Casos mistos não ocorrem porque a imagem de cada é um para todo . - Não sobrejetividade: o elemento
não é imagem de ninguém, pois se então teríamos , o que não faz sentido.
Assim,
é injetiva e não atinge
, logo não é sobrejetiva.
Passo 4
Juntando as duas direções, mostramos que
não ser finito (isto é, ser infinito) equivale a existir
injetiva mas não sobrejetiva.
Resposta
Mostramos que
é infinito se, e somente se, existe uma função
que é injetiva e não é sobrejetiva.