pode ser sobrejetora. Sabemos que isto é verdadeiro quando A é finito, mas queremos encontrar uma prova que funcione para qualquer conjunto A. No que se segue, mostraremos como descobrir a prova que se tornou clássica.
Seja A um conjunto. Provaremos o Teorema de Cantor se mostrarmos que nenhuma função de A em pode ser sobrejetora. Sabemos que isto é verdadeiro quando A é finito, mas queremos encontrar uma prova que funcione para qualquer conjunto A. No que se segue, mostraremos como descobrir a prova que se tornou clássica.
Tomemos uma função 
. Esta função é uma família de subconjuntos de A, indexados pelos próprios elementos de A. Dizer que f é sobrejetora significa dizer que todo subconjunto de A pertence à imagem de f, o que podemos exprimir
simbolicamente como
.
Como queremos provar que f não é sobrejetora, devemos nos concentrar na negação dessa sentença, que é
.
Assim, deve existir um subconjunto X de A para o qual
Em resumo, teremos que descobrir um conjunto 
que não coincida com nenhum dos subconjuntos 
. A definição de X deve ser da forma
,
onde 
é uma propriedade característica de X, isto é, tal que
.
A questão é: como encontrar uma propriedade 
que funcione? Para descobri-lo, vamos raciocinar por "regressão", isto é, por análise: assumiremos que X já foi descoberto e, pelo exame da propriedade 
acima, tentaremos obter condições sobre X que nos levem à propriedade 
.
Fixemos um elemento 
. A condição crucial a ser satisfeita pelo conjunto X é que
.
Ora, temos 
se e somente 
. Por negação desta sentença universal, vemos que 
significa
.
Esta sentença existencial será verdadeira desde que a condição sob o quantificador, a saber,
,
seja satisfeita para 
; isto é, se a sentença
for verdadeira. Claramente, este será o caso se tivermos
,
ou, equivalentemente (já que 
),
.
Mas esta sentença significa que
.
Neste ponto, deve estar claro que já atingimos o nosso objetivo. Agora, basta invertermos os passos da nossa análise e apresentá-los convenientemente. Isto será feito na próxima página, mas numa forma algo diferente.
Carlos César de Araújo, 26 de julho de 2003