Argumento de diagonalización de Cantor

miniatura|325x325px| Unha ilustración do argumento de diagonalización de Cantor (na base 2) para a existencia de conxuntos incontábeis. A secuencia da parte inferior non pode aparecer en lugar ningún da enumeración de secuencias anteriores.
miniatura| Un conxunto infinito pode ter a mesma cardinalidade que un subconxunto de si mesmo, como demostra a bixección representada *f*(*x*)=2*x* 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. 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 *s*1, *s*2, ..., *s**n*, ... é calquera enumeración dos elementos de *T*, entón sempre hai un elemento *s* de *T* que non corresponde con ningún *s**n* 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 *s**n*, 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 *s*1, *s*2, …, *s**n*, … . 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 
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
*