Argumento de diagonalización de Cantor

miniatura| Un conxunto infinito pode ter a mesma cardinalidade que un subconxunto de si mesmo, como demostra a bixección representada f(x)=2x desde os números naturais ata os pares. Porén, existen infinitos conxuntos de cardinalidades diferentes, como mostra o argumento da diagonalización de Cantor .

Na teoría de conxuntos, o argumento de diagonalización de Cantor, foi publicado en 1891 por Georg Cantor como unha proba matemática de que hai conxuntos infinitos que non se poden mapear nunha correspondencia un a un co conxunto de números naturais infinitos. (in german) Estes conxuntos coñécense agora como conxuntos incontábeis (ou non numerábeis), e o tamaño dos conxuntos infinitos agora tratase coa teoría dos números cardinais que iniciou Cantor.

O argumento da diagonalización non foi a primeira proba de Cantor da non numerabilidade dos números reais; en realidade publicouse moito máis tarde do que a súa primeira proba, que apareceu en 1874. No entanto, demostra unha técnica poderosa e xeral, que desde entón se utilizou nunha ampla gama de demostracións, tamén coñecidas como argumentos de diagonalización por analoxía co argumento usado nesta proba. Os exemplos máis famosos son o paradoxo de Russell, o primeiro dos teoremas de incompletitude de Gödel, e a resposta de Turing ao Entscheidungsproblem (problema da decisión).

 Conxunto incontábel 
No seu artigo de 1891, Cantor considerou o conxunto T de todas as secuencias infinitas de díxitos binarios (é dicir, que consta só de ceros e uns). Comeza cunha demostración construtiva do seguinte teorema:

Se s1, s2, ..., sn, ... é calquera enumeración dos elementos de T, entón sempre hai un elemento s de T que non corresponde con ningún sn na enumeración.

Para demostralo, dada unha enumeración dos elementos arbitrarios de T, por exemplo:

e constrúe a secuencia s escollendo o seu enésimo díxito como complemento do e-nésimo díxito de sn, para todo n. No exemplo, isto dá como resultado:

Por construción, s difire de todo sn, xa que os seus enésimos díxitos difiren (resaltados no exemplo). Polo tanto, non pode aparecer s na enumeración.

Baseándose neste teorema, Cantor usa entón un argumento indirecto para demostrar que:

 O conxunto T é incontábel (ou non numerábel).

Asume a contradición de que T era contábel. Entón (todos) os seus elementos pódense escribir como unha enumeración s1, s2, …, sn, … . Aplicando o teorema anterior a esta enumeración produciríase unha secuencia s non pertencente á enumeración. No entanto, s era un elemento de T e, polo tanto, debe estar na enumeración. Isto contradí a suposición orixinal, polo que T debe ser incontábel.

 Interpretación 
A interpretación do resultado de Cantor depende do punto de vista matemático que se teña en conta. Para os construtivistas, o argumento non mostra máis que non hai bixección entre os números naturais e T. Non se exclúe a posibilidade de que estes últimos estean infravalorados. No contexto das matemáticas clásicas, isto é imposíbel, e o argumento da diagonalización estabelece que aínda que ambos os conxuntos son infinitos, en realidade hai máis secuencias infinitas de ceros e uns que números naturais.

 Números reais 
miniatura|172x172px| A función tan: (−π/2,π/2) → R
miniatura|150x150px| A función h : (0,1) → (−π/2,π/2)
A incontabilidade dos números reais xa foi estabelecida pola primeira proba de non numerabilidade de Cantor, mais tamén se desprende do resultado anterior. Para ver isto, imos construír unha correspondencia un a un entre o conxunto T de cadeas binarias infinitas e un subconxunto de R (o conxunto de números reais). Dado que T é incontábel, este subconxunto de R debe ser incontábel. Polo tanto, R é incontábel.

Para construír esta correspondencia un a un (ou bixección), teña en conta que a secuencia t = 0111... aparece despois do punto flotante na correspondencia binaria 0.0111.... Isto suxire definir a función f(t) = 0.t, onde t é unha cadea de caracteres  en T. Desafortunadamente, f(1000...) = 0.1000... = 1/2, e f (0111...) = 0.0111... = 1/4 + 1/8 1/16 + + … = 1/2. Así, esta función non é unha bixección xa que dúas cadeas corresponden a un número, un número con dúas correspondencias binarias.

