✍ Diagonal de Cantor

... quando estou para paródias, dá nisto.

O argumento da diagonal de Cantor pode ser formulado da seguinte forma. Considere-se T o conjunto de todas as sequências de 0 e 1. Se s1, s2, ..., sn ... é uma enumeração dos elementos de T então existe um elemento de T que não corresponde a nenhuma sequência, i=1,2,... Estranho não?

Estranhamente, repito, o resultado obtém-se de uma forma construtiva. Podemos começar por fazer uma lista (note-se que a ordenação escolhida é totalmente arbitrária e qualquer outra podia ser escolhida sem perda de generalidade)

((0 0 0 0 0 0 0 ...)
 (1 1 1 1 1 1 1 ...)
 (0 1 0 1 0 1 0 ...)
 (1 1 0 1 0 1 1 ...)
 (0 0 1 1 0 1 1 ...)
 (1 0 0 0 1 0 0 ...))

Posso assim construir um elemento s de T que não está nessa lista. Como? Tomando o primeiro elemento de s diferente do primeiro elemento de s1, i.e. 1, de seguida o segundo elemento s diferente do segundo elemento de s2, e assim por diante. Viajo pela diagonal e retiro para s um elemento diferente daquele que encontro. s tem então a forma

(1 0 1 1 0 1 ...)

É fácil ver que s não está contido na enumeração inicial que construímos para os elementos de T. E logo que não é possível enumerar todas as sequências de zeros e uns. Falta pelo menos um elemento dessa proposta lista completa.

Não é possível deixar de sentir um certo desconforto que se tem na explicação acima. Admitimos que conseguiríamos enumerar, fazer uma lista de todos as sequências de zeros e uns e depois, de uma foram construtiva, obtemos uma lista extra que não estava contida na lista inicial que nos propusemos construir. A contradição surge de uma forma escandalosa e perturbante e é um sinal de que tomamos uma hipótese que de alguma forma contradiz a nossa habitual forma de ver o mundo e em particular como construímos listas.

Para os matemáticos profissionais (e para mim também, quando não estou para paródias) tal resultado é tomado com muita naturalidade e é uma técnica usada em muitas outras áreas de aplicação.

O facto de T não ser numerável, não conseguirmos fazer uma lista completa, apenas mostra que é sem sentido a afirmação ``consideremos todas as sequências de zeros e uns''. A expressão lista é e si mesma uma variável e não uma coisa com significado primitivo

O paradoxo é sempre o mesmo, em muitas formas surge e reaparece. Mostra bem a nossa confusão sobre tudo isto.

Volte-se então há nossa lista de zeros e uns. Enumerei essa lista na forma s1, s2, ... sn, ... A lista s onde o n-ésimo elemento é dado por

s(n)=1-sn(n)
não está na lista inicial.

Pergunta: é isto uma lei natural? Ou é simplesmente um problema de notação que se revela quando escrevo estas listas de 0's e 1's?

Deve a minha notação prevenir encontrar-me na situação em que me encontro? Que significa pensar que está tudo escrito? A lista foi construída propositadamente para se encontrar o que não lá está. Deve ser isso.

Palavras chave/keywords: Cantor, diagonal

Criado/Created: 21-01-2016 [22:05]

Última actualização/Last updated: 23-01-2017 [09:17]


GNU/Emacs

1999-2017 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.