Teoremas de incompletitud de Gödel

ImprimirCitar

Resultados limitados en la lógica matemática

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 incompletud establece que ningún sistema consistente de axiomas cuyos teoremas puedan enumerarse mediante un procedimiento efectivo (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 de este tipo, siempre habrá afirmaciones sobre números naturales que sean verdaderas, pero que no se puedan probar 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 los primeros de varios teoremas estrechamente relacionados sobre las limitaciones de los sistemas formales. Fueron seguidos por el teorema de indefinibilidad de Tarski sobre la indefinibilidad formal de la verdad, la prueba de Church de que el Entscheidungsproblem de Hilbert no tiene solución, y el teorema de Turing de que no hay No hay algoritmo para resolver el problema de la detención.

Sistemas formales: completitud, consistencia y axiomatización efectiva

Los teoremas de incompletitud se aplican a sistemas formales que tienen la complejidad suficiente para expresar la aritmética básica de los números naturales y que son consistentes y efectivamente axiomatizados. Particularmente en el contexto de la lógica de primer orden, los sistemas formales también se denominan teorías formales. En general, un sistema formal es un aparato deductivo que consta de un conjunto particular de axiomas junto con reglas de manipulación simbólica (o reglas de inferencia) que permiten la derivación de nuevos teoremas a partir de los axiomas. Un ejemplo de tal sistema es la aritmética de Peano de primer orden, un sistema en el que todas las variables están destinadas a denotar números naturales. En otros sistemas, como la teoría de conjuntos, sólo algunas oraciones del sistema formal expresan enunciados sobre los números naturales. Los teoremas de incompletitud se refieren a la demostrabilidad formal dentro de estos sistemas, más que a la "probabilidad" en un sentido informal.

Hay varias propiedades que puede tener un sistema formal, incluyendo la integridad, la consistencia y la existencia de una axiomatización efectiva. Los teoremas de incompletitud muestran que los sistemas que contienen una cantidad suficiente de aritmética no pueden poseer estas tres propiedades.

Axiomatización efectiva

Se dice que un sistema formal está axiomatizado de manera efectiva (también llamado generado de manera efectiva) si su conjunto de teoremas es un conjunto recursivamente enumerable (Franzén 2005, p. 112).

Esto significa que existe un programa de computadora que, en principio, podría enumerar todos los teoremas del sistema sin enumerar ninguna declaración que no sea teoremas. Los ejemplos de teorías generadas de manera efectiva incluyen la aritmética de Peano y la teoría de conjuntos de Zermelo-Fraenkel (ZFC).

La teoría conocida como aritmética verdadera consiste en todas las declaraciones 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 recursivamente enumerable de axiomas y, por lo tanto, no satisface las hipótesis de los teoremas de incompletitud.

Integridad

Un conjunto de axiomas es (sintácticamente, o negación-) completo si, para cualquier declaración en los axiomas' lenguaje, ese enunciado o su negación es demostrable a partir de los axiomas (Smith 2007, p. 24). Esta es la noción relevante para el primer teorema de incompletitud de Gödel. No debe confundirse con la completitud semántica, lo que significa que el conjunto de axiomas 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 se pueden probar ni refutar a partir de los axiomas de la lógica únicamente.

En un sistema de matemáticas, pensadores como Hilbert creían que era solo cuestión de tiempo encontrar una axiomatización que permitiera probar o refutar (probando su negación) todas y cada una de las fórmulas matemáticas.

Un sistema formal puede ser sintácticamente incompleto por diseño, como lo son generalmente 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 algunos enunciados del lenguaje (como el propio postulado de las paralelas) no pueden probarse 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 declaración en el lenguaje de ZFC que no se puede demostrar dentro de ZFC, por lo que ZFC no está 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 ser consistente. Suponiendo que este sea 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í, por el primer teorema de incompletitud, la aritmética de Peano no es completa. El teorema da un ejemplo explícito de un enunciado aritmético 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 coherente y efectivamente axiomatizada de la aritmética de Peano puede ser completa.

Coherencia

Un conjunto de axiomas es (simplemente) consistente si no hay un enunciado tal que tanto el enunciado como su negación sean demostrables a partir de los axiomas, y inconsistente en caso contrario. Es decir, un sistema axiomático consistente es aquel que está libre de contradicción.

La aritmética de Peano es demostrablemente consistente con 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" prueba que ZFC es consistente porque si $κ$ es el cardenal menor, entonces $V κ$ sentado dentro del universo von Neumann hay un modelo de ZFC, y una teoría es consistente si y sólo si tiene un modelo.

Si uno toma todas las declaraciones en el lenguaje de la aritmética de Peano como axiomas, entonces esta teoría está 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 ilimitada en la teoría de conjuntos.

Sistemas que contienen aritmética

Los teoremas de incompletitud se aplican solo a sistemas formales que pueden probar 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 números naturales. Otros, como la teoría de conjuntos ZFC, pueden interpretar declaraciones 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 infinito pero recursivamente enumerable de axiomas. Sin embargo, no es posible codificar los números enteros en esta teoría, y la teoría no puede describir la aritmética de los números enteros. Un ejemplo similar es la teoría de campos cerrados reales, que es esencialmente equivalente a los axiomas de Tarski para la geometría euclidiana. Entonces, la geometría euclidiana en sí misma (en la formulación de Tarski) es un ejemplo de una teoría axiomatizada completa, consistente y efectiva.

El sistema de aritmética de Presburger consiste en un conjunto de axiomas para los números naturales con solo 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 la teoría para codificar 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 una 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).

Objetivos en conflicto

Al elegir un conjunto de axiomas, uno de los objetivos es poder probar tantos resultados correctos como sea posible, sin probar 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 declaración en su lenguaje (esto a veces se llama el principio de explosión) y, por lo tanto, se completa automáticamente. Sin embargo, un conjunto de axiomas que es completo y consistente demuestra un conjunto máximo de teoremas no contradictorios (Hinman 2005, p. 143) error de harv: sin objetivo: CITEREFHinman2005 (ayuda).

El patrón ilustrado en las secciones anteriores con aritmética de Peano, ZFC y ZFC + "existe un cardinal inaccesible" generalmente no se puede romper. Aquí ZFC + "existe un cardenal inaccesible" no puede demostrarse consistente por sí mismo. Tampoco es completa, como ilustra la hipótesis del continuo, que no se puede resolver en ZFC + "existe un cardinal inaccesible".

