¿Cuál es la cosa más espeluznante en matemáticas?

Teoremas de incompletitud de Gödel

Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1931. Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritméticas. los Teoremas de Incompletitud de Gödel son buenos candidatos.

Primer teorema de incompletitud de Gödel

Cualquier teoría aritmética recursiva que sea consistente es incompleta.

Segundo teorema de incompletitud de Gödel

En toda teoría aritmética recursiva consistente T, la fórmula Consistente T no es un teorema.

En 1931, el lógico austríaco Kurt Gödel logró posiblemente uno de los logros intelectuales más impresionantes de la historia.

Los matemáticos de la época buscaban una base sólida para las matemáticas: un conjunto de hechos matemáticos básicos, o axiomas, que fuera consistente, nunca condujera a contradicciones, y completo, sirviendo como los bloques de construcción de todas las verdades matemáticas.

Pero los impactantes teoremas de incompletitud de Gödel, publicados cuando solo tenía 25 años, aplastaron ese sueño. Él demostró que cualquier conjunto de axiomas que pueda plantear como posible base para las matemáticas será inevitablemente incompleto; siempre habrá hechos verdaderos sobre los números que no pueden ser probados por esos axiomas. También demostró que ningún conjunto de axiomas candidato puede probar su propia consistencia. Sus teoremas de incompletitud significaron que no puede haber una teoría matemática de todo, ni una unificación de lo que es demostrable y lo que es verdad. Lo que los matemáticos pueden probar depende de sus suposiciones iniciales, no de ninguna verdad fundamental de la que surjan todas las respuestas.

En los 89 años desde el descubrimiento de Gödel, los matemáticos se han topado con el tipo de preguntas sin respuesta que predijeron sus teoremas. Por ejemplo, el propio Gödel ayudó a establecer que la hipótesis del continuo , que se refiere a los tamaños del infinito, es indecidible, al igual que el problema de detención, que pregunta si un programa de computadora alimentado con una entrada aleatoria se ejecutará para siempre o finalmente se detendrá. Incluso han surgido preguntas indecisas en física , lo que sugiere que la incompletitud de Gödel afecta no solo a las matemáticas, sino, de alguna manera mal entendida, a la realidad.

Aquí hay un resumen informal simplificado de cómo Gödel demostró sus teoremas.

Numeración de Gödel

La principal maniobra de Gödel fue mapear declaraciones sobre un sistema de axiomas en declaraciones dentro del sistema, es decir, declaraciones sobre números. Este mapeo permite que un sistema de axiomas hable convincentemente sobre sí mismo.

El primer paso en este proceso es asignar cualquier posible enunciado matemático, o serie de enunciados, a un número único llamado número de Gödel.

La versión ligeramente modificada del esquema de Gödel presentada por Ernest Nagel y James Newman en su libro de 1958, Gödel's Proof , comienza con 12 símbolos elementales que sirven como vocabulario para expresar un conjunto de axiomas básicos. Por ejemplo, la afirmación de que algo existe puede expresarse con el símbolo ∃, mientras que la suma se expresa con +. Es importante destacar que el símbolo s , que denota "sucesor de", proporciona una forma de especificar números; ss 0, por ejemplo, se refiere a 2.

A estos doce símbolos se les asignan los números de Gödel del 1 al 12.

A continuación, las letras que representan variables, comenzando con x , y y z , se asignan a números primos mayores que 12 (es decir, 13, 17, 19, ...).

Entonces, cualquier combinación de estos símbolos y variables, es decir, cualquier fórmula aritmética o secuencia de fórmulas que se pueda construir, obtiene su propio número de Gödel.

Por ejemplo, considere 0 = 0. Los tres símbolos de la fórmula corresponden a los números 6, 5 y 6. de Gödel. Gödel necesita cambiar esta secuencia de tres números en un número único y único, un número que ninguna otra secuencia de símbolos generará. Para hacer esto, toma los primeros tres primos (2, 3 y 5), eleva cada uno al número Gödel del símbolo en la misma posición en la secuencia y los multiplica. Entonces

La asignación funciona porque no hay dos fórmulas que terminen con el mismo número de Gödel. Los números de Gödel son enteros, y los enteros solo se convierten en primos de una sola manera. Entonces, la única factorización prima de 243,000,000 es

lo que significa que solo hay una forma posible de decodificar el número de Gödel: la fórmula 0 = 0.

Gödel luego fue un paso más allá. Una prueba matemática consiste en una secuencia de fórmulas. Entonces Gödel le dio a cada secuencia de fórmulas un número único de Gödel también. En este caso, comienza con la lista de números primos como antes: 2, 3, 5, etc. Luego eleva cada primo al número de Gödel de la fórmula en la misma posición en la secuencia

y multiplica todo junto.

Aritmetización de la metamatemática

La verdadera bendición es que incluso las declaraciones sobre fórmulas aritméticas, llamadas declaraciones metamatemáticas, pueden traducirse en fórmulas con números de Gödel propios.

Primero considere la fórmula ~ (0 = 0), que significa "cero no es igual a cero". Esta fórmula es claramente falsa. Sin embargo, tiene un número de Gödel: 2 elevado a la potencia de 1 (el número de Gödel del símbolo ~), multiplicado por 3 elevado a la potencia de 8 (el número de Gödel del símbolo de "paréntesis abierto"), y así sucesivamente , produciendo

Como podemos generar números de Gödel para todas las fórmulas, incluso las falsas, podemos hablar con sensatez acerca de estas fórmulas al hablar de sus números de Gödel.

Podemos convertir la última oración en una fórmula aritmética precisa que podamos escribir * usando símbolos elementales. Esta fórmula, por supuesto, tiene un número de Gödel, que podríamos calcular mapeando sus símbolos en potencias de primos.