No entanto, modificando esta función prodúcese unha bixección de T no intervalo (0, 1), é dicir, os números reais maiores que 0 e inferiores a 1. A idea é eliminar os elementos "problemáticos" de T e (0, 1) e tratalos por separado. De (0, 1), elimina os números que teñen dúas correspondencias binarias. Pomos estes números nunha secuencia: a = (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...). Eliminamos as cadeas de T que aparecen despois da coma binaria nas correspondencias binarias de 0, 1, e os números da secuencia de a. Colocamos estas cadeas nunha secuencia: b = (  …,  …, 1  …, 0  …, 01  …, 11  …, 00  …, 10  …,…). Unha bixección g(t) de T a (0, 1) defínese por: Se t é unha cadea n na secuencia b, sexa g (t) o número de orde n na secuencia a ; en caso contrario, g(t) = 0.t.

Para construír unha bixección de T en R: comezamos coa función tanxente tan(x), que nos dá unha bixección de (-π / 2, π / 2) en R; ver imaxe. Entón observe que a función linear h(x) = πx - π/2 dá como resultado a bixección de (0, 1) en (-π/2, π /2); ver imaxe. A función composta tan(h(x)) = tan (πx - π/2) dá unha bixección de (0, 1) en R. Compomos con esta función g(t) para obter tan (h(g(t))) = tan (πg(t) - π/2), que é unha bixección de T en R. Isto significa que T e R teñen a mesma cardinalidade - esta cardinalidade chámase "cardinalidade do contínuo".

 Conxuntos xerais 
Cantor utilizou a forma xeneralizada do argumento da diagonalización para demostrar o seu teorema: para cada conxunto S o conxunto de partes de S, é dicir, o conxunto de todos os subconxuntos de S (aquí escritos como P (S)), ten unha cardinalidade maior que S en si. Esta proba dáse do seguinte xeito:

Sexa f unha función de S a P (S). Basta demostrar que f non pode ser sobrexectiva. Isto significa que algún membro T de P (S), é dicir, un subconxunto de S, non é a imaxe de f. Como exemplo, considere o seguinte conxunto:

 T = { s ∈ S: s ∉ f (s) }.

Para todo s en S, ou s está en T ou non. Se s está en T, entón por definición de T, s non está en f(s), polo que T non é igual a f(s). Por outra banda, se s non está en T, entón por definición de T, s está en f(s), polo que de novo T non é igual a f(s). Para unha descrición máis completa desta demostración, consulte o teorema de Cantor.

 Consecuencias 
Este resultado implica que a noción do conxunto de todos os conxuntos é unha noción inconsistente. Se S fose o conxunto de todos os conxuntos, entón P (S) sería maior que S e un subconxunto de S.

O paradoxo de Russell demostrounos que a inxenua teoría de conxuntos, baseada nun esquema de comprensión sen restricións, é contraditoria. Teña en conta que existe unha semellanza entre a construción de T e o conxunto do paradoxo de Russell. Polo tanto, dependendo de como modifiquemos o esquema axiomático da comprensión para evitar o paradoxo de Russell, argumentos como a inexistencia dun conxunto de todos os conxuntos poden seguir sendo válidos ou non.

O argumento da diagonalización mostra que o conxunto de números reais é "maior" que o conxunto de números naturais (e polo tanto tamén o conxunto de números enteiros e racionais). Polo tanto, podemos preguntarnos se existe un conxunto cuxa cardinalidade estea "entre" a dos números enteiros e os números reais. Esta pregunta leva á hipótese do continuo. Do mesmo xeito, a cuestión de se existe un conxunto cuxa cardinalidade estea entre |S| e |P (S)| para algún infinito S leva á hipótese do continuo xeneralizada.
 Notas 


 Véxase tamén 
 Bibliografía 





 Outros artigos 
 Primeiro artigo de teoría de conxuntos de Cantor.
 Ligazóns externas 
Cantor's Diagonal Proof em MathPages

Categoría:Teoría de conxuntos
Categoría:Wikipedia:Páxinas con traducións non revisadas