Dada
, prove:
(a) Se
é infinito e
é injetiva então
é infinito.
(b) Se
é infinito e
é sobrejetiva, então
é infinito.
(a) Se
(b) Se
Passo 1
O enunciado dá uma função
e pede para provar duas afirmações sobre infinitude de conjuntos usando injeção e sobrejeção. O conteúdo é teoria de cardinalidade: definição de conjunto finito/infinito, imagens, injeções e sobrejeções, e o fato de que todo subconjunto de um conjunto finito é finito.
Passo 2
Recordamos que um conjunto
é finito se existe bijeção entre
e
para algum
. Além disso, todo subconjunto de um conjunto finito é finito. Por fim, se há bijeção entre
e
, então
e
têm a mesma natureza (finito ou infinito).
Passo 3
Prova de (a) por contrapositive. Suponha, em sentido contrário, que
seja finito. Então
é um subconjunto de um conjunto finito, logo
é finito. Como
é injetiva, temos bijeção entre
e
; portanto
também seria finito. Isso contradiz a hipótese de
infinito.
Conclui-se que a suposição “ finito” é falsa, isto é,
deve ser infinito. Assim está provado (a).
Conclui-se que a suposição “
Passo 4
Prova de (b) por contrapositive. Suponha agora que
seja finito. Como
é sobrejetiva,
. Logo
é imagem de um conjunto finito, e portanto
é finito (subconjunto de
ou igual a ele). Isso contradiz a hipótese de
infinito.
Conclui-se que a suposição “ finito” é falsa, isto é,
deve ser infinito. Assim está provado (b).
Conclui-se que a suposição “
Resposta
As afirmações (a) e (b) seguem desses argumentos por contraproposição.