Los teoremas de incompletitud de Gödel son dos teoremas de lógica matemática que se ocupan de los límites de demostrabilidad en las teorías axiomáticas formales. Estos resultados, publicados por Kurt Gödel en 1931, son importantes tanto en lógica matemática como en filosofía de las matemáticas . Los teoremas se interpretan ampliamente, pero no universalmente, como una demostración de que el programa de Hilbert para encontrar un conjunto completo y consistente de axiomas para todas las matemáticas es imposible.
El primer teorema de incompletitud establece que ningún sistema consistente de axiomas cuyos teoremas puedan enumerarse mediante un procedimiento eficaz (es decir, un algoritmo ) es capaz de demostrar todas las verdades sobre la aritmética de los números naturales . Para cualquier sistema formal consistente de este tipo, siempre habrá afirmaciones sobre los números naturales que sean verdaderas, pero que no se puedan demostrar dentro del sistema.
El segundo teorema de incompletitud, una extensión del primero, muestra que el sistema no puede demostrar su propia consistencia.
Los teoremas de incompletitud de Gödel, que emplean un argumento diagonal , fueron los primeros de varios teoremas estrechamente relacionados sobre las limitaciones de los sistemas formales. Les siguieron el teorema de indefinibilidad de Tarski sobre la indefinibilidad formal de la verdad, la prueba de Church de que el Entscheidungsproblem de Hilbert es irresoluble y el teorema de Turing de que no existe un algoritmo para resolver el problema de la detención .
Los teoremas de incompletitud se aplican a sistemas formales que tienen la complejidad suficiente para expresar la aritmética básica de los números naturales y que son consistentes y efectivamente axiomatizados. Particularmente en el contexto de la lógica de primer orden , los sistemas formales también se denominan teorías formales . En general, un sistema formal es un aparato deductivo que consiste en un conjunto particular de axiomas junto con reglas de manipulación simbólica (o reglas de inferencia) que permiten la derivación de nuevos teoremas a partir de los axiomas. Un ejemplo de un sistema de este tipo es la aritmética de Peano de primer orden , un sistema en el que todas las variables están destinadas a denotar números naturales. En otros sistemas, como la teoría de conjuntos , solo algunas oraciones del sistema formal expresan afirmaciones sobre los números naturales. Los teoremas de incompletitud tratan sobre la demostrabilidad formal dentro de estos sistemas, en lugar de sobre la "demostrabilidad" en un sentido informal.
Un sistema formal puede tener varias propiedades, entre ellas la completitud, la consistencia y la existencia de una axiomatización efectiva. Los teoremas de incompletitud muestran que los sistemas que contienen una cantidad suficiente de aritmética no pueden poseer las tres propiedades.
Se dice que un sistema formal está efectivamente axiomatizado (también llamado efectivamente generado ) si su conjunto de teoremas es recursivamente enumerable . Esto significa que existe un programa informático que, en principio, podría enumerar todos los teoremas del sistema sin listar ningún enunciado que no sea teorema. Entre los ejemplos de teorías efectivamente generadas se incluyen la aritmética de Peano y la teoría de conjuntos de Zermelo-Fraenkel (ZFC). [1]
La teoría conocida como aritmética verdadera consiste en todos los enunciados verdaderos sobre los números enteros estándar en el lenguaje de la aritmética de Peano. Esta teoría es consistente y completa, y contiene una cantidad suficiente de aritmética. Sin embargo, no tiene un conjunto de axiomas recursivamente enumerables y, por lo tanto, no satisface las hipótesis de los teoremas de incompletitud.
Un conjunto de axiomas es ( sintácticamente , o negación -) completo si, para cualquier enunciado en el lenguaje de los axiomas, ese enunciado o su negación es demostrable a partir de los axiomas. [2] Esta es la noción relevante para el primer teorema de incompletitud de Gödel. No debe confundirse con la completitud semántica , lo que significa que el conjunto de axiomas demuestra todas las tautologías semánticas del lenguaje dado. En su teorema de completitud (que no debe confundirse con los teoremas de incompletitud descritos aquí), Gödel demostró que la lógica de primer orden es semánticamente completa. Pero no es sintácticamente completa, ya que hay oraciones expresables en el lenguaje de la lógica de primer orden que no pueden probarse ni refutarse a partir de los axiomas de la lógica solo.
En un sistema de matemáticas, pensadores como Hilbert creían que era sólo cuestión de tiempo encontrar una axiomatización que permitiera probar o refutar (demostrando su negación) cada fórmula matemática.
Un sistema formal puede ser sintácticamente incompleto por diseño, como lo son generalmente las lógicas. O puede ser incompleto simplemente porque no se han descubierto o incluido todos los axiomas necesarios. Por ejemplo, la geometría euclidiana sin el postulado de las paralelas es incompleta, porque algunas afirmaciones del lenguaje (como el propio postulado de las paralelas) no se pueden demostrar a partir de los axiomas restantes. De manera similar, la teoría de órdenes lineales densos no está completa, pero se completa con un axioma adicional que afirma que no hay puntos finales en el orden. La hipótesis del continuo es una afirmación en el lenguaje de ZFC que no se puede demostrar dentro de ZFC, por lo que ZFC no está completa. En este caso, no hay un candidato obvio para un nuevo axioma que resuelva el problema.
La teoría de la aritmética de Peano de primer orden parece consistente. Suponiendo que este sea efectivamente el caso, nótese que tiene un conjunto infinito pero recursivamente enumerable de axiomas, y puede codificar suficiente aritmética para las hipótesis del teorema de incompletitud. Así, por el primer teorema de incompletitud, la aritmética de Peano no es completa. El teorema da un ejemplo explícito de un enunciado de aritmética que no es ni demostrable ni refutable en la aritmética de Peano. Además, este enunciado es verdadero en el modelo usual . Además, ninguna extensión consistente y efectivamente axiomatizada de la aritmética de Peano puede ser completa.
Un conjunto de axiomas es (simplemente) consistente si no existe ningún enunciado tal que tanto el enunciado como su negación sean demostrables a partir de los axiomas, y es inconsistente en caso contrario. Es decir, un sistema axiomático consistente es aquel que está libre de contradicciones.
La aritmética de Peano es demostrablemente consistente a partir de ZFC, pero no desde dentro de sí misma. De manera similar, ZFC no es demostrablemente consistente desde dentro de sí misma, pero ZFC + "existe un cardinal inaccesible " demuestra que ZFC es consistente porque si κ es el cardinal menos importante, entonces V κ dentro del universo de von Neumann es un modelo de ZFC, y una teoría es consistente si y solo si tiene un modelo.
Si se toman como axiomas todos los enunciados del lenguaje de la aritmética de Peano , entonces esta teoría es completa, tiene un conjunto de axiomas recursivamente enumerables y puede describir la suma y la multiplicación. Sin embargo, no es consistente.
Ejemplos adicionales de teorías inconsistentes surgen de las paradojas que resultan cuando se asume el esquema axiomático de comprensión irrestricta en la teoría de conjuntos.
Los teoremas de incompletitud se aplican únicamente a sistemas formales que son capaces de demostrar una colección suficiente de hechos sobre los números naturales. Una colección suficiente es el conjunto de teoremas de la aritmética de Robinson Q . Algunos sistemas, como la aritmética de Peano, pueden expresar directamente enunciados sobre los números naturales. Otros, como la teoría de conjuntos ZFC, pueden interpretar enunciados sobre los números naturales en su lenguaje. Cualquiera de estas opciones es apropiada para los teoremas de incompletitud.
La teoría de cuerpos algebraicamente cerrados de una característica dada es completa, consistente y tiene un conjunto infinito pero recursivamente enumerable de axiomas. Sin embargo, no es posible codificar los números enteros en esta teoría, y la teoría no puede describir la aritmética de los números enteros. Un ejemplo similar es la teoría de cuerpos reales cerrados , que es esencialmente equivalente a los axiomas de Tarski para la geometría euclidiana . Por lo tanto, la geometría euclidiana en sí misma (en la formulación de Tarski) es un ejemplo de una teoría completa, consistente y efectivamente axiomatizada.
El sistema de aritmética de Presburger consiste en un conjunto de axiomas para los números naturales con solo la operación de adición (se omite la multiplicación). La aritmética de Presburger es completa, consistente y recursivamente enumerable y puede codificar la adición pero no la multiplicación de números naturales, lo que demuestra que para los teoremas de Gödel se necesita que la teoría codifique no solo la adición sino también la multiplicación.
Dan Willard (2001) ha estudiado algunas familias débiles de sistemas aritméticos que permiten suficientes operaciones aritméticas como relaciones para formalizar la numeración de Gödel, pero que no son lo suficientemente fuertes como para tener la multiplicación como función, y por lo tanto no logran demostrar el segundo teorema de incompletitud; es decir, estos sistemas son consistentes y capaces de demostrar su propia consistencia (ver teorías de autoverificación ).
Al elegir un conjunto de axiomas, uno de los objetivos es poder demostrar tantos resultados correctos como sea posible, sin demostrar ningún resultado incorrecto. Por ejemplo, podríamos imaginar un conjunto de axiomas verdaderos que nos permitan demostrar cada afirmación aritmética verdadera sobre los números naturales (Smith 2007, p. 2). En el sistema estándar de lógica de primer orden, un conjunto inconsistente de axiomas demostrará cada afirmación en su lenguaje (esto a veces se denomina principio de explosión ) y, por lo tanto, es automáticamente completo. Sin embargo, un conjunto de axiomas que es completo y consistente demuestra un conjunto máximo de teoremas no contradictorios . [ cita requerida ]
El patrón ilustrado en las secciones anteriores con la aritmética de Peano, ZFC y ZFC + "existe un cardinal inaccesible" no puede romperse en general. En este caso, ZFC + "existe un cardinal inaccesible" no puede demostrarse, por sí mismo, que es consistente. Tampoco es completo, como lo ilustra la hipótesis del continuo, que es irresoluble [3] en ZFC + "existe un cardinal inaccesible".
El primer teorema de incompletitud muestra que, en sistemas formales que pueden expresar aritmética básica, nunca se puede crear una lista finita, completa y consistente de axiomas: cada vez que se añade un enunciado consistente adicional como axioma, hay otros enunciados verdaderos que siguen sin poder demostrarse, incluso con el nuevo axioma. Si alguna vez se añade un axioma que completa el sistema, lo hace a costa de hacerlo inconsistente. Ni siquiera es posible que una lista infinita de axiomas sea completa, consistente y efectivamente axiomatizada.
El primer teorema de incompletitud de Gödel apareció por primera vez como "Teorema VI" en el artículo de Gödel de 1931 " Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I". Las hipótesis del teorema fueron mejoradas poco después por J. Barkley Rosser (1936) utilizando el truco de Rosser . El teorema resultante (que incorpora la mejora de Rosser) puede parafrasearse en inglés de la siguiente manera, donde "sistema formal" incluye el supuesto de que el sistema se genera efectivamente.
Primer teorema de incompletitud : "Cualquier sistema formal consistente F dentro del cual se puede realizar una cierta cantidad de aritmética elemental es incompleto; es decir, hay afirmaciones del lenguaje de F que no se pueden probar ni refutar en F ". (Raatikainen 2020)
La afirmación indemostrable G F a la que se refiere el teorema se suele denominar "la oración de Gödel" para el sistema F . La prueba construye una oración de Gödel particular para el sistema F , pero hay infinitas afirmaciones en el lenguaje del sistema que comparten las mismas propiedades, como la conjunción de la oración de Gödel y cualquier oración lógicamente válida .
Cada sistema efectivamente generado tiene su propia oración de Gödel. Es posible definir un sistema mayor F' que contenga la totalidad de F más G F como un axioma adicional. Esto no dará como resultado un sistema completo, porque el teorema de Gödel también se aplicará a F' , y por lo tanto F' tampoco puede ser completo. En este caso, G F es de hecho un teorema en F' , porque es un axioma. Debido a que G F establece únicamente que no es demostrable en F , no se presenta ninguna contradicción por su demostrabilidad dentro de F' . Sin embargo, debido a que el teorema de incompletitud se aplica a F' , habrá una nueva oración de Gödel G F ' para F' , que muestra que F' también es incompleta. G F ' se diferenciará de G F en que G F ' se referirá a F' , en lugar de a F .
La oración de Gödel está diseñada para referirse, indirectamente, a sí misma. La oración establece que, cuando se utiliza una secuencia particular de pasos para construir otra oración, esa oración construida no será demostrable en F . Sin embargo, la secuencia de pasos es tal que la oración construida resulta ser G F en sí misma. De esta manera, la oración de Gödel G F establece indirectamente su propia imposibilidad de demostración dentro de F (Smith 2007, p. 135).
Para demostrar el primer teorema de incompletitud, Gödel demostró que la noción de demostrabilidad dentro de un sistema podía expresarse puramente en términos de funciones aritméticas que operan sobre los números de Gödel de las oraciones del sistema. Por lo tanto, el sistema, que puede demostrar ciertos hechos sobre números, también puede demostrar indirectamente hechos sobre sus propios enunciados, siempre que se genere efectivamente. Las preguntas sobre la demostrabilidad de los enunciados dentro del sistema se representan como preguntas sobre las propiedades aritméticas de los propios números, que serían decidibles por el sistema si fuera completo.
Así, aunque la oración de Gödel se refiere indirectamente a oraciones del sistema F , cuando se lee como un enunciado aritmético la oración de Gödel se refiere directamente sólo a números naturales. Afirma que ningún número natural tiene una propiedad particular, donde esa propiedad está dada por una relación recursiva primitiva (Smith 2007, p. 141). Como tal, la oración de Gödel puede escribirse en el lenguaje de la aritmética con una forma sintáctica simple. En particular, puede expresarse como una fórmula en el lenguaje de la aritmética que consiste en un número de cuantificadores universales principales seguidos de un cuerpo libre de cuantificadores (estas fórmulas están en el nivel de la jerarquía aritmética ). A través del teorema MRDP , la oración de Gödel puede reescribirse como una declaración de que un polinomio particular en muchas variables con coeficientes enteros nunca toma el valor cero cuando se sustituyen enteros por sus variables (Franzén 2005, p. 71).
El primer teorema de incompletitud muestra que la oración de Gödel G F de una teoría formal apropiada F es indemostrable en F . Debido a que, cuando se interpreta como una afirmación sobre aritmética, esta indemostrabilidad es exactamente lo que la oración (indirectamente) afirma, la oración de Gödel es, de hecho, verdadera (Smoryński 1977, p. 825; véase también Franzén 2005, pp. 28-33). Por esta razón, a menudo se dice que la oración G F es "verdadera pero indemostrable" (Raatikainen 2020). Sin embargo, dado que la oración de Gödel no puede especificar formalmente su interpretación pretendida, la verdad de la oración G F solo puede determinarse mediante un metaanálisis desde fuera del sistema. En general, este meta-análisis puede llevarse a cabo dentro del sistema formal débil conocido como aritmética recursiva primitiva , que prueba la implicación Con ( F )→ G F , donde Con ( F ) es una oración canónica que afirma la consistencia de F (Smoryński 1977, p. 840, Kikuchi & Tanaka 1994, p. 403).
Aunque la oración de Gödel de una teoría consistente es verdadera como enunciado sobre la interpretación pretendida de la aritmética, la oración de Gödel será falsa en algunos modelos no estándar de aritmética , como consecuencia del teorema de completitud de Gödel (Franzén 2005, p. 135). Ese teorema muestra que, cuando una oración es independiente de una teoría, la teoría tendrá modelos en los que la oración es verdadera y modelos en los que la oración es falsa. Como se describió anteriormente, la oración de Gödel de un sistema F es un enunciado aritmético que afirma que no existe ningún número con una propiedad particular. El teorema de incompletitud muestra que esta afirmación será independiente del sistema F , y la verdad de la oración de Gödel se sigue del hecho de que ningún número natural estándar tiene la propiedad en cuestión. Cualquier modelo en el que la oración de Gödel sea falsa debe contener algún elemento que satisfaga la propiedad dentro de ese modelo. Un modelo de este tipo debe ser “no estándar”: debe contener elementos que no correspondan a ningún número natural estándar (Raatikainen 2020, Franzén 2005, p. 135).
Gödel cita específicamente la paradoja de Richard y la paradoja del mentiroso como análogos semánticos de su resultado de incompletitud sintáctica en la sección introductoria de " Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas relacionados I ". La paradoja del mentiroso es la oración "Esta oración es falsa". Un análisis de la oración del mentiroso muestra que no puede ser verdadera (porque entonces, como afirma, es falsa), ni puede ser falsa (porque entonces, es verdadera). Una oración de Gödel G para un sistema F hace una afirmación similar a la oración del mentiroso, pero con la verdad reemplazada por la demostrabilidad: G dice " G no es demostrable en el sistema F ". El análisis de la verdad y la demostrabilidad de G es una versión formalizada del análisis de la verdad de la oración del mentiroso.
No es posible reemplazar "no demostrable" por "falso" en una oración de Gödel porque el predicado " Q es el número de Gödel de una fórmula falsa" no puede representarse como una fórmula aritmética. Este resultado, conocido como el teorema de indefinibilidad de Tarski , fue descubierto independientemente tanto por Gödel, cuando estaba trabajando en la prueba del teorema de incompletitud, como por el homónimo del teorema, Alfred Tarski .
En comparación con los teoremas enunciados en el artículo de Gödel de 1931, muchos enunciados contemporáneos de los teoremas de incompletitud son más generales en dos sentidos. Estos enunciados generalizados están formulados para que se apliquen a una clase más amplia de sistemas y están formulados para incorporar supuestos de consistencia más débiles.
Gödel demostró la incompletitud del sistema de Principia Mathematica , un sistema particular de aritmética, pero se podría dar una demostración paralela para cualquier sistema efectivo de cierta expresividad. Gödel comentó este hecho en la introducción de su artículo, pero restringió la prueba a un sistema para la concreción. En los enunciados modernos del teorema, es común enunciar las condiciones de efectividad y expresividad como hipótesis para el teorema de incompletitud, de modo que no se limita a ningún sistema formal particular. La terminología utilizada para enunciar estas condiciones aún no estaba desarrollada en 1931 cuando Gödel publicó sus resultados.
El enunciado y la demostración originales de Gödel del teorema de incompletitud requieren la suposición de que el sistema no es sólo consistente sino ω-consistente . Un sistema es ω-consistente si no es ω-inconsistente, y es ω-inconsistente si hay un predicado P tal que para cada número natural específico m el sistema prueba ~ P ( m ) , y sin embargo el sistema también prueba que existe un número natural n tal que P ( n ). Es decir, el sistema dice que existe un número con la propiedad P mientras niega que tenga algún valor específico. La ω-consistencia de un sistema implica su consistencia, pero la consistencia no implica ω-consistencia. J. Barkley Rosser (1936) fortaleció el teorema de incompletitud al encontrar una variación de la prueba ( el truco de Rosser ) que sólo requiere que el sistema sea consistente, en lugar de ω-consistente. Esto tiene un interés principalmente técnico, porque todas las teorías formales verdaderas de la aritmética (teorías cuyos axiomas son todos enunciados verdaderos sobre los números naturales) son ω-consistentes y, por lo tanto, el teorema de Gödel tal como se enunció originalmente se aplica a ellas. La versión más fuerte del teorema de incompletitud que solo supone consistencia, en lugar de ω-consistencia, ahora se conoce comúnmente como teorema de incompletitud de Gödel y como teorema de Gödel-Rosser.
Para cada sistema formal F que contenga aritmética básica, es posible definir canónicamente una fórmula Cons( F ) que exprese la consistencia de F . Esta fórmula expresa la propiedad de que "no existe un número natural que codifique una derivación formal dentro del sistema F cuya conclusión sea una contradicción sintáctica". La contradicción sintáctica se considera a menudo como "0=1", en cuyo caso Cons( F ) afirma que "no existe ningún número natural que codifique una derivación de '0=1' a partir de los axiomas de F ".
El segundo teorema de incompletitud de Gödel muestra que, bajo supuestos generales, este enunciado de consistencia canónica Cons( F ) no será demostrable en F . El teorema apareció por primera vez como "Teorema XI" en el artículo de Gödel de 1931 " Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas relacionados I ". En el enunciado siguiente, el término "sistema formalizado" también incluye un supuesto de que F está efectivamente axiomatizado. Este teorema establece que para cualquier sistema consistente F dentro del cual se puede realizar una cierta cantidad de aritmética elemental, la consistencia de F no se puede demostrar en F mismo. [4] Este teorema es más fuerte que el primer teorema de incompletitud porque el enunciado construido en el primer teorema de incompletitud no expresa directamente la consistencia del sistema. La prueba del segundo teorema de incompletitud se obtiene formalizando la prueba del primer teorema de incompletitud dentro del propio sistema F.
Existe una sutileza técnica en el segundo teorema de incompletitud en lo que respecta al método de expresar la consistencia de F como una fórmula en el lenguaje de F . Hay muchas maneras de expresar la consistencia de un sistema, y no todas ellas conducen al mismo resultado. La fórmula Cons( F ) del segundo teorema de incompletitud es una expresión particular de la consistencia.
Otras formalizaciones de la afirmación de que F es consistente pueden ser inequivalentes en F , y algunas pueden incluso ser demostrables. Por ejemplo, la aritmética de Peano de primer orden (PA) puede demostrar que "el subconjunto consistente más grande de PA" es consistente. Pero, como PA es consistente, el subconjunto consistente más grande de PA es solo PA, por lo que en este sentido PA "prueba que es consistente". Lo que PA no prueba es que el subconjunto consistente más grande de PA sea, de hecho, la totalidad de PA. (El término "subconjunto consistente más grande de PA" se entiende aquí como el segmento inicial consistente más grande de los axiomas de PA bajo alguna enumeración efectiva particular).
La prueba estándar del segundo teorema de incompletitud supone que el predicado de demostrabilidad Prov A ( P ) satisface las condiciones de demostrabilidad de Hilbert-Bernays . Si #( P ) representa el número de Gödel de una fórmula P , las condiciones de demostrabilidad dicen:
Existen sistemas, como la aritmética de Robinson, que son lo suficientemente fuertes como para cumplir los supuestos del primer teorema de incompletitud, pero que no prueban las condiciones de Hilbert-Bernays. La aritmética de Peano, sin embargo, es lo suficientemente fuerte como para verificar estas condiciones, como lo son todas las teorías más fuertes que la aritmética de Peano.
El segundo teorema de incompletitud de Gödel también implica que un sistema F 1 que satisface las condiciones técnicas descritas anteriormente no puede probar la consistencia de ningún sistema F 2 que pruebe la consistencia de F 1 . Esto se debe a que dicho sistema F 1 puede probar que si F 2 prueba la consistencia de F 1 , entonces F 1 es de hecho consistente. Porque la afirmación de que F 1 es consistente tiene la forma "para todos los números n , n tiene la propiedad decidible de no ser un código para una prueba de contradicción en F 1 ". Si F 1 fuera de hecho inconsistente, entonces F 2 probaría para algún n que n es el código de una contradicción en F 1 . Pero si F 2 también probara que F 1 es consistente (es decir, que no existe tal n ), entonces sería inconsistente en sí mismo. Este razonamiento se puede formalizar en F 1 para mostrar que si F 2 es consistente, entonces F 1 es consistente. Dado que, por el segundo teorema de incompletitud, F 1 no prueba su consistencia, tampoco puede probar la consistencia de F 2 .
Este corolario del segundo teorema de incompletitud muestra que no hay esperanza de probar, por ejemplo, la consistencia de la aritmética de Peano utilizando cualquier medio finitista que pueda formalizarse en un sistema cuya consistencia sea demostrable en la aritmética de Peano (PA). Por ejemplo, el sistema de aritmética recursiva primitiva (PRA), que es ampliamente aceptado como una formalización precisa de las matemáticas finitistas, es demostrablemente consistente en PA. Por lo tanto, PRA no puede probar la consistencia de PA. Este hecho se considera generalmente que implica que el programa de Hilbert , que apuntaba a justificar el uso de principios matemáticos "ideales" (infinitistas) en las pruebas de enunciados matemáticos "reales" (finitistas) al dar una prueba finitista de que los principios ideales son consistentes, no puede llevarse a cabo. [5]
El corolario también indica la relevancia epistemológica del segundo teorema de incompletitud. No proporcionaría ninguna información interesante si un sistema F demostrara su consistencia. Esto se debe a que las teorías inconsistentes prueban todo, incluida su consistencia. Por lo tanto, una prueba de consistencia de F en F no nos daría ninguna pista sobre si F es consistente; ninguna duda sobre la consistencia de F se resolvería con tal prueba de consistencia. El interés en las pruebas de consistencia radica en la posibilidad de demostrar la consistencia de un sistema F en algún sistema F' que sea en algún sentido menos dudoso que el propio F , por ejemplo, más débil que F . Para muchas teorías naturales F y F' , como F = teoría de conjuntos de Zermelo-Fraenkel y F' = aritmética recursiva primitiva, la consistencia de F' es demostrable en F , y por lo tanto F' no puede demostrar la consistencia de F por el corolario anterior del segundo teorema de incompletitud.
El segundo teorema de incompletitud no descarta por completo la posibilidad de demostrar la consistencia de un sistema diferente con axiomas diferentes. Por ejemplo, Gerhard Gentzen demostró la consistencia de la aritmética de Peano en un sistema diferente que incluye un axioma que afirma que el ordinal llamado ε 0 está bien fundado ; véase la prueba de consistencia de Gentzen . El teorema de Gentzen impulsó el desarrollo del análisis ordinal en la teoría de la demostración.
Existen dos sentidos distintos de la palabra "indecidible" en matemáticas y ciencias de la computación. El primero de ellos es el sentido teórico de la prueba utilizado en relación con los teoremas de Gödel, que se refiere a que una afirmación no es ni demostrable ni refutable en un sistema deductivo específico . El segundo sentido, que no se tratará aquí, se utiliza en relación con la teoría de la computabilidad y se aplica no a afirmaciones sino a problemas de decisión , que son conjuntos infinitos de preguntas que requieren cada una una respuesta de sí o no. Se dice que un problema de este tipo es indecidible si no existe una función computable que responda correctamente a todas las preguntas del conjunto de problemas (véase problema indecidible ).
Debido a los dos significados de la palabra indecidible, a veces se utiliza el término independiente en lugar de indecidible para el sentido "ni demostrable ni refutable".
La indecidibilidad de un enunciado en un sistema deductivo particular no resuelve por sí misma la cuestión de si el valor de verdad del enunciado está bien definido o si puede determinarse por otros medios. La indecidibilidad sólo implica que el sistema deductivo particular que se esté considerando no prueba la verdad o falsedad del enunciado. La existencia de los llamados enunciados "absolutamente indecidibles", cuyo valor de verdad nunca puede conocerse o está mal especificado, es un punto controvertido en la filosofía de las matemáticas .
El trabajo combinado de Gödel y Paul Cohen ha dado dos ejemplos concretos de enunciados indecidibles (en el primer sentido del término): la hipótesis del continuo no puede ser probada ni refutada en ZFC (la axiomatización estándar de la teoría de conjuntos ), y el axioma de elección no puede ser probado ni refutado en ZF (que son todos los axiomas de ZFC excepto el axioma de elección). Estos resultados no requieren el teorema de incompletitud. Gödel demostró en 1940 que ninguno de estos enunciados podía ser refutado en ZF o en la teoría de conjuntos ZFC. En la década de 1960, Cohen demostró que ninguno es demostrable a partir de ZF, y la hipótesis del continuo no puede ser probada a partir de ZFC.
Shelah (1974) demostró que el problema de Whitehead en la teoría de grupos es indecidible, en el primer sentido del término, en la teoría de conjuntos estándar. [6]
Gregory Chaitin produjo enunciados indecidibles en la teoría de la información algorítmica y demostró otro teorema de incompletitud en ese contexto. El teorema de incompletitud de Chaitin establece que para cualquier sistema que pueda representar suficiente aritmética, existe un límite superior c tal que no se puede demostrar que ningún número específico en ese sistema tenga una complejidad de Kolmogorov mayor que c . Mientras que el teorema de Gödel está relacionado con la paradoja del mentiroso , el resultado de Chaitin está relacionado con la paradoja de Berry .
Se trata de equivalentes matemáticos naturales de la oración de Gödel "verdadera pero indecidible". Se pueden demostrar en un sistema más amplio que generalmente se acepta como una forma válida de razonamiento, pero son indecidibles en un sistema más limitado como la aritmética de Peano.
En 1977, Paris y Harrington demostraron que el principio de Paris-Harrington , una versión del teorema de Ramsey infinito, es indecidible en la aritmética de Peano (de primer orden) , pero puede demostrarse en el sistema más fuerte de la aritmética de segundo orden . Kirby y Paris demostraron más tarde que el teorema de Goodstein , un enunciado sobre secuencias de números naturales algo más simple que el principio de Paris-Harrington, también es indecidible en la aritmética de Peano.
El teorema del árbol de Kruskal , que tiene aplicaciones en informática, también es indecidible a partir de la aritmética de Peano, pero demostrable en la teoría de conjuntos. De hecho, el teorema del árbol de Kruskal (o su forma finita) es indecidible en un sistema mucho más fuerte ATR 0 que codifica los principios aceptables según una filosofía de las matemáticas llamada predicativismo . [7] El teorema del grafo menor (2003), relacionado pero más general, tiene consecuencias para la teoría de la complejidad computacional .
El teorema de incompletitud está estrechamente relacionado con varios resultados sobre conjuntos indecidibles en la teoría de la recursión .
Kleene (1943) presentó una prueba del teorema de incompletitud de Gödel utilizando resultados básicos de la teoría de la computabilidad. Uno de esos resultados muestra que el problema de la detención es indecidible: ningún programa informático puede determinar correctamente, dado cualquier programa P como entrada, si P se detiene eventualmente cuando se ejecuta con una entrada dada particular. Kleene demostró que la existencia de un sistema completo y efectivo de aritmética con ciertas propiedades de consistencia obligaría a que el problema de la detención fuera decidible, una contradicción. [8] Este método de prueba también ha sido presentado por Shoenfield (1967); Charlesworth (1981); y Hopcroft & Ullman (1979). [9]
Franzén (2005) explica cómo la solución de Matiyasevich al décimo problema de Hilbert puede usarse para obtener una prueba del primer teorema de incompletitud de Gödel. [10] Matiyasevich demostró que no existe un algoritmo que, dado un polinomio multivariado p ( x 1 , x 2 ,..., x k ) con coeficientes enteros, determine si hay una solución entera para la ecuación p = 0. Debido a que los polinomios con coeficientes enteros, y los enteros mismos, son directamente expresables en el lenguaje de la aritmética, si una ecuación polinómica entera multivariada p = 0 tiene una solución en los enteros, entonces cualquier sistema aritmético T suficientemente fuerte probará esto. Además, supongamos que el sistema T es ω-consistente. En ese caso, nunca probará que una ecuación polinómica particular tiene una solución cuando no hay solución en los enteros. Por lo tanto, si T fuera completa y ω-consistente, sería posible determinar algorítmicamente si una ecuación polinómica tiene una solución simplemente enumerando pruebas de T hasta que se encuentre " p tiene una solución" o " p no tiene solución", en contradicción con el teorema de Matiyasevich. De lo que se sigue que T no puede ser ω-consistente y completa. Además, para cada sistema consistente efectivamente generado T , es posible generar efectivamente un polinomio multivariado p sobre los enteros tal que la ecuación p = 0 no tenga soluciones sobre los enteros, pero la falta de soluciones no puede probarse en T . [11]
Smoryński (1977) muestra cómo la existencia de conjuntos recursivamente inseparables puede utilizarse para demostrar el primer teorema de incompletitud. Esta prueba se suele ampliar para demostrar que sistemas como la aritmética de Peano son esencialmente indecidibles . [12]
El teorema de incompletitud de Chaitin ofrece un método diferente para producir oraciones independientes, basado en la complejidad de Kolmogorov . Al igual que la prueba presentada por Kleene que se mencionó anteriormente, el teorema de Chaitin solo se aplica a teorías con la propiedad adicional de que todos sus axiomas son verdaderos en el modelo estándar de los números naturales. El teorema de incompletitud de Gödel se distingue por su aplicabilidad a teorías consistentes que, no obstante, incluyen enunciados falsos en el modelo estándar; estas teorías se conocen como ω-inconsistentes .
La demostración por contradicción tiene tres partes esenciales. Para empezar, se elige un sistema formal que cumpla los criterios propuestos:
El principal problema para desarrollar la prueba descrita anteriormente es que, en un principio, parece que para construir una afirmación p que sea equivalente a " p no puede probarse", p tendría que contener de algún modo una referencia a p , lo que fácilmente podría dar lugar a una regresión infinita. La técnica de Gödel consiste en demostrar que las afirmaciones pueden relacionarse con números (lo que a menudo se denomina aritmetización de la sintaxis ) de tal manera que "probar una afirmación" puede sustituirse por "probar si un número tiene una propiedad dada" . Esto permite construir una fórmula autorreferencial de forma que se evite cualquier regresión infinita de definiciones. La misma técnica fue utilizada posteriormente por Alan Turing en su trabajo sobre el Entscheidungsproblem .
En términos simples, se puede idear un método para que cada fórmula o enunciado que se pueda formular en el sistema obtenga un número único, llamado su número de Gödel , de tal manera que sea posible convertir mecánicamente de una fórmula a otra y viceversa. Los números involucrados pueden ser muy largos (en términos de número de dígitos), pero esto no es una barrera; lo único que importa es que se puedan construir dichos números. Un ejemplo simple es cómo se puede almacenar el inglés como una secuencia de números para cada letra y luego combinarlos en un solo número más grande:
En principio, demostrar que una afirmación es verdadera o falsa puede demostrarse que es equivalente a demostrar que el número que coincide con la afirmación tiene o no una propiedad dada. Debido a que el sistema formal es lo suficientemente fuerte como para admitir el razonamiento sobre números en general , también puede admitir el razonamiento sobre números que representan fórmulas y afirmaciones . Fundamentalmente, debido a que el sistema puede admitir el razonamiento sobre las propiedades de los números , los resultados son equivalentes al razonamiento sobre la demostrabilidad de sus afirmaciones equivalentes .
Habiendo demostrado que en principio el sistema puede hacer declaraciones indirectamente acerca de la demostrabilidad, al analizar las propiedades de aquellos números que representan declaraciones, ahora es posible mostrar cómo crear una declaración que realmente haga esto.
Una fórmula F ( x ) que contiene exactamente una variable libre x se llama forma de enunciado o signo de clase . Tan pronto como x se reemplaza por un número específico, la forma de enunciado se convierte en un enunciado genuino , y entonces es demostrable en el sistema, o no. Para ciertas fórmulas se puede demostrar que para cada número natural n , es verdadero si y solo si puede demostrarse (el requisito preciso en la prueba original es más débil, pero para el esbozo de la prueba esto será suficiente). En particular, esto es cierto para cada operación aritmética específica entre un número finito de números naturales, como "2 × 3 = 6".
Las formas de enunciado en sí mismas no son enunciados y, por lo tanto, no se pueden probar ni refutar. Pero a cada forma de enunciado F ( x ) se le puede asignar un número de Gödel denotado por G ( F ) . La elección de la variable libre utilizada en la forma F ( x ) no es relevante para la asignación del número de Gödel G ( F ) .
La noción de demostrabilidad también puede ser codificada por los números de Gödel, de la siguiente manera: dado que una prueba es una lista de enunciados que obedecen a ciertas reglas, se puede definir el número de Gödel de una prueba. Ahora bien, para cada enunciado p , se puede preguntar si un número x es el número de Gödel de su prueba. La relación entre el número de Gödel de p y x , el número de Gödel potencial de su prueba, es una relación aritmética entre dos números. Por lo tanto, existe una forma de enunciado Bew ( y ) que utiliza esta relación aritmética para afirmar que existe un número de Gödel de una prueba de y :
El nombre Bew es la abreviatura de beweisbar , la palabra alemana que significa "demostrable"; este nombre fue utilizado originalmente por Gödel para denotar la fórmula de demostrabilidad que se acaba de describir. Nótese que " Bew ( y ) " es simplemente una abreviatura que representa una fórmula particular, muy larga, en el idioma original de T ; no se afirma que la cadena " Bew " en sí sea parte de este idioma.
Una característica importante de la fórmula Bew ( y ) es que si un enunciado p es demostrable en el sistema, entonces Bew ( G ( p )) también lo es. Esto se debe a que cualquier demostración de p tendría un número de Gödel correspondiente, cuya existencia hace que se cumpla Bew( G ( p )) .
El siguiente paso en la prueba es obtener un enunciado que, indirectamente, afirme su propia imposibilidad de ser probado. Aunque Gödel construyó este enunciado directamente, la existencia de al menos un enunciado de este tipo se sigue del lema diagonal , que dice que para cualquier sistema formal suficientemente fuerte y cualquier enunciado de la forma F existe un enunciado p tal que el sistema demuestra
Al ser F la negación de Bew ( x ) , obtenemos el teorema
y la p definida por esto establece aproximadamente que su propio número de Gödel es el número de Gödel de una fórmula indemostrable.
La afirmación p no es literalmente igual a ~ Bew ( G ( p )) ; más bien, p afirma que si se realiza un determinado cálculo, el número de Gödel resultante será el de una afirmación indemostrable. Pero cuando se realiza este cálculo, el número de Gödel resultante resulta ser el número de Gödel de p en sí. Esto es similar a la siguiente oración en inglés:
Esta oración no se refiere directamente a sí misma, sino que al realizar la transformación indicada se obtiene como resultado la oración original, y por lo tanto esta oración afirma indirectamente su propia imposibilidad de ser demostrada. La demostración del lema diagonal emplea un método similar.
Ahora, supongamos que el sistema axiomático es ω-consistente , y sea p el enunciado obtenido en la sección anterior.
Si p fuera demostrable, entonces Bew ( G ( p )) sería demostrable, como se argumentó anteriormente. Pero p afirma la negación de Bew ( G ( p )) . Por lo tanto, el sistema sería inconsistente, ya que probaría tanto un enunciado como su negación. Esta contradicción muestra que p no puede ser demostrable.
Si la negación de p fuera demostrable, entonces Bew ( G ( p )) sería demostrable (porque p fue construido para ser equivalente a la negación de Bew ( G ( p )) ). Sin embargo, para cada número específico x , x no puede ser el número de Gödel de la prueba de p , porque p no es demostrable (del párrafo anterior). Así, por un lado, el sistema demuestra que hay un número con una cierta propiedad (que es el número de Gödel de la prueba de p ), pero por otro lado, para cada número específico x , podemos demostrar que no tiene esta propiedad. Esto es imposible en un sistema ω-consistente. Por lo tanto, la negación de p no es demostrable.
Por lo tanto, el enunciado p es indecidible en nuestro sistema axiomático: no puede ser probado ni refutado dentro del sistema.
De hecho, para demostrar que p no es demostrable sólo se requiere la suposición de que el sistema es consistente. La suposición más fuerte de ω-consistencia es necesaria para demostrar que la negación de p no es demostrable. Por lo tanto, si p se construye para un sistema particular:
Si uno intenta "agregar los axiomas faltantes" para evitar la incompletitud del sistema, entonces uno tiene que agregar p o "no p " como axiomas. Pero entonces la definición de "ser un número de Gödel de una prueba" de un enunciado cambia, lo que significa que la fórmula Bew ( x ) ahora es diferente. Así, cuando aplicamos el lema diagonal a este nuevo Bew, obtenemos un nuevo enunciado p , diferente del anterior, que será indecidible en el nuevo sistema si es ω-consistente.
Boolos (1989) esboza una prueba alternativa del primer teorema de incompletitud que utiliza la paradoja de Berry en lugar de la paradoja del mentiroso para construir una fórmula verdadera pero no demostrable. Un método de prueba similar fue descubierto independientemente por Saul Kripke . [13] La prueba de Boolos procede construyendo, para cualquier conjunto computablemente enumerable S de oraciones aritméticas verdaderas, otra oración que es verdadera pero no está contenida en S. Esto da como corolario el primer teorema de incompletitud. Según Boolos, esta prueba es interesante porque proporciona un "tipo diferente de razón" para la incompletitud de teorías aritméticas efectivas y consistentes. [14]
Los teoremas de incompletitud se encuentran entre un número relativamente pequeño de teoremas no triviales que se han transformado en teoremas formalizados que pueden verificarse completamente mediante software de asistencia para pruebas . Las pruebas originales de Gödel de los teoremas de incompletitud, como la mayoría de las pruebas matemáticas, se escribieron en lenguaje natural destinado a lectores humanos.
En 1986, Natarajan Shankar anunció pruebas verificadas por computadora de versiones del primer teorema de incompletitud utilizando Nqthm (Shankar 1994), en 2003, Russell O'Connor utilizando Coq (O'Connor 2005), y en 2009, John Harrison utilizando HOL Light (Harrison 2009). En 2013, Lawrence Paulson anunció una prueba verificada por computadora de ambos teoremas de incompletitud utilizando Isabelle (Paulson 2014).
La principal dificultad para demostrar el segundo teorema de incompletitud es demostrar que varios hechos sobre demostrabilidad utilizados en la demostración del primer teorema de incompletitud pueden formalizarse dentro de un sistema S utilizando un predicado formal P para demostrabilidad. Una vez hecho esto, el segundo teorema de incompletitud sigue formalizando toda la demostración del primer teorema de incompletitud dentro del propio sistema S.
Sea p la oración indecidible construida anteriormente y supongamos, para efectos de obtener una contradicción, que la consistencia del sistema S puede probarse desde dentro del propio sistema S. Esto es equivalente a probar la afirmación "El sistema S es consistente". Ahora consideremos la afirmación c , donde c = "Si el sistema S es consistente, entonces p no es demostrable". La prueba de la oración c puede formalizarse dentro del sistema S , y por lo tanto la afirmación c , " p no es demostrable", (o, de manera idéntica, "no P ( p ) ") puede probarse en el sistema S .
Obsérvese entonces que si podemos probar que el sistema S es consistente (es decir, el enunciado en la hipótesis de c ), entonces hemos probado que p no es demostrable. Pero esto es una contradicción ya que por el 1er Teorema de Incompletitud, esta oración (es decir, lo que está implícito en la oración c , "" p " no es demostrable") es lo que construimos como no demostrable. Nótese que esta es la razón por la que requerimos formalizar el primer Teorema de Incompletitud en S : para probar el 2do Teorema de Incompletitud, obtenemos una contradicción con el 1er Teorema de Incompletitud que solo puede hacerse mostrando que el teorema se cumple en S. Por lo tanto, no podemos probar que el sistema S es consistente. Y el enunciado del 2do Teorema de Incompletitud se deduce.
Los resultados de incompletitud afectan a la filosofía de las matemáticas , particularmente a las versiones del formalismo , que utilizan un único sistema de lógica formal para definir sus principios.
A veces se piensa que el teorema de incompletitud tiene graves consecuencias para el programa del logicismo propuesto por Gottlob Frege y Bertrand Russell , que tenía como objetivo definir los números naturales en términos de lógica. [15] Bob Hale y Crispin Wright sostienen que no es un problema para el logicismo porque los teoremas de incompletitud se aplican tanto a la lógica de primer orden como a la aritmética. Argumentan que solo aquellos que creen que los números naturales deben definirse en términos de lógica de primer orden tienen este problema.
Muchos lógicos creen que los teoremas de incompletitud de Gödel dieron un golpe fatal al segundo problema de David Hilbert , que pedía una prueba de consistencia finita para las matemáticas. El segundo teorema de incompletitud, en particular, suele considerarse como el factor que hace imposible el problema. Sin embargo, no todos los matemáticos están de acuerdo con este análisis, y el estatus del segundo problema de Hilbert aún no está decidido (véase " Puntos de vista modernos sobre el estatus del problema ").
Autores como el filósofo JR Lucas y el físico Roger Penrose han debatido qué implican, si es que implican algo, los teoremas de incompletitud de Gödel sobre la inteligencia humana. Gran parte del debate se centra en si la mente humana es equivalente a una máquina de Turing o, según la tesis de Church-Turing , a cualquier máquina finita. Si lo es, y si la máquina es consistente, entonces los teoremas de incompletitud de Gödel se aplicarían a ella.
Putnam (1960) sugirió que si bien los teoremas de Gödel no pueden aplicarse a los seres humanos, ya que cometen errores y, por lo tanto, son inconsistentes, sí pueden aplicarse a la facultad humana de la ciencia o de las matemáticas en general. Suponiendo que sean consistentes, o bien su consistencia no puede probarse o bien no pueden representarse mediante una máquina de Turing. [16]
Wigderson (2010) ha propuesto que el concepto de “cognoscibilidad” matemática debería basarse en la complejidad computacional más que en la decidibilidad lógica. Escribe que “cuando la cognoscibilidad se interpreta según los estándares modernos, es decir, a través de la complejidad computacional, los fenómenos de Gödel están muy presentes entre nosotros”. [17]
Douglas Hofstadter , en sus libros Gödel, Escher, Bach y Soy un bucle extraño , cita los teoremas de Gödel como un ejemplo de lo que él llama un bucle extraño , una estructura jerárquica y autorreferencial que existe dentro de un sistema formal axiomático. Sostiene que este es el mismo tipo de estructura que da lugar a la conciencia, el sentido del "yo", en la mente humana. Mientras que la autorreferencia en el teorema de Gödel proviene de la oración de Gödel que afirma su imposibilidad de demostración dentro del sistema formal de Principia Mathematica, la autorreferencia en la mente humana proviene de cómo el cerebro abstrae y clasifica los estímulos en "símbolos", o grupos de neuronas que responden a conceptos, en lo que es efectivamente también un sistema formal, dando lugar eventualmente a símbolos que modelan el concepto de la entidad misma que realiza la percepción. Hofstadter sostiene que un bucle extraño en un sistema formal suficientemente complejo puede dar lugar a una causalidad "hacia abajo" o "al revés", una situación en la que la jerarquía normal de causa y efecto se invierte. En el caso del teorema de Gödel, esto se manifiesta, en resumen, de la siguiente manera:
Con sólo conocer el significado de la fórmula, se puede inferir su verdad o falsedad sin ningún esfuerzo por deducirla a la antigua usanza, que exige avanzar metódicamente "hacia arriba" a partir de los axiomas. Esto no sólo es peculiar, sino asombroso. Normalmente, no se puede simplemente observar lo que dice una conjetura matemática y simplemente apelar al contenido de esa afirmación por sí sola para deducir si la afirmación es verdadera o falsa. [18]
En el caso de la mente, un sistema formal mucho más complejo, esta "causalidad descendente" se manifiesta, en la visión de Hofstadter, como el inefable instinto humano de que la causalidad de nuestras mentes reside en el alto nivel de los deseos, conceptos, personalidades, pensamientos e ideas, más que en el bajo nivel de las interacciones entre neuronas o incluso partículas fundamentales, aunque según la física estas últimas parecen poseer el poder causal.
Existe, pues, una curiosa inversión de nuestra forma humana habitual de percibir el mundo: estamos diseñados para percibir “cosas grandes” en lugar de “cosas pequeñas”, aunque el dominio de lo diminuto parece ser donde residen los verdaderos motores que impulsan la realidad. [18]
Aunque los teoremas de Gödel se estudian habitualmente en el contexto de la lógica clásica, también tienen un papel en el estudio de la lógica paraconsistente y de los enunciados inherentemente contradictorios ( dialetheia ). Priest (1984, 2006) sostiene que sustituir la noción de prueba formal en el teorema de Gödel por la noción habitual de prueba informal puede utilizarse para demostrar que las matemáticas ingenuas son inconsistentes, y utiliza esto como prueba del dialeteísmo . [19] La causa de esta inconsistencia es la inclusión de un predicado de verdad para un sistema dentro del lenguaje del sistema. [20] Shapiro (2002) ofrece una valoración más mixta de las aplicaciones de los teoremas de Gödel al dialeteísmo. [21]
En ocasiones se apela a la incompletitud de los teoremas y se hacen analogías para apoyar argumentos que van más allá de las matemáticas y la lógica. Varios autores han comentado negativamente sobre tales extensiones e interpretaciones, entre ellos Franzén (2005), Raatikainen (2005), Sokal & Bricmont (1999); y Stangroom & Benson (2006). [22] Sokal & Bricmont (1999) y Stangroom & Benson (2006), por ejemplo, citan los comentarios de Rebecca Goldstein sobre la disparidad entre el platonismo declarado de Gödel y los usos antirrealistas que a veces se hacen de sus ideas. Sokal & Bricmont (1999) critican la invocación del teorema por parte de Régis Debray en el contexto de la sociología; Debray ha defendido este uso como metafórico (ibid.). [23]
Después de que Gödel publicara su prueba del teorema de completitud como tesis doctoral en 1929, se dedicó a un segundo problema para su habilitación . Su objetivo original era obtener una solución positiva al segundo problema de Hilbert . [24] En ese momento, las teorías de números naturales y números reales similares a la aritmética de segundo orden se conocían como "análisis", mientras que las teorías de números naturales solo se conocían como "aritmética".
Gödel no fue la única persona que trabajó en el problema de la consistencia. Ackermann había publicado una prueba de consistencia defectuosa para el análisis en 1925, en la que intentó utilizar el método de sustitución ε desarrollado originalmente por Hilbert. Más tarde ese año, von Neumann pudo corregir la prueba para un sistema de aritmética sin ningún axioma de inducción. En 1928, Ackermann había comunicado una prueba modificada a Bernays; esta prueba modificada llevó a Hilbert a anunciar su creencia en 1929 de que se había demostrado la consistencia de la aritmética y que probablemente pronto seguiría una prueba consistente del análisis. Después de que la publicación de los teoremas de incompletitud mostrara que la prueba modificada de Ackermann debía ser errónea, von Neumann produjo un ejemplo concreto que demostraba que su técnica principal era incorrecta. [25]
En el curso de su investigación, Gödel descubrió que, si bien una oración que afirma su falsedad conduce a una paradoja, una oración que afirma su imposibilidad de demostración no la produce. En particular, Gödel conocía el resultado que ahora se denomina teorema de indefinibilidad de Tarski , aunque nunca lo publicó. Gödel anunció su primer teorema de incompletitud a Carnap, Feigel y Waismann el 26 de agosto de 1930; los cuatro asistirían a la Segunda Conferencia sobre la Epistemología de las Ciencias Exactas , una conferencia clave en Königsberg la semana siguiente.
La conferencia de Königsberg de 1930 fue una reunión conjunta de tres sociedades académicas, a la que asistieron muchos de los lógicos más importantes de la época. Carnap, Heyting y von Neumann pronunciaron discursos de una hora sobre las filosofías matemáticas del logicismo, el intuicionismo y el formalismo, respectivamente. [26] La conferencia también incluyó el discurso de jubilación de Hilbert, ya que dejaba su puesto en la Universidad de Göttingen. Hilbert utilizó el discurso para argumentar su creencia de que todos los problemas matemáticos pueden resolverse. Terminó su discurso diciendo:
Para el matemático no existe el Ignorabimus y, en mi opinión, tampoco para las ciencias naturales. ... La verdadera razón por la que [nadie] ha logrado encontrar un problema irresoluble es, en mi opinión, que no existe ningún problema irresoluble. En contraste con el tonto Ignorabimus , nuestro credo afirma: ¡Debemos saber! ¡Sabremos!
Este discurso se hizo conocido rápidamente como un resumen de las creencias de Hilbert sobre las matemáticas (sus últimas seis palabras, " Wir müssen wissen. Wir werden wissen! ", se usaron como epitafio de Hilbert en 1943). Aunque es probable que Gödel estuviera presente en el discurso de Hilbert, los dos nunca se encontraron cara a cara. [27]
Gödel anunció su primer teorema de incompletitud en una mesa redonda celebrada el tercer día de la conferencia. El anuncio atrajo poca atención, salvo la de von Neumann, que se llevó a Gödel aparte para conversar. Más tarde ese año, trabajando de forma independiente con el conocimiento del primer teorema de incompletitud, von Neumann obtuvo una prueba del segundo teorema de incompletitud, que anunció a Gödel en una carta fechada el 20 de noviembre de 1930. [28] Gödel había obtenido de forma independiente el segundo teorema de incompletitud y lo había incluido en el manuscrito que envió, que fue recibido por Monatshefte für Mathematik el 17 de noviembre de 1930.
El artículo de Gödel fue publicado en Monatshefte en 1931 bajo el título "Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas relacionados I" (" Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas relacionados I "). Como el título implica, Gödel originalmente planeó publicar una segunda parte del artículo en el siguiente volumen de Monatshefte ; la rápida aceptación del primer artículo fue una de las razones por las que cambió sus planes. [29]
Gödel dio una serie de conferencias sobre sus teoremas en Princeton en 1933-1934 ante un público que incluía a Church, Kleene y Rosser. Para entonces, Gödel había comprendido que la propiedad clave que exigían sus teoremas era que el sistema debía ser eficaz (en aquella época se utilizaba el término "recursivo general"). Rosser demostró en 1936 que la hipótesis de la ω-consistencia, que era parte integral de la prueba original de Gödel, podía ser reemplazada por la consistencia simple si se cambiaba apropiadamente la oración de Gödel. Estos avances dejaron los teoremas de incompletitud en esencia en su forma moderna.
Gentzen publicó su prueba de consistencia para la aritmética de primer orden en 1936. Hilbert aceptó esta prueba como "finitaria" aunque (como ya había demostrado el teorema de Gödel) no puede formalizarse dentro del sistema de aritmética cuya consistencia se está demostrando.
El impacto de los teoremas de incompletitud en el programa de Hilbert se hizo evidente rápidamente. Bernays incluyó una prueba completa de los teoremas de incompletitud en el segundo volumen de Grundlagen der Mathematik (1939), junto con resultados adicionales de Ackermann sobre el método de sustitución ε y la prueba de consistencia de la aritmética de Gentzen. Esta fue la primera prueba completa publicada del segundo teorema de incompletitud.
Finsler (1926) utilizó una versión de la paradoja de Richard para construir una expresión que era falsa pero no demostrable en un marco informal particular que había desarrollado. [30] Gödel no conocía este artículo cuando demostró los teoremas de incompletitud (Collected Works Vol. IV., p. 9). Finsler le escribió a Gödel en 1931 para informarle sobre este artículo, que Finsler sentía que tenía prioridad para un teorema de incompletitud. Los métodos de Finsler no se basaban en la demostrabilidad formalizada y solo tenían un parecido superficial con el trabajo de Gödel. [31] Gödel leyó el artículo pero lo encontró profundamente defectuoso, y su respuesta a Finsler expuso preocupaciones sobre la falta de formalización. [32] Finsler continuó defendiendo su filosofía de las matemáticas, que evitaba la formalización, durante el resto de su carrera.
En septiembre de 1931, Ernst Zermelo le escribió a Gödel para anunciarle lo que describió como una "brecha esencial" en el argumento de Gödel. [33] En octubre, Gödel respondió con una carta de 10 páginas, donde señaló que Zermelo asumió erróneamente que la noción de verdad en un sistema es definible en ese sistema; no es cierto en general según el teorema de indefinibilidad de Tarski . [34] Sin embargo, Zermelo no cedió y publicó sus críticas impresas con "un párrafo bastante mordaz sobre su joven competidor". [35] Gödel decidió que no tenía sentido seguir investigando el asunto, y Carnap estuvo de acuerdo. [36] Gran parte del trabajo posterior de Zermelo estaba relacionado con una lógica más fuerte que la lógica de primer orden, con la que esperaba demostrar tanto la consistencia como la categoricidad de las teorías matemáticas.
Ludwig Wittgenstein escribió varios pasajes sobre los teoremas de incompletitud que fueron publicados póstumamente en sus Observaciones sobre los fundamentos de las matemáticas de 1953 , en particular, una sección a veces llamada el "párrafo notorio" donde parece confundir las nociones de "verdadero" y "demostrable" en el sistema de Russell. Gödel fue miembro del Círculo de Viena durante el período en el que la filosofía del lenguaje ideal de Wittgenstein y el Tractatus Logico-Philosophicus dominaron el pensamiento del círculo. Ha habido cierta controversia sobre si Wittgenstein entendió mal el teorema de incompletitud o simplemente se expresó de manera poco clara. Los escritos en el Nachlass de Gödel expresan la creencia de que Wittgenstein interpretó mal sus ideas.
Varios comentaristas han interpretado que Wittgenstein no entendió a Gödel , aunque Floyd y Putnam (2000) así como Priest (2004) han proporcionado lecturas textuales que argumentan que la mayoría de los comentarios no entienden a Wittgenstein. [37] En su publicación, Bernays, Dummett y Kreisel escribieron revisiones separadas sobre las observaciones de Wittgenstein, todas las cuales fueron extremadamente negativas. [38] La unanimidad de esta crítica hizo que las observaciones de Wittgenstein sobre los teoremas de incompletitud tuvieran poco impacto en la comunidad lógica. En 1972, Gödel afirmó: "¿Wittgenstein ha perdido la cabeza? ¿Lo dice en serio? Él expresa intencionalmente declaraciones triviales y sin sentido", y escribió a Karl Menger que los comentarios de Wittgenstein demuestran una mala comprensión de los teoremas de incompletitud escribiendo:
De los pasajes que usted cita se desprende claramente que Wittgenstein no comprendió [el primer teorema de incompletitud] (o fingió no comprenderlo). Lo interpretó como una especie de paradoja lógica, cuando en realidad es exactamente lo contrario, es decir, un teorema matemático dentro de una parte absolutamente indiscutible de las matemáticas (la teoría de los números finitarios o la combinatoria). [39]
Desde la publicación del Nachlass de Wittgenstein en 2000, una serie de artículos en filosofía han buscado evaluar si la crítica original a las observaciones de Wittgenstein estaba justificada. Floyd y Putnam (2000) sostienen que Wittgenstein tenía una comprensión más completa del teorema de incompletitud de lo que se suponía anteriormente. Se preocupan particularmente por la interpretación de una oración de Gödel para un sistema ω-inconsistente como si dijera "no soy demostrable", ya que el sistema no tiene modelos en los que el predicado de demostrabilidad corresponda a la demostrabilidad real. Rodych (2003) sostiene que su interpretación de Wittgenstein no está justificada históricamente. Berto (2009) explora la relación entre los escritos de Wittgenstein y las teorías de la lógica paraconsistente. [40]
Ninguna de las siguientes traducciones coincide en todas las palabras traducidas ni en la tipografía. La tipografía es un asunto serio, porque Gödel deseaba expresamente enfatizar "aquellas nociones metamatemáticas que habían sido definidas en su sentido usual antes..." (van Heijenoort 1967, p. 595). Existen tres traducciones. De la primera, John Dawson afirma que: "La traducción de Meltzer era seriamente deficiente y recibió una crítica devastadora en el Journal of Symbolic Logic ; "Gödel también se quejó del comentario de Braithwaite (Dawson 1997, p. 216). "Afortunadamente, la traducción de Meltzer fue pronto suplantada por una mejor preparada por Elliott Mendelson para la antología de Martin Davis The Undecidable ... encontró que la traducción "no era tan buena" como esperaba... [pero debido a las limitaciones de tiempo] aceptó su publicación" (ibid). (En una nota al pie, Dawson afirma que "se arrepentiría de haber cumplido con su deber, ya que el volumen publicado estaba estropeado en su totalidad por una tipografía descuidada y numerosos errores de imprenta" (ibid)). Dawson afirma que "la traducción que Gödel favorecía era la de Jean van Heijenoort" (ibid). Para el estudiante serio existe otra versión como un conjunto de notas de clase grabadas por Stephen Kleene y JB Rosser "durante las clases dadas por Gödel en el Instituto de Estudios Avanzados durante la primavera de 1934" (cf comentario de Davis 1965, p. 39 y a partir de la p. 41); esta versión se titula "Sobre proposiciones indecidibles de sistemas matemáticos formales". En su orden de publicación:
Reimpreso en Boolos (1998, pp. 383–388)
`
