Questão 40 Seja
um conjunto qualquer.
a) Exiba uma função injetora entre
e
.
b) Mostre que não existe uma função sobrejetora
. (Teorema de Cantor).
a) Exiba uma função injetora entre
b) Mostre que não existe uma função sobrejetora
Passo 1
O enunciado dá um conjunto qualquer
(sem hipótese extra: pode ser vazio, finito ou infinito) e pede duas coisas:
- (a) Exibir uma função injetora de
em . - (b) Mostrar que não existe nenhuma função sobrejetora
— isto é o Teorema de Cantor.
Informações úteis que vamos usar (definições e notação):
-
é o conjunto de todas as partes (subconjuntos) de . - Uma função
é injetora se, para quaisquer , . - Uma função
é sobrejetora se, para todo , existe tal que .
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
.
Ideia simples e natural (muito usada): associar a cada elemento
o subconjunto formado só por
, isto é, a singleton (conjunto unitário)
. Definimos:
Antes de provar injetividade, veja um exemplo concreto para fixar a ideia: se
então
cada imagem é um subconjunto de
, então
realmente tem imagem em
.
Passo 3
Provar que
é injetora.
Tomemos
e suponha
. Isso significa
. Dois conjuntos unitários são iguais somente se o elemento que eles contêm é o mesmo; portanto
. Assim, por definição de injetividade,
logo
é injetora.
Comentário didático: a razão é simples — conjuntos unitários distinguem seus elementos. Esse é um truque padrão para embutir
em
. Observe que a construção funciona mesmo se
for vazio: nesse caso não há
e a função vazia
(nenhum par imagem-antecedente) é vacuamente injetora.
Passo 4
Agora a segunda tarefa: provar que não existe função sobrejetora
.
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
Como
é sobrejetora, todo subconjunto de
aparece como imagem de algum ponto de
.
Passo 5
Defina o subconjunto especial
por
Ou seja,
é o conjunto de todos os elementos de
que não pertencem ao seu próprio subconjunto imagem
. Note que
é um subconjunto de
, então
.
Raciocínio sobre a definição: esta é a etapa “diagonal” — construímos um subconjunto que discrimina cada
de forma a gerar a contradição.
Passo 6
Como
é suposta sobrejetora e
, existe algum
tal que
Agora examinamos se
pertence ou não a
.
-
Se
, então, pela definição de , deve valer . Mas , logo isto dá . Contradição. -
Se
, então, novamente pela definição de , deve valer . Como , isto dá . Contradição.
Em ambos os casos obtemos contradição. Logo a suposição de que existe
com
é impossível.
Passo 7
Concluímos que a hipótese de
ser sobrejetora é falsa: não pode existir função
que seja sobrejetora. Esse é exatamente o Teorema de Cantor: para todo conjunto
, não há bijeção (nem sobrejeção) de
em
; em particular
em termos de cardinalidade.
Breve encorajamento: essa prova é curta mas muito poderosa — é normal estranhar a definição do conjunto
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)
dada por
é injetora.
(b) Não existe função sobrejetora .
(b) Não existe função sobrejetora