El argumento diagonal de Cantor (entre otros nombres similares [nota 1] ) es una prueba matemática de que existen conjuntos infinitos que no pueden ponerse en correspondencia biunívoca con el conjunto infinito de números naturales ; informalmente, que existen conjuntos que en cierto sentido contienen más elementos que números enteros positivos. Dichos conjuntos se denominan ahora conjuntos incontables , y el tamaño de los conjuntos infinitos se trata en la teoría de los números cardinales , que inició Cantor.
Georg Cantor publicó esta prueba en 1891, [1] [2] : 20– [3] pero no fue su primera prueba de la incontabilidad de los números reales , que apareció en 1874. [4] [5] Sin embargo, demuestra una técnica general que desde entonces se ha utilizado en una amplia gama de pruebas, [6] incluyendo el primero de los teoremas de incompletitud de Gödel [2] y la respuesta de Turing al Entscheidungsproblem . Los argumentos de diagonalización son a menudo también la fuente de contradicciones como la paradoja de Russell [7] [8] y la paradoja de Richard . [2] : 27
Cantor consideró el conjunto T de todas las secuencias infinitas de dígitos binarios (es decir, cada dígito es cero o uno). [nota 2] Comienza con una prueba constructiva del siguiente lema :
La prueba comienza con una enumeración de elementos de T , por ejemplo
A continuación, se construye una secuencia s eligiendo el primer dígito como complementario del primer dígito de s 1 (intercambiando 0 por 1 y viceversa), el segundo dígito como complementario del segundo dígito de s 2 , el tercer dígito como complementario del tercer dígito de s 3 y, en general, para cada n , el n -ésimo dígito como complementario del n -ésimo dígito de s n . Para el ejemplo anterior, esto da como resultado
Por construcción, s es un miembro de T que difiere de cada s n , ya que sus n dígitos difieren (resaltados en el ejemplo). Por lo tanto, s no puede aparecer en la enumeración.
Basándose en este lema, Cantor utiliza entonces una prueba por contradicción para demostrar que:
La prueba comienza suponiendo que T es numerable . Entonces todos sus elementos pueden escribirse en una enumeración s 1 , s 2 , ... , s n , ... . La aplicación del lema anterior a esta enumeración produce una secuencia s que es un miembro de T , pero no está en la enumeración. Sin embargo, si T está enumerado, entonces cada miembro de T , incluido este s , está en la enumeración. Esta contradicción implica que la suposición original es falsa. Por lo tanto, T es incontable. [1]
La incontabilidad de los números reales ya fue establecida por la primera prueba de incontabilidad de Cantor , pero también se deduce del resultado anterior. Para demostrarlo, se construirá una inyección a partir del conjunto T de cadenas binarias infinitas al conjunto R de números reales. Como 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 o .
Una inyección de T a R se da al mapear cadenas binarias en T a fracciones decimales , como al 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 base b : 0.0111... b . Esto lleva a la familia de funciones: f b ( t ) = 0. t b . Las funciones f b ( t ) son inyecciones, excepto f 2 ( 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 el teorema de Cantor : para cada conjunto S , el conjunto potencia de S —es decir, el conjunto de todos los subconjuntos de S (escrito aquí como P ( S ))— no puede estar en biyección con el propio S. Esta demostración se realiza 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, considere el conjunto:
Para cada s en S , 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 nuevamente T no es igual a f ( s ); cf. figura. Para una explicación más completa de esta prueba, véase el teorema de Cantor .
Con la igualdad definida como la existencia de una biyección entre sus conjuntos subyacentes, Cantor también define predicado binario de cardinalidades y en términos de la existencia de inyecciones entre y . Tiene las propiedades de un preorden y aquí se escribe " ". Uno puede incrustar los naturales en las secuencias binarias, probando así explícitamente varias afirmaciones de existencia de inyección , de modo que en este sentido , donde denota el espacio de funciones . 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 , donde " " 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 en este sentido, como se ha demostrado, y al mismo tiempo es el caso de que , para todos los conjuntos .
Suponiendo la ley del medio excluido , las funciones características sobreyectan sobre conjuntos potencia, y entonces . Por lo tanto, lo incontable tampoco es enumerable y también se puede mapear sobre . Clásicamente, el teorema de Schröder-Bernstein es válido y dice que dos conjuntos cualesquiera que estén en la imagen inyectiva uno del otro también están en biyección. Aquí, cada subconjunto no acotado de está entonces en biyección consigo mismo, y cada conjunto subcontable (una propiedad en términos de sobreyecciones) es entonces ya contable, es decir, en la imagen sobreyectiva de . En este contexto, las posibilidades se agotan, haciendo " " un orden parcial no estricto , o incluso un orden total al suponer la elección . El argumento diagonal establece así que, aunque ambos conjuntos en consideración son infinitos, hay en realidad más secuencias infinitas de unos y ceros que números naturales. El resultado de Cantor implica entonces también que la noción de conjunto de todos los conjuntos es inconsistente: si fuera el conjunto de todos los conjuntos, entonces sería al mismo tiempo mayor que y un subconjunto de .
También en matemáticas constructivas , no hay sobreyección desde el dominio completo hacia el espacio de funciones o hacia la colección de subconjuntos , es decir, estas dos colecciones son incontables. Nuevamente, utilizando " " para demostrar la existencia de inyección junto con la ausencia de biyección, se tiene y . Además, , como se señaló anteriormente. Asimismo, , y por supuesto , también en la teoría de conjuntos constructivos .
Sin embargo, es más difícil o imposible ordenar ordinales y también cardinales, de manera constructiva. Por ejemplo, el teorema de Schröder-Bernstein requiere la ley del medio excluido. [10] De hecho, el ordenamiento estándar de los reales, que extiende el ordenamiento de los números racionales, tampoco es necesariamente decidible. Tampoco son decidibles la mayoría de las propiedades de clases interesantes de funciones, por el teorema de Rice , es decir, el conjunto de números contables para los conjuntos subcontables puede no ser recursivo y, por lo tanto, puede dejar de ser contable. La elaborada colección de subconjuntos de un conjunto no es constructivamente intercambiable con la colección de sus funciones características. En un contexto por lo demás constructivo (en el que la ley del medio excluido no se toma como axioma), es coherente adoptar axiomas no clásicos que contradigan las consecuencias de la ley del medio excluido. Se puede afirmar que conjuntos incontables como o son subcontables . [11] [12] Esta es una noción de tamaño que es redundante en el contexto clásico, pero que de otro modo no necesariamente implica contabilidad. La existencia de inyecciones desde lo incontable o hacia dentro también es posible aquí. [13] Por lo tanto, la relación cardinal no es antisimétrica . En consecuencia, incluso en presencia de conjuntos de espacios de funciones que son incluso clásicamente incontables, los intuicionistas no aceptan que esta relación constituya una jerarquía de tamaños transfinitos. [14] Cuando no se adopta el axioma de conjunto-potencia , en un marco constructivo incluso la subcontabilidad de todos los conjuntos es entonces consistente. Dicho todo esto, en las teorías de conjuntos comunes, la no existencia de un conjunto de todos los conjuntos también se sigue ya de la separación predicativa .
En una teoría de conjuntos, las teorías de las matemáticas se modelan . Los axiomas lógicos más débiles significan menos restricciones y, por lo tanto, permiten una clase más rica de modelos. Un conjunto puede identificarse como un modelo del campo de números reales cuando cumple algunos axiomas de números reales o una reformulación constructiva de los mismos. Se han estudiado varios modelos, como los reales de Cauchy o los reales de Dedekind , entre otros. Los primeros se relacionan con cocientes de secuencias, mientras que los últimos son cortes bien comportados tomados de un conjunto potencia, si existen. En presencia de un medio excluido, todos son isomorfos e incontables. De lo contrario, las variantes de los reales de Dedekind pueden ser contables [15] o inyectarse en los naturales, pero no conjuntamente. Al suponer una elección contable , los reales de Cauchy constructivos incluso sin un módulo de convergencia explícito son entonces Cauchy-completos [16] y los reales de Dedekind se simplifican para volverse isomorfos a ellos. De hecho, aquí la elección también ayuda a las construcciones diagonales y, al asumirla, los modelos Cauchy-completos de los reales son incontables.
Motivados por la idea de que el conjunto de los números reales es "mayor" que el conjunto de los números naturales, nos vemos obligados a preguntarnos si existe un conjunto cuya cardinalidad esté "entre" la de los números enteros y la de los reales. Esta pregunta nos lleva a la famosa hipótesis del continuo . De manera similar, la pregunta de si existe un conjunto cuya cardinalidad esté entre | S | y | P ( S )| para algún infinito S nos lleva a la hipótesis generalizada del continuo .
La paradoja de Russell ha demostrado que la teoría de conjuntos que incluye un esquema de comprensión sin restricciones es contradictoria. Nótese que existe una 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.
Los análogos del argumento diagonal se utilizan ampliamente en matemáticas para demostrar la existencia o inexistencia de ciertos objetos. Por ejemplo, la prueba convencional de la insolubilidad del problema de la detención 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 jugó un papel clave en los primeros intentos de demostrar que P no es igual a NP .
La prueba anterior falla para la teoría de conjuntos de los " Nuevos Fundamentos " de WV Quine (NF). En NF, el esquema axiomático ingenuo de comprensión se modifica para evitar las paradojas mediante la introducción de una especie de teoría de tipos "local" . En este esquema axiomático,
no es un conjunto, es decir, no satisface el esquema axiomático. Por otra parte, podríamos intentar crear un argumento diagonal modificado observando que
es un conjunto en NF. En cuyo caso, si P 1 ( S ) es el conjunto de subconjuntos de un elemento de S y f es una biyección propuesta de P 1 ( S ) a P ( S ), se puede usar la prueba por contradicción para demostrar que | P 1 ( S )| < | P ( S )|.
La prueba se deduce del hecho de que si f fuera de hecho una función sobre P ( S ), entonces podríamos hallar r en S , de modo que f ({ r }) coincida con el conjunto diagonal modificado, arriba. Concluiríamos que si r no está en f ({ r }), entonces r está en f ({ r }) y viceversa.
No es posible poner P 1 ( S ) en una relación uno a uno con S , ya que los dos tienen tipos diferentes y, por lo tanto, cualquier función así definida violaría las reglas de tipificación del esquema de comprensión.
