Entender el Teorema de Incompletitud de Gödel

Question

Me estoy esforzando por entender el Teorema de Incompletitud de Gödel. Me interesa mucho lo que dice sobre los lenguajes axiomáticos, pero tengo algunas preguntas:

El teorema de Gödel se demuestra a partir de la aritmética y sus cuatro operadores: ¿todas las matemáticas derivan de estos cuatro operadores (×, +, -, ÷)?

Operaciones como log(x) y sin(x) son, efectivamente, operaciones atómicas, como las de la aritmética, pero ¿no hay infinitos operadores de este tipo que tengan inversos (es decir, + y - son operaciones "inversas", × y ÷ son operaciones inversas).

A mí me parece que hacer una afirmación sobre las limitaciones de la demostrabilidad dados 4 operadores arbitrarios es absurdo, pero eso probablemente pone de manifiesto una laguna en mi comprensión, dado que lo demostró en 1931 y es poco probable que haya encontrado un argumento contrario.

Como comentario adicional, ¿por qué la obsesión por los operadores aritméticos? Probablemente nos parezcan "fundamentales" como humanos, pero a mí me parecen todos ellos derivados de cuatro posibles disposiciones gráficas de los números (si consideramos cuatro lados a un dígito), y fundamentalmente derivados de la suma.

[][] o [][] la suma y, su inversa, la resta

[][]
[][] multiplicación (suma iterativa) y, su inversa, la división

Debe haber operadores consistentes en los números naturales que ciertamente desconocemos, ¿no?

Por favor, disculpen mi ignorancia, espero no haber ofendido a ningún matemático de verdad con esta publicación.

---

edit: Creo que lo estoy entendiendo mucho más, y creo que mi principal dificultad para entenderlo era esa:

Hay afirmaciones que son verdaderas y que no son demostrables.

Parecía una afirmación imposible. Sin embargo, en este momento tiene sentido para mí en el contexto de un lenguaje axiomático con un número limitado de axiomas. En última instancia, sugerir que hay afirmaciones que son verdaderas y expresables en el lenguaje, pero que son indemostrables en el lenguaje (debido al conjunto limitado de axiomas), es lo que creo que es el punto de la prueba -- ¿es esto correcto?

Answer 1

Hay una buena cantidad de contexto histórico que aclara algunas de las decisiones de Gödel en su prueba original. Para una buena visión general de la prueba, el libro de Nagel y Newman Prueba de Goedel es bastante bueno (aunque no está exento de detractores). También recomiendo encarecidamente la obra del difunto Torkel Franzen Teorema de Godel: Una guía incompleta para su uso y abuso . Puede que yo mismo sea culpable de algunos de esos abusos; estoy tratando de evitar muchos detalles técnicos, y esto suele invitar a la imprecisión e incluso al abuso en este campo concreto. Espero que los que saben más que yo me mantengan honesto a través de los comentarios y los tirones de orejas apropiados.

Algo de historia. A veces pienso en el siglo XIX como el El siglo de las fieras . Un "menagerie" era como un zoológico de animales raros. Durante gran parte del siglo XIX, la gente intentaba limpiar algunos de los problemas lógicos que abundaban en los fundamentos de las matemáticas. El cálculo claramente trabajó pero muchas de las nociones de infinitesimales eran simplemente incompatibles con algunos "hechos" sobre los números reales (eventualmente resueltos por la noción de límites de Weierstrass usando $\epsilon$ s y $\delta$ s). Muchas suposiciones que la gente había estado haciendo implícitamente (o explícitamente) se demostraron falsas a través de la construcción de contraejemplos explícitos (los "animales raros" que me llevaron a llamar la siglo de las fieras Muchos matemáticos eran como exploradores que traían animales extraños que nadie había visto antes y que desafiaban las nociones de la gente sobre lo que era y no era el caso): la función de Dirichlet para mostrar que se pueden tener funciones que son discontinuas en todas partes; funciones que son continuas en todas partes pero no diferenciables en ninguna; el fracaso del principio de Dirichlet para algunas funciones; la curva de Peano que rellenaba un cuadrado; etc. Luego, las antinomias (paradojas y contradicciones) en la primera teoría de conjuntos. Incluso algunos trabajos que hoy nos parecen completamente sin problemas causaron mucho debate: la solución de Hilbert al problema de una base finita para invariantes en cualquier número de variables fue originalmente ridiculizada por Gordan como "teología, no matemáticas" (la solución no era constructiva e implicaba el uso de un argumento por contradicción). Muchos encontraron muchos de estos desarrollos profundamente preocupantes. Surgió una crisis fundacional (véase el enlace en la respuesta de Qiaochu).