El primer teorema de incompletitud muestra que, en sistemas formales que pueden expresar aritmética básica, nunca se puede crear una lista finita completa y consistente de axiomas: cada vez que se agrega una declaración consistente adicional como axioma, hay otras declaraciones verdaderas eso todavía no se puede demostrar, incluso con el nuevo axioma. Si alguna vez se agrega un axioma que hace que el sistema sea completo, lo hace a costa de hacer que el sistema sea inconsistente. Ni siquiera es posible que una lista infinita de axiomas sea completa, consistente y efectivamente axiomatizada.

Primer teorema de incompletitud

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 las proposiciones formalmente indecidibles de Principia Mathematica y los 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) se puede parafrasear en inglés de la siguiente manera, donde "formal system" incluye el supuesto de que el sistema se genera efectivamente.

Primera Incomplesión Theorem: "Cualquier sistema formal consistente $F$ dentro del cual se puede llevar a cabo una cierta cantidad de aritmética elemental es incompleta; es decir, hay declaraciones del idioma $F$ que no puede probarse ni refutarse $F$ ." (Raatikainen 2020)

La afirmación no demostrable $G F$ a la que hace referencia el teorema a menudo se denomina como "la sentencia 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 el mismas propiedades, como la conjunción de la oración de Gödel y cualquier oración lógicamente válida.

Cada sistema efectivamente generado tiene su propia sentencia de Gödel. Es posible definir un sistema más grande $F'$ que contiene la totalidad de $F$ más $G F$ como 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 estar completo. En este caso, $G F$ es de hecho un teorema en $F'$ , porque es un axioma. Porque $G F$ establece únicamente que no es demostrable en $F$ , no se presenta ninguna contradicción por su demostrabilidad dentro de $F'$ . Sin embargo, debido a que el teorema de incompletitud se aplica a $F'$ , habrá una nueva declaración de Gödel $G F'$ para $F'$ , lo que muestra que $F'$ también está incompleto. $G F'$ diferirá de $G F$ en ese $G F'$ se referirá a $F'$ , en lugar de $F$ .

Forma sintáctica de la oración de Gödel

La oración 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 $G F$ sí mismo. De esta forma, la oración de Gödel $G F$ establece indirectamente su propia indemostrabilidad 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 en los números de oraciones de Gödel del sistema. Por lo tanto, el sistema, que puede probar ciertos hechos sobre los números, también puede probar indirectamente hechos sobre sus propios enunciados, siempre que se genere efectivamente. Las preguntas sobre la demostrabilidad de los enunciados dentro del sistema se representan como preguntas sobre las propiedades aritméticas de los números mismos, que serían decidibles por el sistema si estuviera completo.

Así pues, aunque la frase Gödel se refiere indirectamente a las sentencias del sistema $F$ , cuando se lee como una declaración aritmética la frase Gödel se refiere directamente sólo a números naturales. Afirma que ningún número natural tiene una propiedad particular, donde esa propiedad es dada por una relación recursiva primitiva (Smith 2007, p. 141). Como tal, la frase Gödel se puede escribir en el lenguaje de aritmética con una forma sintáctica simple. En particular, se puede expresar como una fórmula en el lenguaje de la aritmética que consiste en una serie de cuantificadores universales líderes seguidos de un cuerpo libre de cuantificadores (estas fórmulas están a nivel $Pi _{1}^{0}$ de la jerarquía aritmética). A través del teorema MRDP, la frase Gödel puede ser re-escrita como una afirmación de que un polinomio particular en muchas variables con coeficientes enteros nunca toma el valor cero cuando los enteros son sustituidos por sus variables (Franzén 2005, p. 71).

Verdad de la sentencia de Gödel

El primer teorema de incompletitud muestra que la oración de Gödel $G F$ de un la teoría formal $F$ no es demostrable en $F. Debido a que, cuando se interpreta como una afirmación sobre aritmética, esta indemostrabilidad es exactamente lo que afirma (indirectamente) la oración, la oración de Gödel es, de hecho, verdadera (Smoryński 1977, p. 825; también ver Franzén 2005, pp. 28-33). Por esta razón, a menudo se dice que la oración G F es " cierto pero indemostrable." (Raatikainen 2015) error de harv: sin destino: CITEREFRaatikainen2015 (ayuda) . Sin embargo, dado que la oración de Gödel por sí misma no puede especificar formalmente su interpretación prevista, la verdad de la oración G F solo se puede llegar a través de un metanálisis desde fuera del sistema. En general, este metanálisis puede llevarse a cabo dentro del sistema formal débil conocido como aritmética recursiva primitiva, que prueba la implicación Con (F)\to 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ág. 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 aritméticos no estándar, como consecuencia del teorema de completitud de Gödel (Franzén 2005, pág. 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. Tal modelo debe ser "no estándar" – debe contener elementos que no correspondan a ningún número natural estándar (Raatikainen 2015 harvnb error: no target: CITEREFRaatikainen2015 (ayuda), Franzén 2005, p. 135).

Relación con la paradoja del mentiroso

Gödel cita específicamente la paradoja de Richard y la paradoja del mentiroso como análogos semánticos a 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 oración "Esta oración 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 del mentiroso, pero con la verdad reemplazada por demostrabilidad: $G$ dice " $G$ no es comprobable 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 oración mentirosa.

No es posible reemplazar "no comprobable" con "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 estaba trabajando en la prueba del teorema de incompletitud, como por el homónimo del teorema, Alfred Tarski.

Extensiones del resultado original de Gödel

En comparación con los teoremas establecidos en el artículo de Gödel de 1931, muchas declaraciones contemporáneas de los teoremas de incompletitud son más generales de dos maneras. Estas declaraciones generalizadas están redactadas para aplicarse a una clase más amplia de sistemas, y están redactadas para incorporar suposiciones de consistencia más débiles.

Gödel demostró la incompletitud del sistema de Principia Mathematica, un sistema particular de aritmética, pero se podría dar una demostración paralela para cualquier sistema efectivo de cierta expresividad. Gödel comentó sobre este hecho en la introducción de su artículo, pero restringió la prueba a un sistema para mayor concreción. En las declaraciones modernas del teorema, es común establecer 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 estaba desarrollada en 1931 cuando Gödel publicó sus resultados.

La declaración original de Gödel y la prueba del teorema de incompletitud requieren la suposición de que el sistema no solo 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 existe un número natural $n$ tal que $P$ ( $n$ ). Es decir, el sistema dice que existe un número con la propiedad $P$ mientras niega que tenga un valor específico. La consistencia ω de un sistema implica su consistencia, pero la consistencia no implica consistencia ω. J. Barkley Rosser (1936) fortaleció el teorema de incompletitud al encontrar una variación de la prueba (el truco de Rosser) que solo 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 números naturales) son ω-consistentes y, por lo tanto, el teorema de Gödel, tal como se estableció originalmente, se aplica a ellas. La versión más fuerte del teorema de incompletitud que solo 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.

