O argumento diagonal de Cantor: por que os números reais não podem ser listados
Suponha que alguém entregue uma lista para você. É uma lista infinita, e a pessoa garante que ela contém todos os números reais entre 0 e 1. Não uma amostra, não uma seleção: todos, um por um, indexados direitinho como r1, r2, r3, e assim por diante, para sempre.
A resposta de Georg Cantor, em 1891, foi esta: seja qual for a lista que você me entregar, eu consigo ler nela um número que não está lá. A construção leva uns trinta segundos para ser descrita. A consequência levou décadas para ser digerida pelos matemáticos, porque significa que o infinito vem em mais de um tamanho.
Contar e listar
Antes do movimento diagonal, ajuda ser preciso sobre o que "enumerável" quer dizer. Um conjunto é enumerável quando dá para dar a cada elemento um rótulo natural único: um primeiro elemento, um segundo, um terceiro, e assim por diante, sem sobrar nada. Os próprios números naturais são enumeráveis por definição. Os inteiros também (liste-os como 0, 1, -1, 2, -2, ...) e até os racionais, embora listar toda fração exija um zigue-zague engenhoso.
O argumento de Cantor mostra que os números reais entre 0 e 1 são genuinamente diferentes: nenhuma rotulação existe, tente como quiser. Isso não é falta de imaginação. É uma prova de que a tarefa é impossível.
Suponha que a lista existe
O argumento é uma demonstração por absurdo. Comece concedendo ao adversário tudo o que ele quiser: suponha que exista de fato uma lista completa de todos os números reais em (0, 1). Escreva cada número como uma expansão decimal infinita.
A lista poderia começar assim:
- r1 = 0,14159265...
- r2 = 0,73205080...
- r3 = 0,00000000...
- r4 = 0,27182818...
- r5 = 0,91415926...
- ...
Cada entrada segue para sempre. A lista segue para sempre. E, por hipótese, todo número real entre 0 e 1 aparece em algum ponto dela.
Agora repare no que acontece quando você lê a diagonal.
Lendo a diagonal
Olhe para o primeiro algarismo decimal de r1, o segundo algarismo decimal de r2, o terceiro de r3, e assim por diante. No exemplo acima, esses algarismos da diagonal são: 1, 3, 0, 2, 9, ...
Agora você constrói um número novo, chame-o de d, um algarismo de cada vez. A regra: para cada algarismo da diagonal, escolha um algarismo diferente, mas evite deliberadamente 0 e 9.
| r₁ | 0 | . | 1 | 4 | 1 | 5 | 9 | |
| r₂ | 0 | . | 3 | 3 | 3 | 3 | 3 | |
| r₃ | 0 | . | 5 | 0 | 0 | 0 | 0 | |
| r₄ | 0 | . | 7 | 1 | 8 | 2 | 8 | |
| r₅ | 0 | . | 6 | 0 | 2 | 5 | 9 | |
| new | 0 | . | 2 | 4 | 1 | 3 | 8 | … |
Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.
Os algarismos da diagonal são 1, 3, 0, 2, 9. Aplicando a regra, saem 2, 4, 1, 3, 8. Logo d = 0,24138...
Evitar 0 e 9 é uma precaução pequena, mas necessária. Alguns números reais têm duas representações decimais: 0,4999... e 0,5000... nomeiam o mesmo ponto da reta numérica. Trocar um algarismo por 0 ou por 9 poderia levar você ao "outro nome" de um número que já está na lista, o que embaçaria o argumento. Ficando na faixa de 1 a 8 em cada algarismo trocado, você garante que d tem exatamente uma expansão decimal, e a comparação abaixo fica limpa.
O novo número difere de toda entrada
Aqui está a recompensa.
d difere de r1 na primeira casa decimal
O primeiro algarismo de d foi escolhido para diferir do primeiro algarismo de r1. Portanto d não é igual a r1. Eles diferem na posição 1.
d difere de r2 na segunda casa decimal
O segundo algarismo de d foi escolhido para diferir do segundo algarismo de r2. Portanto d não é igual a r2. Eles diferem na posição 2.
d difere de rn na enésima casa decimal, para todo n
Por construção, o enésimo algarismo de d difere do enésimo algarismo de rn. Como dois números com um algarismo diferente em qualquer posição são desiguais, d não é igual a rn, para nenhum n que você escolha.
Esse é o movimento diagonal: d foi projetado para bater de frente com toda entrada da lista, no único ponto em que cada entrada está mais exposta, a sua própria posição diagonal.
d é um número real entre 0 e 1 e mesmo assim não está na lista
O número d = 0,24138... é claramente um número real no intervalo (0, 1). Mas acabamos de mostrar que ele difere de r1, de r2, de r3, de toda entrada. Se a lista fosse completa, d teria de aparecer em algum lugar nela. Não aparece. Logo a lista não é completa.
A contradição é afiada: supusemos que a lista era completa e produzimos um número real que não está nela. A suposição tem de ser falsa. Nenhuma lista completa dos números reais entre 0 e 1 pode existir.
O que isso realmente diz
Os matemáticos dizem que os números naturais têm cardinalidade aleph zero (escrita com a letra hebraica aleph: o primeiro cardinal transfinito). Os números reais têm uma cardinalidade estritamente maior, às vezes escrita como c ou como 2 elevado a aleph zero. É o argumento de Cantor que estabelece que esses dois infinitos não têm o mesmo tamanho.
Isso foi profundamente controverso quando Cantor publicou. Alguns colegas descartaram o resultado como curiosidade ou como erro. Não é nem uma coisa nem outra. Ele está na base de como os matemáticos pensam conjuntos, cardinalidade e a estrutura da reta real, e se conecta diretamente a perguntas sobre o que pode e o que não pode ser computado (veja também a demonstração do teorema de Goodstein para outro caso em que algo comprovadamente verdadeiro pressiona os limites dos sistemas formais).
Por que a diagonal funciona
O que torna o argumento elegante é a sua precisão. Você não está chutando um número ausente nem apelando para uma intuição vaga sobre o tamanho dos reais. Você está lendo exatamente quais posições da lista cada entrada controla e então construindo um número que escapa de toda entrada exatamente naquela posição.
A própria lista diz onde olhar. Cada entrada da lista entrega uma coordenada, o seu próprio algarismo da diagonal, e a construção transforma essas coordenadas num número que a lista não consegue conter.
A simplicidade engana. Não há nada aqui que exija saber qualquer coisa sobre as entradas da lista. Não importa que números estão nela, em que ordem, nem como foram escolhidos. O argumento é universal: pegue qualquer lista de números reais e a construção diagonal produz um número real que não está nela.
O zen de tudo isso
O argumento diagonal de Cantor pertence a uma longa tradição de resultados matemáticos que parecem não ter como funcionar. Você encara a demonstração esperando o truque, a hipótese escondida, o ponto em que a lógica escorrega. Não está lá. A prova é exatamente tão simples quanto parece.
O que ela pede que você aceite é mais estranho que a própria prova: que "infinito" não é um destino único. Os inteiros e os reais são ambos infinitos, mas são infinitos de maneiras categoricamente diferentes. O argumento diagonal é a linha divisória.
Para sentir melhor como coleções infinitas podem se comportar de forma estranha, a estrutura dos decimais infinitos é um bom próximo passo, ou então como funcionam os limites quando sequências se aproximam de um valor para sempre sem alcançá-lo. O argumento diagonal pertence a essa mesma família: um olhar preciso e paciente sobre o que acontece na borda do infinito, onde a intuição precisa de uma prova para se manter honesta.
O infinito não é uma coisa só. Essa é a notícia. E o argumento que a entrega cabe em meia página.
Perguntas frequentes
- O que o argumento diagonal de Cantor prova?
- Prova que os números reais entre 0 e 1 são não enumeráveis: nenhuma lista, por mais engenhosa que seja, consegue conter todos os números reais desse intervalo. Existem simplesmente mais números reais do que posições disponíveis em qualquer lista.
- O que significa 'não enumerável'?
- Um conjunto é enumerável quando dá para associar cada um de seus elementos a um número natural (1, 2, 3, ...) sem deixar nada de fora. Os naturais, os inteiros e até os racionais são todos enumeráveis. Os reais não são: eles são numerosos demais para caber em qualquer correspondência um a um desse tipo.
- Por que não basta acrescentar o número que faltou à lista?
- Dá para acrescentar, mas aí o argumento diagonal se aplica de novo à lista nova, mais longa, e produz mais um número ausente. O argumento funciona para qualquer lista, por mais longa ou bem arrumada que seja, então não há como remendar a lista até deixá-la completa.
- Por que evitar os algarismos 0 e 9 na hora de trocar?
- Alguns números reais têm duas representações decimais: 0,4999... e 0,5000... são o mesmo número. Se você trocar um algarismo por 0 ou por 9, pode cair por acidente no 'outro nome' de um número que já está na lista. Evitar 0 e 9 contorna esse detalhe técnico e mantém a demonstração limpa.
- Os números racionais também são não enumeráveis?
- Não. Os números racionais são enumeráveis: dá para listar sistematicamente toda fração p/q e atribuir a cada uma um índice natural, sem deixar nenhuma de fora. O argumento diagonal de Cantor mira os números reais, não os racionais.
Coloque em prática
Gostou de pensar sobre isso?
O Math Zen transforma esse tipo de intuição em prática diária, com exercícios adaptativos em 24 temas de matemática.
