Gödel: ¿Por qué una proposición es indecidible?

Esta respuesta es un poco técnica, pero creo que el OP la encontrará interesante.

Permítanme primero recordar un poco sobre la historia del teorema de incompletitud (IT). La forma en que generalmente se expresa es:

Si PA (o cualquier teoría recursivamente axiomatizable que extienda PA) es consistente, entonces "PA es consistente" es indecidible en PA.

Sin embargo, ¡esto no es lo que Goedel probó originalmente! La prueba de Goedel requería una suposición adicional: que PA es razonablemente correcto (específicamente, que PA es $\omega$-consistente ). Esta es, por supuesto, una hipótesis desafortunada; además de debilitar el teorema, también aporta un poco de platonismo, con suerte innecesario. (Está bien, digamos que está bien con el platonismo; ¿por qué debería preocuparse por las teorías que son consistentes pero falsas? Vea a continuación una respuesta a esto).

Específicamente, Goedel podría mostrar fácilmente que "PA no prueba Con (PA)", pero mostrar "PA no refuta Con (PA)" requería la suposición adicional. Hablando estrictamente, el argumento original de Goedel ciertamente contenía un teorema de indemostrabilidad , pero podría decirse que no llegó a ser un teorema completo de indecidibilidad (es decir, indemostrabilidad e indemostrabilidad).

Goedel dejó como una pregunta abierta si esta suposición podría eliminarse. Esto fue resuelto, dando lugar a la habitual declaración de IT, por parte de Rosser , quien mostró cómo un truco técnico podía mejorar el argumento de Goedel. Así que eso elevó la prueba de Goedel a un genuino teorema de indecidibilidad.

La mejora de Rosser no solo condujo a una versión "más formalista" de TI; también tuvo consecuencias reales, relevantes para su pregunta. En concreto, muestra:

La imposibilidad de demostrar es incomputable: no existe ningún algoritmo que pueda determinar si una oración determinada en el lenguaje de la aritmética no es demostrable a partir de PA.

¿Por que no? Bueno, supongamos que A fuera un algoritmo de este tipo. Entonces podríamos construir una extensión recursivamente axiomatizable completa consistente de PA (¡contradiciendo la versión de IT de Rosser!) de la siguiente manera:

• Enumerar las oraciones de la aritmética de manera razonable como P_1, P_2, P_3,...

• Defina Q_i inductivamente de la siguiente manera:

  • Q_1="No P_1" si P_1 no es demostrable en PA, y Q_1="P_1" en caso contrario.

  • Habiendo definido Q_i, hacemos Q_{i+1}="Not P_{i+1}" si la oración "(Q_1 and Q_2 and ... and Q_i) implica P_{i+1}" no es demostrable en PA, y Q_{i+1}="P_{i+1}" en caso contrario.

Suponiendo la existencia de A, la sucesión Q_i es computable. Ahora considere la teoría T=PA+{Q_1, Q_2, Q_3, ...}; esta teoría se axiomatiza recursivamente, extiende PA y (por un argumento de inducción fácil) es consistente; ¡ups!

¡Ahora tenga en cuenta que T probablemente esté equivocado en muchas cosas! En ningún momento de la construcción de T nos referimos a la verdad de las oraciones de la aritmética, simplemente a su (no) demostrabilidad . Así que este argumento realmente necesitaba toda la fuerza de la versión de TI de Rosser; sin embargo, la conclusión de que la demostrabilidad PA es incomputable es de interés incluso si adoptamos un punto de vista completamente platónico y no tenemos ningún interés a priori en las teorías incorrectas de la aritmética.

Pasemos ahora al meollo de la cuestión: algunas razones para la indecidibilidad.

El punto anterior, que la indemostrabilidad es incomputable, puede modificarse a "la indecidibilidad es incomputable" sin demasiado esfuerzo. Intuitivamente, esto dice que hay muchas razones para la indecidibilidad (o no demostrabilidad), y que nunca tendremos una comprensión completa de lo que impulsa el fenómeno. Curiosamente, esto choca con el hecho general, mencionado anteriormente por jobermark, de que casi todos los ejemplos conocidos actualmente de indecidibilidad provienen de problemas de autorreferencia.

