En teoría de conjuntos , el argumento diagonal de Cantor , también llamado argumento de diagonalización , argumento de la barra diagonal , argumento antidiagonal , método diagonal y prueba de diagonalización de Cantor , fue publicado en 1891 por Georg Cantor como una prueba matemática de que existen conjuntos infinitos. que no se puede poner en correspondencia uno a uno con el conjunto infinito de números naturales . [1] [2] : 20– [3] Estos conjuntos ahora se conocen como conjuntos incontables , y el tamaño de los conjuntos infinitos ahora se trata mediante la teoría de los números cardinales que comenzó Cantor.
El argumento de la diagonal no fue la primera prueba de Cantor 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 problema de Entscheidungs . Los argumentos sobre la diagonalización son a menudo también 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 1] 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 al primer dígito de s 1 (intercambiando 0 s por 1 s y viceversa), el segundo dígito como complementario al segundo dígito de s 2 , el tercer dígito como complementario al tercer dígito de s 3 , y generalmente para cada n , el enésimo dígito como complementario al enésimo dígito de s n . Para el ejemplo anterior, esto produce
Por construcción, s es un miembro de T que difiere de cada s n , ya que sus enésimos dígitos difieren (resaltados en el ejemplo). Por tanto, s no puede aparecer en la enumeración.
Con base en este lema, Cantor utiliza una prueba por contradicción para demostrar que:
La demostración comienza suponiendo que T es contable . Entonces todos sus elementos se pueden escribir 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 miembro de T , pero que no está en la enumeración. Sin embargo, si se enumera T , entonces todos los miembros de T , incluido este s , están en la enumeración. Esta contradicción implica que la suposición original es falsa. Por 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 desprende del resultado anterior. Para demostrar esto, se construirá una inyección a partir del conjunto T de infinitas cadenas binarias 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 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 denomina " cardinalidad del continuo " y generalmente se denota por o .
Una inyección de T a R se realiza asignando cadenas binarias en T a fracciones decimales , como mapeando t = 0111... al decimal 0.0111.... Esta función, definida por f ( t ) = 0. t , es una inyección porque asigna diferentes cadenas a diferentes números. [nota 3]
Construir una biyección entre T y R es un poco más complicado. En lugar de asignar 0111... al decimal 0.0111..., se puede asignar 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 S mismo. Esta prueba procede de la siguiente manera:
Sea f cualquier función de S a P ( S ). Basta demostrar que f no puede ser sobreyectiva . Eso 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:
Por 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. imagen. Para una descripción más completa de esta prueba, 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 y en términos de la existencia de inyecciones entre y . Tiene las propiedades de un pedido anticipado y aquí está escrito " ". Se pueden incrustar los naturales en las secuencias binarias, demostrando así explícitamente varias declaraciones de existencia de inyección , de modo que, en este sentido , donde denota el espacio funcional . Pero siguiendo el argumento de las secciones anteriores, no hay sobreyección y, por tanto, tampoco hay biyección, es decir, el conjunto es incontable. Para ello se puede escribir , donde " " se entiende como la existencia de una inyección junto con la ausencia probada de una biyección (en contraposición a 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 se da el caso de que , para todos los conjuntos .
Suponiendo la ley del medio excluido , las funciones características se superponen a conjuntos de potencias, y luego . Por lo tanto, lo incontable tampoco es enumerable y también se puede asignar a . Clásicamente , el teorema de Schröder-Bernstein es válido y dice que dos conjuntos cualesquiera que estén en la imagen inyectiva el uno del otro también están en biyección. Aquí, cada subconjunto ilimitado de está entonces en biyección consigo mismo, y cada conjunto subcontable (una propiedad en términos de sobreyecciones) ya es contable, es decir, en la imagen sobreyectiva de . En este contexto las posibilidades se agotan entonces, convirtiéndose " " en un orden parcial no estricto , o incluso en un orden total cuando se supone la elección . El argumento de la 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 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 .
Además, en matemáticas constructivas , no hay sobreyección del dominio completo al espacio de funciones o a la colección de subconjuntos , es decir, estas dos colecciones son incontables. Nuevamente usando " " para la existencia comprobada 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 constructiva de conjuntos .
Sin embargo, es más difícil o imposible ordenar constructivamente los ordinales y también los cardenales. Por ejemplo, el teorema de Schröder-Bernstein requiere la ley del tercero excluido. [10] De hecho, el orden estándar de los reales, ampliando el orden de los números racionales, tampoco es necesariamente decidible. La mayoría de las propiedades de clases interesantes de funciones tampoco son decidibles según el teorema de Rice , es decir, el conjunto de números de conteo para los conjuntos subcontables puede no ser recursivo y, por lo tanto, puede no ser contable. La colección elaborada 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 tercero excluido no se toma como axioma), es coherente adoptar axiomas no clásicos que contradicen las consecuencias de la ley del tercero excluido. Conjuntos incontables como o pueden afirmarse que son subcontables . [11] [12] Esta es una noción de tamaño que es redundante en el contexto clásico, pero por lo demás no tiene por qué implicar contabilidad. Aquí también es posible la existencia de inyecciones de lo incontable o de lo incontable . [13] Entonces la relación cardinal no logra ser antisimétrica . En consecuencia, también en presencia de conjuntos de espacios funcionales 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 del conjunto de poderes , en un marco constructivo incluso la subcontabilidad de todos los conjuntos es consistente. Dicho todo esto, en las teorías de conjuntos comunes, la inexistencia de un conjunto de todos los conjuntos también se deriva de la separación predicativa .
En una teoría de conjuntos se modelan las teorías de las matemáticas . Los axiomas lógicos más débiles significan menos restricciones y, por lo tanto, permiten una clase de modelos más rica. Un conjunto puede identificarse como modelo del cuerpo de los números reales cuando cumple algunos axiomas de los números reales o una reformulación constructiva de los mismos. Se han estudiado diversos modelos, como los reales de Cauchy o los reales de Dedekind , entre otros. Los primeros se relacionan con cocientes de secuencias, mientras que los segundos son cortes de buen comportamiento tomados de un conjunto de poderes, si existen. En presencia de terceros excluidos, todos ellos son isomórficos e incontables. De lo contrario, las variantes de los reales de Dedekind pueden ser contables [15] o inyectarse en los naturales, pero no de forma conjunta. Cuando se supone 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 de reales completos de Cauchy son incontables.
Motivado por la idea de que el conjunto de números reales es "mayor" que el conjunto de números naturales, uno se ve llevado a preguntarse si existe un conjunto cuya cardinalidad esté "entre" la de los números enteros y la de los reales. Esta pregunta lleva a la famosa hipótesis del continuo . De manera similar, la cuestión de si existe un conjunto cuya cardinalidad esté entre | S | y | P ( S )| para algún S infinito conduce a la hipótesis del continuo generalizado .
La paradoja de Russell ha demostrado que la teoría ingenua de conjuntos , basada en un esquema de comprensión irrestricta , es contradictoria. Tenga en cuenta que existe una similitud entre la construcción de T y el conjunto de la paradoja de Russell. Por lo tanto, dependiendo de cómo modifiquemos el esquema de comprensión del axioma para evitar la paradoja de Russell, argumentos como la no existencia de un conjunto de todos los conjuntos pueden seguir siendo válidos o no.
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 mostrar la existencia de clases de complejidad arbitrariamente estrictas y jugó un papel clave en los primeros intentos de demostrar que P no es igual a NP .
La prueba anterior falla en el caso de la teoría de conjuntos (NF) " Nuevos fundamentos " de WV Quine . En NF, el ingenuo esquema de comprensión del axioma se modifica para evitar las paradojas mediante la introducción de una especie de teoría de tipos "local" . En este esquema de axioma,
no es un conjunto, es decir, no satisface el esquema del axioma. Por otro lado, podríamos intentar crear un argumento diagonal modificado notando 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 utilizar la prueba por contradicción para demostrar que | P 1 ( S )| < | P ( S )|.
La prueba se desprende del hecho de que si f fuera realmente un mapa de P ( S ), entonces podríamos encontrar 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 para el esquema de comprensión.
