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 teorías axiomáticas formales. Estos resultados, publicados por Kurt Gödel en 1931, son importantes tanto en la lógica matemática como en la filosofía de las matemáticas . Los teoremas se interpretan ampliamente, pero no universalmente, como que muestran 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 probar todas las verdades sobre la aritmética de los números naturales . Para cualquier sistema formal consistente, siempre habrá afirmaciones sobre números naturales que sean verdaderas, pero que no sean demostrables dentro del sistema.
El segundo teorema de incompletitud, una extensión del primero, muestra que el sistema no puede demostrar su propia consistencia.
Empleando un argumento diagonal , los teoremas de incompletitud de Gödel fueron el primero 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 ningún algoritmo para resolver el problema de la detención .
Los teoremas de incompletitud se aplican a sistemas formales que son de suficiente complejidad 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 consta de un conjunto particular de axiomas junto con reglas de manipulación simbólica (o reglas de inferencia) que permiten derivar nuevos teoremas a partir de los axiomas. Un ejemplo de tal sistema es la aritmética de Peano de primer orden , un sistema en el que todas las variables pretenden denotar números naturales. En otros sistemas, como la teoría de conjuntos , sólo algunas oraciones del sistema formal expresan enunciados sobre los números naturales. Los teoremas de incompletitud tratan de la demostrabilidad formal dentro de estos sistemas, más que de la "demostrabilidad" en un sentido informal.
Hay varias propiedades que puede tener un sistema formal, incluida la integridad, la coherencia 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 estas 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 de computadora que, en principio, podría enumerar todos los teoremas del sistema sin enumerar ningún enunciado que no sea teorema. Ejemplos de teorías generadas eficazmente 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 consta de todas las afirmaciones verdaderas 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 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] Ésta es la noción relevante para el primer teorema de incompletitud de Gödel. No debe confundirse con completitud semántica , lo que significa que el conjunto de axiomas prueba 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 completo, ya que hay oraciones expresables en el lenguaje de la lógica de primer orden que no pueden ser demostradas ni refutadas únicamente a partir de los axiomas de la lógica.
En un sistema matemático, pensadores como Hilbert creían que era sólo cuestión de tiempo encontrar una axiomatización que permitiera probar o refutar (probando su negación) cada fórmula matemática.
Un sistema formal puede ser sintácticamente incompleto por diseño, como generalmente lo son las lógicas. O puede estar 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 está incompleta, porque algunas afirmaciones del lenguaje (como el propio postulado de las paralelas) no pueden demostrarse a partir de los axiomas restantes. De manera similar, la teoría de los órdenes lineales densos no está completa, pero se completa con un axioma adicional que establece 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 existe un candidato obvio para un nuevo axioma que resuelva la cuestión.
La teoría de la aritmética de Peano de primer orden parece coherente. Suponiendo que este sea realmente el caso, tenga en cuenta que tiene un conjunto de axiomas infinito pero recursivamente enumerable y puede codificar suficiente aritmética para las hipótesis del teorema de incompletitud. Así, según 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, esta afirmación es cierta en el modelo habitual . Además, ninguna extensión consistente y axiomatizada de la aritmética de Peano puede ser completa.
Un conjunto de axiomas es (simplemente) consistente si no existe un 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 desde ZFC, pero no desde dentro de sí misma. De manera similar, ZFC no es demostrablemente consistente desde dentro de sí mismo, pero ZFC + "existe un cardinal inaccesible " demuestra que ZFC es consistente porque si κ es el menor cardinal, entonces V κ ubicado dentro del universo de von Neumann es un modelo de ZFC, y una teoría es consistente si y sólo si tiene un modelo.
Si se toman todos los enunciados en el lenguaje de la aritmética de Peano como axiomas, 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 sólo 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 Q de Robinson . Algunos sistemas, como la aritmética de Peano, pueden expresar directamente enunciados sobre números naturales. Otros, como la teoría de conjuntos ZFC, pueden interpretar afirmaciones sobre números naturales en su lenguaje. Cualquiera de estas opciones es apropiada para los teoremas de incompletitud.
La teoría de campos algebraicamente cerrados de una característica dada es completa, consistente y tiene un conjunto de axiomas infinito pero recursivamente enumerable. 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 números enteros. Un ejemplo similar es la teoría de campos cerrados reales , que es esencialmente equivalente a los axiomas de Tarski para la geometría euclidiana . De modo que la propia geometría euclidiana (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 consta de un conjunto de axiomas para los números naturales con sólo la operación de suma (se omite la multiplicación). La aritmética de Presburger es completa, consistente y recursivamente enumerable y puede codificar la suma 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 suma sino también la multiplicación.
Dan Willard (2001) ha estudiado algunas familias débiles de sistemas aritméticos que permiten suficiente aritmética 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 probar 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 probar 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 probará cada enunciado en su lenguaje (a esto a veces se le llama principio de explosión ) y, por lo tanto, está automáticamente completo. Sin embargo, un conjunto de axiomas que sea completo y consistente demuestra un conjunto máximo de teoremas no contradictorios . [ cita necesaria ]
El patrón ilustrado en las secciones anteriores con aritmética de Peano, ZFC y ZFC + "existe un cardenal inaccesible" generalmente no se puede romper. Aquí ZFC + "existe un cardenal inaccesible" no puede demostrarse por sí solo como coherente. Tampoco es completo, como lo ilustra la hipótesis del continuo, que es irresoluble [3] en ZFC + "existe un cardenal 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 agrega un enunciado adicional y consistente como axioma, hay otros enunciados verdaderos que aún no pueden demostrarse, incluso con el nuevo axioma. Si alguna vez se agrega un axioma que completa el sistema, lo hace a costa de volverlo 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 pueda realizar una cierta cantidad de aritmética elemental es incompleto; es decir, hay enunciados del lenguaje de F que no se pueden probar ni refutar en F ". (Raatikainen 2020)
El enunciado no demostrable G F al que se refiere el teorema a menudo se denomina "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 declaraciones 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 generado efectivamente tiene su propia sentencia de Gödel. Es posible definir un sistema más grande F' que contenga el conjunto 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 GF establece únicamente que no es demostrable en F , su demostrabilidad dentro de F' no presenta ninguna contradicción . Sin embargo, debido a que el teorema de incompletitud se aplica a F' , habrá un nuevo enunciado de Gödel G F ' para F' , que demuestra que F' también es incompleto. GF ' se diferenciará de GF en que GF ' se referirá a F' , en lugar de a F.
La frase de Gödel está diseñada para referirse, indirectamente, a sí misma. La oración establece que, cuando se usa 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 la propia G F. De esta manera, la oración de Gödel G F establece indirectamente su propia imposibilidad de demostrar dentro de F (Smith 2007, p. 135).
Para probar el primer teorema de incompletitud, Gödel demostró que la noción de demostrabilidad dentro de un sistema podría expresarse puramente en términos de funciones aritméticas que operan sobre los números de Gödel de oraciones del sistema. Por lo tanto, el sistema, que puede probar ciertos hechos sobre números, también puede probar indirectamente hechos sobre sus propios enunciados, siempre que se generen efectivamente. Las preguntas sobre la demostrabilidad de enunciados dentro del sistema se representan como preguntas sobre las propiedades aritméticas de los números mismos, que el sistema podría decidir 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, cuando esa propiedad está dada por una relación recursiva primitiva (Smith 2007, p. 141). Como tal, la oración de Gödel se puede escribir 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 consta de una serie de cuantificadores universales principales seguidos de un cuerpo libre de cuantificadores (estas fórmulas se encuentran en el nivel de la jerarquía aritmética ). A través del teorema MRDP , la oración de Gödel se puede reescribir como una afirmación de que un polinomio particular en muchas variables con coeficientes enteros nunca toma el valor cero cuando se sustituyen sus variables por números enteros (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 no es demostrable en F . Debido a que, cuando se interpreta como una afirmación sobre aritmética, esta imposibilidad de demostrar es exactamente lo que la oración afirma (indirectamente), la oración de Gödel es, de hecho, verdadera (Smoryński 1977, p. 825; ver 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 prevista, sólo se puede llegar a la verdad de la oración G F a través de un metanálisis desde fuera del sistema. En general, este metanálisis se puede llevar 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ágina 840, Kikuchi y Tanaka 1994, página 403).
Aunque la oración de Gödel de una teoría consistente es verdadera como afirmación sobre la interpretación prevista 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 una declaración aritmética 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 deriva 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. Dicho modelo 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 analogías semánticas de su resultado sintáctico incompleto en la sección introductoria de " Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas relacionados I ". La paradoja del mentiroso es la frase "Esta frase es falsa". Un análisis de la oración mentirosa 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 mentirosa, pero con la verdad reemplazada por demostrabilidad: G dice " G no es demostrable en el sistema F ". El análisis de la verdad y demostrabilidad de G es una versión formalizada del análisis de la verdad de la sentencia mentirosa.
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 teorema de indefinibilidad de Tarski , fue descubierto de forma independiente tanto por Gödel, cuando trabajaba en la demostración 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, muchas declaraciones contemporáneas de los teoremas de incompletitud son más generales en dos sentidos. Estas declaraciones generalizadas están redactadas para aplicarse a una clase más amplia de sistemas, y están redactadas para incorporar supuestos de coherencia más débiles.
Gödel demostró lo incompleto 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 por motivos de concreción. En los enunciados modernos del teorema, es común plantear las condiciones de efectividad y expresividad como hipótesis para el teorema de incompletitud, de modo que no se limite a ningún sistema formal en particular. La terminología utilizada para expresar estas condiciones aún no estaba desarrollada en 1931 cuando Gödel publicó sus resultados.
La afirmación original de Gödel y la prueba del teorema de incompletitud requieren la suposición de que el sistema no sólo es 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 hay Existe un número natural n tal que P ( n ). Es decir, el sistema dice que existe un número con la propiedad P pero 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) reforzó el teorema de la 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 es principalmente de interés 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 planteó originalmente se aplica a ellas. La versión más fuerte del teorema de incompletitud que sólo asume 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 contiene aritmética básica, es posible definir canónicamente una fórmula Cons( F ) que expresa 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". A menudo se considera que la contradicción sintáctica es "0=1", en cuyo caso Cons( F ) establece "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 la siguiente afirmación, el término "sistema formalizado" también incluye el supuesto de que F está efectivamente axiomatizado. Este teorema establece que para cualquier sistema consistente F dentro del cual se pueda realizar una cierta cantidad de aritmética elemental, la consistencia de F no se puede probar 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.
Hay una sutileza técnica en el segundo teorema de incompletitud con respecto al método de expresar la consistencia de F como una fórmula en el lenguaje de F. Hay muchas formas de expresar la coherencia de un sistema y no todas conducen al mismo resultado. La fórmula Cons( F ) del segundo teorema de incompletitud es una expresión particular de consistencia.
Otras formalizaciones de la afirmación de que F es consistente pueden no ser equivalentes en F , y algunas incluso pueden ser demostrables. Por ejemplo, la aritmética de Peano (PA) de primer orden puede demostrar que "el subconjunto consistente más grande de PA" es consistente. Pero, debido a que la PA es consistente, el subconjunto consistente más grande de PA es solo PA, por lo que en este sentido la PA "demuestra que es consistente". Lo que la AP no prueba es que el subconjunto consistente más grande de AP sea, de hecho, la totalidad de la AP. (El término "subconjunto consistente más grande de PA" pretende ser 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 . Dejando que #( P ) represente el número de Gödel de una fórmula P , las condiciones de demostrabilidad dicen:
Hay 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 sólida como para verificar estas condiciones, como lo son todas las teorías más sólidas 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 demuestre la consistencia de F 1 . Esto se debe a que dicho sistema F 1 puede demostrar que si F 2 demuestra 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 demostrara que F 1 es consistente (es decir, que no existe tal n ), entonces sería en sí mismo inconsistente. Este razonamiento puede formalizarse en F 1 para demostrar que si F 2 es consistente, entonces F 1 es consistente. Dado que, según 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 demostrar, 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 AP. Por tanto, la PRA no puede probar la coherencia de la PA. Generalmente se considera que este hecho implica que el programa de Hilbert , que pretendía justificar el uso de principios matemáticos "ideales" (infinitistas) en las pruebas de enunciados matemáticos "reales" (finitistas) dando una prueba finitista de que los principios ideales son consistentes, no se puede llevar a cabo. [5]
El corolario también indica la relevancia epistemológica del segundo teorema de incompletitud. No proporcionaría información interesante si un sistema F demostrara su consistencia. Esto se debe a que las teorías inconsistentes lo prueban todo, incluida su coherencia. Así, 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 mediante tal prueba de consistencia. El interés de las pruebas de consistencia radica en la posibilidad de probar la consistencia de un sistema F en algún sistema F' que en algún sentido es 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 probar la consistencia de F mediante lo anterior. Corolario del segundo teorema de incompletitud.
El segundo teorema de incompletitud no descarta por completo la posibilidad de demostrar la consistencia de alguna teoría T , y sólo lo hace en una teoría en la que T en sí pueda demostrar ser consistente. 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 fundamentado ; consulte la prueba de coherencia de Gentzen . El teorema de Gentzen impulsó el desarrollo del análisis ordinal en la teoría de la prueba.
Hay dos sentidos distintos de la palabra "indecidible" en matemáticas e informática. El primero de ellos es el sentido de la teoría de la prueba utilizado en relación con los teoremas de Gödel, el de un enunciado que no es demostrable ni refutable en un sistema deductivo específico . El segundo sentido, que no se discutirá aquí, se utiliza en relación con la teoría de la computabilidad y no se aplica a enunciados sino a problemas de decisión , que son conjuntos contablemente infinitos de preguntas, cada una de las cuales requiere 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 (ver problema indecidible ).
Debido a los dos significados de la palabra indecidible, a veces se utiliza el término independiente en lugar de indecidible en el sentido de "ni demostrable ni refutable".
La indecidibilidad de un enunciado en un sistema deductivo particular no aborda, en 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 La elección no se puede probar ni refutar 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 ninguna de estas afirmaciones podía ser refutada en la teoría de conjuntos ZF o ZFC. En la década de 1960, Cohen demostró que ninguna de las dos cosas es demostrable a partir de ZF y que la hipótesis del continuo no puede demostrarse 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 afirmaciones indecidibles en la teoría algorítmica de la información 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 .
Estos son equivalentes matemáticos naturales de la frase "verdadera pero indecidible" de Gödel. 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 infinito de Ramsey , 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 desde la aritmética de Peano pero demostrable en 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 basados en una filosofía de las matemáticas llamada predicativismo . [7] El teorema menor del grafo relacionado pero más general (2003) 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 recursividad .
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 de computadora puede determinar correctamente, dado cualquier programa P como entrada, si P eventualmente se detiene cuando se ejecuta con una entrada dada en particular. Kleene demostró que la existencia de un sistema aritmético completo y efectivo con ciertas propiedades de consistencia obligaría al problema de detención a ser decidible, una contradicción. [8] Este método de prueba también ha sido presentado por Shoenfield (1967); Charlesworth (1981); y Hopcroft y Ullman (1979). [9]
Franzén (2005) explica cómo la solución de Matiyasevich al décimo problema de Hilbert puede utilizarse para obtener una prueba del primer teorema de incompletitud de Gödel. [10] Matiyasevich demostró que no existe ningún algoritmo que, dado un polinomio multivariado p ( x 1 , x 2 ,..., x k ) con coeficientes enteros, determine si existe una solución entera a la ecuación p = 0. Porque Los polinomios con coeficientes enteros, y los propios números enteros, 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 números enteros, entonces cualquier sistema de aritmética T suficientemente fuerte lo demostrará. Además, supongamos que el sistema T es ω-consistente. En ese caso, nunca se demostrará que una ecuación polinómica particular tiene solución cuando no hay solución en los números enteros. Por lo tanto, si T fuera completo y ω-consistente, sería posible determinar algorítmicamente si una ecuación polinómica tiene solución simplemente enumerando pruebas de T hasta que se encuentre " p tiene solución" o " p no tiene solución", en contradicción con el teorema de Matiyasevich. De ahí se sigue que T no puede ser ω-consistente y completo. Además, para cada sistema consistente T generado efectivamente , es posible generar efectivamente un polinomio multivariado p sobre los números enteros tal que la ecuación p = 0 no tenga soluciones sobre los números enteros, pero la falta de soluciones no se puede probar en T. [11]
Smoryński (1977) muestra cómo se puede utilizar la existencia de conjuntos recursivamente inseparables para demostrar el primer teorema de incompletitud. Esta prueba se amplía a menudo para mostrar 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 mencionada anteriormente, el teorema de Chaitin sólo 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, sin embargo, incluyen declaraciones falsas en el modelo estándar; estas teorías se conocen como ω-inconsistentes .
La prueba por contradicción tiene tres partes esenciales. Para comenzar, elija un sistema formal que cumpla con los criterios propuestos:
El principal problema al desarrollar la prueba descrita anteriormente es que al principio parece que para construir un enunciado p que sea equivalente a " p no puede ser probado", p tendría que contener de alguna manera 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 mostrar que los enunciados pueden relacionarse con números (a menudo llamado aritmetización de la sintaxis ) de tal manera que "probar un enunciado" puede reemplazarse por "probar si un número tiene una propiedad determinada" . Esto permite construir una fórmula autorreferencial de manera que evite cualquier regresión infinita de definiciones. La misma técnica fue utilizada más tarde 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 número de Gödel , de tal manera que sea posible convertir mecánicamente de un lado a otro entre fórmulas y Gödel. números. 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 esos números puedan construirse. Un ejemplo simple es cómo el inglés se puede almacenar como una secuencia de números para cada letra y luego combinarse en un único número mayor:
En principio, se puede demostrar que demostrar que una afirmación es verdadera o falsa es equivalente a demostrar que el número que coincide con la afirmación tiene o no una propiedad determinada. Debido a que el sistema formal es lo suficientemente fuerte como para respaldar el razonamiento sobre números en general , también puede respaldar el razonamiento sobre números que representan fórmulas y enunciados . Fundamentalmente, debido a que el sistema puede soportar el razonamiento sobre las propiedades de los números , los resultados son equivalentes al razonamiento sobre la demostrabilidad de sus enunciados equivalentes .
Habiendo demostrado que, en principio, el sistema puede hacer afirmaciones indirectamente sobre la demostrabilidad, al analizar las propiedades de esos números que representan afirmaciones, ahora es posible mostrar cómo crear una afirmación que realmente haga esto.
Una fórmula F ( x ) que contiene exactamente una variable libre x se llama forma de declaración o signo de clase . Tan pronto como x se reemplaza por un número específico, la forma de declaración se convierte en una declaración auténtica , y entonces es demostrable en el sistema o no. Para ciertas fórmulas se puede demostrar que para todo número natural n , es verdadero si y sólo si se puede demostrar (el requisito preciso en la prueba original es más débil, pero para el esquema de 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".
Los formularios de declaración en sí mismos no son declaraciones y, por lo tanto, no se pueden probar ni refutar. Pero a cada enunciado en forma 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 misma de demostrabilidad también puede codificarse mediante números de Gödel, de la siguiente manera: dado que una prueba es una lista de enunciados que obedecen ciertas reglas, se puede definir el número de Gödel de una prueba. Ahora bien, para cada enunciado p , uno puede preguntarse 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 potencial de Gödel de su prueba, es una relación aritmética entre dos números. Por lo tanto, existe un enunciado en forma de 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"; Gödel utilizó originalmente este nombre para indicar la fórmula de demostrabilidad que acabamos de describir. Tenga en cuenta 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 " sea parte de este lenguaje.
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 prueba 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 demostrarlo. Aunque Gödel construyó este enunciado directamente, la existencia de al menos uno de esos enunciados se deduce del lema diagonal , que dice que para cualquier sistema formal suficientemente fuerte y cualquier enunciado en forma F existe un enunciado p tal que el sistema prueba
Haciendo que F sea 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 no demostrable.
La declaración p no es literalmente igual a ~ Bew ( G ( p )) ; más bien, p establece que si se realiza un determinado cálculo, el número de Gödel resultante será el de una afirmación no demostrable. Pero cuando se realiza este cálculo, el número de Gödel resultante resulta ser el número de Gödel de p mismo. Esto es similar a la siguiente oración en inglés:
Esta oración no se refiere directamente a sí misma, pero cuando se realiza la transformación establecida se obtiene como resultado la oración original y, por lo tanto, esta oración afirma indirectamente su propia indemostrabilidad. La prueba 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 tanto, el sistema sería inconsistente, demostrando 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 se construyó para que fuera 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 prueba que hay un número con una determinada 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 probar que no tiene esta propiedad. Esto es imposible en un sistema ω-consistente. Por tanto, la negación de p no es demostrable.
Así, 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 el supuesto de que el sistema es consistente. Se requiere el supuesto más fuerte de consistencia ω para demostrar que la negación de p no es demostrable. Por tanto, si p se construye para un sistema particular:
Si uno intenta "agregar los axiomas que faltan" para evitar que el sistema esté incompleto, entonces hay que agregar p o "no p " como axiomas. Pero entonces cambia la definición de "ser un número de Gödel de una prueba" de un enunciado. lo que significa que la fórmula Bew ( x ) ahora es diferente. Así, cuando aplicamos el lema de la 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. Saul Kripke descubrió de forma independiente un método de prueba similar . [13] La prueba de Boolos procede construyendo, para cualquier conjunto computable enumerable S de oraciones aritméticas verdaderas, otra oración que sea 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 explicar lo incompletos que son las 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 un software asistente de prueba . Las demostraciones originales de Gödel de los teoremas de incompletitud, como la mayoría de las demostraciones matemáticas, fueron escritas en lenguaje natural destinado a lectores humanos.
Natarajan Shankar anunció pruebas verificadas por computadora de versiones del primer teorema de incompletitud en 1986 usando Nqthm (Shankar 1994), Russell O'Connor en 2003 usando Coq (O'Connor 2005) y John Harrison en 2009 usando HOL Light ( Harrison 2009). Lawrence Paulson anunció en 2013 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 mostrar que varios hechos sobre la demostrabilidad utilizados en la demostración del primer teorema de incompletitud pueden formalizarse dentro de un sistema S utilizando un predicado formal P para la demostrabilidad. Una vez hecho esto, el segundo teorema de incompletitud sigue al formalizar la prueba completa del primer teorema de incompletitud dentro del propio sistema S.
Sea p la oración indecidible construida anteriormente y supongamos, para obtener una contradicción, que la consistencia del sistema S puede demostrarse desde dentro del propio sistema S. Esto equivale a demostrar la afirmación "El sistema S es consistente". Ahora considere 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 el enunciado c , " p no es demostrable", (o de manera idéntica, "no P ( p ) ") puede probarse en el sistema S.
Observe entonces que si podemos demostrar que el sistema S es consistente (es decir, el enunciado de la hipótesis de c ), entonces habremos demostrado que p no es demostrable. Pero esto es una contradicción ya que según el primer 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. Observe que esta es la razón por la que requerimos formalizar el primer teorema de incompletitud en S : para demostrar el segundo teorema de incompletitud, obtenemos una contradicción con el primer teorema de incompletitud que sólo puede funcionar demostrando que el teorema se cumple en S. Entonces no podemos probar que el sistema S sea consistente. Y sigue el segundo enunciado del teorema de incompletitud.
Los resultados de incompletitud afectan la filosofía de las matemáticas , particularmente 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 la incompletitud tiene graves consecuencias para el programa de logicismo propuesto por Gottlob Frege y Bertrand Russell , que pretendía 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 igualmente a la lógica de primer orden como a la aritmética. Sostienen que sólo 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 asestaron un golpe fatal al segundo problema de David Hilbert , que pedía una prueba de consistencia finita para las matemáticas. A menudo se considera que el segundo teorema de incompletitud, en particular, hace que el problema sea imposible. Sin embargo, no todos los matemáticos están de acuerdo con este análisis y el estado del segundo problema de Hilbert aún no está decidido (ver " Puntos de vista modernos sobre el estado del problema ").
Autores, entre ellos 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 se le aplicarían los teoremas de incompletitud de Gödel.
Putnam (1960) sugirió que, si bien los teoremas de Gödel no pueden aplicarse a los seres humanos, ya que cometen errores y, por tanto, son inconsistentes, sí pueden aplicarse a la facultad humana de las ciencias o de las matemáticas en general. Suponiendo que sea consistente, o no se puede probar su consistencia o no se puede representar mediante una máquina de Turing. [dieciséis]
Wigderson (2010) ha propuesto que el concepto de "conocibilidad" matemática debería basarse en la complejidad computacional en lugar de 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". [17]
Douglas Hofstadter , en sus libros Gödel, Escher, Bach y Soy un bucle extraño , cita los teoremas de Gödel como 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 origen 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 demostrar 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 efectivamente es 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 "descendente" 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, como sigue:
Simplemente conociendo el significado de la fórmula, uno puede inferir su verdad o falsedad sin ningún esfuerzo por derivarla a la antigua usanza, que requiere caminar metódicamente "hacia arriba" desde los axiomas. Esto no es sólo peculiar; es asombroso. Normalmente, uno no puede limitarse a mirar lo que dice una conjetura matemática y simplemente apelar al contenido de esa afirmación por sí solo para deducir si es verdadera o falsa. [18]
En el caso de la mente, un sistema formal mucho más complejo, esta "causalidad descendente" se manifiesta, en opinió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, y no en el bajo nivel de interacciones entre neuronas o incluso partículas fundamentales, aunque según la física estas últimas parecen poseer el poder causal.
Por lo tanto, existe una curiosa inversión en nuestra forma humana normal de percibir el mundo: estamos hechos para percibir “cosas grandes” en lugar de “cosas pequeñas”, aunque el dominio de lo pequeño parece ser donde los motores reales impulsan la realidad. residir. [18]
Aunque los teoremas de Gödel suelen estudiarse en el contexto de la lógica clásica, también tienen un papel en el estudio de la lógica paraconsistente y de enunciados inherentemente contradictorios ( dialetheia ). Priest (1984, 2006) sostiene que reemplazar la noción de prueba formal en el teorema de Gödel con la noción habitual de prueba informal puede usarse para mostrar que las matemáticas ingenuas son inconsistentes, y usa esto como evidencia a favor 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 evaluación más variada de las aplicaciones de los teoremas de Gödel al dialeteísmo. [21]
A veces se hacen apelaciones y analogías a la incompletitud de los teoremas en apoyo de 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 y Benson (2006). [22] Sokal & Bricmont (1999) y Stangroom & Benson (2006), por ejemplo, citan comentarios de Rebecca Goldstein sobre la disparidad entre el platonismo declarado de Gödel y los usos antirrealistas que a veces se dan a sus ideas. Sokal y Bricmont (1999) critican la invocación del teorema por 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 demostración del teorema de completitud como su tesis doctoral en 1929, recurrió 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 los números naturales y los números reales similares a la aritmética de segundo orden se conocían como "análisis", mientras que las teorías de los números naturales únicamente se conocían como "aritmética".
Gödel no fue el único que trabajó en el problema de la coherencia. Ackermann había publicado una prueba de consistencia defectuosa para análisis en 1925, en la que intentaba utilizar el método de sustitución ε desarrollado originalmente por Hilbert. Más tarde ese año, von Neumann pudo corregir la prueba de 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 en 1929 su creencia de que se había demostrado la consistencia de la aritmética y que pronto seguiría una prueba de análisis consistente. 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 no era sólida. [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 no demostrabilidad no. En particular, Gödel estaba al tanto del resultado ahora llamado 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 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 clave 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 defender su creencia de que todos los problemas matemáticos pueden resolverse. Terminó su discurso diciendo:
Para el matemático no existe Ignorabimus y, en mi opinión, tampoco existe 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. ¡Lo sabremos!
Este discurso rápidamente se hizo conocido como un resumen de las creencias de Hilbert sobre las matemáticas (sus últimas seis palabras, " Wir müssen wissen. Wir werden wissen! ", se utilizaron como epitafio de Hilbert en 1943). Aunque Gödel probablemente estuvo 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 el tercer día de la conferencia. El anuncio no llamó mucho la atención, aparte de la de von Neumann, quien llamó 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 incluyó en el manuscrito que presentó, que fue recibido por Monatshefte für Mathematik el 17 de noviembre de 1930.
El artículo de Gödel se publicó en el Monatshefte en 1931 con el título "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" ("Sobre proposiciones formalmente indecidibles en Principia Mathematica y sistemas relacionados I "). Como sugiere el título, Gödel originalmente planeó publicar una segunda parte del artículo en el próximo volumen de Monatshefte ; la pronta 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 una audiencia que incluía a Church, Kleene y Rosser. En ese momento, Gödel había comprendido que la propiedad clave que requerían sus teoremas es que el sistema debe ser efectivo (en ese momento, se usaba el término "recursivo general"). Rosser demostró en 1936 que la hipótesis de ω-consistencia, que era una parte integral de la prueba original de Gödel, podía ser reemplazada por consistencia simple si la oración de Gödel se cambiaba apropiadamente. Estos desarrollos dejaron los teoremas de incompletitud esencialmente 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 que se está demostrando consistente.
Rápidamente se comprendió el impacto de los teoremas de incompletitud en el programa de Hilbert. 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 particular e informal que él había desarrollado. [30] Gödel desconocía este artículo cuando demostró los teoremas de incompletitud (Obras completas Vol. IV., p. 9). Finsler escribió a Gödel en 1931 para informarle sobre este artículo, que según Finsler tenía prioridad para un teorema de incompletitud. Los métodos de Finsler no se basaban en una demostrabilidad formalizada y sólo 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 expresó su preocupación por 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 escribió a Gödel para anunciarle lo que describió como una "laguna esencial" en el argumento de Gödel. [33] En octubre, Gödel respondió con una carta de 10 páginas, donde señalaba 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 en forma impresa con "un párrafo bastante mordaz sobre su joven competidor". [35] . Gödel decidió que no tenía sentido seguir adelante con el asunto y Carnap estuvo de acuerdo. [36] Gran parte del trabajo posterior de Zermelo estuvo relacionado con una lógica más fuerte que la lógica de primer orden, con la que esperaba mostrar tanto la consistencia como la categoricidad de las teorías matemáticas.
Ludwig Wittgenstein escribió varios pasajes sobre los teoremas de incompletitud que se publicaron póstumamente en sus Comentarios 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 temprana filosofía del lenguaje ideal de Wittgenstein y el Tractatus Logico-Philosophicus dominaban 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 del Nachlass de Gödel expresan la creencia de que Wittgenstein interpretó mal sus ideas.
Múltiples comentaristas han interpretado a Wittgenstein como un malentendido de Gödel , aunque Floyd y Putnam (2000), así como Priest (2004), han proporcionado lecturas textuales argumentando que la mayoría de los comentarios malinterpretan a Wittgenstein. [37] Tras su liberación, Bernays, Dummett y Kreisel escribieron reseñas separadas sobre los comentarios de Wittgenstein, todas las cuales fueron extremadamente negativas. [38] La unanimidad de esta crítica hizo que los comentarios de Wittgenstein sobre los teoremas de incompletitud tuvieran poco impacto en la comunidad lógica. En 1972, Gödel declaró: "¿Ha perdido Wittgenstein la cabeza? ¿Lo dice en serio? Pronuncia intencionalmente declaraciones trivialmente sin sentido", y le escribió a Karl Menger que los comentarios de Wittgenstein demuestran una mala comprensión de los teoremas de incompletitud que escribe:
De los pasajes que usted cita se desprende claramente que Wittgenstein no entendió [el primer teorema de incompletitud] (o fingió no entenderlo). Lo interpretó como una especie de paradoja lógica, cuando en realidad es todo lo contrario, es decir, un teorema matemático dentro de una parte absolutamente indiscutible de las matemáticas (teoría de los números finitos o combinatoria). [39]
Desde la publicación de Nachlass de Wittgenstein en 2000, una serie de artículos en filosofía han tratado de evaluar si la crítica original de los comentarios 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. Están particularmente preocupados por la interpretación de una oración de Gödel para un sistema ω-inconsistente como que dice "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á históricamente justificada. Berto (2009) explora la relación entre los escritos de Wittgenstein y las teorías de la lógica paraconsistente. [40]
Ninguno de los siguientes concuerda en todas las palabras traducidas y 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 antes en su sentido habitual...". (van Heijenoort 1967, pág. 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 pronto fue 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 había esperado... [pero debido a limitaciones de tiempo ] aceptó su publicación" (ibid). (En una nota a pie de página, Dawson afirma que "lamentaría su cumplimiento, ya que el volumen publicado se vio empañado por una tipografía descuidada y numerosos errores tipográficos" (ibid)). Dawson afirma que "La traducción que favoreció Gödel fue la de Jean van Heijenoort" (ibid). Para el estudiante serio existe otra versión como un conjunto de notas grabadas por Stephen Kleene y JB Rosser "durante las conferencias 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ágina 41); esta versión se titula "Sobre proposiciones indecidibles de sistemas matemáticos formales". En su orden de publicación:
reimpreso en Boolos (1998, págs. 383–388)
`
