Interpretación del Segundo Teorema de Incompletitud

Question

Para simplificar, permítanme elegir un caso particular de la Segunda Incompletitud de Gödel Teorema de Gödel:

ZFC (Teoría de Conjuntos de Zermelo-Fraenkel más el Axioma de Elección, el fundamento habitual de las matemáticas) no demuestra Con(ZFC), donde Con(ZFC) es una fórmula que expresa que ZFC es consistente.

(En este caso, ZFC puede ser sustituido por cualquier otro conjunto de axiomas suficientemente bueno y fuerte, pero este no es el tema aquí).

Este teorema ha sido interpretado por muchos como que "nunca podemos saber si las matemáticas son consistentes" y ha animado a mucha gente a intentar demostrar que ZFC (o incluso PA) es de hecho inconsistente. Creo que una opinión mayoritaria en matemáticas (al menos entre los matemáticos que piensan en fundamentos) es que creemos que no hay ningún problema con ZFC, simplemente no podemos demostrar su consistencia.

Un comentario que surge de vez en cuando (también en mathoverflow), con el que suelo estar de acuerdo, es el siguiente:

(*) "¿Qué ganamos si pudiéramos demostrar la consistencia de (digamos ZFC) dentro de ZFC? Si ZFC fuera inconsistente, demostraría su consistencia igualmente".

En otras palabras, no tiene sentido demostrar la consistencia de las matemáticas mediante una demostración matemática, ya que si las matemáticas fueran defectuosas, demostrarían cualquier cosa, por ejemplo su propia no-falsedad. Por lo tanto, una prueba de este tipo no mejoraría nuestra confianza en las matemáticas (o en ZFC, según el caso).

Esta es mi pregunta: ¿Implica la observación (*) que la única ventaja del Segundo Teorema de Incompletitud sobre el primero es que ahora tenemos una sentencia específica (en este caso Con(ZFC)) que es indecidible, que puede utilizarse para demostrar teoremas como "la existencia de un cardinal inaccesible no es demostrable en ZFC"? En otras palabras, ¿se reduce el Segundo Teorema de Incompletitud a un mero tecnicismo sin ninguna implicación filosófica que vaya más allá del Primer Teorema de Incompletitud (que afirma que hay alguna sentencia $\phi$ de tal manera que ni $\phi$ ni $\neg\phi$ seguir desde ZFC)?

Answer 1

Para el punto filosófico encapsulado en (*) en la pregunta, parece que los corolarios del segundo teorema de incompletitud son más relevantes que el propio teorema. Si tuviéramos dudas sobre la consistencia de ZFC, entonces una demostración de Con(ZFC) realizada en ZFC sería, en efecto, de poca utilidad. Pero una prueba de Con(ZFC) realizada en un sistema más fiable, como la aritmética de Peano o la aritmética recursiva primitiva, habría sido útil (antes de Gödel), y creo que esto es lo que Hilbert esperaba. El segundo teorema de incompletitud de Gödel nos dice que este tipo de cosas no pueden suceder (a menos que incluso el sistema más fiable sea inconsistente).

Answer 2

La respuesta es la siguiente observación debida a Hilbert:

Si podemos demostrar la consistencia de $ZFC$ utilizando elemental entonces cualquier teorema elemental de $ZFC$ tiene un prueba elemental es decir, no necesitamos objetos ideales/abstractos como los conjuntos o los números reales para tratar objetos concretos/finitos como los números.

La importancia de los teoremas de Godel no es que $ZFC$ no puede demostrar su propia consistencia, sino el resultado más débil de que los métodos elementales (asumiendo que la enumeración de estos métodos es fácil, es decir, recursivamente enumerable) no pueden demostrar todos los resultados elementales, en otras palabras, necesitamos objetos abstractos incluso para hacer teoría de números elemental. Hilbert quería demostrar que, aunque los objetos abstractos son útiles para la matemática elemental en la práctica, no son esenciales y pueden evitarse (al menos en teoría) si son necesarios. Pero la teoría de Godel primer teorema de incompletitud ya muestra que esto no es cierto. (Aquí lo elemental puede identificarse con fórmulas libres de cuantificadores no limitados o $\Pi_1$ sentencias).

Answer 3

Yudkowsky y Herreshoff tienen un (desordenado pero) gran papel que relaciona el segundo teorema de incompletitud con cuestiones de inteligencia artificial teórica. ( Este documento mía podría ser una introducción más accesible al tema). En principio, una forma de que un agente inteligente $M$ puede lograr un objetivo es mediante la construcción de un agente auxiliar $M'$ y encargarle el objetivo. Pero presumiblemente $M$ no puede satisfacer su criterio de actuación a menos que pueda demostrar que $M'$ razona de forma consistente --- de lo contrario podría estar construyendo un agente que podría fallar porque razona de forma incorrecta. Pero por el segundo teorema de incompletitud, $M$ no puede demostrar que el sistema en el que él mismo razona es sólido, lo que significa que $M'$ tendría que razonar dentro de un sistema más débil.

Es especialmente un problema para la idea de una IA auto-modificable. Una IA suficientemente avanzada debería ser mejor que nosotros en el diseño de IAs. Así que podríamos querer diseñar una IA que sea capaz de mejorarse a sí misma modificando su propio código fuente. Pero el obstáculo de la incompletitud parece implicar que sólo podría hacerlo a costa de debilitar el sistema formal en el que razona. Dado que la fuerza de la teoría de la prueba se mide por ordinales, después de un número finito de iteraciones llegaría a la imbecilidad.

A primera vista parece que debería tener una resolución trivial, pero cuanto más se piensa en ello, más grave es el problema.

Answer 4

Aunque no es directamente un beneficio filosófico, el Segundo Teorema de Incompletitud es bastante útil para dar resultados concretos de improbabilidad: si queremos demostrar que la teoría T no demuestra el teorema X, basta con mostrar que X implica la consistencia de T. Por ejemplo, Harvey Friedman tiene una serie de resultados que muestran que algún teorema implica la fundamentación de alguna notación ordinal, donde se sabe que la notación ordinal, a su vez, implica la consistencia (de hecho, la consistencia 1) de la teoría.

Answer 5

El hecho de que el segundo teorema de incompletitud se refiera a la consistencia es importante para varias aplicaciones, tanto filosóficas como matemáticas.

Filosóficamente, el segundo teorema de incompletitud es el que nos permite saber que no podemos, en general, demostrar la existencia de un modelo (conjunto) de ZFC dentro de la propia ZFC. Este es un obstáculo fundamental para los métodos ingenuos de demostración de resultados de consistencia relativa. No podemos demostrar, por ejemplo, que la hipótesis del continuo es indemostrable en ZFC construyendo un modelo de conjunto de ZFC en el que falla la CH utilizando métodos que a su vez pueden ser formalizados en ZFC . Filosóficamente, esto dice que no debería sorprendernos que los resultados de consistencia relativa que tenemos requieran métodos que no pueden ser formalizados dentro de ZFC.

En segundo lugar, hay algunos teoremas (quizás menos conocidos) que aprovechan el segundo teorema de incompletitud para demostrar la existencia de tipos especiales de modelos. Son resultados matemáticos, no filosóficos.

Teorema (Harvey Friedman). Dejemos que $S$ sea una teoría efectiva de la aritmética de segundo orden que contenga la teoría ACA ₀ . Si existe un modelo ω contable de $S$ , entonces hay un contable $\omega$ -modelo de $S$ + "no hay contable $\omega$ -modelo de $S$ ."

La prueba procede mostrando que, si la conclusión falla, una cierta teoría efectiva obtenida de $S$ es consistente y demuestra su propia consistencia. El tipo de modelo construido por el teorema es útil para demostrar que ciertos sistemas de aritmética de segundo orden no son iguales.