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.
Created: 21-01-2016 [22:05]
Last updated: 23-01-2025 [00:03]
For attribution, please cite this page as:
Charters, T., "Diagonal de Cantor": https://nexp.pt/cantor.html (23-01-2025 [00:03])
(cc-by-sa) Tiago Charters - tiagocharters@nexp.pt