Hilbert, uno de los principales matemáticos de finales del siglo XIX, propuso una forma de resolver las diferencias entre los dos campos principales. Su propuesta consistía esencialmente en tratar de utilizar métodos que ambos bandos consideraban indiscutiblemente válidos para demostrar que las matemáticas eran consistente que no era posible demostrar tanto una proposición como su negación. De hecho, su propuesta consistía en utilizar métodos que ambos campos consideraban inatacables para demostrar que los métodos que un campamento que se encuentra con problemas no introduciría ningún problema. Esta era la esencia de la Programa Hilbert.

Sin embargo, para poder lograr esto, era necesario tener alguna forma de estudiar las pruebas y las propias matemáticas. Así surgió la noción de "prueba formal", la idea de una axiomatización de las matemáticas básicas, etc. Hubo varios sistemas axiomáticos que compitieron por los fundamentos de las matemáticas: Zermelo intentó axiomatizar la teoría de conjuntos (que luego se amplió a la teoría de conjuntos de Zermelo-Fraenkel); Peano propuso una colección de axiomas para la aritmética básica; y Russell y Whitehead, en su enorme libro Principia Mathematica intentó establecer un sistema axiomático y deductivo para todas las matemáticas (si no recuerdo mal, tarda cientos de páginas en llegar finalmente a $1+1=2$ ). Se lograron algunos éxitos iniciales, con personas que demostraron que algunas partes de tales teorías eran, de hecho, consistentes (se hablará de esto más adelante). Luego vino el trabajo de Gödel.

Coherencia y exhaustividad. Decimos que una teoría formal es consistente si no puede probar ambos $P$ y $\neg P$ en la teoría para alguna frase $P$ . De hecho, porque desde $P$ y $\neg P$ se puede demostrar cualquier cosa usando la lógica clásica, es equivalente que una teoría es consistente si y sólo si hay al menos una frase $Q$ de tal manera que no hay prueba de $Q$ en la teoría. Por el contrario, se dice que una teoría completa si se le da cualquier sentencia $P$ , o bien el tiene una prueba de $P$ o una prueba de $\neg P$ . (Nótese que una teoría inconsistente es necesariamente completa). Hilbert se propuso encontrar una axiomatización consistente y completa de la aritmética, junto con una prueba (utilizando sólo las matemáticas básicas en las que ambos campos estaban de acuerdo) de que era completa y consistente, y de que seguiría siéndolo aunque se utilizaran con ella algunas de las herramientas que su campo utilizaba (y que el otro encontraba desagradables y dudosas).

¿Por qué la aritmética? La aritmética fue un campo particularmente bueno para centrarse en los primeros esfuerzos. En primer lugar, era la base del "otro campo". Kronecker dijo famosamente que "Dios nos dio los números naturales, el resto es obra del hombre". Se esperaba que una axiomatización de los números naturales y sus operaciones básicas (adición, multiplicación) y relaciones (orden) fuera relativamente fácil y también tuviera la esperanza de ser consistente y completa. Es decir, era un buen campo de pruebas, porque contenía muchas matemáticas interesantes y no triviales, y sin embargo parecía ser razonablemente simple.

Gödel . Por esta razón, Gödel se centró en la aritmética. Resulta que la multiplicación es la clave del argumento (hay algo especial en la multiplicación; algunas teorías de los números naturales que sólo incluyen la adición pueden demostrarse consistentes utilizando sólo los tipos de herramientas que Hilbert permitía). Para responder a una de tus preguntas en el camino, Gödel incluso definió nuevas operaciones y relaciones sobre los números naturales que tenían poco que ver con la suma y la multiplicación a lo largo del camino, de modo que sí, hay operaciones distintas a esas (no hay fetichismo alguno sobre ellas). Pero, de hecho, Gödel no se limitó únicamente a la aritmética. Su prueba es, a primera vista, sobre todo el sistema de matemáticas expuesto en la obra de Russell y Whitehead Principia aunque, como señala Gödel, puede adaptarse fácilmente a otros sistemas siempre que cumplan ciertos criterios (por eso el artículo original de Gödel tiene un título que se refiere explícitamente al Principia "y sistemas conexos").

Lo que Gödel demostró fue que cualquier teoría, sujeta a algunas restricciones técnicas (por ejemplo, debe tener una forma de reconocer si una frase dada es o no un axioma), que sea "lo suficientemente fuerte" como para poder usarla para definir una cierta porción de la aritmética será necesariamente incompleta o inconsistente (es decir, o se puede demostrar todo en esa teoría, o bien hay al menos una frase $P$ de tal manera que ni $P$ ni $\neg P$ puede probarse). No es una limitación basada en cuatro operaciones, ni una obsesión por esas operaciones: todo lo contrario. Lo que dice es que si quieres que tu teoría incluya al menos algo de aritmética, entonces su teoría va a ser tan complicada que o bien es inconsistente, o bien hay proposiciones que no pueden ser probadas ni refutadas utilizando únicamente los métodos que ambos bandos consideran válidos.

Es decir: lo que muestra es una limitación de esos métodos particulares (lógicamente inatacables). Si utilizamos otros métodos, podemos establecer la consistencia de la aritmética, por ejemplo, pero si usted tenía sus dudas sobre la consistencia de la aritmética en primer lugar, lo más probable es que encuentre esos métodos igual de dudosos.

Ahora, sobre tu coda, y la afirmación "afirmaciones que son verdaderas pero no demostrables"; esto no es muy acertado. Encontrarás muchas críticas a esta paráfrasis en el libro de Franzen, con razón. Lo mejor es pensar que hay afirmaciones que no son ni demostrables ni refutables. De hecho, una de las cosas que sabemos es que si tienes una afirmación así $P$ en una teoría $M$ entonces puede encontrar un modelo (una interpretación de los axiomas de $M$ que hace que los axiomas sean verdaderos) en el que $P$ es verdadera, y un modelo diferente en el que $P$ es falso. Así que en cierto sentido, $P$ no es ni "verdadera" ni "falsa", porque que sea verdadera o falsa dependerá de la modelo que está utilizando. Por ejemplo, la sentencia de Gödel $G$ que demuestra el Primer Teorema de Incompletitud (que si la aritmética es consistente entonces es incompleta, ya que no puede haber demostración de la sentencia $G$ y ninguna prueba de $\neg G$ ) suele decirse que es "verdadero pero indemostrable" porque $G$ puede interpretarse como que "no hay pruebas de $G$ en esta teoría". Pero de hecho, se puede encontrar un modelo de aritmética en el que $G$ es falso Entonces, ¿por qué decimos $G$ ¿es "verdadero"? Bueno, la cuestión es que $G$ es cierto en lo que se llama "el modelo estándar". Hay una interpretación particular de la aritmética (de lo que significa "número natural", de lo que $0$ significa, de qué "sucesor de $n$ " significa, de lo que $+$ medios, etc.) que solemos tener en mente; en ese modelo , $G$ es verdadera pero no demostrable. Pero sabemos que hay diferentes modelos (donde "número natural" puede significar algo completamente diferente, o quizás $+$ significa algo diferente) donde podemos mostrar que $G$ es falso según esta interpretación de los axiomas. Yo me mantendría alejado de "verdadero" y "falso", y me quedaría con "demostrable" e "indemostrable" al hablar de esto; tiende a evitar problemas.

Primer resumen. Así que: hubo razones históricas por las que Gödel se centró en la aritmética; la limitación no es de la aritmética en sí, sino de los métodos formales en cuestión: si tu teoría es lo suficientemente "fuerte" como para poder representar parte de la aritmética (además de satisfacer las pocas restricciones técnicas), entonces o bien tu teoría es inconsistente, o bien los métodos de prueba finíticos en cuestión no pueden bastar para resolver todas las cuestiones (hay sentencias $P$ que no se puede probar ni refutar).

¿Se puede rescatar algo? Bueno, lo ideal hubiera sido tener una teoría completa y consistente, y que pudiéramos mostrar es completa y coherente utilizando sólo los tipos de métodos lógicos que nosotros, y casi todo el mundo, encuentra fuera de toda duda. Pero, ¿quizás podamos demostrar al menos que los otros métodos no introducen ningún problema? Es decir, que la teoría es consistente, aunque no sea completa. Eso, al menos, sería una especie de victoria.

Desgraciadamente, Gödel también demostró que esto no es así. Demostró que si su teoría es lo suficientemente compleja como para poder representar la parte de la aritmética en cuestión (y satisface las condiciones técnicas aludidas anteriormente), y la teoría es ¡consistente, entonces de hecho una de las cosas que no puede resolver es si la teoría es consistente! Es decir, se puede escribir una frase $C$ que tiene sentido en la teoría, y que esencialmente "significa" "Esta teoría es consistente" (muy parecido a la sentencia de Gödel $G$ esencialmente "significa" que "no hay pruebas de $G$ en esta teoría"), y que se puede demostrar que si la teoría es consistente entonces la teoría no tiene pruebas de $C$ y ninguna prueba de $\neg C$ .

