4. A heurística da demonstração
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.