Sus teoremas de incompletitud derrotaron la búsqueda de una teoría matemática del todo. Casi cien años después, todavía estamos tratando de comprender las consecuencias de esto.
En 1931, el lógico austriaco Kurt Gödel llevó a cabo posiblemente uno de los trucos intelectuales más asombrosos de la historia.
Los matemáticos de esa época buscaban los fundamentos inquebrantables de las matemáticas: un conjunto de hechos básicos, axiomas que fueran consistentes y completos, desempeñando el papel de los bloques de construcción de todas las verdades matemáticas.
Sin embargo, los impactantes teoremas de incompletitud de Gödel, publicado por él con tan solo 25 años, hizo añicos este sueño. Demostró que cualquier conjunto de axiomas que puedas proponer como fundamento de las matemáticas será inevitablemente incompleto. Siempre habrá afirmaciones verdaderas sobre los números que no se puedan probar usando estos axiomas. También mostró que ningún conjunto de axiomas puede usarse para probar su propia consistencia.
Sus teoremas de incompletitud significan que no puede haber una teoría matemática de todo, y es imposible combinar el conjunto de enunciados demostrables con el conjunto de los verdaderos. Lo que los matemáticos pueden probar depende de suposiciones iniciales, no de alguna verdad fundamental de la que se originan todas las respuestas.
En los 89 años transcurridos desde el descubrimiento de Gödel, los matemáticos se han topado con preguntas similares sin respuesta, cuya existencia predecían sus teoremas. Por ejemplo, el propio Gödel ayudó a establecer que la hipótesis del continuo sobre las cardinalidades de los infinitos es indecidible, al igual que el problema de la parada., en el que se requiere determinar si la ejecución de un programa de computadora terminará alguna vez con ciertos datos de entrada, o se ejecutará para siempre. Surgieron preguntas sin solución incluso en física , lo que sugiere que la insuficiencia de Gödel afecta no solo a las matemáticas, sino en algún sentido (no del todo claro) a la realidad.
Lo que sigue es un resumen breve, simplificado e informal de cómo Gödel demostró sus teoremas.
Numeración de Gödel
El movimiento principal de Gödel fue comparar declaraciones relativas al sistema de axiomas con declaraciones realizadas dentro de este sistema, con declaraciones relativas a números. Esta yuxtaposición permite que el sistema de axiomas razone con calma sobre sí mismo.
El primer paso es hacer coincidir cualquier posible enunciado matemático, o secuencia de enunciados, con un número único llamado número de Gödel .
Una versión ligeramente revisada de la numeración de Gödel como se presenta en el libro de 1958 La prueba de Gödel de Ernest Nagel y James Newman, comienza con 12 símbolos elementales, que sirven como diccionario para expresar un conjunto de axiomas básicos. Por ejemplo, un enunciado sobre la existencia de algo se puede expresar con el símbolo ∃ y la suma con el símbolo +. La s, que significa "elemento siguiente", permite denotar números: por ejemplo, ss0 significa dos.
A estos doce caracteres se les asignan los números de Gödel del 1 al 12.
| Notación constante | Numeración de Gödel | Significado común |
| ~ | 1 | no |
| ∨ | 2 | o |
| ⊃ | 3 | si ... entonces ... |
| ∃ | 4 | existe |
| = | cinco | es igual a |
| 0 | 6 | cero |
| s | 7 | proximo articulo |
| ( | 8 | signo de puntuación |
| ) | nueve | signo de puntuación |
| , | diez | signo de puntuación |
| + | once | un plus |
| × | 12 | multiplicar |
Luego, las letras que denotan variables, comenzando con x, y y z, se emparejan con números primos mayores que 12 (13, 17, 19, ..).
Luego, cada una de las combinaciones de estos símbolos y variables, es decir, cualquier fórmula aritmética o secuencia de fórmulas que se pueda inventar, obtiene su propio número de Gödel.
Considere, por ejemplo, el enunciado 0 = 0. Sus tres símbolos corresponden a los números 6, 5 y 6 de Gödel. Gödel necesita reemplazar esta secuencia de tres números con uno único, un número que ninguna otra secuencia de símbolos producirá. Para hacer esto, toma los primeros tres números primos (2, 3 y 5), eleva cada uno de ellos a la potencia igual al número correspondiente en la secuencia y los multiplica. Entonces 0 = 0 se convierte en 2 6 × 3 5 × 56 , o 243 000 000.
Este marcado funciona porque no hay dos fórmulas que den el mismo número de Gödel. Los números de Gödel son números enteros y los números se pueden descomponer en factores primos de una sola manera. Por tanto, la única forma de factorizar 243.000.000 en factores es 2 6 × 3 5 × 5 6 , es decir, solo hay una forma de descifrar este número de Gödel: escribiendo la fórmula 0 = 0.
Entonces Gödel fue aún más lejos. Una prueba matemática consta de una secuencia de fórmulas. Por lo tanto, Gödel asignó a cada secuencia de fórmulas su propio número de Gödel. En este caso, también comienza con una secuencia de números primos: 2, 3, 5, etc. Luego eleva cada uno de ellos a la potencia correspondiente al número de Gödel de la fórmula en la misma posición ordinal en la secuencia (digamos, 2,243,000,000 , si la primera fórmula es 0 = 0), y multiplica todo junto.
Matemática aritmética
Es notable que incluso las declaraciones sobre fórmulas aritméticas, las llamadas. Los enunciados metamatemáticos se pueden traducir a fórmulas y asignarles sus propios números de Gödel.
Considere primero la fórmula ~ (0 = 0), que significa que "cero no es cero". Claramente es falso. Sin embargo, tiene un número de Gödel: 2 elevado a 1 (número de Gödel para el carácter ~), multiplicado por 3 elevado a la octava potencia (número de Gödel para el paréntesis izquierdo), y así sucesivamente, lo que finalmente da 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 .
Dado que podemos generar números de Gödel para todas las fórmulas, incluso las falsas, podemos razonar sobre ellas de manera significativa usando sus números de Gödel.
Considere el enunciado "El primer carácter de la fórmula ~ (0 = 0) es una tilde". Esta verdadera afirmación metamatemática sobre ~ (0 = 0) se convierte en una afirmación sobre el número de Gödel de una fórmula en particular, es decir, que su primer grado es 1, es decir, el número de Gödel para la tilde. En otras palabras, nuestro enunciado dice que solo hay un factor "2" en 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 . Si ~ (0 = 0) comenzara con cualquier carácter que no sea una tilde, su número GG tendría al menos dos factores de 2. Entonces, para decirlo con más precisión, 2 es un factor de 2 1 × 3 8 × 5 6 × 7 5× 11 6 × 13 9 , pero 2 2 no lo es.
Podemos convertir la última oración en una fórmula matemática exacta y escribirla usando símbolos elementales. Esta fórmula tendrá naturalmente su propio número de Gödel, que podemos calcular haciendo coincidir sus símbolos con las potencias de los números primos.
Si está interesado, la formulación resulta así: hay un número entero x tal que x, multiplicado por 2, será igual a 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , pero no existe un número entero x tal que multiplicado por 4 dio 2 1 × 3 8 × 5 6× 7 5 × 11 6 × 13 9 . La fórmula correspondiente se ve así:
(∃x) (x × ss0 = sss… sss0) ⋅ ~ (∃x) (x × ssss0 = sss… sss0)
Donde sss… sss0 significa 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 copias del carácter del siguiente elemento s. El símbolo ⋅ significa "y", y es una notación más corta del vocabulario fundamental: p ⋅ q significa ~ (~ p ∨ ~ q).
Este ejemplo, como escribieron Nagel y Newman, “ilustra una idea general y profunda que subyace al descubrimiento de Gödel: podemos hablar con mucha precisión sobre las propiedades tipográficas de largas secuencias de caracteres, pero no directamente, sino a través de las propiedades de la factorización de números enteros grandes.
Los enunciados metamatemáticos también se pueden transformar en símbolos. “Hay una cierta secuencia de fórmulas con el número de Gödel x, lo que demuestra una fórmula con el número de Gödel k” - o, en resumen, “una fórmula con el número de Gödel k es demostrable”. Fue la capacidad de "aritmética" tales declaraciones lo que sentó las bases del golpe.
G por sí mismo
Además, Gödel se dio cuenta de que era posible sustituir el propio número de Gödel, que denota una fórmula, en la fórmula misma, y esto ya conduce a un sinfín de problemas.
Para entender cómo funciona esta sustitución, considere la fórmula (∃x) (x = sy). Significa “hay una variable x que es el siguiente elemento de y”, o, más simplemente, “y '' '' tiene el siguiente elemento”. Como todas las fórmulas, tiene su propio número de Gödel, un entero grande, llamémoslo m.
Ahora ingresaremos el número m en la fórmula en lugar del símbolo y. El resultado es una nueva fórmula (∃x) (x = sm), lo que significa que "m tiene el siguiente elemento". ¿Cuál es el número de Gödel para esta fórmula? Necesitamos transmitir tres características: comenzamos con una fórmula que tiene el número m de Gödel. En él, reemplazamos el símbolo y con el símbolo m. Y, según el esquema de comparación descrito anteriormente, el número de Gödel del símbolo y es 17. Denotemos entonces el número de Gödel de la nueva fórmula sub (m, m, 17).
La sustitución constituye la base de la demostración de Gödel.
Estudiante Kurt Gödel en Viena. Publicó Teoremas de incompletitud en 1931, un año después de recibir su diploma.
Consideró el siguiente enunciado matemático: "La fórmula con el número de Gödel sub (y, y, 17) no se puede probar". Recordando la notación que acabamos de adoptar, sabemos que obtenemos la fórmula con el número de Gödel sub (y, y, 17) tomando la fórmula con el número de Gödel y (alguna variable desconocida) y sustituyendo esta variable y siempre que haya un símbolo en la fórmula. Número de Gödel 17 (es decir, dondequiera que ocurra y).
La cabeza ya está empezando a girar, pero, sin embargo, definitivamente podemos traducir nuestro enunciado metamatemático, “una fórmula con el número de Gödel sub (y, y, 17) no se puede probar”, en una fórmula con un número de Gödel único. Llamémoslo n.
Y la última etapa de sustituciones: Gödel crea una nueva fórmula, sustituyendo el número n donde aparece y en la fórmula anterior. Su nueva fórmula es la siguiente: “La fórmula con el número sub (n, n, 17) de Gödel no se puede probar”. Llamemos a esta fórmula G.
G naturalmente tiene un número de Gödel. ¿Cual es este numero? Voila - debería ser sub (n, n, 17). Por definición, sub (n, n, 17) es el número de Gödel para la fórmula, que se obtiene tomando la fórmula con el número de Gödel ny sustituyendo n siempre que aparezca un símbolo con el número de Gödel igual a 17 en la fórmula. Y G es exactamente esa fórmula y ¡Ahi esta! Dado que los números enteros se descomponen en factores primos de una manera única, nos queda claro que la Fórmula G solo nos dice sobre la Fórmula G en sí, y nada más.
G dice que no se puede probar en sí mismo.
Pero, ¿se puede probar G? Si fuera posible, significaría que hay alguna secuencia de fórmulas que prueben una fórmula con el número de Gödel sub (n, n, 17). Pero esto es lo opuesto a la Fórmula G, que dice que no existe tal prueba. Los enunciados opuestos, G y ~ G, en un sistema consistente de axiomas no pueden ser simultáneamente verdaderos. Por tanto, G debe ser indemostrable.
Sin embargo, aunque no se puede probar G, definitivamente es cierto. G dice que “la fórmula con el número de Gödel sub (n, n, 17) no se puede probar”, ¡que es exactamente lo que hemos establecido! Dado que G es un enunciado verdadero pero no demostrable que existe dentro del sistema axiomático que usamos para construirlo, este sistema está incompleto.
Podría pensar que podemos simplemente agregar algún axioma adicional, usarlo para probar G y resolver esta paradoja. Pero esto es imposible. Gödel demostró que el sistema aumentado de axiomas permitirá crear una nueva fórmula verdadera G 'de acuerdo con el mismo esquema que antes, lo que no puede probarse en el marco del nuevo sistema aumentado. Al intentar construir un sistema matemático completo, solo perseguirá su propia cola sin éxito.
Falta de prueba de coherencia
Ahora sabemos que si un conjunto de axiomas es consistente, está incompleto. Este es el primer teorema de incompletitud de Gödel. El segundo se deriva fácilmente de él: ningún conjunto de axiomas puede probar su consistencia.
¿Qué significaría si un conjunto de axiomas pudiera probar que nunca sería controvertido? Esto significaría que hay una secuencia de fórmulas construidas sobre estos axiomas, probando una fórmula que metamatemáticamente significa “este conjunto de axiomas es consistente”. Pero entonces, según el primer teorema, este conjunto de axiomas sería necesariamente incompleto.
Sin embargo, decir que “el conjunto de axiomas está incompleto” es lo mismo que decir “hay una fórmula verdadera que no se puede probar”. Y esto es equivalente a nuestra fórmula G. Y sabemos que los axiomas no pueden probar G.
Entonces Gödel construyó una prueba por contradicción: si un conjunto de axiomas pudiera probar su propia consistencia, entonces podríamos probar G. Pero no podemos. En consecuencia, ningún conjunto de axiomas prueba su propia consistencia.
La demostración de Gödel acabó con la búsqueda de un sistema matemático completo y consistente. Los matemáticos “no lograron captar toda la profundidad” de lo incompleto, escribieron Nagel y Newman en 1958. Y hoy esta afirmación sigue siendo cierta.
Ver también: