Teoremas de incompletitud de Gödel

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 incluir ninguna afirmación que no sea un teorema. Ejemplos de teorías efectivamente generadas incluyen la aritmética de Peano y la teoría de conjuntos de Zermelo-Fraenkel (ZFC). ^{[ 2 ]}

La teoría conocida como aritmética verdadera consiste en 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 posee un conjunto de axiomas recursivamente enumerable 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. ^{[ 3 ]} Esta es la noción relevante para el primer teorema de incompletitud de Gödel. No debe confundirse con la completitud semántica , 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 enunciados expresables en el lenguaje de la lógica de primer orden que no pueden ser ni demostrados ni refutados a partir de los axiomas de la lógica por sí solos.

En un sistema matemático, pensadores como Hilbert creían que era solo cuestión de tiempo encontrar una axiomatización que permitiera demostrar o refutar (mediante la demostración de su negación) cualquier fórmula matemática.

Un sistema formal puede ser sintácticamente incompleto por diseño, como suele ocurrir con 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 proposiciones 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 es completa, pero se completa con un axioma adicional que establece que no hay extremos en el orden. La hipótesis del continuo es una proposición del lenguaje de ZFC que no se puede demostrar dentro de ZFC, por lo que ZFC no es completo. 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 esto sea cierto, cabe destacar que posee un conjunto infinito, pero recursivamente enumerable, de axiomas, y puede codificar suficiente aritmética para las hipótesis del teorema de incompletitud. Por lo tanto, según el primer teorema de incompletitud, la aritmética de Peano no es completa. El teorema proporciona un ejemplo explícito de una proposición aritmética que no es ni demostrable ni refutable en la aritmética de Peano. Además, esta proposición es verdadera en el modelo usual . Asimismo, 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 ninguna proposición tal que tanto la proposición como su negación puedan demostrarse a partir de los axiomas, e 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í misma, pero ZFC + "existe un cardinal inaccesible " demuestra que ZFC es consistente porque si κ es el menor de esos cardinales, 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 consideran como axiomas todas las proposiciones del lenguaje de la aritmética de Peano , entonces esta teoría es completa, posee un conjunto de axiomas recursivamente enumerable y puede describir la suma y la multiplicación. Sin embargo, no es consistente.

Otros ejemplos de teorías inconsistentes surgen de las paradojas que aparecen 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 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 propio lenguaje. Cualquiera de estas opciones es apropiada para los teoremas de incompletitud.

La teoría de los cuerpos algebraicamente cerrados de una característica dada es completa, consistente y posee un conjunto infinito, pero recursivamente enumerable, de axiomas. Sin embargo, no es posible codificar los números enteros en esta teoría, y esta no puede describir la aritmética de los enteros. Un ejemplo similar es la teoría de los cuerpos reales cerrados , que es esencialmente equivalente a los axiomas de Tarski para la geometría euclidiana . Por lo tanto, la geometría euclidiana 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 que incluyen únicamente la 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 una teoría que 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 suficientes relaciones aritméticas 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 autoverificables ). 

Al elegir un conjunto de axiomas, uno de los objetivos es poder demostrar la mayor cantidad posible de resultados correctos, sin demostrar ninguno incorrecto. Por ejemplo, podríamos imaginar un conjunto de axiomas verdaderos que nos permitan demostrar cualquier 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 de axiomas inconsistente demostrará cualquier enunciado 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 sea a la vez completo y consistente demuestra un conjunto máximo de teoremas no contradictorios . 

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. Aquí, ZFC + "existe un cardinal inaccesible" no puede demostrarse consistente por sí mismo. Tampoco es completo, como lo demuestra la hipótesis del continuo, que es irresoluble ^{[ 4 ]} en ZFC + "existe un cardinal inaccesible".

El primer teorema de incompletitud demuestra que, en sistemas formales capaces de expresar aritmética básica, jamás se puede crear una lista finita de axiomas completa y consistente: cada vez que se añade un enunciado consistente como axioma, existen otros enunciados verdaderos que aún no pueden demostrarse, incluso con el nuevo axioma. Si se añade un axioma que completa el sistema, esto se logra a costa de su inconsistencia. Ni siquiera es posible que una lista infinita de axiomas sea completa, consistente y axiomatizada de forma efectiva.

La oración de Gödel está diseñada para referirse, indirectamente, a sí misma. La oración afirma 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 misma. De esta manera, la oración de Gödel G _F afirma indirectamente su propia indemostrabilidad dentro de F. ^{[ 5 ]}

Para demostrar el primer teorema de incompletitud, Gödel demostró que la noción de demostrabilidad dentro de un sistema podía expresarse exclusivamente en términos de funciones aritméticas que operan sobre los números de Gödel de las proposiciones del sistema. Por lo tanto, el sistema, que puede demostrar ciertos hechos sobre los números, también puede demostrar indirectamente hechos sobre sus propias proposiciones, siempre que se genere de forma efectiva. Las preguntas sobre la demostrabilidad de las proposiciones dentro del sistema se representan como preguntas sobre las propiedades aritméticas de los números mismos, que serían decidibles por el sistema si este fuera completo.

Así, aunque la sentencia de Gödel se refiere indirectamente a sentencias del sistema F , cuando se lee como una proposición aritmética, se refiere directamente solo a números naturales. Afirma que ningún número natural posee una propiedad particular, donde dicha propiedad está dada por una relación recursiva primitiva ( Smith 2007 , p. 141) . De este modo, la sentencia 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 consta de varios cuantificadores universales principales seguidos de un cuerpo sin cuantificadores (estas fórmulas se encuentran al nivel de la jerarquía aritmética ). Mediante el teorema MRDP , la sentencia de Gödel puede reescribirse como una proposición que afirma 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) . ${\displaystyle \Pi _{1}^{0}}$ 