Sin embargo, hay casos de indemostrabilidad que no provienen de paradojas y para los cuales existe evidencia filosófica razonable de indemostrabilidad; permítanme dar un ejemplo de uno de estos, que aprendí de Asaf Karagila . Esta es una instancia de indecidibilidad, no de PA, sino de ZFC (= teoría de conjuntos estándar; esta es una teoría de primer orden, a pesar de tratarse de conjuntos, y los teoremas de Goedel se aplican a ella ). En particular, el lenguaje relevante es diferente: en lugar de trabajar en el lenguaje ${+, \times, <, 0, 1}$ (o similar) de la aritmética, estamos trabajando en el lenguaje ${\in}$ de teoría de conjuntos.

Un cardenal inaccesible es un cardenal infinito particularmente grande. Específicamente, es un cardenal que es más grande que el conjunto de potencia de cualquier cardenal debajo de él, y también satisface una condición de "regularidad" más técnica . Intuitivamente, los cardenales inaccesibles no pueden "construirse a partir de cardenales más pequeños".

Sea P la oración "Hay un cardinal inaccesible" (no es difícil, pero algo tedioso, expresar esto en el lenguaje de la teoría de conjuntos), y pensemos en P en la teoría de conjuntos ZFC. Hay una serie de argumentos filosóficos a favor de la consistencia de ZFC junto con P; véase, por ejemplo, el artículo de Penelope Maddy "Believing the axioms". Así que por el momento demos por sentado Con(ZFC+P), es decir, que ZFC no refuta P. ¿Cómo podemos demostrar que ZFC tampoco prueba P?

La prueba habitual de esto es a través del teorema de Goedel: muestra que ZFC+P prueba Con(ZFC). Sin embargo, ¡hay una prueba que evita esto! Supongamos que ZFC demostró P. Entonces sea V un modelo de ZFC. Dado que V es un modelo de ZFC, y ZFC prueba P, hay algo de k en V que V cree que es (i) un cardinal inaccesible y (ii) el cardinal menos inaccesible (ya que V satisface Regularidad, para cualquier propiedad definible hay un cardenal mínimo con esa propiedad si existe algún cardenal con esa propiedad en primer lugar).

Pero ahora considere V_k, el k-ésimo nivel de la jerarquía acumulativa de V. No es difícil comprobar que V_k satisface los axiomas de ZFC. ¡Pero V_k no puede tener un cardenal inaccesible! Esto se debe a que cualquier cardinal inaccesible m en V_k también sería un cardinal inaccesible en V (esto no es obvio y requiere un argumento corto; en particular, ¡esto falla si reemplazamos "inaccesible" con una noción cardinal grande más complicada !) , y sería menor que k (ya que todo cardenal en V_k es menor que k); pero k era por definición el cardenal menos inaccesible en V. Así que esto es una contradicción.

¡Tenga en cuenta que en ningún momento lo invocamos! Este es un ejemplo de un fenómeno de indemostrabilidad que surge por razones "puramente matemáticas" (es decir, no metamatemáticas). Por supuesto, la distinción es muy subjetiva, y es posible que personas razonables mucho más inteligentes que yo no estén de acuerdo con la afirmación que hice en la oración anterior; pero sigo pensando que es interesante.

Por cierto, también vale la pena señalar que el teorema de incompletitud en sí mismo tiene una prueba que en realidad no depende de las paradojas: a saber, Kripke dio una prueba que, en ciertos aspectos, es similar al argumento sobre los inaccesibles que describí anteriormente. Consulte esta pregunta mía en mathoverflow para obtener más pruebas de incompletitud.

Conocemos algunas, pero no todas, las posibles causas de la indecidibilidad, y las que conocemos son, en esencia, las mismas razones por las que tenemos paradojas en el pensamiento ordinario. Las pruebas que tenemos de la indecidibilidad generalmente se basan en una paradoja conocida específica y simplemente la formalizan.

Por ejemplo, la prueba de Goedel es una versión elaborada e ineludible de la paradoja de Creta. Produce una proposición que dice: La proposición #[número grande] no está en la lista de cosas que podemos probar y, por cierto, esta es la proposición #[número grande]. En otras palabras: las proposiciones numeradas de Creta nunca son demostrablemente verdaderas, dice la proposición numerada de Creta. Pero a diferencia del cretense original, solo dice que no es demostrable, no que esté mintiendo. Entonces podemos evitar la paradoja absoluta aceptando el hecho de que hay cosas que son ciertas pero el sistema no puede probarlas.

Una versión más simple se basa en la 'paradoja de Berry': 'El entero positivo más pequeño no definible en menos de doce palabras' contiene menos de doce palabras y, por lo tanto, no define ningún entero positivo. Si contamos sistemáticamente el número de proposiciones demostrables, podemos, usando el sistema de enumeración, encontrar siempre el equivalente del número mágico doce en la paradoja original. Podemos demostrar que cualquier enunciado demostrable sobre un número dado es 'al menos tan complejo de enunciar', pero enunciar ese hecho en un enunciado menos complejo que el mínimo establecido.