Segundo teorema de incompletitud

Para cada sistema formal $F$ que contiene aritmética básica, es posible definir canónicamente una fórmula Cons( $F$ ) expresando 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 es una contradicción sintáctica." La contradicción sintáctica a menudo se toma como "0=1", en cuyo caso Cons( $F$ ) establece "no existe un número natural que codifique una derivación de '0=1' de los axiomas de $F$ ."

El segundo teorema de incompletitud de Gödel muestra que, bajo suposiciones generales, esta declaración 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 declaración, el término "sistema formalizado" también incluye la suposición de que $F$ está efectivamente axiomatizado.

Second Incompleteness Theorem: "Para cualquier sistema consistente F dentro del cual se puede realizar cierta cantidad de aritmética elemental, la consistencia de F no se puede probar F en sí mismo." (Raatikainen 2020)
también se puede escribir como
"Asume" $F$ es un sistema formalizado consistente que contiene aritmética elemental. Entonces... ${displaystyle Fnot vdash {text{Cons}}(F)}$ ." (Raatikainen 2020) F no prueba la consistencia F)

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$ .

Expresar consistencia

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 idioma de $F$ . Hay muchas formas 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 no ser equivalentes en $F$ , y algunos incluso pueden ser comprobables. 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 PA es consistente, el subconjunto consistente más grande de PA es solo PA, por lo que, en este sentido, PA 'prueba que es consistente'. Lo que PA no prueba es que el subconjunto consistente más grande de PA es, de hecho, todo PA. (El término 'el subconjunto consistente más grande de PA' pretende aquí ser el segmento inicial más grande y consistente de los axiomas de PA bajo alguna enumeración efectiva particular).

Las condiciones de Hilbert-Bernays

La prueba estándar del segundo teorema de incompletitud asume que el predicado de demostrabilidad $Prov A (P)$ satisface las condiciones de demostrabilidad de Hilbert-Bernays. Dejar que $#(P)$ represente el número de Gödel de una fórmula $P$ , las condiciones de demostrabilidad dicen:

