Seja X um conjunto. O conjunto de todos os subconjuntos de X, i.e.,
P(X)=A mid A subset X
é chamado de conjunto das partes de X.
Prove que se X é infinito, não existe nenhuma função sobrejetiva f: X P(X).
Sugestão: Considere o conjunto
A=x in X mid x notin f(x)
Suponha que f é sobrejetiva e seja z in X tal que f(z)=A. Verifique que
  • z in A Rightarrow z notin A, e
  • z notin A Rightarrow z in A.
    Daí concluimos que a suposição estava errada e portanto não pode existir nenhuma f sobrejetiva.

Passo 1

Beleza, vamos lá! O enunciado pede para provar que, se X é um conjunto infinito, não existe nenhuma função sobrejetiva f: X P(X) . Aqui, P(X) é o conjunto das partes de X , ou seja, todos os subconjuntos de X . 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 f: X Y é sobrejetiva se, para todo elemento y em Y , existe pelo menos um elemento x em X tal que f(x) = y . Ou seja, a função cobre todo o conjunto Y .

Passo 3

Agora, vamos supor, para chegar a uma contradição, que existe uma função sobrejetiva f: X P(X) . Isso significa que para todo subconjunto A de X , existe pelo menos um elemento x em X tal que f(x) = A .

Passo 4

Vamos considerar o conjunto A definido como:
A = x in X mid x notin f(x)
Esse conjunto A é um subconjunto de X , então, pela nossa suposição de que f é sobrejetiva, deve existir algum elemento z em X tal que f(z) = A .

Passo 5

Agora, vamos analisar se z está ou não em A :
  • Se z in A : Pela definição de A , isso significa que z não está em f(z) . Mas como f(z) = A , temos que z notin A . Contradição!
  • Se z notin A : Então, pela definição de A , isso significa que z está em f(z) . Como f(z) = A , temos que z in A . 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 f: X P(X) está errada.

Resposta

Portanto, se X é um conjunto infinito, não existe nenhuma função sobrejetiva f: X P(X) .

Exercícios relacionados