Argumento de diagonalização de Cantor

Está ai um negócio que muito provavelmente cairá na prova de Teoria da Computação ...



http://pt.wikipedia.org/wiki/Argumento_da_Diagonal_de_Cantor


Argumento de diagonalização de Cantor
Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Argumento da Diagonal de Cantor)
Ir para: navegação, pesquisa
Diagonal usada no argumento de Cantor.
Diagonal usada no argumento de Cantor.

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, ( 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.

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 f\colon (0,1)\rightarrow\mathbb{R} definida por f(x) = \tan\left(\pi\left(x-\frac{1}{2}\right)\right). 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. De fato, o conjunto de todas as seqüencias infinitas de números inteiros é um conjunto não enumerável.