Si $F$ prueba $P$ , entonces $F$ prueba $Prov A (# P)$ .
$F$ 1.; es decir, $F$ prueba $Prov A (# P) \to Prov A (# Prov A (# P)))$ .
$F$ prueba $Prov A (# P \to Q) \land Prov A (# P) \to Prov A (# Q)$ (analogo de modus ponens).

Hay sistemas, como la aritmética de Robinson, que son lo suficientemente fuertes como para cumplir con los supuestos del primer teorema de incompletitud, pero que no prueban las condiciones de Hilbert-Bernays. La aritmética de Peano, sin embargo, es lo suficientemente fuerte para verificar estas condiciones, como todas las teorías son más fuertes que la aritmética de Peano.

Implicaciones para pruebas de consistencia

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 prueba la consistencia de $F 1$ . Esto se debe a que tal sistema $F 1$ puede probar que si $F 2$ demuestra la consistencia de $F 1$ , entonces $F 1$ es de hecho consistente. Para afirmar 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 algunos $n$ que $n$ es el código de una contradicción en $F 1$ . Pero si $F 2$ también probara que $F 1$ es coherente (es decir, que no existe tal $n$ ), entonces sería en sí mismo inconsistente. Este razonamiento se puede formalizar en $F 1$ para mostrar 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, no puede probar la consistencia de $F 2$ tampoco.

Este corolario del segundo teorema de incompletitud muestra que no hay esperanza de probar, por ejemplo, la consistencia de la aritmética de Peano usando cualquier medio finitista que pueda formalizarse en un sistema cuya consistencia es 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 finitas, es demostrablemente consistente en PA. Por lo tanto, PRA no puede probar la consistencia de PA. En general, se considera que este hecho implica que el programa de Hilbert, cuyo objetivo era justificar el uso de 'ideal'; Principios matemáticos (infinitistas) en las demostraciones de "real" Las declaraciones matemáticas (finitistas) al dar una prueba finitista de que los principios ideales son consistentes, no se pueden llevar a cabo (Franzén 2005, p. 106).

El corolario también indica la relevancia epistemológica del segundo teorema de incompletitud. En realidad, no proporcionaría información interesante si un sistema $F$ demostrara su consistencia. Esto se debe a que las teorías inconsistentes prueban todo, incluida su consistencia. Por lo tanto, una prueba de consistencia de $F$ en $F$ no nos daría ninguna pista sobre si $F$ es realmente consistente; ninguna duda sobre la consistencia de $F$ se resolvería con 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 cierto sentido, es menos dudoso que $F$ , por ejemplo, más débil que $F$ . Para muchas teorías naturales $F$ y $F& #39;$ , como $F$ = teoría de conjuntos de Zermelo–Fraenkel y estilo $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$ por el corolario anterior del segundo teorema de incompletitud.

El segundo teorema de incompletitud no descarta por completo la posibilidad de probar la consistencia de alguna teoría $T$ , solo hacerlo en una teoría que $T$ en sí misma puede resultar 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 fundado; consulte la prueba de consistencia de Gentzen. El teorema de Gentzen estimuló el desarrollo del análisis ordinal en la teoría de la demostración.

Ejemplos de declaraciones indecidibles

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 demostración utilizado en relación con los teoremas de Gödel, en el sentido de que un enunciado no es demostrable ni refutable en un sistema deductivo específico. El segundo sentido, que no se discutirá aquí, se usa 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 infinitos contables 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 todas las preguntas del conjunto de problemas (ver problema indecidible).

Debido a los dos significados de la palabra indecidible, a veces se usa el término independiente en lugar de indecidible para el "ni comprobable ni refutable" sentido.

La indecidibilidad de un enunciado en un sistema deductivo particular no aborda, por sí misma, la cuestión de si el valor de verdad del enunciado está bien definido o si puede determinarse por otros medios. La indecidibilidad solo implica que el sistema deductivo particular que se está considerando no prueba la verdad o la falsedad del enunciado. Si existen los llamados "absolutamente indecidibles" enunciados, 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 declaraciones indecidibles (en el primer sentido del término): la hipótesis del continuo no se puede probar ni refutar en ZFC (la axiomatización estándar de la teoría de conjuntos), y el axioma de 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 se podía refutar en la teoría de conjuntos ZF o ZFC. En la década de 1960, Cohen demostró que ninguno de los dos es demostrable a partir de ZF y que la hipótesis del continuo no puede demostrarse a partir de ZFC.

En 1973, Saharon Shelah 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.

Gregory Chaitin produjo declaraciones indecidibles en la teoría algorítmica de la información y demostró otro teorema de incompletitud en ese entorno. 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 un número específico en ese sistema tiene 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.

Declaraciones indecidibles comprobables en sistemas más grandes

Estos son equivalentes matemáticos naturales de Gödel "verdadero pero indecidible" oración. Se pueden probar en un sistema más grande 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 probarse en el sistema más fuerte de la aritmética de segundo orden. Kirby y Paris demostraron más tarde que el teorema de Goodstein, un enunciado sobre secuencias de números naturales algo más simple que el principio de Paris-Harrington, también es indecidible en la aritmética de Peano.

El teorema del árbol de Kruskal, que tiene aplicaciones en informática, también es indecidible a partir de la aritmética de Peano, pero demostrable en la teoría de conjuntos. De hecho, el teorema del árbol de Kruskal (o su forma finita) es indecidible en un sistema mucho más fuerte ATR₀ que codifica los principios aceptables basados en una filosofía de las matemáticas llamada predicativismo. El teorema menor del grafo relacionado pero más general (2003) tiene consecuencias para la teoría de la complejidad computacional.

Relación con la computabilidad

El teorema de incompletitud está estrechamente relacionado con varios resultados sobre conjuntos indecidibles en la teoría de la recursión.

Stephen Cole Kleene (1943) presentó una demostración del teorema de incompletitud de Gödel utilizando los resultados básicos de la teoría de la computabilidad. Uno de esos resultados muestra que el problema de la detención es indecidible: no hay ningún programa de computadora que pueda determinar correctamente, dado cualquier programa $P$ como entrada, si $P$ finalmente se detiene cuando se ejecuta con una determinada entrada. Kleene demostró que la existencia de un sistema efectivo completo de aritmética con ciertas propiedades de consistencia obligaría al problema de la detención a ser decidible, una contradicción. Este método de prueba también ha sido presentado por Shoenfield (1967, p. 132) harvtxt error: no target: CITEREFShoenfield1967 (ayuda); Charlesworth (1980) error de harvtxt: sin objetivo: CITEREFCharlesworth1980 (ayuda); y Hopcroft & Ullman (1979) error de harvtxt: sin objetivo: CITEREFHopcroftUllman1979 (ayuda).

Franzén (2005, p. 73) explica cómo la solución de Matiyasevich al décimo problema de Hilbert puede usarse para obtener una demostración del primer teorema de incompletitud de Gödel. Matiyasevich demostró que no existe ningún algoritmo que, dado un polinomio multivariante $p (x 1, x 2,..., x k)$ con coeficientes enteros, determina si hay una solución entera a la ecuación $p$ = 0. Debido a que los polinomios con coeficientes enteros, y los propios enteros, son directamente expresables en el lenguaje de la aritmética, si una ecuación polinomial entera multivariante $p$ = 0 tiene una solución en los números enteros entonces cualquier sistema aritmético suficientemente fuerte $T$ probará esto. Además, si el sistema $T$ es ω-consistente, entonces nunca probará que una ecuación polinomial particular tiene una solución cuando en realidad no hay solución en los números enteros. Por lo tanto, si $T$ fuera completa y ω-consistente, sería posible determinar algorítmicamente si una ecuación polinomial tiene una solución simplemente enumerando pruebas de $T$ hasta que " $p$ tiene una solución" o " $p$ no tiene solución" se encuentra, en contradicción con el teorema de Matiyasevich. De ahí se deduce que $T$ no puede ser $w$ -consistente y completo. Además, para cada sistema consistente generado efectivamente $T$ , es posible generar efectivamente un polinomio multivariado $p$ sobre los enteros tales que la ecuación $p$ = 0 tiene no hay soluciones sobre los números enteros, pero la falta de soluciones no se puede probar en $T$ (Davis 2006, p. 416; Jones 1980 harvnb error: no target: CITEREFJones1980 (ayuda)).

Smorynski (1977, p. 842) error de harvtxt: sin objetivo: CITEREFSmorynski1977 (ayuda) muestra cómo la existencia de conjuntos recursivamente inseparables puede usarse para probar el primer teorema de incompletud. Esta prueba a menudo se amplía para mostrar que los sistemas como la aritmética de Peano son esencialmente indecidibles (ver Kleene 1967, p. 274 harvnb error: sin destino: CITEREFKleene1967 (ayuda)).

El teorema de incompletitud de Chaitin brinda un método diferente para producir oraciones independientes, basado en la complejidad de Kolmogorov. Al igual que la demostración presentada por Kleene que se mencionó anteriormente, el teorema de Chaitin solo se aplica a teorías con la propiedad adicional de que todos sus axiomas son verdaderos en el modelo estándar de los números naturales. El teorema de incompletitud de Gödel se distingue por su aplicabilidad a teorías consistentes que, sin embargo, incluyen declaraciones que son falsas en el modelo estándar; estas teorías se conocen como ω-inconsistentes.

Bosquejo de prueba del primer teorema

La prueba por contradicción tiene tres partes esenciales. Para comenzar, elija un sistema formal que cumpla con los criterios propuestos:

Las declaraciones en el sistema pueden estar representadas por números naturales (conocidos como números Gödel). El significado de esto es que las propiedades de las declaraciones, como su verdad y falsedad, serán equivalentes a determinar si sus números de Gödel tienen ciertas propiedades, y que las propiedades de las declaraciones pueden demostrarse examinando sus números de Gödel. Esta parte culmina en la construcción de una fórmula que expresa la idea de que "establecimiento $S$ es prable en el sistema" (que se puede aplicar a cualquier declaración " $S$ "en el sistema".
En el sistema formal es posible construir un número cuya declaración coincidente, cuando se interpreta, es auto-referencial y esencialmente dice que (es decir, la propia declaración) es inprovable. Esto se hace utilizando una técnica llamada "diagonalización" (llamado por sus orígenes como argumento diagonal de Cantor).
Dentro del sistema formal, esta declaración permite una demostración de que no es ni provable ni desprovable en el sistema, y por lo tanto el sistema no puede en realidad ser ω-consistent. Por lo tanto, la suposición original de que el sistema propuesto cumplió los criterios es falsa.

Aritmetización de sintaxis

El problema principal al desarrollar la prueba descrita anteriormente es que al principio parece que para construir una declaración $p$ que es equivalente a " $p$ no se puede probar", $p$ de alguna manera tendría que contener una referencia a $p$ , lo que fácilmente podría dar lugar a una regresión infinita. La técnica de Gödel es mostrar que las declaraciones se pueden emparejar con números (a menudo llamada aritmetización de la sintaxis) de tal manera que "demostrar una declaración" se puede reemplazar con "probar si un número tiene una determinada propiedad". Esto permite que se construya una fórmula autorreferencial de una manera que evite cualquier regresión infinita de definiciones. La misma técnica fue utilizada posteriormente por Alan Turing en su trabajo sobre el Entscheidungsproblem.

En términos simples, se puede idear un método para que cada fórmula o declaración que se pueda formular en el sistema obtenga un número único, llamado su número de Gödel, de tal manera que sea posible convertir mecánicamente entre fórmulas y números de Gödel. Los números involucrados pueden ser realmente muy largos (en términos de número de dígitos), pero esto no es una barrera; todo lo que importa es que tales números puedan construirse. Un ejemplo simple es cómo el inglés puede almacenarse como una secuencia de números para cada letra y luego combinarse en un solo número más grande:

La palabra hello está codificado como 104-101-108-108-111 en ASCII, que se puede convertir en el número 104101108111.
La declaración lógica x=y => y=x está codificado como 120-061-121-032-061-062-032-121-061-120 en ASCII, que se puede convertir en el número 120061121032061062032121061120.

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 dada. Debido a que el sistema formal es lo suficientemente fuerte para respaldar el razonamiento sobre números en general, también puede respaldar el razonamiento sobre números que representan fórmulas y declaraciones. Fundamentalmente, debido a que el sistema puede admitir el razonamiento sobre las propiedades de los números, los resultados son equivalentes al razonamiento sobre la probabilidad de sus enunciados equivalentes.

Construcción de un enunciado sobre "probabilidad"

Habiendo demostrado que, en principio, el sistema puede hacer afirmaciones indirectas sobre demostrabilidad, al analizar las propiedades de esos números que representan declaraciones, ahora es posible mostrar cómo crear una declaración que realmente haga esto.

Una fórmula $F () x)$ que contiene exactamente una variable libre $x$ se llama formulario de declaración o de clase. Tan pronto $x$ es reemplazado por un número específico, el formulario de declaración se convierte en un Bona fide declaración, y entonces es provable en el sistema, o no. Para ciertas fórmulas se puede demostrar que por cada número natural $n$ , $F(n)$ es cierto si y sólo si se puede probar (el requisito preciso en la prueba original es más débil, pero para el boceto de prueba esto 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".

Los formularios de declaración en sí mismos no son declaraciones y, por lo tanto, no se pueden probar ni refutar. Pero a cada forma de declaración $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 en sí también puede codificarse mediante números de Gödel, de la siguiente manera: dado que una prueba es una lista de declaraciones que obedecen ciertas reglas, se puede definir el número de Gödel de una prueba. Ahora, para cada afirmación $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 una forma de enunciado $Bew (y)$ que usa esta relación aritmética para establecer que un número de Gödel de un existe una prueba de $y$ :

Bew () Sí.) = x

()

Sí.

es el número de Gödel de una fórmula y

x

es el número de Gödel una prueba de la fórmula codificada por

Sí.

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 probabilidad que se acaba 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$ ; la cadena " $Bew$ " en sí mismo no se afirma que sea parte de este lenguaje.

Una característica importante de la fórmula $Bew (y)$ es que si una declaración $p$ es demostrable en el sistema entonces $Bew (G (p))$ también es demostrable. Esto se debe a que cualquier prueba de $p$ tendría un número de Gödel correspondiente, cuya existencia provoca $Bew(G (p))$ para estar satisfecho.

Diagonalización

El siguiente paso en la prueba es obtener una afirmación que, indirectamente, afirme su propia indemostrabilidad. Aunque Gödel construyó esta declaración directamente, la existencia de al menos una de tales declaraciones se deriva del lema diagonal, que dice que para cualquier sistema formal suficientemente fuerte y cualquier forma de declaración $F$ hay una declaración $p$ tal que el sistema prueba

p Administración F () G () p)

Dejando que $F$ sea la negación de $Bew (x)$ , obtenemos el teorema

p \leftrightarrow ~ Bew () G () p)

y la $p$ definida por this establece 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$ establece que si se realiza cierto 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:

", cuando precedido por sí mismo en citas, es inproviable.", cuando precedido por sí mismo en citas, es inprovable.

Esta oración no se refiere directamente a sí misma, pero cuando se realiza la transformación enunciada, 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, suponga 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))$ . Así, el sistema sería inconsistente, demostrando tanto un enunciado como su negación. Esta contradicción muestra que $p$ no se puede demostrar.