De nuevo, se trata de una limitación de esos métodos finistas que todo el mundo considera lógicamente inatacables. De hecho, hay pruebas de la consistencia de la aritmética que utilizan la inducción transfinita, pero como he aludido anteriormente, si usted albergaba dudas sobre la aritmética en primer lugar, ¡simplemente no se va a sentir muy cómodo con la inducción transfinita! Imagina que no estás seguro de que $X$ es ser sincero, y $X$ sugiere que se pregunte $Y$ sobre $X$ de la verdad; no sabes $Y$ pero $X$ le asegura que $Y$ es muy de confianza. Bueno, eso no te va a ayudar, ¿verdad?

Lo más importante: Como el teorema se aplica a cualquier teoría que es suficientemente compleja (y satisface las restricciones técnicas), ni siquiera estamos en condiciones de ampliar nuestro conjunto de axiomas para escapar de estos problemas. Mientras nos limitemos a los métodos de ampliación que nos parezcan lógicamente inatacables, las restricciones técnicas seguirán satisfaciéndose, de modo que la nueva teoría, aunque sea más fuerte y más grande porque tiene más axiomas, será todavía estar incompleta (aunque posiblemente sea otros oraciones que ahora son incompletas o indemostrables; recuerde que al añadir axiomas, también estamos ampliando potencialmente el tipo de cosas sobre las que podemos hablar). Así que los teoremas no se refieren a las deficiencias de particular sistemas axiomáticos, sino sobre aquellos métodos finíticos dentro de una clase muy grande de sistemas.

¿Qué pasa con esas "restricciones técnicas"? Son importantes. Supongamos que la aritmética fuera consistente. Eso significa que hay al menos un modelo para ella. Podríamos elegir un modelo $M$ y luego decir "Hagamos una teoría cuyos axiomas sean exactamente aquellas frases que son verdaderas cuando se interpretan en $M$ ." Este es un completa y consistente sistema axiomático para la aritmética. Completo, porque cada frase es verdadera en $M$ (y por lo tanto un axioma, por lo tanto demostrable en esta teoría) o bien falso en $M$ en cuyo caso su negación es verdadera (y por tanto un axioma, y por tanto demostrable). Y consistente, porque tiene un modelo, $M$ y una teoría es consistente si y sólo si tiene un modelo. El problema con esta teoría axiomática es que si te doy una frase, ¡te va a costar decidir si es o no un axioma! En realidad no conseguimos nada con este sistema axiomático. Las "restricciones técnicas" consisten tanto en hacer que el sistema sea realmente utilizable, como en ciertas cuestiones técnicas que surgen de la mecánica de la demostración. Pero las restricciones son lo suficientemente suaves como para que casi todo el mundo esté de acuerdo en que la mayoría de las teorías razonables probablemente las satisfagan.

Segundo resumen. Así que: si tienes un sistema axiomático formal que satisface ciertas restricciones técnicas (pero leves), si la teoría es lo suficientemente grande como para que puedas representar (cierta parte de) la aritmética en ella, entonces la teoría es inconsistente, o bien los métodos finíticos que todo el mundo está de acuerdo en que son inatacables son insuficientes para demostrar o refutar cada frase de la teoría; peor aún, una de las cosas que los métodos finíticos no pueden demostrar o refutar es si la teoría es de hecho consistente o no.

Espero que eso ayude. En cualquier caso, recomiendo el libro de Franzen. Te alejará de posibles interpretaciones erróneas de lo que dice el teorema (probablemente yo mismo soy culpable de algunas de las anteriores, que sin duda serán abordadas en los comentarios por aquellos que saben mejor que yo).

Answer 2

El teorema de incompletitud es mucho más general que "la aritmética y sus cuatro operadores". Lo que dice es que cualquier sistema formal efectivamente generado que sea suficientemente potente es inconsistente o incompleto. Esto requiere que el sistema sea capaz de hablar de aritmética, pero también puede hablar de mucho más que de aritmética.

A mí me parece que hacer una afirmación sobre las limitaciones de la demostrabilidad dados 4 operadores arbitrarios es absurdo

Entonces deberías estudiar más. Las matemáticas no están supeditadas a tu intuición. Cuando tu intuición choca con las matemáticas, debes asumir que tu intuición está equivocada. (No pretendo ser duro, pero esta es una actitud que debes digerir antes de poder aprender realmente las matemáticas).

