El argumento diagonal de Cantor

La incontableidad de los números reales ya fue establecida por la primera prueba de incontableidad de Cantor , pero también se deduce del resultado anterior. Para probar esto, se construirá una inyección del conjunto T de cadenas binarias infinitas al conjunto R de números reales. Dado que T es incontable, la imagen de esta función, que es un subconjunto de R , es incontable. Por lo tanto, R es incontable. Además, utilizando un método de construcción ideado por Cantor, se construirá una biyección entre T y R. Por lo tanto, T y R tienen la misma cardinalidad, que se llama " cardinalidad del continuo " y se suele denotar por${\displaystyle {\mathfrak {c}}}$o${\displaystyle 2^{\aleph _ {0}}}$.

Una inyección de T a R se obtiene mapeando cadenas binarias en T a fracciones decimales , como mapear t  =  0111... al decimal 0.0111.... Esta función, definida por f ( t ) = 0. t , es una inyección porque mapea diferentes cadenas a diferentes números. ^{[ nota 4 ]}

Construir una biyección entre T y R es un poco más complicado. En lugar de mapear 0111... al decimal 0.0111..., se puede mapear al número en base b : 0.0111... _b . Esto lleva a la familia de funciones: f _b ( t ) = 0. t _b . Las funciones f _b ( t ) son inyectivas, excepto f ₂ ( t ) . Esta función se modificará para producir una biyección entre T y R.

Cantor utilizó una forma generalizada del argumento diagonal para demostrar su teorema : para todo conjunto S , el conjunto potencia de S —es decir, el conjunto de todos los subconjuntos de S (que aquí se escribe como P ( S ))— no puede estar en biyección con S mismo. Esta demostración procede de la siguiente manera:

Sea f una función cualquiera de S a P ( S ). Basta con demostrar que f no puede ser sobreyectiva . Esto significa que algún miembro T de P ( S ), es decir, algún subconjunto de S , no está en la imagen de f . Como candidato, consideremos el conjunto

${\displaystyle T=\{s\in S:s\notin f(s)\}.}$

Para cada s en S , o bien s está en T o no. Si s está en T , entonces, por definición de T , s no está en f ( s ), por lo que T no es igual a f ( s ). Por otro lado, si s no está en T , entonces, por definición de T , s está en f ( s ), por lo que, de nuevo, T no es igual a f ( s ); véase la imagen.

Para una explicación más completa de esta demostración, consulte el teorema de Cantor .

Con la igualdad definida como la existencia de una biyección entre sus conjuntos subyacentes, Cantor también define el predicado binario de cardinalidades.${\displaystyle |S|}$y${\displaystyle |T|}$en términos de la existencia de inyecciones entre${\displaystyle S}$y${\displaystyle T}$. Tiene las propiedades de un preorden y aquí está escrito "${\displaystyle \leq }$". Se pueden incrustar los números naturales en las secuencias binarias, demostrando así explícitamente varias afirmaciones de existencia por inyección , de modo que en este sentido${\displaystyle |{\mathbb {N} }|\leq |2^{\mathbb {N} }|}$, dónde${\displaystyle 2^{\mathbb {N} }}$denota el espacio de funciones${\displaystyle {\mathbb {N} }\to \{0,1\}}$. Pero, siguiendo el argumento de las secciones anteriores, no hay sobreyección y, por lo tanto, tampoco biyección, es decir, el conjunto es incontable. Para esto se puede escribir${\displaystyle |{\mathbb {N} }|<|2^{\mathbb {N} }|}$, dónde "${\displaystyle <}$" se entiende que significa la existencia de una inyección junto con la ausencia probada de una biyección (a diferencia de alternativas como la negación del preorden de Cantor o una definición en términos de ordinales asignados ). También${\displaystyle |S|<|{\mathcal {P}}(S)|}$en este sentido, como se ha demostrado, y al mismo tiempo es cierto que${\displaystyle \neg (|{\mathcal {P}}(S)|\leq |S|)}$, para todos los conjuntos${\displaystyle S}$.

Suponiendo la ley del tercero excluido , las funciones características se proyectan sobre conjuntos potencia, y luego${\displaystyle |2^{S}|=|{\mathcal {P}}(S)|}$. Entonces, los incontables${\displaystyle 2^{\mathbb {N} }}$tampoco es enumerable y también se puede mapear a${\displaystyle {\mathbb {N} }}$Clásicamente, el teorema de Schröder-Bernstein es válido y afirma que dos conjuntos cualesquiera que sean imágenes inyectivas entre sí también son biyectivos. Aquí, todo subconjunto no acotado de${\displaystyle {\mathbb {N} }}$entonces está en biyección con${\displaystyle {\mathbb {N} }}$en sí mismo, y todo conjunto subcontable (una propiedad en términos de sobreyecciones) es entonces ya contable, es decir, en la imagen sobreyectiva de${\displaystyle {\mathbb {N} }}$. En este contexto, las posibilidades se agotan, haciendo "${\displaystyle \leq }$"un orden parcial no estricto , o incluso un orden total al asumir la elección . El argumento diagonal establece así que, aunque ambos conjuntos considerados son infinitos, en realidad hay más secuencias infinitas de unos y ceros que números naturales. El resultado de Cantor también implica que la noción del conjunto de todos los conjuntos es inconsistente: Si${\displaystyle S}$eran el conjunto de todos los conjuntos, entonces${\displaystyle {\mathcal {P}}(S)}$sería al mismo tiempo más grande que${\displaystyle S}$y un subconjunto de${\displaystyle S}$.

La paradoja de Russell ha demostrado que la teoría de conjuntos que incluye un esquema de comprensión irrestricto es contradictoria. Cabe destacar la similitud entre la construcción de T y el conjunto en la paradoja de Russell. Por lo tanto, dependiendo de cómo modifiquemos el esquema axiomático de comprensión para evitar la paradoja de Russell, argumentos como la no existencia de un conjunto de todos los conjuntos pueden o no seguir siendo válidos.

En matemáticas, se utilizan ampliamente análogos del argumento diagonal para demostrar la existencia o inexistencia de ciertos objetos. Por ejemplo, la demostración convencional de la irresolubilidad del problema de la parada es esencialmente un argumento diagonal. Además, la diagonalización se utilizó originalmente para demostrar la existencia de clases de complejidad arbitrariamente difíciles y desempeñó un papel clave en los primeros intentos de demostrar que P no es igual a NP .