Questão 40 Seja X um conjunto qualquer.
a) Exiba uma função injetora entre X e \boldsymbol{\mathcal { P }}(X).
b) Mostre que não existe uma função sobrejetora f: X \rightarrow \mathcal{P}(X). (Teorema de Cantor).

Passo 1

O enunciado dá um conjunto qualquer X (sem hipótese extra: pode ser vazio, finito ou infinito) e pede duas coisas:
  • (a) Exibir uma função injetora de X em \mathcal{P}(X).
  • (b) Mostrar que não existe nenhuma função sobrejetora f: X \to \mathcal{P}(X) — isto é o Teorema de Cantor.
Informações úteis que vamos usar (definições e notação):
  • \mathcal{P}(X) é o conjunto de todas as partes (subconjuntos) de X.
  • Uma função f:A\to B é injetora se, para quaisquer u,v\in A, f(u)=f(v)\Rightarrow u=v.
  • Uma função f:A\to B é sobrejetora se, para todo b\in B, existe a\in A tal que f(a)=b.
Não vamos resolver nada ainda, só organizei o que é pedido e as ferramentas que usaremos.

Passo 2

Primeira tarefa: construir uma função injetora f:X\to\mathcal{P}(X).
Ideia simples e natural (muito usada): associar a cada elemento x\in X o subconjunto formado só por x, isto é, a singleton (conjunto unitário) \{x\}. Definimos:
f:X\longrightarrow\mathcal{P}(X),\qquad f(x)=\{x\}.
Antes de provar injetividade, veja um exemplo concreto para fixar a ideia: se X=\{1,2,3\} então
f(1)=\{1\},\quad f(2)=\{2\},\quad f(3)=\{3\},
cada imagem é um subconjunto de X, então f realmente tem imagem em \mathcal{P}(X).

Passo 3

Provar que f(x)=\{x\} é injetora.
Tomemos x,y\in X e suponha f(x)=f(y). Isso significa \{x\}=\{y\}. Dois conjuntos unitários são iguais somente se o elemento que eles contêm é o mesmo; portanto x=y. Assim, por definição de injetividade,
f(x)=f(y)\Rightarrow x=y,
logo f é injetora.
Comentário didático: a razão é simples — conjuntos unitários distinguem seus elementos. Esse é um truque padrão para embutir X em \mathcal{P}(X). Observe que a construção funciona mesmo se X for vazio: nesse caso não há x\in X e a função vazia f:\varnothing\to\mathcal{P}(\varnothing) (nenhum par imagem-antecedente) é vacuamente injetora.

Passo 4

Agora a segunda tarefa: provar que não existe função sobrejetora f:X\to\mathcal{P}(X).
Vamos provar por contradição, usando o argumento clássico de Cantor (diagonalização em linguagem de conjuntos). Suponha, para contradizer, que exista uma função sobrejetora qualquer
f:X\longrightarrow\mathcal{P}(X).
Como f é sobrejetora, todo subconjunto de X aparece como imagem de algum ponto de X.

Passo 5

Defina o subconjunto especial A\subseteq X por
A=\{x\in X \mid x\notin f(x)\}.
Ou seja, A é o conjunto de todos os elementos de X que não pertencem ao seu próprio subconjunto imagem f(x). Note que A é um subconjunto de X, então A\in\mathcal{P}(X).
Raciocínio sobre a definição: esta é a etapa “diagonal” — construímos um subconjunto que discrimina cada f(x) de forma a gerar a contradição.

Passo 6

Como f é suposta sobrejetora e A\in\mathcal{P}(X), existe algum a\in X tal que
f(a)=A.
Agora examinamos se a pertence ou não a A.
  • Se a\in A, então, pela definição de A, deve valer a\notin f(a). Mas f(a)=A, logo isto dá a\notin A. Contradição.
  • Se a\notin A, então, novamente pela definição de A, deve valer a\in f(a). Como f(a)=A, isto dá a\in A. Contradição.
Em ambos os casos obtemos contradição. Logo a suposição de que existe a com f(a)=A é impossível.

Passo 7

Concluímos que a hipótese de f ser sobrejetora é falsa: não pode existir função f:X\to\mathcal{P}(X) que seja sobrejetora. Esse é exatamente o Teorema de Cantor: para todo conjunto X, não há bijeção (nem sobrejeção) de X em \mathcal{P}(X); em particular \lvert\mathcal{P}(X)\rvert>\lvert X\rvert em termos de cardinalidade.
Breve encorajamento: essa prova é curta mas muito poderosa — é normal estranhar a definição do conjunto A na primeira vez; pense nela como uma maneira automática de fabricar um subconjunto que “escapa” de qualquer tentativa de cobrir todos os subconjuntos por imagens.

Resposta

(a) f:X\to\mathcal{P}(X) dada por f(x)=\{x\} é injetora.
(b) Não existe função sobrejetora f:X\to\mathcal{P}(X).

Exercícios relacionados