Tampoco hay que pensar que la aritmética se limita a las operaciones aritméticas: también se trata de la cuantificadores .

Como comentario adicional, ¿por qué la obsesión por los operadores aritméticos?

¿Quién dice tener una obsesión por los operadores aritméticos? Quizás lo que te falta aquí es el contexto histórico. El contexto histórico es, a grandes rasgos, el siguiente: en la época de Gödel había un programa, iniciado por Hilbert que pretendía dar un conjunto completo de axiomas para toda la matemática. Es decir, Hilbert quería escribir un conjunto de axiomas (consistentes) a partir de los cuales se pudieran deducir todas las verdades matemáticas. (Para entender realmente por qué Hilbert quería hacer esto, debería leer sobre el crisis fundacional de las matemáticas ). Esto era muy grandioso y ambicioso y mucha gente tenía grandes esperanzas en el programa de Hilbert hasta que Gödel destruyó esas esperanzas con el teorema de Incompletitud, que muestra que el programa de Hilbert no podía tener éxito: si los axiomas son lo suficientemente poderosos como para hablar de aritmética, entonces son inconsistentes (se pueden demostrar enunciados falsos) o incompletos (no se pueden demostrar algunos enunciados verdaderos).

Answer 3

Antes de entender el teorema de incompletitud de Gödel, hay que saber qué es un sistema formal. Un sistema formal puede considerarse como un lenguaje muy estricto en el que la gramática determina completamente las oraciones permitidas. Así pues, el teorema de incompletitud es una afirmación de que "en un sistema formal lo suficientemente fuerte como para representar la aritmética, hay oraciones que son verdaderas pero no demostrables", lo cual es, para usar tu frase, una "limitación de la demostrabilidad (en un sistema formal)".

Has preguntado "El teorema de Godel se demuestra a partir de la Aritmética y sus cuatro operadores: ¿todas las matemáticas derivan de estos cuatro operadores (×, +, -, ÷)?"

Respuesta: No, hay matemáticas que no utilizan esos operadores. También estás afirmando que la multiplicación y la división son inversas en los números naturales pero eso no es cierto. 7/4 no es una división permitida en los números naturales, sólo es posible cuando se permiten las fracciones.

Preguntaste: "Debe haber operadores consistentes en los números naturales de los que ciertamente no somos conscientes, ¿no?"

Respuesta: Depende de lo que se entienda por "operador". En matemáticas solemos pensar que un "operador" sobre los números naturales es una función que va de un par de números naturales a otro número natural, por lo que, de hecho, hay infinitos operadores sobre los números naturales. Así que sí, hay algunos que "no conocemos" porque hay más de los que podríamos contar. Por ejemplo, inventemos el "operador producto cuadrado" (démosle el símbolo ¤) como llevar dos números al producto de sus cuadrados, de modo que 2 ¤ 3 = (2*2)*(3*3) = 36. Las posibilidades son ilimitadas.

Answer 4

Esta es una recomendación personal.

El libro de Peter Smith "An Introduction to Gödel's Theorems" es muy fácil de leer y muy completo.

Creo que para apreciar plenamente los teoremas de Gödel es una buena idea aprender algo de teoría de la computabilidad antes (Smith incluye algunos de estos antecedentes en su libro, pero un poco más de perspectiva no hace daño).

Dos fuentes muy buenas para los principiantes son "Computability" de Cutland y "Computability and Logic" de Boolos y Jeffrey. Hay un libro de próxima aparición de Enderton (que desgraciadamente ha fallecido hace poco), "Computability Theory", que he podido leer y que también recomiendo encarecidamente. Para una introducción rápida (e inusualmente clara) a la teoría de la computabilidad puedes echar un vistazo a las notas de Enderton, que, por cierto, son un extracto de su libro:

http://www.math.ucla.edu/~hbe/computabilidad.pdf

Espero que esto ayude (a mí me sirvió).

Edición: Permítanme también recomendar un libro muy bueno de Melvin Fitting, Incompletitud en el país de los conjuntos . Como sugiere el título, el autor nos muestra cómo discutir la incompletitud en su lugar más natural: el terreno de los conjuntos hereditariamente finitos.

Answer 5

El primer teorema de incompletitud de Gödel dice, a grandes rasgos, que un sistema formal consistente debe contener enunciados indemostrables (pero verdaderos), aunque ese sistema formal sólo cubra la aritmética de números enteros . Un sistema más fuerte, que contenga aritmética real o compleja, y sin y cos, etc., debe cubrir también la aritmética de los números enteros, por lo que también debe contener afirmaciones indemostrables (pero verdaderas).