Ao Infinito e Além

Prévia do material em texto

Ao Infinito e Além 
 
O que há de comum entre Cantor, Gödel e Turing? Pelo menos duas coisas, e a primeira delas é que os três 
tentaram expandir os limites da matemática. 
Cantor, por exemplo, queria contar até infinito. Essa é uma tarefa bem difícil: todos os que tentaram, cansaram 
antes de concluir! Mas o que o Cantor percebeu foi que, embora seja difícil contar diretamente, você pode contar 
até infinito indiretamente, desde que você saiba qual o significado real de "contar" alguma coisa. 
 
O que significa, por exemplo, que você tem quatro maçãs? Na interpretação de Cantor, isso significa que você 
pode criar uma bijeção do seu conjunto de maçãs com um subconjunto dos números naturais, como na figura 
abaixo: 
 
 
 
 
Se você criou uma bijeção do seu conjunto com o conjunto dos quatro primeiros naturais, então você efetivamente 
contou seu conjunto e concluiu que ele tem quatro elementos. O truque do Cantor foi perceber que você podia 
estender esse conceito, e criar bijeções com todos os naturais, ao invés de só algum subconjunto. E isso leva a 
resultados que são bem pouco intuitivos! 
Por exemplo, o conjunto dos números pares. A intuição do iniciante é que esse conjunto tem a metade dos 
elementos dos naturais. Mas não é verdade, porque você pode construir uma bijeção entre os dois: 
 
 
 
 
 
Para cada natural você tem um par correspondente, para cada par você tem um natural. Pelo raciocínio do Cantor, 
então esses dois conjuntos tem o mesmo número de elementos, o que também mostra que, pelo menos quando 
você está lidando com o infinito, a parte pode ser igual ao todo. 
Indo além, o Cantor também mostrou que os Números Racionais também são do mesmo tamanho dos Naturais. 
Quem quiser repetir a demonstração original dele, pode tentar fazer o problema CANTON do spoj, que pede para 
você criar a bijeção. Uma maneira alternativa é utilizar uma construção inventada pelo Gödel: a cada racional p/q, 
você associa o natural 2p3q, e pra transformar o natural de volta numa racional, você usa a fatoração única que o 
Teorema Fundamental da Aritmética te garante. 
Quando um conjunto tem o mesmo tamanho dos naturais, diz-se que ele tem cardinalidade aleph-zero, ou ainda, 
que é um conjunto contável. Mas todos os conjuntos infinitos são contáveis? Não! O Cantor também mostrou que 
o conjunto dos Números Reais é maior que qualquer conjunto contável dado, utilizando um método chamado 
argumento diagonal. Ou seja, os números reais são um tipo de infinito maior que o infinito dos naturais! 
Agora, se os racionais são contáveis, e os reais não são, fica claro que os culpados por existir um infinito maior 
que o outro são os irracionais. Mas quais irracionais? Existem vários tipos deles também. Por exemplo, alguns 
irracionais podem ser construídos como raízes de polinômios de coeficientes inteiros (diz-se que esses são 
irracionais algébricos). Um exemplo é a razão áurea, que é a maior raiz do polinômio x2-x-1. 
Porém, os irracionais algébricos são contáveis também. Basta utilizar novamente o mesmo truque do Gödel, 
dessa vez você associa cada coeficiente do polinômio a um expoente de um número primo. Um polinômio como 
x2+2x+1, por exemplo, escrever-se-ia como 21*32*51. 
Ora, se os irracionais algébricos são contáveis, então o que torna os reais maiores que os naturais são os 
irracionais não-algébricos (ou transcendentes). Mas mesmo entre esses existem vários tipos. O número Pi, por 
exemplo: você não consegue construí-lo como uma raiz de um polinômio, mas pode aproximá-lo com um 
algoritmo computacional, com tanta precisão quanto se queira. Dos números que podem ser aproximados por 
algoritmos, diz-se que são números computáveis. 
Surpreendentemente, os irracionais computáveis são contáveis também. A maneira simples de visualizar isso é da 
seguinte maneira: se existe um algoritmo que aproxima o número, então esse algoritmo pode ser implementado 
numa linguagem qualquer (como nos garante a tese de Church-Turing). Agora, imagine que você criou um binário 
que implementou esse algoritmo, e esse binário tem X bytes. Se você fizer um hexdump do binario e imprimi-lo, 
você vai ter na sua frente um número hexa de 2X dígitos (que é um número natural grandinho, mas ainda assim 
um natural). 
 
Mas se os irracionais computáveis são contáveis, quem são os não-contáveis? Existem números que não podem 
ser calculados por algoritmos? A resposta é sim, e um desses números é a constante de Chaitin. A construção da 
constante é curiosa. Nós vimos que, a cada algoritmo possível, existe um natural associado. Calcule então a 
seguinte somatória: para cada algoritmo existente (cujo natural associado é n), se o algoritmo pára, você soma 2-n, 
senão não soma nada. Ora, essa somatória não pode ser calculada por um algoritmo, porque o Teorema de 
Turing garante que você não pode construir um algoritmo que detecta se outro algoritmo pára. A constante de 
Chaitin, então, é um número não-computável. 
Mas os irracionais não-computáveis ainda não são o segredo do infinito real. Eu não consigo construir um 
algoritmo que aproxima a constante de Chaitin, mas no parágrafo acima eu consegui descrever exatamente do 
que a constante se trata. Os números que eu consigo descrever são números definíveis, e, (surpresa), eles são 
contáveis também. O argumento é ainda mais simples, se eu posso escrever um arquivo texto que contenha a 
descrição do número, o hexdump desse arquivo também vai associar a descrição a um número natural. 
Então, os números que fazem o infinito dos reais ser maior que o infinito dos naturais são os números que não 
podemos construir, não podemos aproximar e não podemos descrever, ou seja, nem dá pra pensar sobre eles! 
 
Se a essa altura sua cabeça deu tilt, então deixe-me concluir qual é a segunda coisa em comum entre Cantor, 
Gödel e Turing: os três ficaram doidos. De fato, Cantor achava que era um mensageiro de Deus, e terminou a vida 
num hospício. Gödel ficou paranóico com comida contaminada, e só comia o que a mulher preparava (quando a 
mulher ficou doente e internada num hospital, ele literalmente morreu de fome). E o Turing ficou tão deprimido que 
se matou, comendo uma maçã envenenada. 
Há quem diga que existe relação causal entre estudar o infinito e ficar doido. Se você é desse tipo, hum, então era 
melhor não ter lido esse post :) 
(Esse post é dedicado ao prof. Henrique, in memorian, líder do nosso grupo de doidos, que se reunia toda sexta 
na USP para estudar matemática, computação e ciências cognitivas. Três vivas aos que estudam o infinito, e 
além!)