Argumento de la diagonal de Cantor
En la teoría de conjuntos , Georg Cantor publicó en 1891 el argumento diagonal de Cantor , también llamado argumento de diagonalización , argumento de barra diagonal , argumento anti-diagonal , método diagonal y prueba de diagonalización de Cantor, como prueba matemática de que hay conjuntos infinitos. que no se puede poner en correspondencia biunívoca con el conjunto infinito de los números naturales . [1] [2] : 20– [3] Dichos conjuntos ahora se conocen como conjuntos incontables, y el tamaño de los conjuntos infinitos ahora es tratado por la teoría de los números cardinales que comenzó Cantor.
El argumento 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 Entscheidungsproblem . Los argumentos de diagonalización también son a menudo 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 1] Comienza con una demostración constructiva del siguiente lema :
A continuación, se construye una secuencia s eligiendo el primer dígito como complementario al primer dígito de s 1 (cambiando 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 complementaria de la 3ª cifra de s 3 , y generalmente para toda n , la n ésima cifra como complementaria de la n ésima cifra 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 n -ésimos dígitos difieren (resaltados en el ejemplo). Por lo tanto, s no puede ocurrir en la enumeración.
La prueba comienza suponiendo que T es contable . Entonces todos sus elementos se pueden escribir en una enumeración s 1 , s 2 , ... , s n , ... . Aplicando el lema anterior a esta enumeración se produce una secuencia s que es miembro de T , pero 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 lo tanto, T es incontable. [1]