Si la negación de $p$ fuera demostrable, entonces $Bew (G (p))$ sería demostrable (porque $p$ fue construido para ser equivalente a la negación de $Bew (G (p))). Sin embargo, para cada número específico x, x no puede ser el número de Gödel de la prueba de p, porque p no es demostrable (del párrafo anterior). Así, por un lado, el sistema prueba que hay un número con cierta propiedad (que es el número de Gödel de la prueba de p), pero por otro lado, para cada número específico x, podemos probar que no tiene esta propiedad. Esto es imposible en un sistema ω-consistente. Por lo tanto, la negación de p no es demostrable.$

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

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

Si el sistema es compatible con ω, no puede probar $p$ ni su negación, y así $p$ es indecible.
Si el sistema es consistente, puede tener la misma situación, o puede probar la negación de $p$ . En el caso posterior, tenemos una declaración ("no $p$ ") lo cual es falso pero provable, y el sistema no es ω-consistent.

Si uno intenta "agregar los axiomas que faltan" para evitar que el sistema esté incompleto, se debe agregar $p$ o "no $p$ " como axiomas. Pero entonces la definición de "ser un número de Gödel de una prueba" de una declaración cambia. lo que significa que la fórmula $Bew (x)$ ahora es diferente. Así cuando aplicamos el lema diagonal a este nuevo Bew, obtenemos un nuevo enunciado $p$ , diferente al anterior, que ser indecidible en el nuevo sistema si es ω-consistente.

Prueba a través de la paradoja de Berry

George Boolos (1989) esboza una prueba alternativa del primer teorema de incompletitud que usa 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 (Boolos 1998, p. 383) harv error: no target: CITEREFBoolos1998 (ayuda). La prueba de Boolos procede mediante la construcción, para cualquier conjunto computablemente enumerable $S$ de oraciones aritméticas verdaderas, otra oración que es verdadera pero no está contenido en $S$ . Esto da como corolario el primer teorema de incompletud. Según Boolos, esta prueba es interesante porque proporciona un "tipo diferente de razón" por lo incompleto de las teorías aritméticas consistentes y efectivas (Boolos 1998, p. 388) harv error: no target: CITEREFBoolos1998 (ayuda).

Pruebas verificadas por computadora

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 se pueden verificar por completo mediante el 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) error de harv: sin objetivo: CITEREFShankar1994 (ayuda), por Russell O'Connor en 2003 usando Coq (O'Connor 2005) harv error: no target: CITEREFO'Connor2005 (ayuda) y por John Harrison en 2009 usando HOL Light (Harrison 2009) error de harv: sin destino: CITEREFHarrison2009 (ayuda). Lawrence Paulson anunció una prueba verificada por computadora de ambos teoremas de incompletitud en 2013 usando Isabelle (Paulson 2014) harv error: sin destino: CITEREFPaulson2014 (ayuda).

Bosquejo de prueba del segundo teorema

La principal dificultad para probar 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$ usando un predicado formal $P$ para demostrar la probabilidad. Una vez hecho esto, sigue el segundo teorema de incompletitud al formalizar toda la prueba del primer teorema de incompletitud dentro del propio sistema $S$ .

Dejemos que $p$ represente la oración indecidible construida arriba, y supongamos con el propósito de obtener una contradicción que la consistencia del sistema $S$ se puede demostrar desde dentro del sistema $S$ en sí mismo. Esto es equivalente a demostrar que la declaración "System $S$ es consistente". Ahora considere la declaración $c$ , donde $c$ = "Si el sistema $S$ es coherente, entonces $p$ no es demostrable". La prueba de sentencia $c$ se puede formalizar dentro del sistema $S$ , y por lo tanto la sentencia $c$ , " $p$ no es demostrable", (o de manera idéntica, "no $P (p)$ ") se puede probar en el sistema $S$ .