El primer teorema de incompletitud demuestra que la sentencia de Gödel G _F de una teoría formal apropiada F es indemostrable en F. Dado que, interpretada como una afirmación sobre aritmética, esta indemostrabilidad es precisamente lo que la sentencia afirma (indirectamente), la sentencia 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 sentencia G _F es "verdadera pero indemostrable" ( Raatikainen 2020 ) . Sin embargo, dado que la sentencia de Gödel no puede especificar formalmente su interpretación prevista, la verdad de la sentencia G _F solo puede alcanzarse mediante un metaanálisis externo al sistema. En general, este metaaná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 sentencia de Gödel de una teoría consistente es verdadera como afirmación sobre la interpretación prevista de la aritmética, 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) . Dicho teorema demuestra que, cuando una sentencia es independiente de una teoría, esta tendrá modelos en los que la sentencia es verdadera y modelos en los que es falsa. Como se describió anteriormente, la sentencia de Gödel de un sistema F es una afirmación aritmética que sostiene que no existe ningún número con una propiedad particular. El teorema de incompletitud demuestra que esta afirmación será independiente del sistema F , y la verdad de la sentencia de Gödel se deduce del hecho de que ningún número natural estándar posee la propiedad en cuestión. Cualquier modelo en el que la sentencia 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 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 (pues entonces, como afirma, es falsa), ni puede ser falsa (pues 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 sentencia 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 trabajaba en la demostración del teorema de incompletitud, como por Alfred Tarski , quien da nombre al teorema .

En comparación con los teoremas enunciados en el artículo de Gödel de 1931, muchas formulaciones contemporáneas de los teoremas de incompletitud son más generales en dos sentidos. Estas formulaciones generalizadas están diseñadas para aplicarse a una clase más amplia de sistemas y, además, incorporan supuestos de consistencia menos estrictos.

Gödel demostró la incompletitud del sistema de Principia Mathematica , un sistema aritmético particular, pero una demostración similar podría aplicarse a cualquier sistema efectivo con cierta expresividad. Gödel comentó este hecho en la introducción de su artículo, pero restringió la demostración a un solo sistema por razones de concreción. En las formulaciones modernas 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 en particular. La terminología utilizada para enunciar estas condiciones aún no se había desarrollado en 1931, cuando Gödel publicó sus resultados.

La formulación y demostración original de Gödel del teorema de incompletitud requiere la suposición de que el sistema no solo es consistente, sino también ω-consistente . Un sistema es ω-consistente si no es ω-inconsistente, y es ω-inconsistente si existe un predicado P tal que para cada número natural m específico 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 afirma 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 la ω-consistencia. J. Barkley Rosser ( 1936 ) reforzó el teorema de incompletitud al encontrar una variación de la demostración ( el truco de Rosser ) que solo requiere que el sistema sea consistente, en lugar de ω-consistente. Esto es principalmente de interés técnico, ya que todas las teorías formales verdaderas de la aritmética (teorías cuyos axiomas son afirmaciones verdaderas sobre los números naturales) son ω-consistentes, y por lo tanto, el teorema de Gödel, tal como fue formulado originalmente, se aplica a ellas. La versión más fuerte del teorema de incompletitud, que solo presupone consistencia, en lugar de ω-consistencia, se conoce comúnmente como el teorema de incompletitud de Gödel y como el teorema de Gödel-Rosser. 

Existe una sutileza técnica en el segundo teorema de incompletitud con respecto al método para 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 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 ser no equivalentes en F , e incluso algunas pueden ser demostrables. Por ejemplo, la aritmética de Peano de primer orden (PA) puede probar que "el subconjunto consistente más grande de PA" es consistente. Pero, dado que PA es consistente, el subconjunto consistente más grande de PA es simplemente 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 refiere aquí al segmento inicial consistente más grande de los axiomas de PA bajo alguna enumeración efectiva particular).

La demostración 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 representamos con #( P ) el número de Gödel de una fórmula P , las condiciones de demostrabilidad dicen:

1. Si F prueba P , entonces F prueba Prov _A (#( P )) .
2. F prueba 1.; es decir, F prueba Prov _A (#( P )) → Prov _A (#( Prov _A (#( P )))) .
3. F prueba Prov _A (#( P → Q )) ∧ Prov _A (#( P )) → Prov _A (#( Q ))  (análogo del modus ponens ).

Existen sistemas, como la aritmética de Robinson, que son lo suficientemente robustos como para cumplir con los supuestos del primer teorema de incompletitud, pero que no demuestran las condiciones de Hilbert - Bernays. Sin embargo, la aritmética de Peano es lo suficientemente robusta como para verificar estas condiciones, al igual que 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 ₁ que satisfaga las condiciones técnicas descritas anteriormente no puede probar la consistencia de ningún sistema F ₂ que pruebe la consistencia de F _1. Esto se debe a que dicho sistema F ₁ puede probar que si F ₂ prueba la consistencia de F ₁ , entonces F ₁ es de hecho consistente. La afirmación de que F ₁ es consistente tiene la forma "para todo número n , n tiene la propiedad decidible de no ser un código para una prueba de contradicción en F ₁ ". Si F ₁ fuera de hecho inconsistente, entonces F ₂ probaría para algún n que n es el código de una contradicción en F _1. Pero si F ₂ también probara que F ₁ es consistente (es decir, que no existe tal n ), entonces sería inconsistente. Este razonamiento puede formalizarse en F ₁ para mostrar que si F ₂ es consistente, entonces F ₁ es consistente. Dado que, por el segundo teorema de incompletitud, F ₁ no prueba su consistencia, tampoco puede probar la consistencia de F ₂ .

Este corolario del segundo teorema de incompletitud demuestra que no hay esperanza de probar, por ejemplo, la consistencia de la aritmética de Peano utilizando ningún método finitista que pueda formalizarse en un sistema cuya consistencia sea demostrable en la aritmética de Peano (AP). Por ejemplo, el sistema de aritmética recursiva primitiva (ARP), ampliamente aceptado como una formalización precisa de las matemáticas finitistas, es demostrablemente consistente en AP. Por lo tanto, ARP no puede probar la consistencia de AP. Este hecho generalmente se interpreta como una implicación de que el programa de Hilbert , que pretendía justificar el uso de principios matemáticos "ideales" (infinitistas) en las demostraciones de enunciados matemáticos "reales" (finitistas) mediante una prueba finitista de la consistencia de dichos principios, no puede llevarse a cabo. ^{[ 7 ]}

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 demuestran 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 dicha prueba. 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 cierto 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 mediante 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 distintos. 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 ε₀ está bien fundado ; véase la demostración de consistencia de Gentzen . El teorema de Gentzen impulsó el desarrollo del análisis ordinal en la teoría _de la demostración.

Estas son equivalentes matemáticas naturales de la proposición de Gödel "verdadera pero indecidible". Se pueden demostrar en un sistema más amplio, generalmente aceptado 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 . Posteriormente, Kirby y Paris demostraron que el teorema de Goodstein , una afirmación 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 ciencias de la computación, también es indecidible desde 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 ₀ que codifica los principios aceptables basados ​​en una filosofía de las matemáticas llamada predicativismo . ^{[ 9 ]} El teorema menor de grafos relacionado pero más general (2003) tiene consecuencias para la teoría de la complejidad computacional .

El principal problema para desarrollar la demostración descrita es que, en un principio, parece que para construir una proposición p equivalente a " p no se puede demostrar", 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 demostrar que las proposiciones se pueden relacionar con números (a menudo denominada aritmetización de la sintaxis ) de tal forma que "demostrar una proposición" se puede sustituir por "comprobar si un número tiene una propiedad determinada" . Esto permite construir una fórmula autorreferencial que evita cualquier regresión infinita de definiciones. Alan Turing utilizó posteriormente la misma técnica en su trabajo sobre el problema de decisión .

En términos sencillos, se puede idear un método para que cada fórmula o enunciado formulado en el sistema obtenga un número único, denominado número de Gödel , de manera que sea posible convertir mecánicamente entre fórmulas y números de Gödel. Los números involucrados pueden ser muy largos (en cuanto a la cantidad de dígitos), pero esto no representa un obstáculo; lo importante es que dichos números se puedan construir. Un ejemplo sencillo es cómo el inglés se puede almacenar como una secuencia de números para cada letra y luego combinarlos en un único número mayor:

• La palabra helloestá codificada como 104-101-108-108-111 en ASCII , que se puede convertir en el número 104101108108111.
• La expresión lógica x=y => y=xestá codificada como 120-061-121-032-061-062-032-121-061-120 en ASCII , que se puede convertir en el número 120061121032061062032121061120.

En principio, demostrar que una afirmación es verdadera o falsa equivale a demostrar que el número que la representa posee o no una propiedad determinada. Dado que el sistema formal es lo suficientemente robusto como para razonar sobre números en general , también puede razonar sobre números que representan fórmulas y afirmaciones . Fundamentalmente, como el sistema permite razonar sobre propiedades de los números , los resultados son equivalentes a razonar sobre la demostrabilidad de sus afirmaciones equivalentes .

Habiendo demostrado que, en principio, el sistema puede hacer afirmaciones indirectas sobre la demostrabilidad, al analizar las propiedades de los números que representan dichas afirmaciones 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 denomina proposición o signo de clase . Tan pronto como x se reemplaza por un número específico, la proposición se convierte en una proposición válida , y entonces es demostrable en el sistema o no. Para ciertas fórmulas se puede demostrar que para cada número natural n , es verdadera si y solo${\displaystyle F(n)}$ si se puede demostrar (el requisito preciso en la demostración original es menos estricto, pero para el esbozo de la demostración bastará). 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 proposicionales en sí mismas no son proposiciones y, por lo tanto, no pueden probarse ni refutarse. Sin embargo, a cada forma proposicional 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 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. Entonces, 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 proposicional Bew ( y ) que utiliza esta relación aritmética para afirmar que existe un número de Gödel de una prueba de y :

Bew ( y ) = ∃ x ( y es el número de Gödel de una fórmula y x es el número de Gödel de una demostración de la fórmula codificada por y ).

El nombre Bew es la abreviatura de beweisbar , la palabra alemana para "demostrable"; este nombre fue utilizado originalmente por Gödel para denotar la fórmula de demostrabilidad que acabamos de describir. Cabe señalar que " Bew ( y ) " es simplemente una abreviatura que representa una fórmula particular, muy larga, en el lenguaje original de T ; no se afirma que la cadena " Bew " en sí misma forme parte de este lenguaje.

Una característica importante de la fórmula Bew ( y ) es que si una proposición 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 Bew( G ( p )) se cumpla.

El siguiente paso en la demostración es obtener una afirmación que, indirectamente, asegure su propia indemostrabilidad. Aunque Gödel construyó esta afirmación directamente, la existencia de al menos una afirmación de este tipo se deduce del lema diagonal , que dice que para cualquier sistema formal suficientemente fuerte y cualquier forma de afirmación F existe una afirmación p tal que el sistema demuestra

p ↔ F ( G ( p )) .

Haciendo F la negación de Bew ( x ) , obtenemos el teorema

p ↔ ~ Bew ( G ( p ))

y la p definida por esto indica aproximadamente que su propio número de Gödel es el número de Gödel de una fórmula no demostrable.

La afirmación p no es literalmente igual a ~ Bew ( G ( p )) ; más bien, p indica 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 mismo. Esto es similar a la siguiente frase en inglés:

", cuando va precedido de sí mismo entre comillas, es imposible de probar.", cuando va precedido de sí mismo entre comillas, es imposible de probar.

Esta oración no se refiere directamente a sí misma, pero al realizar la transformación indicada se obtiene la oración original como resultado, afirmando así indirectamente su propia imposibilidad de demostración. La demostración del lema diagonal emplea un método similar.

A continuación, supongamos que el sistema axiomático es ω-consistente y sea p la afirmación obtenida en la sección anterior.

Si p fuera demostrable, entonces Bew ( G ( p )) también lo sería, como se argumentó anteriormente. Pero p afirma la negación de Bew ( G ( p )) . Por lo tanto, el sistema sería inconsistente, ya que demostraría tanto una proposición como su negación. Esta contradicción demuestra que p no puede ser demostrable.

Si la negación de p fuera demostrable, entonces Bew ( G ( p )) también lo sería (ya que p se construyó 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 demostración de p , porque p no es demostrable (según el párrafo anterior). Por lo tanto, por un lado, el sistema demuestra que existe un número con una propiedad determinada (que es el número de Gödel de la demostración de p ), pero por otro lado, para cada número específico x , podemos demostrar que no posee esta propiedad. Esto es imposible en un sistema ω-consistente. Por consiguiente, la negación de p no es demostrable.

Por lo tanto, la afirmación p es indecidible en nuestro sistema axiomático: no se puede probar ni refutar dentro del sistema.

De hecho, para demostrar que p no es demostrable solo se requiere la suposición de que el sistema es consistente. Se requiere la suposición más fuerte de ω-consistencia para demostrar que la negación de p no es demostrable. Por lo tanto, si p se construye para un sistema particular:

• Si el sistema es ω-consistente, no puede probar ni p ni su negación, por lo que p es indecidible.
• Si el sistema es consistente, puede tener la misma situación, o puede probar la negación de p . En este último caso, tenemos una afirmación ("no p ") que es falsa pero demostrable, y el sistema no es ω-consistente.

Si se intenta "añadir los axiomas que faltan" para evitar la incompletitud del sistema, entonces hay que añadir p o "no p " como axiomas. Pero entonces cambia la definición de "ser un número de Gödel de una prueba" de una proposición, lo que significa que la fórmula Bew ( x ) ahora es diferente. Así, cuando aplicamos el lema diagonal a esta nueva Bew, obtenemos una nueva proposición p , distinta de la anterior, que será indecidible en el nuevo sistema si es ω-consistente.

Boolos (1989) esboza una demostración 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 indemostrable. Saul Kripke descubrió independientemente un método de demostración similar . ^{[ 15 ]} La demostración de Boolos procede construyendo, para cualquier conjunto S computablemente enumerable de enunciados verdaderos de la aritmética, otro enunciado que es verdadero pero no está contenido en S. Esto da como corolario el primer teorema de incompletitud. Según Boolos, esta demostración es interesante porque proporciona un «tipo diferente de razón» para la incompletitud de las teorías efectivas y consistentes de la aritmética. ^{[ 16 ]}

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 a la demostración . 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, pensado para lectores humanos.

Natarajan Shankar anunció en 1986 demostraciones verificadas por computadora de versiones del primer teorema de incompletitud utilizando Nqthm ( Shankar 1994 ) , Russell O'Connor en 2003 utilizando Rocq (anteriormente conocido como Coq ) ( O'Connor 2005 ) y John Harrison en 2009 utilizando HOL Light ( Harrison 2009 ) . Lawrence Paulson anunció en 2013 una demostración verificada por computadora de ambos teoremas de incompletitud utilizando Isabelle ( Paulson 2014 ) .

A veces se considera que el teorema de incompletitud tiene graves consecuencias para el programa del logicismo propuesto por Gottlob Frege y Bertrand Russell , cuyo objetivo era definir los números naturales en términos de lógica. ^{[ 17 ]} Bob Hale y Crispin Wright argumentan que no representa un problema para el logicismo, ya que los teoremas de incompletitud se aplican tanto a la lógica de primer orden como a la aritmética. Sostienen que este problema solo afecta a quienes creen que los números naturales deben definirse en términos de lógica de primer orden.

Muchos lógicos creen que los teoremas de incompletitud de Gödel asestaron un golpe fatal al segundo problema de David Hilbert , que requería una prueba de consistencia finita para las matemáticas. El segundo teorema de incompletitud, en particular, suele considerarse como la causa de la imposibilidad del problema. Sin embargo, no todos los matemáticos coinciden con este análisis, y el estatus del segundo problema de Hilbert aún no está definido (véase « Perspectivas modernas sobre el estatus del problema »).

Autores como el filósofo J.R. Lucas y el físico Roger Penrose han debatido sobre las implicaciones, si las hay, de los teoremas de incompletitud de Gödel respecto a 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 humanos, ya que estos cometen errores y, por lo tanto, son inconsistentes, sí pueden aplicarse a la facultad humana de ciencias o matemáticas en general. Suponiendo que sea consistente, o bien su consistencia no puede probarse o bien no puede representarse mediante una máquina de Turing. ^{[ 18 ]}

Wigderson (2010) propuso que el concepto de "cognoscibilidad" 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 siguen muy presentes". ^{[ 19 ]}

Douglas Hofstadter , en sus libros Gödel, Escher, Bach y Yo soy un bucle extraño , cita los teoremas de Gödel como ejemplo de lo que él denomina 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, al sentido del "yo", en la mente humana. Mientras que la autorreferencia en el teorema de Gödel proviene de la frase 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 categoriza los estímulos en "símbolos" o grupos de neuronas que responden a conceptos, en lo que es, en efecto, también un sistema formal, dando lugar finalmente a símbolos que modelan el concepto de la entidad misma que realiza la percepción. Hofstadter argumenta que un bucle extraño en un sistema formal suficientemente complejo puede dar lugar a una causalidad "descendente" o "invertida", 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 solo conocer el significado de la fórmula, se puede inferir su veracidad o falsedad sin ningún esfuerzo por derivarla de la manera tradicional, que requiere avanzar metódicamente "hacia arriba" a partir de los axiomas. Esto no solo es peculiar, sino asombroso. Normalmente, no se puede simplemente observar lo que dice una conjetura matemática y recurrir al contenido de esa afirmación por sí sola para deducir si es verdadera o falsa. ^{[ 20 ]}

En el caso de la mente, un sistema formal mucho más complejo, esta "causalidad descendente" se manifiesta, según 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, en lugar de en el bajo nivel de las interacciones entre neuronas o incluso partículas fundamentales, aunque según la física estas últimas parezcan poseer el poder causal.

Existe, pues, una curiosa inversión en nuestra forma humana normal de percibir el mundo: estamos construidos para percibir las "cosas grandes" en lugar de las "cosas pequeñas", aunque el dominio de lo diminuto parece ser donde residen los verdaderos motores que impulsan la realidad. ^{[ 20 ]}

Aunque los teoremas de Gödel se estudian habitualmente en el contexto de la lógica clásica, también desempeñan un papel en el estudio de la lógica paraconsistente y de las afirmaciones inherentemente contradictorias ( dialeteia ). Priest ( 1984 , 2006 ) argumenta que reemplazar 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 evidencia del dialeteísmo . ^{[ 21 ]} La causa de esta inconsistencia es la inclusión de un predicado de verdad para un sistema dentro del lenguaje del sistema. ^{[ 22 ]} Shapiro (2002) ofrece una valoración más mixta de las aplicaciones de los teoremas de Gödel al dialeteísmo. ^{[ 23 ]} 

En ocasiones, se recurre a la incompletitud de los teoremas para argumentar cuestiones que van más allá de las matemáticas y la lógica. Varios autores han criticado estas extensiones e interpretaciones, entre ellos Franzén (2005) , Raatikainen (2005) , Sokal y Bricmont (1999) y Stangroom y Benson (2006) . ^{[ 24 ]} Sokal y Bricmont (1999) y Stangroom y 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 dan a sus ideas. Sokal y 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 (ibíd.). ^{[ 25 ]}

La conferencia de Königsberg de 1930 fue una reunión conjunta de tres sociedades académicas, con la asistencia de 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. ^{[ 28 ]} 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 tal problema. A diferencia del necio Ignorabimus , nuestro credo afirma: ¡Debemos saber! ¡Lo sabremos!

Este discurso pronto se conoció 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 es probable que Gödel estuviera presente durante el discurso de Hilbert, nunca se conocieron en persona. ^{[ 29 ]}

Gödel anunció su primer teorema de incompletitud en una mesa redonda el tercer día de la conferencia. El anuncio pasó prácticamente desapercibido, salvo para von Neumann, quien apartó a Gödel para conversar. Más tarde ese mismo año, trabajando de forma independiente con el conocimiento del primer teorema de incompletitud, von Neumann obtuvo una demostración del segundo teorema de incompletitud, que le comunicó a Gödel en una carta fechada el 20 de noviembre de 1930. ^{[ 30 ]} Gödel había obtenido de forma independiente el segundo teorema de incompletitud y lo incluyó en su manuscrito, 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 planeaba publicar una segunda parte del artículo en el siguiente volumen del Monatshefte ; la pronta aceptación del primer artículo fue una de las razones por las que cambió sus planes. ^{[ 31 ]}

En 1933-1934, Gödel impartió una serie de conferencias sobre sus teoremas en Princeton ante un público que incluía a Church, Kleene y Rosser. Para entonces, Gödel ya había comprendido que la propiedad clave que requerían sus teoremas era que el sistema debía ser efectivo (en aquel momento se utilizaba el término "recursivo general"). En 1936, Rosser demostró que la hipótesis de la ω-consistencia, que era parte integral de la demostración original de Gödel, podía sustituirse por la consistencia simple si se modificaba adecuadamente la formulación de Gödel. Estos avances 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 aritmético 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 demostración 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 demostración de consistencia de la aritmética de Gentzen. Esta fue la primera demostración completa publicada del segundo teorema de incompletitud.

• Kurt Gödel, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte für Mathematik und Physik , v. 38 n. 1, págs.  173 – 198. doi : 10.1007/BF01700692
• —, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", en Solomon Feferman , ed., 1986. Kurt Gödel Obras completas, vol. I . Oxford University Press, págs .  144-195 . ISBN 978-0195147209. El texto original en alemán con su traducción al inglés en página opuesta, precedido por una nota introductoria de Stephen Cole Kleene .
• —, 1951, «Algunos teoremas básicos sobre los fundamentos de las matemáticas y sus implicaciones», en Solomon Feferman , ed., 1995. Kurt Gödel , Obras completas, vol. III , Oxford University Press, págs.  304-323 . ISBN 978-0195147223.

Ninguna de las siguientes coincide 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 en su sentido habitual 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 reseña 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 sustituida por una mejor preparada por Elliott Mendelson para la antología de Martin Davis, The Undecidable ... encontró la traducción "no tan buena" como había esperado... [pero debido a limitaciones de tiempo] accedió a su publicación» (ibid.). (En una nota a pie de página, Dawson afirma que "lamentaría su consentimiento, pues el volumen publicado estaba plagado de tipografía descuidada y numerosos errores tipográficos" (ibid.)). Dawson afirma que "la traducción que Gödel prefería era la de Jean van Heijenoort" (ibid.). Para el estudiante serio existe otra versión como un conjunto de apuntes de clase registrados por Stephen Kleene y JB Rosser "durante las clases impartidas por Gödel en el Instituto de Estudios Avanzados durante la primavera de 1934" (cf. comentario de Davis 1965 , pág. 39 y a partir de la pág. 41); Esta versión se titula "Sobre proposiciones indecidibles de sistemas matemáticos formales". En su orden de publicación:    

• B. Meltzer (traducción) y RB Braithwaite (introducción), 1962. Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados , Dover Publications, Nueva York (edición de Dover de 1992), ISBN 0-486-66980-7(rbk.) Contiene una útil traducción de las abreviaturas alemanas de Gödel en las páginas  33-34. Como se indicó anteriormente, la tipografía, la traducción y los comentarios son cuestionables. Desafortunadamente, esta traducción fue reimpresa con todo su contenido cuestionable por

• Stephen Hawking (editor), 2005. Dios creó los números enteros: los avances matemáticos que cambiaron la historia , Running Press, Filadelfia, ISBN. 0-7624-1922-9El artículo de Gödel aparece a partir de la página 1097, y el comentario de Hawking a partir de la página 1089.

• Martin Davis (editor), 1965. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions , Raven Press, Nueva York, sin ISBN. El artículo de Gödel comienza en la página 5, precedido por una página de comentarios.
• Jean van Heijenoort, editor, 1967, 3.ª edición 1967. De Frege a Gödel: Un libro de referencia en lógica matemática, 1879-1931 , Harvard University Press, Cambridge, Massachusetts, ISBN 0-674-32449-8(pbk). Van Heijenoort realizó la traducción. Afirma que «el profesor Gödel aprobó la traducción, la cual, en muchos pasajes, se adaptó a sus preferencias» (p.  595). El artículo de Gödel comienza en la p.  595; el comentario de van Heijenoort comienza en la p.  592.
• Martin Davis (editor), 1965, ibíd. «Sobre proposiciones indecidibles de sistemas matemáticos formales». Una copia con las correcciones de erratas y las notas adicionales de Gödel comienza en la página 41, precedida por dos páginas del comentario de Davis. Hasta que Davis incluyó esta lección en su volumen, existía únicamente como apuntes mimeografiados.

• Boolos, George (1989). «Una nueva demostración del teorema de incompletitud de Gödel». Notices of the American Mathematical Society . 36 : 388–390 , 676. Reimpreso en Boolos (1998 , pp.  383–388).
• Boolos, George (1998). Lógica, lógica y lógica . Harvard University Press . pág.  443. ISBN 0-674-53766-1.
• Bernd Buldt, 2014, " El alcance del primer teorema de incompletitud de Gödel. Archivado el 6 de marzo de 2016 en Wayback Machine ", Logica Universalis , vol. 8, págs.  499-552 . doi : 10.1007/s11787-014-0107-3
• Charlesworth, Arthur (1981). "Una demostración del teorema de Gödel en términos de programas informáticos". Mathematics Magazine . 54 (3): 109– 121. doi : 10.2307/2689794 . JSTOR 2689794 . 
• Davis, Martin (1965). Lo indecidible: Artículos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Raven Press. ISBN 978-0-911216-01-1.
• Davis, Martin (2006). "El teorema de la incompletitud" (PDF) . Notices of the AMS . 53 (4): 414.
• Finsler, Paul (1926). "Formale Beweise und die Entscheidbarkeit" . Mathematische Zeitschrift . 25 : 676– 682. doi : 10.1007/bf01283861 . S2CID 121054124 . 
• Grattan-Guinness, Ivor , ed. (2005). Obras fundamentales de las matemáticas occidentales 1640-1940 . Elsevier. ISBN 9780444508713.
• van Heijenoort, Jean (1967). "Teorema de Gödel". En Edwards, Paul (ed.). Enciclopedia de Filosofía . vol.  3. Macmillan. págs. 348-357 . 
• Hellman, Geoffrey (1981). "Cómo aplicar el método de Gödel a un teorema de Frege-Russell: los teoremas de incompletitud de Gödel y el logicismo". Noûs . 15 (4 - Número especial sobre filosofía de las matemáticas): 451–468 . doi : 10.2307/2214847 . ISSN 0029-4624 . JSTOR 2214847 .  
• David Hilbert , 1900, " Problemas matemáticos ". Traducción al inglés de una conferencia pronunciada ante el Congreso Internacional de Matemáticos en París, que contiene el enunciado de Hilbert de su Segundo Problema.
• Martin Hirzel, 2000, « Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados I ». Traducción al inglés del artículo de Gödel. Archivado del original el 16 de septiembre de 2004.
• Kikuchi, Makoto; Tanaka, Kazuyuki (julio de 1994). "Sobre la formalización de las demostraciones de teoría de modelos de los teoremas de Gödel" . Notre Dame Journal of Formal Logic . 35 (3): 403– 412. doi : 10.1305/ndjfl/1040511346 . MR 1326122 . 
• Kleene, SC (1943). "Predicados y cuantificadores recursivos". Transactions of the American Mathematical Society . 53 (1): 41– 73. doi : 10.1090/S0002-9947-1943-0007371-8 .Reimpreso en Davis 1965 , págs. 255–287 
• Raatikainen, Panu (2020). "Teoremas de incompletitud de Gödel" . Enciclopedia de filosofía de Stanford . Recuperado el 7 de noviembre de 2022 .
• Raatikainen, Panu (2005). "Sobre la relevancia filosófica de los teoremas de incompletitud de Gödel" . Revue Internationale de Philosophie . 59 (4): 513– 534. doi : 10.3917/rip.234.0513 . S2CID 52083793 . 
• John Barkley Rosser , 1936, "Extensiones de algunos teoremas de Gödel y Church", reimpreso del Journal of Symbolic Logic , vol. 1 (1936), págs.  87-91, en Martin Davis, 1965, The Undecidable (loc. cit.), págs.  230-235.
• —, 1939, "Una exposición informal de las demostraciones del teorema de Gödel y del teorema de Church", reimpreso del Journal of Symbolic Logic , vol. 4 (1939), págs.  53-60, en Martin Davis 1965, The Undecidable (loc. cit.), págs.  223-230
• Smoryński, C. (1977). «Los teoremas de incompletitud». En Jon Barwise (ed.). Manual de lógica matemática . Ámsterdam: North-Holland Pub. Co., pp. 821–866 . ISBN  978-0-444-86388-1.
• Willard, Dan E. (2001). "Sistemas de axiomas autoverificables, el teorema de incompletitud y principios de reflexión relacionados". Journal of Symbolic Logic . 66 (2): 536– 596. doi : 10.2307/2695030 . JSTOR 2695030 . 
• Zach, Richard (2003). "La práctica del finitismo: cálculo épsilon y pruebas de consistencia en el programa de Hilbert" (PDF) . Synthese . 137 (1). Springer Science and Business Media LLC: 211–259 . arXiv : math/0102189 . doi : 10.1023 /a:1026247421383 . ISSN 0039-7857 . S2CID 16657040 .  
• Zach, Richard (2005). «Kurt Gödel, artículo sobre los teoremas de incompletitud (1931)». En Grattan-Guinness, Ivor (ed.). Obras fundamentales de las matemáticas occidentales 1640-1940 . Elsevier. pp. 917–925 . doi : 10.1016/b978-044450871-3/50152-2 . ISBN  9780444508713.

• Francesco Berto. Hay algo especial en Gödel: la guía completa del teorema de incompletitud. John Wiley and Sons. 2010.
• Norbert Domeisen, 1990. Logik der Antinomien . Berna: Peter Lang. 142 S. 1990. ISBN 3-261-04214-1. Zbl 0724.03003 . 
• Franzén, Torkel (2005). El teorema de Gödel  : una guía incompleta sobre su uso y abuso . Wellesley, MA: AK Peters. ISBN 1-56881-238-8MR 2146326 .​ 
• Douglas Hofstadter , 1979. Gödel, Escher, Bach: Una eterna trenza dorada . Vintage Books. ISBN 0-465-02685-0Reimpresión de 1999: ISBN 0-465-02656-7MR 0530196​ 
•  —, 2007. Soy un bucle extraño . Basic Books. ISBN 978-0-465-03078-1ISBN​ 0-465-03078-5MR 2360307​ 
• Stanley Jaki , OSB, 2005. El drama de las cantidades . Real View Books.
• Per Lindström , 1997. Aspectos de la incompletitud , Lecture Notes in Logic v. 10.
• JR Lucas , FBA, 1970. La libertad de la voluntad . Clarendon Press, Oxford, 1970.
• Adrian William Moore , 2022. El teorema de Gödel: una introducción muy breve . Oxford University Press, Oxford, 2022.
• Ernest Nagel , James Roy Newman , Douglas Hofstadter, 2002 (1958). Gödel's Proof , edición revisada. ISBN 0-8147-5816-9MR 1871678​ 
• Rudy Rucker , 1995 (1982). El infinito y la mente: La ciencia y la filosofía del infinito . Princeton Univ. Press. MR 0658492 
• Smith, Peter (2007). Introducción a los teoremas de Gödel . Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-67453-9. MR 2384958 . Archivado del original el 23-10-2005 . Recuperado el 29-10-2005 . 
• Shankar, N. (1994). Metamatemáticas, máquinas y la prueba de Gödel . Cambridge tracts in theoretical computer science. Vol.  38. Cambridge: Cambridge University Press. ISBN 0-521-58533-3.
• Raymond Smullyan , 1987. Siempre indeciso ISBN 0192801414- Rompecabezas basados ​​en la indecidibilidad en sistemas formales
• —, 1992. Teoremas de incompletitud de Gödel . Oxford Univ. Press. ISBN 0195046722
• —, 1994. Diagonalización y autorreferencia . Oxford Univ. Press. MR 1318913. ISBN  0198534507
• —, 2013. El libro de acertijos de Godel: acertijos, paradojas y demostraciones . Courier Corporation. ISBN 978-0-486-49705-1.
• Wang, Hao (1996). Un viaje lógico: De Gödel a la filosofía . MIT Press. ISBN 0-262-23189-1.MR 1433803 

• Berto, Francesco (2009). "La paradoja de Gödel y las razones de Wittgenstein". Philosophia Mathematica . III (17).
• Dawson, John W. Jr. (1996). Dilemas lógicos: La vida y obra de Kurt Gödel . Taylor & Francis. ISBN 978-1-56881-025-6.
• Dawson, John W. Jr. (1997). Dilemas lógicos: La vida y obra de Kurt Gödel . Wellesley, Massachusetts: AK Peters . ISBN 978-1-56881-256-4OCLC 36104240​​ 
• Rebecca Goldstein , 2005, Incompleteness: the Proof and Paradox of Kurt Gödel , WW Norton & Company. ISBN 0-393-05169-2
• Floyd, Juliet; Putnam, Hilary (2000). «Una nota sobre el “Párrafo Notorio” de Wittgenstein acerca del Teorema de Gödel». The Journal of Philosophy . 97 (11). JSTOR: 624– 632. doi : 10.2307/2678455 . ISSN 0022-362X . JSTOR 2678455 .  
• Harrison, J. (2009). Manual de lógica práctica y razonamiento automatizado . Cambridge: Cambridge University Press. ISBN 978-0521899574.
• David Hilbert y Paul Bernays , Grundlagen der Mathematik , Springer-Verlag.
• Hopcroft, John E.; Ullman , Jeffrey (1979). Introducción a la teoría de autómatas, lenguajes y computación . Reading, Mass.: Addison-Wesley. ISBN 0-201-02988-X.
• Hofstadter, Douglas R. (2007) [2003]. «Capítulo 12. Sobre la causalidad descendente» . Soy un bucle extraño . Basic Books. ISBN 978-0-465-03078-1Archivado del original el 8 de mayo de 2019. Consultado el 24 de octubre de 2018 .
• Jones, James P. (1980). "Ecuaciones diofánticas indecidibles" (PDF) . Boletín de la Sociedad Matemática Americana . 3 (2): 859– 862. doi : 10.1090/S0273-0979-1980-14832-6 .
• Kleene, Stephen Cole (1967). "Lógica matemática". Nature . 216 (5111): 201. Bibcode : 1967Natur.216..201G . doi : 10.1038/216201b0 .Reimpreso por Dover, 2002. ISBN 0-486-42533-9
• O'Connor, Russell (2005). «La incompletitud esencial de la aritmética verificada por Coq». Demostración de teoremas en lógicas de orden superior . Notas de clase en informática. Vol.  3603. pp. 245–260 . arXiv : cs/0505034 . doi : 10.1007/11541868_16 . ISBN  978-3-540-28372-0. S2CID 15610367 . 
• Paulson, Lawrence (2014). "Una demostración asistida por máquina de los teoremas de incompletitud de Gödel para la teoría de conjuntos hereditariamente finitos" . Review of Symbolic Logic . 7 (3): 484– 498. arXiv : 2104.14260 . doi : 10.1017/S1755020314000112 . S2CID 13913592 . 
• Priest, Graham (1984). "Revisited Logic of Paradox". Journal of Philosophical Logic . 13 (2): 153– 179. doi : 10.1007/BF00453020 .
• Priest, Graham (2004). «Observaciones de Wittgenstein sobre el teorema de Gödel». En Max Kölbel (ed.). La importancia perdurable de Wittgenstein . Psychology Press. pp. 207–227 . ISBN  978-1-134-40617-3.
• Priest, Graham (2006). En contradicción: un estudio de lo transconsistente . Oxford University Press. ISBN 0-19-926329-9.
• Putnam, Hilary (1960). "Mentes y máquinas". En Sidney Hook (ed.). Dimensiones de la mente: un simposio . New York University Press.Reimpreso en Anderson, AR, ed., 1964. Mentes y máquinas . Prentice-Hall: 77.
• Wolfgang Rautenberg , 2010, Introducción concisa a la lógica matemática , 3.ª ed., Springer, ISBN 978-1-4419-1220-6
• Rodych, Victor (2003). "Malentendido sobre Gödel: Nuevos argumentos sobre Wittgenstein y nuevas observaciones de Wittgenstein". Dialectica . 57 (3): 279– 313. doi : 10.1111/j.1746-8361.2003.tb00272.x .doi : 10.1111/j.1746-8361.2003.tb00272.x
• Shelah, Saharon (1974). "Grupos abelianos infinitos, problema de Whitehead y algunas construcciones" . Israel Journal of Mathematics . 18 (3): 243– 256. doi : 10.1007/BF02757281 . MR 0357114 . 
• Shapiro, Stewart (2002). "Incompletitud e inconsistencia". Mind . 111 (444): 817– 32. doi : 10.1093/mind/111.444.817 .
• Sokal, Alan ; Bricmont, Jean (1999). Disparates de moda : El abuso de la ciencia por parte de los intelectuales posmodernos . Picador. ISBN 0-312-20407-8.
• Shoenfield, Joseph R. (1967). Lógica matemática . Natick, Mass.: Association for Symbolic Logic (publicado en 2001). ISBN 978-1-56881-135-2.
• Stangroom, Jeremy ; Benson, Ophelia (2006). Por qué importa la verdad . Continuum. ISBN 0-8264-9528-1.
• George Tourlakis, Lecciones de lógica y teoría de conjuntos, Volumen 1, Lógica matemática , Cambridge University Press, 2003. ISBN 978-0-521-75373-9
• Wigderson, Avi (2010). "El fenómeno Gödel en matemáticas: una visión moderna" (PDF) . Kurt Gödel y los fundamentos de las matemáticas: horizontes de la verdad . Cambridge University Press.
• Hao Wang , 1996, Un viaje lógico: De Gödel a la filosofía , The MIT Press, Cambridge, MA, ISBN 0-262-23189-1.
• Zach, Richard (2007). «El programa de Hilbert: antes y ahora». En Jacquette, Dale (ed.). Filosofía de la lógica . Manual de filosofía de la ciencia. Vol.  5. Ámsterdam: Elsevier. pp. 411–447 . arXiv : math/0508572 . doi : 10.1016/b978-044451541-4/50014-2 . ISBN  978-0-444-51541-4. OCLC 162131413 . S2CID 291599 .