Pero sólo podemos ver las paradojas que vemos . Si podemos forzar una sola paradoja en un sistema tan complejo, no podemos saber que no hay otras paradojas al acecho a la vuelta de la esquina. De hecho, sabemos que no podemos saber eso . La prueba en sí no es una sola deducción, sino un algoritmo que se puede aplicar a cualquier sistema de este tipo. Por lo tanto, elaborar el sistema para resolver una paradoja conocida siempre lo deja sujeto a la misma prueba de incompletitud.

Podemos encontrar nuevos aspectos indecidibles de cualquier sistema formal formalizando los principios de los que derivan las paradojas que conocemos :

1. La autorreferencia y la negación tienen una compatibilidad limitada (la paradoja de Russel y todos sus parientes)
2. El infinito y el orden tienen una aplicación significativa limitada con respecto al otro (la independencia inesperada del Axioma de Elección y la Hipótesis del Continuo)
3. La continuidad y la identificabilidad tienen una compatibilidad limitada (problemas de sorites, las peculiares limitaciones de los infinitesimales y la paradoja de Banach-Tarski)
4. La capacidad de saber qué generalizaciones constituyen definiciones y cuáles no, está implícitamente limitada (colecciones importantes de Goedel-Bernays-VonNeumann que no pueden ser conjuntos, por ejemplo, el 'grupo' de todos los grupos bajo productos, que no puede ser un grupo porque su conjunto base contendría conjuntos de todos los tamaños, pero simplemente es un grupo desde cualquier perspectiva normal).

Kant ya había señalado un solo caso de cada una de estas limitaciones con sus 'antinomias': cuatro problemas que sintió que había demostrado eran problemas significativos más allá de la capacidad de resolución de los humanos:

• 1 es la esencia de su respuesta al problema del libre albedrío,
• 2 es la esencia de su respuesta al problema del fin de los tiempos,
• 3 es la esencia de su respuesta al problema de los átomos,
• 4 es la esencia de su respuesta al problema del ser necesario.

Ahora que entendemos que los sistemas formales en realidad no ayudan a eliminar estas limitaciones, hemos producido sistemas formales que las evaden o resuelven, o hemos llegado a aceptarlas. Pero eso no significa que sean las únicas fuentes de conflicto potencial. Sabemos que no lo son.

Dado que su pregunta principal se ha abordado adecuadamente en los comentarios y respuestas, pensé que tal vez otra perspectiva podría ser esclarecedora.

Definición: Un enunciado es indecidible si no hay prueba de que es verdadero ni prueba de que es falso.

Proposición: Ayer tomé una taza de café en la mañana.

Ahora bien, ¿hay alguna prueba de esta proposición bastante inocua? No hay nada complicado o metafísico al respecto; es fácil de entender y no requiere matemáticas complicadas o incluso simples, y está dentro de la experiencia cotidiana de casi todo el mundo; en cuanto a su verdad... puedo dar fe de su verdad.

Ergo: las proposiciones verdaderas e indecidibles son fáciles de encontrar; usted también puede hacerlo en casa, sin ningún peligro para su salud o la de sus invitados o amigos; aunque es posible que no estén impresionados.

Sugeriría que la mayoría de las proposiciones son así, verdaderas o falsas, pero indecidiblemente. ¿Por qué, entonces, deberíamos suponer que los sistemas formales son diferentes?

Se puede dar la vuelta a la pregunta: ¿podemos encontrar un sistema formal tal que todas las proposiciones sobre él puedan demostrar que son decidibles? Sí hay; pero son tan simples que no vale la pena preocuparse por ellos.

Lo importante del ejercicio por el que pasó Gödel es la invención de un sistema formal y su aparato concomitante; por ejemplo, hay una prueba de Hilberts Nullstellensatz utilizando herramientas desarrolladas a partir de las ideas de Godel.

La indecidibilidad es entonces un fenómeno generalizado sobre el mundo real, que no debería sorprendernos en absoluto encontrar reflejado en sistemas formales que buscan explicarlo o reflejarlo, como los números naturales o la geometría; la sorpresa, supongo, es que se puede demostrar en un sistema tan simple como la aritmética; pero entonces, como han demostrado cuestiones como el teorema de Fermat, o la aún pendiente hipótesis de Riemann, pueden ser muy difíciles; así que, en realidad no es tan sorprendente.