Seja
um conjunto. O conjunto de todos os subconjuntos de
, i.e.,
é chamado de conjunto das partes de
.
Prove que se
é infinito, não existe nenhuma função sobrejetiva
.
Sugestão: Considere o conjunto
Suponha que
é sobrejetiva e seja
tal que
. Verifique que
-
-
.
Daí concluimos que a suposição estava errada e portanto não pode existir nenhuma
sobrejetiva.
Prove que se
Sugestão: Considere o conjunto
Daí concluimos que a suposição estava errada e portanto não pode existir nenhuma
Passo 1
Beleza, vamos lá! O enunciado pede para provar que, se
é um conjunto infinito, não existe nenhuma função sobrejetiva
. Aqui,
é o conjunto das partes de
, ou seja, todos os subconjuntos de
. Para resolver isso, vamos usar o conceito de função sobrejetiva e um argumento clássico chamado “diagonalização”.
Passo 2
Primeiro, vamos lembrar o que é uma função sobrejetiva. Uma função
é sobrejetiva se, para todo elemento
em
, existe pelo menos um elemento
em
tal que
. Ou seja, a função cobre todo o conjunto
.
Passo 3
Agora, vamos supor, para chegar a uma contradição, que existe uma função sobrejetiva
. Isso significa que para todo subconjunto
de
, existe pelo menos um elemento
em
tal que
.
Passo 4
Vamos considerar o conjunto
definido como:
Esse conjunto
é um subconjunto de
, então, pela nossa suposição de que
é sobrejetiva, deve existir algum elemento
em
tal que
.
Passo 5
Agora, vamos analisar se
está ou não em
:
- Se
: Pela definição de , isso significa que não está em . Mas como , temos que . Contradição! - Se
: Então, pela definição de , isso significa que está em . Como , temos que . Outra contradição!
Passo 6
Em ambos os casos, chegamos a uma contradição. Isso significa que nossa suposição inicial de que existe uma função sobrejetiva
está errada.
Resposta
Portanto, se
é um conjunto infinito, não existe nenhuma função sobrejetiva
.