Argumento de diagonalização de Cantor
Na teoria dos conjuntos, o argumento da diagonalização de Cantor, também chamada de argumento da diagonalização, foi publicado em 1891 por Georg Cantor como uma prova matemática de que existem conjuntos infinitos que não podem ser mapeados em uma correspondência um-para-um ao conjunto infinito de números naturais. Tais conjuntos são agora conhecidos como conjuntos incontáveis, e o tamanho dos conjuntos infinitos agora é tratada pela teoria dos números cardinais que Cantor iniciou.
Em seu artigo de 1891, Cantor considerou o conjunto T de todas as sequências infinitas de dígitos binários (isto é, consistindo apenas de zeros e uns). Ele começa com uma prova construtiva do seguinte teorema: Se s1, s2, … , sn, … é qualquer enumeração dos elementos de T, então existe sempre um elemento s de T que corresponde a nenhum sn na enumeração. Para provar isso, dada uma enumeração dos elementos arbitrários de T, por exemplo: ele constrói a sequência s escolhendo seu n-ésimo dígito como um complemento para o n-ésimo dígito de sn, para cada n. No exemplo, isso resulta em: Por construção, s difere de cada sn, uma vez que seus n-ésimos dígitos diferem (destacado no exemplo). Portanto, não é possível s ocorrer na enumeração. Com base neste teorema, Cantor, em seguida, usa um argumento indireto para mostrar que: Ele assume a contradição de que T era contável. Em seguida, (todos) os seus elementos podem ser escritos como uma enumeração s1, s2, … , sn, … . Aplicando o teorema anterior a esta enumeração seria produzir uma seqüência s não pertencente à enumeração. No entanto, s era um elemento de T e, portanto, deve estar na enumeração. Isto contradiz a suposição original, assim T deve ser incontável.
Interpretação
A interpretação do resultado de Cantor depende do ponto de vista matemático levado em consideração. Para os construtivistas, o argumento não mostra mais de que não existe [bijeção] entre os números naturais e T. Não é excluída a possibilidade de que os últimos são subcontáveis. No contexto da matemática clássica, isso é impossível, e o argumento da diagonalização estabelece que, embora ambos os conjuntos sejam infinitos, na verdade existem sequências mais infinitas de zeros e uns do que há números naturais.
Números reais
A incontabilidade dos números reais já foi estabelecida pela primeira prova de incontabilidade de Cantor, mas também decorre do resultado acima. Para ver isso, vamos construir uma correspondência um-para-um entre o conjunto T de cadeias binárias infinitas e um subconjunto de R (o conjunto dos números reais). Como T é incontável, este subconjunto de R deve ser incontável. Daí R é incontável. Para construir esta correspondência um-para-um (ou bijeção), observa-se que a sequência de t = 0111… aparece depois do ponto flutuante na correspondência binária 0.0111…. Isto sugere a definição da função f(t) = 0.t, em que t é uma cadeia de caracteres em T. Infelizmente, f(1000…) = 0.1000… = 1/2, e f(0111…) = 0.0111… = 1/4 + 1/8 1/16 + + … = 1/2. Assim, esta função não é uma bijeção dado que duas cadeias de caracteres correspondem a um número—um número com duas correspondências binárias.
A forma generalizada do argumento da diagonalização foi usado por Cantor para provar o teorema de Cantor: para cada conjunto S o conjunto das partes de S, ou seja, o conjunto de todos os subconjuntos de S (aqui escrito como P(S)), tem uma cardinalidade maior do que o próprio S. Esta prova é dada da seguinte forma: Seja f uma função de S para P(S). Basta provar que f não pode ser sobrejetiva. Isso significa que algum membro T de P(S), ou seja, um subconjunto de S, não é a imagem de f. Como um exemplo, considere o seguinte conjunto: Para todo s em S, ou s está em T ou não. Se s está em T, então, por definição de T, s não está em f(s), de modo que T não é igual a f(s). Por outro lado, se s não está em T, então por definição de T, s está em f(s), então novamente T não é igual a f(s). Para uma descrição mais completa desta prova, consulte o teorema de Cantor.
Consequências
Este resultado implica que a noção do conjunto de todos os conjuntos é uma noção inconsistente. Se S fosse o conjunto de todos os conjuntos, então P(S) seria ao mesmo tempo maior do que S e um subconjunto de S. O paradoxo de Russell tem nos mostrado que a teoria ingênua dos conjuntos, baseada em um esquema de compreensão irrestrita, é contraditória. Note que há uma semelhança entre a construção de T e o conjunto no paradoxo de Russell. Portanto, dependendo de como modificamos o esquema do axioma de compreensão, a fim de evitar o paradoxo de Russell, argumentos como a não-existência de um conjunto de todos os conjuntos podem ou não permanecer válido.
Versão da "New Foundations" de W. V. Quine
A prova acima falha para a teoria dos conjutos de "New Foundations" de W. V. Quine (NF). Em NF, o esquema de axioma ingênuo de compreensão é modificado para evitar os paradoxos através da introdução de uma espécie de teoria local. No esquema do axioma, não é um conjunto - ou seja, não satisfaz o esquema de axioma. Por outro lado, poderíamos tentar criar um argumento da diagonalização modificado por perceber que é um conjunto no NF. No caso em que, se P1(S) é o conjunto de subconjuntos de um único elemento de Se f é uma proposta bijeção de P1(S) para P(S), ao menos um é capaz de utilizar a prova por contradição para provar que |P1(S)| < |P(S)|.