Observe entonces, que si podemos probar que el sistema $S$ es consistente (es decir, el enunciado en la hipótesis de $c$ ), entonces hemos probado que $p$ no es demostrable. Pero esto es una contradicción ya que por el primer teorema de incompletitud, esta oración (es decir, lo que está implícito en la oración $c$ , &# 34;" $p$ " no es demostrable") es lo que construimos para que no sea demostrable. Note que es por eso que requerimos formalizar el primer Teorema de Incompletitud en $S$ : para probar el 2do Teorema de Incompletitud, obtenemos una contradicción con el 1.er teorema de incompletitud que solo se puede hacer mostrando que el teorema se cumple en $S$ . Entonces no podemos probar que el sistema $S$ sea consistente. Y sigue el enunciado del segundo teorema de incompletitud.

Discusión e implicaciones

Los resultados de incompletitud afectan a la filosofía de las matemáticas, en particular a las versiones del formalismo, que utilizan un único sistema de lógica formal para definir sus principios.

Consecuencias para el logicismo y el segundo problema de Hilbert

A veces se piensa que el teorema de incompletitud tiene graves consecuencias para el programa de logicismo propuesto por Gottlob Frege y Bertrand Russell, cuyo objetivo era definir los números naturales en términos de lógica (Hellman 1981, pp. 451–468) harv error: no target: CITEREFHellman1981 (ayuda). Bob Hale y Crispin Wright argumentan que no es un problema para el logicismo porque los teoremas de incompletitud se aplican por igual a la lógica de primer orden que a la aritmética. Argumentan que solo aquellos que creen que los números naturales deben definirse en términos de lógica de primer orden tienen este problema.

Muchos lógicos creen que los teoremas de incompletitud de Gödel dieron un golpe fatal al segundo problema de David Hilbert, que pedía una prueba de consistencia finita para las matemáticas. El segundo teorema de incompletitud, en particular, a menudo se considera que hace que el problema sea imposible. No todos los matemáticos están de acuerdo con este análisis, sin embargo, y el estado del segundo problema de Hilbert aún no está decidido (ver 'Puntos de vista modernos sobre el estado del problema').

Mentes y máquinas

Autores como el filósofo J. R. Lucas y el físico Roger Penrose han debatido qué implican, en todo caso, 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.

Hilary Putnam (1960) sugirió que si bien los teoremas de Gödel no se pueden aplicar a los humanos, ya que cometen errores y, por lo tanto, son inconsistentes, se pueden aplicar a la facultad humana de ciencias o matemáticas en general. Suponiendo que sea consistente, su consistencia no puede probarse o no puede representarse mediante una máquina de Turing.

Avi Wigderson (2010) ha propuesto que el concepto de "cognoscibilidad" debería basarse en la complejidad computacional más que en la decidibilidad lógica. Escribe que "cuando la cognoscibilidad se interpreta según los estándares modernos, es decir, a través de la complejidad computacional, los fenómenos de Gödel están muy presentes entre nosotros."

Douglas Hofstadter, en sus libros Gödel, Escher, Bach y I Am a Strange Loop, cita los teoremas de Gödel como un ejemplo de lo que él llama un bucle extraño, una estructura jerárquica autorreferencial que existe dentro de un sistema formal axiomático. Argumenta que este es el mismo tipo de estructura que da lugar a la conciencia, el sentido de "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 propia indemostrabilidad dentro del sistema formal de Principia Mathematica, la autorreferencia en la mente humana proviene de la forma en que el cerebro abstrae y categoriza los estímulos en 'símbolos', o grupos de neuronas que responden a conceptos, en lo que efectivamente también es un sistema formal, eventualmente dando lugar a símbolos que modelan el concepto de la misma entidad que realiza la percepción. Hofstadter argumenta que un bucle extraño en un sistema formal suficientemente complejo puede dar lugar a un "descendente" o "al revés" causalidad, una situación en la que la jerarquía normal de causa y efecto se invierte. En el caso del teorema de Gödel, este se manifiesta, resumidamente, como sigue:

"Simplemente conociendo el significado de la fórmula, uno puede inferir su verdad o falsedad sin ningún esfuerzo para deducirlo a la antigua usanza, lo que requiere que uno avance metódicamente "hacia arriba" 34; de los axiomas. Esto no es solo peculiar; es asombroso Normalmente, uno no puede simplemente mirar lo que dice una conjetura matemática y simplemente apelar al contenido de esa declaración por sí mismo para deducir si la declaración es verdadera o falsa." (Soy un bucle extraño.)

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 se encuentra en el alto nivel de deseos, conceptos, personalidades, pensamientos e ideas, más que en el bajo nivel de interacciones entre neuronas o incluso fundamentales. partículas, aunque según la física estas últimas parecen poseer el poder causal.

"Por lo tanto, existe un curioso revés 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 diminuto parece estar donde residen los motores reales que impulsan la realidad." (Soy un bucle extraño.)

Lógica paraconsistente

Aunque los teoremas de Gödel generalmente se estudian en el contexto de la lógica clásica, también tienen un papel en el estudio de la lógica paraconsistente y de declaraciones inherentemente contradictorias (dialetheia). Graham Priest (1984, 2006) argumenta 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 para el dialeteísmo. La causa de esta inconsistencia es la inclusión de un predicado de verdad para un sistema dentro del lenguaje del sistema (Priest 2006, p. 47) error de harv: sin objetivo: CITEREFPriest2006 (ayuda). Stewart Shapiro (2002) da una evaluación más mixta de las aplicaciones de los teoremas de Gödel al dialeteísmo.

Apela a los teoremas de incompletitud en otros campos

A veces se hacen apelaciones y analogías a los teoremas de incompletitud en apoyo de argumentos que van más allá de las matemáticas y la lógica. Varios autores han comentado negativamente tales extensiones e interpretaciones, entre ellos Torkel Franzén (2005); Panu Raatikainen (2005); Alan Sokal y Jean Bricmont (1999); y Ophelia Benson y Jeremy Stangroom (2006). Bricmont &amperio; Stangroom (2006, p. 10) error de harvtxt: sin destino: CITEREFBricmontStangroom2006 (ayuda), por ejemplo, cita de 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 &amperio; Bricmont (1999, p. 187) error de harvtxt: sin destino: CITEREFSokalBricmont1999 (ayuda) criticar a Régis Debray& #39;s invocación del teorema en el contexto de la sociología; Debray ha defendido este uso como metafórico (ibid.).

Historia

Después de que Gödel publicara su prueba del teorema de completitud como su tesis doctoral en 1929, se centró en un segundo problema para su habilitación. Su objetivo original era obtener una solución positiva al segundo problema de Hilbert (Dawson 1997, p. 63). 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 solos se conocían como "aritmética".

Gödel no fue la única persona que trabajó en el problema de la consistencia. Ackermann había publicado una prueba de consistencia defectuosa para el análisis en 1925, en la que intentó utilizar el método de sustitución ε desarrollado originalmente por Hilbert. Más tarde ese año, von Neumann pudo corregir la prueba de un sistema de aritmética sin ningún axioma de inducción. En 1928, Ackermann le había comunicado una prueba modificada a Bernays; esta prueba modificada llevó a Hilbert a anunciar su creencia en 1929 de que se había demostrado la consistencia de la aritmética y que probablemente pronto seguiría una prueba de consistencia del análisis. Después de que la publicación de los teoremas de incompletitud mostró que la prueba modificada de Ackermann debe ser errónea, von Neumann produjo un ejemplo concreto que muestra que su técnica principal no era sólida (Zach 2007, p. 418; Zach 2003, p. 33).

En el curso de su investigación, Gödel descubrió que aunque una oración que afirma su propia falsedad conduce a la paradoja, una oración que afirma su propia no demostrabilidad no lo hace. 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.

Anuncio

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 (Dawson 1996, p. 69). La conferencia también incluyó el discurso de retiro de Hilbert, cuando dejaba su puesto en la Universidad de Göttingen. Hilbert usó el discurso para argumentar su creencia de que todos los problemas matemáticos se pueden resolver. Terminó su discurso diciendo:

Para el matemático no hay IgnorabimusY, en mi opinión, no para nada para la ciencia natural tampoco... La verdadera razón por la que nadie ha logrado encontrar un problema insolvable es, en mi opinión, que no hay ningún problema insolvable. En contraste con los tontos Ignorabimus, nuestro credo avers: Debemos saberlo. ¡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!", fueron utilizados 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 (Dawson 1996, p. 72).

Gödel anunció su primer teorema de incompletitud en una sesión de discusión de mesa redonda en el tercer día de la conferencia. El anuncio atrajo poca atención aparte de la de von Neumann, quien apartó a Gödel 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 (Dawson 1996, p. 70). Gödel obtuvo de forma independiente el segundo teorema de incompletitud y lo incluyó en su manuscrito enviado, 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 implica el título, Gödel planeó originalmente 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 (van Heijenoort 1967, página 328, nota al pie 68a) error de harv: sin destino: CITEREFvan_Heijenoort1967 (ayuda).

Generalización y aceptación

Gödel dio una serie de conferencias sobre sus teoremas en Princeton entre 1933 y 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 la consistencia ω, que era una parte integral de la prueba original de Gödel, podía ser reemplazada por la consistencia simple, si la oración de Gödel se cambiaba de manera adecuada. 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.

El impacto de los teoremas de incompletitud en el programa de Hilbert se percató rápidamente. Bernays incluyó una prueba completa de los teoremas de incompletitud en el segundo volumen de Grundlagen der Mathematik (1939), junto con resultados adicionales de Ackermann sobre el método de sustitución ε y la prueba de aritmética de consistencia de Gentzen.. Esta fue la primera prueba completa publicada del segundo teorema de incompletitud.

Críticas

Finsler

Paul Finsler (1926) usó una versión de la paradoja de Richard para construir una expresión que era falsa pero indemostrable en un marco informal particular que había desarrollado. Gödel desconocía este artículo cuando demostró los teoremas de incompletitud (Collected Works Vol. IV., p. 9). Finsler le escribió a Gödel en 1931 para informarle sobre este artículo, que Finsler sintió que tenía prioridad para un teorema de incompletitud. Los métodos de Finsler no se basaban en demostrabilidad formalizada y solo tenían un parecido superficial con el trabajo de Gödel (van Heijenoort 1967, p. 328) error de harv: sin destino: CITEREFvan_Heijenoort1967 (ayuda). Gödel leyó el documento pero lo encontró profundamente defectuoso, y su respuesta a Finsler expuso preocupaciones sobre la falta de formalización (Dawson, p. 89 error de harvnb: sin objetivo: CITEREFDawson (ayuda)). Finsler continuó defendiendo su filosofía de las matemáticas, que evitaba la formalización, durante el resto de su carrera.

Zermelo

En septiembre de 1931, Ernst Zermelo le escribió a Gödel para anunciar lo que describió como una "brecha esencial" en el argumento de Gödel (Dawson, p. 76 harvnb error: no target: CITEREFDawson (ayuda)). En octubre, Gödel respondió con una carta de 10 páginas (Dawson, p. 76 harvnb error: no target: CITEREFDawson (ayuda), Grattan-Guinness, págs. 512–513 error de harvnb: sin destino: CITEREFGrattan-Guinness (ayuda)), donde señaló que Zermelo asumió erróneamente que la noción de verdad en un sistema es definible en ese sistema (lo que no es cierto en general por el teorema de indefinibilidad de Tarski). Pero Zermelo no cedió y publicó sus críticas en forma impresa con 'un párrafo bastante mordaz sobre su joven competidor'. (Grattan-Guinness, págs. 513 error de harvnb: sin objetivo: CITEREFGrattan-Guinness (ayuda)). Gödel decidió que continuar con el asunto no tenía sentido, y Carnap estuvo de acuerdo (Dawson, p. 77 harvnb error: no target: CITEREFDawson (ayuda)). Gran parte del trabajo posterior de Zermelo estuvo relacionado con lógicas más fuertes que la lógica de primer orden, con las que esperaba mostrar tanto la consistencia como la categoricidad de las teorías matemáticas.

Wittgenstein

Ludwig Wittgenstein escribió varios pasajes sobre los teoremas de incompletitud que se publicaron póstumamente en sus Observaciones sobre los fundamentos de las matemáticas de 1953, en particular una sección a veces llamada el "párrafo notorio" donde parece confundir las nociones de "verdadero" y "probable" en el sistema de Russell. Gödel fue miembro del Círculo de Viena durante el período en el que la primera filosofía del lenguaje ideal de Wittgenstein y el Tractatus Logico-Philosophicus dominaron el pensamiento del círculo. Ha habido cierta controversia sobre si Wittgenstein entendió mal el teorema de incompletitud o simplemente se expresó de manera poco clara. Los escritos del Nachlass de Gödel expresan la creencia de que Wittgenstein malinterpretó sus ideas.

Varios comentaristas han interpretado que Wittgenstein malinterpretó a Gödel (Rodych 2003) error harv: no target: CITEREFRodych2003 (ayuda) , aunque Juliet Floyd y Hilary Putnam (2000), así como Graham Priest (2004) han proporcionado lecturas textuales argumentando que la mayoría de los comentarios malinterpretan a Wittgenstein. En su publicación, Bernays, Dummett y Kreisel escribieron reseñas separadas sobre los comentarios de Wittgenstein, todas extremadamente negativas (Berto 2009, p. 208) error de harv: sin objetivo: CITEREFBerto2009 (ayuda). 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 afirmó: '¿Se ha vuelto loco Wittgenstein? ¿Lo dice en serio? Él intencionalmente pronuncia declaraciones trivialmente sin sentido & # 34; (Wang 1996, p. 179) harv error: no target: CITEREFWang1996 (ayuda), y escribió a Karl Menger que los comentarios de Wittgenstein demuestran un malentendido de los teoremas de incompletud escribiendo:

Está claro de los pasajes que citas que Wittgenstein hizo no entender [el primer teorema de incomplesión] (o pretendía no entenderlo). Él lo interpretó como una especie de paradoja lógica, mientras que de hecho es justo lo contrario, a saber, un teorema matemático dentro de una parte absolutamente incontroversial de las matemáticas (teoría número final o combinatoria). (Wang 1996, pág. 179) harv error: no target: CITEREFWang1996 (help)

Desde la publicación de Nachlass de Wittgenstein en el año 2000, una serie de artículos de filosofía han tratado de evaluar si la crítica original a las declaraciones de Wittgenstein estaba justificada. floyd &amperio; Putnam (2000) argumenta que Wittgenstein tenía una comprensión más completa del teorema de incompletitud de lo que se suponía anteriormente. Están particularmente interesados en la interpretación de una oración de Gödel para un sistema ω-inconsistente como si realmente dijera 'No soy demostrable', ya que el sistema no tiene modelos en los que el predicado de demostrabilidad corresponda a la demostrabilidad real. Rodych (2003) harvtxt error: no target: CITEREFRodych2003 (ayuda) argumenta que su interpretación de Wittgenstein es no históricamente justificado, mientras que Bays (2004) harvtxt error: no target: CITEREFBays2004 (ayuda) argumenta en contra El análisis filosófico de Floyd y Putnam del predicado de demostrabilidad. Berto (2009) harvtxt error: no target: CITEREFBerto2009 (ayuda) explora la relación entre Wittgenstein's escritura y teorías de la lógica paraconsistente.

Contenido relacionado

Más resultados...