Argumento de diagonalização de Cantor

Origem: Wikipédia, a enciclopédia livre.

O argumento de diagonalização de Cantor é uma prova matemática imaginada por Georg 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.

[editar] 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 deste intervalo como uma seqüência, ( r₁, r₂, r₃, ... )
• (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 r_k.

      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 r_k é 5 então o k-ésimo dígito de x é 4.
• se o k-ésimo dígito de r_k 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 r_n = x para algum n, uma vez que assumimos que ( r₁, r₂, r₃, ... ) 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 r_n, então x não está na seqüência ( r₁, r₂, r₃, ... ).
• (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.

Alternativamente, poderíamos mostrar que [0,1] e R são do mesmo tamanho, construindo uma bijecção entre eles. Para o intervalo (0,1) podemos usar a bijecção definida por . Para o intervalo [0,1] isto também é possível, embora de forma não tão directa.

[editar] 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.