Infinitos de tamanhos diferentes: Cantor

Infinitos de tamanhos diferentes

Os números naturais 1, 2, 3, … são infinitos. Os números pares também são infinitos, e parecem "menos" que os naturais, já que estão entre eles. Mas Galileu e outros já notaram que há uma correspondência perfeita: 1 com 2, 2 com 4, 3 com 6. Então, em certo sentido, os dois infinitos têm o mesmo tamanho.

Contáveis e não contáveis

Georg Cantor, em 1874, deu nome a essa ideia: um conjunto é contável quando pode ser colocado em correspondência com os naturais. Os inteiros, os racionais e até as frações são contáveis, por mais estranho que pareça.

Os números reais, porém, não são. Em 1891, Cantor usou o argumento da diagonal: suponha uma lista de todos os reais entre 0 e 1 em expansão decimal. Construa um número mudando um dígito de cada linha da diagonal. Esse número novo não está na lista. Logo, nenhuma lista pode ser completa.

O argumento da diagonal

Na aula, a tabela tem 8 linhas, e cada linha é um real 0,d₁d₂d₃… A diagonal são os dígitos d₁₁, d₂₂, d₃₃, … Para construir x' = 0,d'₁d'₂d'₃…, troque cada dígito da diagonal por outro diferente. A aula usa +1 módulo 10.

Por construção, x' difere da linha 1 no primeiro dígito, da linha 2 no segundo, e assim por diante. Logo, x' não está em nenhuma linha. Como o mesmo vale para qualquer lista, nenhuma lista de reais de 0 a 1 pode ser completa. A tabela de 8 linhas é um modelo: com uma lista infinita, o argumento é idêntico.

Você pode testar: clique num dígito da tabela e veja a diagonal e o número construído mudarem. Por mais que você mexa, a última linha continua diferente de cada linha.

Racionais e inteiros são contáveis

O zigue-zague mostra como contar os racionais positivos. Organize as frações p/q numa grade, com p no eixo horizontal e q no vertical. As frações com p + q = 2 formam a primeira diagonal, com p + q = 3 a segunda, e assim por diante. Percorra cada diagonal em zigue-zague e pule as frações que não estão na forma reduzida (como 2/2, que é 1/1). A ordem é: 1/1, 1/2, 2/1, 3/1, 1/3, 2/2 (pulada), 1/4, 2/3, 3/2, 4/1, …

Os inteiros são ainda mais simples. O natural n corresponde a 0 (n = 1), 1 (n = 2), −1 (n = 3), 2 (n = 4), −2 (n = 5), e assim por diante. Os pares vão para os positivos, e os ímpares a partir de 3 para os negativos; o 1 vai para o 0. Nenhum inteiro fica de fora, e nenhum aparece duas vezes.

Uma hierarquia de infinitos

A cardinalidade dos naturais é chamada de alef-zero (ℵ₀). A dos reais é maior, e Cantor mostrou que sempre existe um infinito maior que qualquer outro dado. A hipótese do contínuo, sobre se há algo entre ℵ₀ e a cardinalidade dos reais, foi mostrada independente dos axiomas usuais por Gödel e Cohen.

Aplicações

• Computação: o argumento da diagonal é a base de resultados como a indecidibilidade do problema da parada.
• Teoria dos números: saber que os racionais são contáveis permite enumerá-los em programas.
• Filosofia da matemática: o argumento mostra que "quantos" existem é uma pergunta com respostas diferentes para infinitos diferentes.

Curiosidade

Cantor enfrentou forte resistência em vida, inclusive de Kronecker, que se opunha às ideias dele. Hoje a teoria dos conjuntos que ele criou é a base de quase toda a matemática.

Perguntas de revisão

1. Qual é a cardinalidade dos números naturais?

Resposta: alef-zero (ℵ₀). Não é "infinita, mas menor que a dos reais" nem igual a zero.

1. O que o argumento da diagonal de Cantor prova?

Resposta: que os reais não podem ser listados de forma completa. Ele não prova que os reais são contáveis.