Argumento de diagonalização de Cantor
Keywords: Argumento de diagonalização de Cantor, Número real, Prova matemática, Prova por contradição, Seqüência
O argumento de diagonalização de Cantor é uma prova matemática imaginada por George Cantor para demonstrar que os números reais não são contavelmente infinitos (ou, equivalentemente, não formam um conjunto infinito enumerável).
Ao contrário do que muitos matemáticos acreditam, o argumento de diagonalização não foi a primeira prova de Cantor da não-enumerabilidade dos números reais, que foi publicada três anos antes.
Números reais
A prova de Cantor mostra que o intervalo [0,1] não é contavelmente infinito.
A prova por contradição é feita da seguinte forma:
- (1) Assuma (para fins de argumentação) que o intervalo [0,1] é infinito enumerável.
- (2) Então nós podemos enumerar todos os números desde intervalo como uma seqüência, ( r1, r2, r3, ... )
- (3) Nós sabemos que cada um desses números pode ser representado como uma expansão decimal.
- (4) Arranjamos os números em uma lista (eles não precisam estar em ordem). No caso de números com duas expansões decimais, como 0,499... = 0,500..., escolhemos aquele que acaba com noves. Assuma, por exemplo, que as expansões decimais do início da seqüência são como se segue:
r1 = 0 , 5 1 0 5 1 1 0 ...
r2 = 0 , 4 1 3 2 0 4 3 ...
r3 = 0 , 8 2 4 5 0 2 6 ...
r4 = 0 , 2 3 3 0 1 2 6 ...
r5 = 0 , 4 1 0 7 2 4 6 ...
r6 = 0 , 9 9 3 7 8 3 8 ...
r7 = 0 , 0 1 0 5 1 3 5 ...
...
- (5) Nós devemos agora construir um número real x dentro do intervalo [0,1]] considerando o k-ésimo dígito depois da vírgula da expansão decimal de rk.
r1 = 0 , 5 1 0 5 1 1 0 ...
r2 = 0 , 4 1 3 2 0 4 3 ...
r3 = 0 , 8 2 4 5 0 2 6 ...
r4 = 0 , 2 3 3 0 1 2 6 ...
r5 = 0 , 4 1 0 7 2 4 6 ...
r6 = 0 , 9 9 3 7 8 3 8 ...
r7 = 0 , 0 1 0 5 1 3 5 ...
...
Os dígitos que consideraremos estão sublinhados e em negrito, ilustrando por que isso é chamado de argumento de diagonalização.
- (6) A partir desses dígitos nós definimos os dígitos do número x como a seguir.
- se o k-ésimo dígito de rk é 5 então o k-ésimo dígito de x é 4.
- se o k-ésimo dígito de rk não é 5 então o k-ésimo dígito de x é 5.
- Para o exemplo anterior, isto resultará na seguinte expansão decimal para x:
x = 0 , 4 5 5 5 5 5 4 ...
- (7) O número x é um número real (nós sabemos que todas as expansões decimais representam números reais) dentro do intervalo [0,1].
- (8) Por isso, devemos ter rn = x para algum n, uma vez que assumimos que ( r1, r2, r3, ... ) enumera todos os números reais no intervalo [0,1].
- (9) No entanto, por causa da maneira como escolhemos os dígitos 4 e 5 no passo (6), x difere na n-ésima posição de rn, então x não está na seqüência ( r1, r2, r3, ... ).
- (10) Essa seqüência portanto não é uma enumeração do conjunto de todos os reais no intervalor [0,1]. Isto é uma contradição..
- (11) Logo, a hipótese (1) de que o intervalo [0,1] é contavelmente finita deve ser falsa.
É um corolário direto deste resultado que o conjunto R de todos os números reais é incontável. Se R fosse contável, poderíamos enumerar todos os números reais em uma seqüência, e então obter uma seqüência enumerando [0,1] através da remoção de todos os números reais fora deste intervalo. Mas nós acabamos de mostrar que esta última lista não pode existir.
Por que isto não funciona com os inteiros
As pessoas às vezes acham que a prova acima pode ser adaptada para os inteiros para provar que eles também são incontáveis. Eles tentam fazer isso retirando a vírgula decimal nas expansões acima. O problema é que uma seqüência infinita de digitos não-nulos não representa um inteiro. Esta é a razão para o passo (7) acima.