Este ejemplo, escribieron Nagel y Newman, "ejemplifica una visión muy general y profunda que se encuentra en el corazón del descubrimiento de Gödel: las propiedades tipográficas de largas cadenas de símbolos se pueden hablar de manera indirecta pero perfectamente precisa al hablar de las propiedades de factorizaciones primas de enteros grandes ".

La conversión en símbolos también es posible para el enunciado metamatemático: "Existe una secuencia de fórmulas con el número de Gödel x que prueba la fórmula con el número de Gödel k " o, en resumen, "la fórmula con el número de Gödel k se puede probar". La capacidad de "aritmetizar" este tipo de afirmación preparó el escenario para el golpe.

G mismo

La idea adicional de Gödel era que podía sustituir el número de Gödel de una fórmula en la fórmula misma, lo que llevaría a un sinfín de problemas.

Para ver cómo funciona la sustitución, considere la fórmula (∃ x ) ( x = sy). (Se lee: "Existe una variable x que es el sucesor de y " o, en resumen, " y tiene un sucesor".) Al igual que todas las fórmulas, tiene un número de Gödel: algún número entero grande que llamaremos m .

Ahora introduzcamos m en la fórmula en lugar del símbolo y . Esto forma una nueva fórmula, (∃ x ) ( x = sm ), que significa " m tiene un sucesor". ¿Cómo llamaremos al número de Gödel de esta fórmula? Hay tres piezas de información para transmitir: Comenzamos con la fórmula que tiene el número m de Gödel . En él, sustituimos m por el símbolo y . Y de acuerdo con el esquema de mapeo presentado anteriormente, el símbolo y tiene el número Gödel 17. Entonces, designemos el número sub de Gödel de la nueva fórmula ( m , m , 17).

La sustitución forma el quid de la prueba de Gödel.

Consideró una declaración metamatemática en la línea de "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 aprender, la fórmula con el número de Gödel sub ( y , y , 17) es la obtenida tomando la fórmula con el número de Gödel y (alguna variable desconocida) y sustituyendo esta variable y en cualquier lugar donde haya un símbolo cuyo número de Gödel sea 17 (es decir, en cualquier lugar hay una y ).

Las cosas se están poniendo difíciles, pero sin embargo, nuestra declaración metamatemática: "La fórmula con el número de Gödel sub ( y , y , 17) no se puede probar", seguramente se traducirá en una fórmula con un número de Gödel único. Llamémoslo n .

Ahora, una última ronda de sustitución: Gödel crea una nueva fórmula sustituyendo el número n en cualquier lugar donde haya una y en la fórmula anterior. Su nueva fórmula dice: "La fórmula con el número de Gödel sub ( n , n , 17) no se puede probar". Llamemos a esta nueva fórmula G.

Naturalmente, G tiene un número de Gödel. ¿Cuál es su valor? Lo y he aquí, debe ser sub ( n , n , 17). Por definición, sub ( n , n , 17) es el número de Gödel de la fórmula que resulta de tomar la fórmula con el número de Gödel n y sustituir n en cualquier lugar donde haya un símbolo con el número de Gödel 17. ¡Y G es exactamente esta fórmula! Debido a la singularidad de la factorización prima, ahora vemos que la fórmula de la que habla G no es otra que la propia G.

G afirma de sí mismo que no se puede probar.

Pero, ¿se puede probar G? Si es así, esto significaría que hay alguna secuencia de fórmulas que prueba la fórmula con el número de Gödel sub ( n , n , 17). Pero eso es lo opuesto a G, que dice que no existe tal prueba. Las afirmaciones opuestas, G y ~ G, no pueden ser ciertas en un sistema axiomático consistente. Entonces la verdad de G debe ser indecidible.

Sin embargo, aunque G es indecidible, es claramente cierto. G dice: "La fórmula con el número de Gödel sub ( n , n , 17) no se puede probar", ¡y ese es exactamente el caso! Como G es verdadero pero indecidible dentro del sistema axiomático utilizado para construirlo, ese sistema está incompleto.

Podría pensar que podría plantear un axioma adicional, usarlo para probar G y resolver la paradoja. Pero no puedes. Gödel demostró que el sistema axiomático aumentado permitirá la construcción de una nueva fórmula verdadera Gʹ (de acuerdo con un plan similar al anterior) que no se puede probar dentro del nuevo sistema aumentado. Al luchar por un sistema matemático completo, nunca puedes atrapar tu propia cola.

Sin prueba de consistencia

Hemos aprendido que si un conjunto de axiomas es consistente, entonces está incompleto. Ese es el primer teorema de incompletitud de Gödel. El segundo, que ningún conjunto de axiomas puede demostrar su propia consistencia, se sigue fácilmente.

¿Qué significaría si un conjunto de axiomas pudiera demostrar que nunca arrojará una contradicción? Significaría que existe una secuencia de fórmulas construidas a partir de estos axiomas que demuestra la fórmula que significa, metamatemáticamente, "Este conjunto de axiomas es consistente". Según el primer teorema, este conjunto de axiomas estaría necesariamente incompleto.

Pero "El conjunto de axiomas está incompleto" es lo mismo que decir: "Hay una fórmula verdadera que no se puede probar". Esta afirmación es equivalente a nuestra fórmula G. Y sabemos que los axiomas no pueden probar G.

Entonces, Gödel ha creado una prueba por contradicción: si un conjunto de axiomas pudiera probar su propia consistencia, entonces podríamos probar G. Pero no podemos. Por lo tanto, ningún conjunto de axiomas puede probar su propia consistencia.

La prueba de Gödel mató la búsqueda de un sistema matemático completo y consistente. El significado de lo incompleto "no ha sido completamente comprendido", escribieron Nagel y Newman en 1958. Sigue siendo cierto hoy.