Con esta definición de completitud, el resultado de Incompletitud de Gödel no parece sorprendente, ¿por qué lo fue entonces?

Question

Según wikipedia una teoría (es decir, un conjunto de oraciones) es completa si para cada fórmula es demostrable o su negación.

Por otro lado, una lógica es completa si "semánticamente válida" y "demostrable" son lo mismo.

La primera noción de completitud es con la que se relaciona el resultado de Incompletitud de Gödel, pero entonces no entiendo el significado que se le da, o por qué sorprendió a la gente? Porque si leo la primera definición, si puedo dar una fórmula que se satisface en un modelo, pero no en el otro, entonces esta fórmula y su negación no podrían ser demostrables (si la lógica es sólida). Y en general, yo esperaría esta propiedad más que la propiedad de que en toda teoría, toda frase o bien se cumple en todos los modelos (es válida), o bien su negación es válida.

Para ser más específicos, el resultado de Gödel en su formulación original se refiere a la aritmética de Peano, pero también es válido en alguna forma de teoría de primer orden de los números naturales con la multiplicación y la suma como nociones primitivas, y para ello sabemos que los números naturales no son el único modelo.

Entonces, ¿por qué me sorprendió? ¿Realmente se pensaba que para cada teoría y una fórmula determinada, ésta o su negación son semánticamente válidas, es decir, que se cumplen en todos los modelos?

Answer 1

¿La gente realmente pensó que para cada teoría y una fórmula dada, tanto ésta como su negación son semánticamente válidas, es decir, las cumple todo modelo?

(Énfasis añadido). No, claro que no. Es fácil hacer teorías que son obviamente incompletas.

Pero el contenido del teorema de incompletitud de Gödel no es sólo que "hay algunas teorías que son incompletas", sino que toda axiomatización razonable de la aritmética básica será una de las teorías incompletas.

Muchos matemáticos de principios del siglo XX sí esperaban que hubiera algunos manera de presentar un fundamento de las matemáticas de forma que (al menos en principio) resolviera todas las cuestiones que pudiéramos plantear sobre ellas. La sensación era que sólo era cuestión de averiguar cómo para hacerlo, y había una sensación general de estar avanzando hacia el objetivo.

Entonces llegó Gödel y demostró que no se puede hacer -- ni siquiera para la aritmética básica.

Answer 2

EDIT: He añadido aquí algunos de los hechos de la discusión entre el OP y yo en los comentarios debajo de la pregunta. Estos no abordan el OP real - "¿por qué fue sorprendente el teorema de Godel?" - pero creo que aclaran algunas confusiones relevantes.

Godel demuestra (esencialmente) que cualquier teoría recursivamente axiomatizable que es verdadera de $\mathbb{N}$ es incompleta; en particular, que bajo hipótesis razonables la teoría específica PA es incompleta. (Obsérvese que el AT, por definición, es completo -véase más adelante-, pero por el teorema de la compacidad no se puede precisar $\mathbb{N}$ hasta el isomorfismo). Obsérvese que esto es equivalente a la afirmación de que la verdadera teoría del AT aritmético no es recursivamente axiomatizable, por lo que es expresable sin utilizar nunca la palabra "incompleto". Sin embargo, la interpretación computacional-teórica anterior no capta realmente el espíritu del teorema en ese momento.

Además, centrarnos en el AT nos hace perder una importante extensión del teorema: que no La teoría completa y consistente que extiende PA es recursivamente axiomatizable. Esto sólo implica un simple ajuste de la prueba pero se trata fundamentalmente de la AP y no de la AT (y, por cierto, la AP puede sustituirse aquí por un una teoría mucho más débil ).

---

Usted escribe:

Para ser más específicos, el resultado de Gödels en su formulación original se refiere a la aritmética de Peano, pero también es válido en alguna forma de teoría de primer orden de los números naturales con la multiplicación y la suma como nociones primitivas, y para ello sabemos que los números naturales no son el único modelo.

Pero esto no es cierto en la forma en que usted quiere que lo sea. La prueba de que la teoría de primer orden de los números naturales (llámese "TA" por "aritmética verdadera") tiene modelos no isomorfos al modelo estándar es a través de la teorema de la compacidad . Sin embargo, estos modelos hacer satisfacen todas las mismas sentencias que $\mathbb{N}$ ¡lo hace! Es decir, que no son isomorfas a Pero ellos son elementalmente equivalentes a El modelo estándar $\mathbb{N}$ .

El punto clave aquí es que el AT es una teoría completa. En concreto, definimos TA como $\{\theta: \mathbb{N}\models\theta\}$ , es decir, el conjunto de oraciones de primer orden verdaderas en $\mathbb{N}$ . Esto es completo porque para cualquier frase $\eta$ , ya sea $\mathbb{N}\models \eta$ (en cuyo caso $\eta\in$ TA) o $\mathbb{N}\models\neg\eta$ (en cuyo caso $\neg\eta\in$ TA). De forma más general, para cualquier estructura $\mathcal{A}$ el conjunto $Th(\mathcal{A})=\{\theta: \mathcal{A}\models\theta\}$ es una teoría completa. Obsérvese que estamos no alegando que $Th(\mathcal{A})$ caracteriza $\mathcal{A}$ hasta el isomorfismo. Una consecuencia de la compacidad es que la equivalencia elemental -es decir, la concordancia en todas las oraciones de primer orden- es estrictamente más débil que el isomorfismo, por lo que tener muchos modelos no sugiere de ninguna manera la incompletitud (por ejemplo DLO tiene muchos modelos no isomórficos, pero es completa) . Así, La producción de modelos no isomórficos no demuestra que una teoría sea incompleta .

---

Lo anterior explica por qué los resultados no implicaba inmediatamente el teorema de la incompletitud. Pero, ¿por qué la existencia de técnicas ¿dar una prueba rápida?

Bueno, el problema es que en realidad sólo había dos técnicas para construir modelos: se podía demostrar la existencia de un modelo a través de la compacidad, o se podía encontrar una estructura "en la naturaleza" (o cocinar una a mano) y demostrar que era un modelo de la teoría deseada.

El teorema de la compacidad no es útil para demostrar que la AP es incompleta:

• Para demostrar que la AP es incompleta, basta con encontrar un modelo $M$ de PA y una sentencia $\varphi$ tal que $M\models\varphi$ pero $\varphi$ no está en AT.

• Una vez que haya elegido un $\varphi$ se puede hacer mediante el teorema de la compacidad aplicado a PA + $\varphi$ ...

• si sabes que PA + $\varphi$ ¡es finitamente satisfacible! Por el teorema de completitud, se sabe que PA + $\varphi$ es finitamente satisfacible si PA + $\varphi$ es consistente (trivialmente "finitamente consistente" y "consistente" significan lo mismo), así que todo lo que necesitas hacer es ...

• ... elige alguna frase $\varphi$ no en TA (= falso en $\mathbb{N}$ ) tal que PA + $\varphi$ es consistente.

¡Aaaaand hemos ido en un círculo!

Otra opción sería encontrar primero un modelo no estándar $M$ de PA y luego demostrar que $M$ no es elementalmente equivalente a $\mathbb{N}$ encontrando explícitamente una frase en la que no están de acuerdo. Este tipo de argumento es extremadamente útil en los casos en que la teoría que se estudia tiene muchos modelos fácilmente descriptibles. Sin embargo, $\mathbb{N}$ es el único modelo de AP fácilmente descriptible en un sentido preciso ¡! Aunque esto no se sabía en ese momento, se hace significa que el fracaso de los intentos de encontrar explícitamente modelos no estándar de AP que no sean elementalmente equivalentes a $\mathbb{N}$ no es sorprendente.

La cuestión es que no había pruebas concretas de que la AP estuviera incompleta en su momento, al menos desde el punto de vista de la teoría de los modelos.

Answer 3

Puede ser útil señalar que hay (al menos) dos propósitos para los que se crean las teorías axiomáticas y, como resultado, dos tipos de teorías, para las que podemos tener expectativas muy diferentes. Una situación, conocida desde la época de Euclides, es que tenemos una estructura matemática particular (geometría plana, o los números naturales, o los números complejos, etc.) cuyas propiedades queremos organizar de forma sistemática. Así que tomamos unas pocas propiedades (fácilmente comprensibles y aceptadas) como axiomas y deducimos el resto. La segunda situación, que parece haber surgido sólo en los siglos XIX y XX, es que tenemos numerosas estructuras en las que hemos observado algunas similitudes, y resumimos las similitudes mediante axiomas que se aplican a todas esas estructuras. Un ejemplo importante serían los axiomas para los grupos, que están diseñados para aplicarse igualmente a los enteros con la operación de adición, a las permutaciones con la composición, a los conjuntos con la diferencia simétrica y a muchas otras estructuras.

Para los sistemas de axiomas del segundo tipo, sería una tontería esperar que fueran completos. Los axiomas fueron diseñados para aplicarse a muchas estructuras diferentes, por lo que cualquier aspecto en el que esas estructuras difieran sería indecidible sobre la base de los axiomas. Por ejemplo, sería una tontería esperar que los axiomas de la teoría de grupos demostraran o refutaran la ley conmutativa, porque los axiomas se diseñaron para aplicarse a ejemplos conmutativos (adición de enteros) y no conmutativos (composición de permutaciones).

Sin embargo, para los sistemas de axiomas del primer tipo, las expectativas eran muy diferentes. Dado que los axiomas pretendían describir una estructura concreta, uno querría deducir, a partir de los axiomas, todas las propiedades de esa estructura. Cualquier afirmación significativa $A$ sobre esa estructura sería verdadera o falsa, por lo que uno esperaría deducir $A$ o para deducir $\neg A$ , lo que sea cierto en la estructura prevista. Si los axiomas no producen tales deducciones, entonces se podría decir razonablemente que son deficientes, que la persona que elaboró el sistema axiomático ha omitido alguna información que debería estar allí.

Hasta que apareció el teorema de Gödel, tales expectativas eran bastante razonables para los sistemas axiomáticos del primer tipo, como PA o Principia Mathematica (el único sistema explícitamente nombrado en el título del artículo de Gödel) o ZFC. Y parece haber sido aceptado casi universalmente que, incluso si los sistemas axiomáticos conocidos fueran incompletos, la situación podría corregirse añadiendo más axiomas de alguna manera razonable. Es decir, deberíamos ser capaces de dar un fundamento axiomático a todos los hechos matemáticos sobre, por ejemplo, los números naturales y los números reales, o sobre la geometría plana, etc. Parte del gran logro de Gödel fue mostrar que tales expectativas no pueden cumplirse, en el caso de la aritmética o en el de la teoría de conjuntos, si el sistema de axiomas ha de ser razonable, es decir, si queremos ser capaces de decir, sin inspiración divina, qué es y qué no es un axioma.

Answer 4

Porque en los años 30, que fue el contexto de los resultados de Gödel, cuando se plantearon por primera vez las preguntas, las "expectativas" eran diferentes.

Véase el primer libro de texto moderno de lógica matemática, con la primera definición clara de lo que ahora llamamos problemas metamatemáticos:

• David Hilbert y Wilhelm Ackermann, Principios de lógica matemática Traducción al inglés (1950) de la 2ª edición alemana de 1937. (1950) de la 2ª ed. alemana de 1937, página 42:

Consideremos ahora la cuestión de integridad . La completitud de un sistema de axiomas puede definirse de dos maneras. En primer lugar, puede considerarse que todas las fórmulas verdaderas de un determinado dominio caracterizado por el contenido pueden demostrarse a partir del conjunto de axiomas. Sin embargo, el concepto de completitud puede También se puede formular de forma más estricta, de modo que un sistema de axiomas se denomina completo sólo si siempre surge una contradicción cuando se añade a los axiomas una fórmula que no se puede demostrar previamente a partir de ellos.

Aplicado a cálculo de predicados La primera cuestión fue resuelta (en sentido positivo) por el Teorema de Completitud de Gödel:

Cualquier fórmula universalmente válida del cálculo de predicados es demostrable.

Pero la pregunta puede hacerse también sobre un sistema con axiomas no lógicos. Y este es el objetivo del Teorema de Incompletitud de Gödel de 1931:

Si a los axiomas de Peano añadimos la lógica de Principios matemáticos (con los números naturales como individuos) junto con el axioma de elección (para todos los tipos), obtenemos un sistema formal $S$ para los que se cumplen los siguientes teoremas:

I. El sistema $S$ no es completa [entscheidungsdefinit] ; es decir, contiene proposiciones [ frases ] $A$ (y de hecho podemos exhibir tales proposiciones) para las que ni $A$ ni $\lnot A$ es demostrable.

Pero decir que podemos exhibir una frase $A$ del sistema $S$ (correspondiente a la aritmética de Peano) tal que ni $A$ ni $\lnot A$ es demostrable en $S$ significa que es no verdadero

"que todas las fórmulas verdaderas de un determinado dominio que se caracteriza por el contenido [en este caso : el dominio $\mathbb N$ ] se puede demostrar a partir del conjunto de axiomas".

---

La existencia de un modelo no estándar para la aritmética fue demostrada por Th. Skolem en 1933.

Parece que sólo alrededor de 1950 se observó por primera vez (por S.C. Kleene en su Introducción a la metamatemática (1952) , página 430) que la existencia de modelos no estándar de los axiomas habituales de la teoría elemental de los números era derivable yuxtaponiendo el teorema de completitud de Gödel y su teorema de incompletitud.

Answer 5

La prueba de incompletitud de Godel se publica en 1931. En 1931, la respuesta de la comunidad matemática a su pregunta

"¿Realmente se pensaba que para cada teoría y una fórmula dada, o bien ella o su negación son semánticamente válidas, es decir, se cumplen en cada modelo?"

y comentar

"Porque si leo la primera definición, si puedo dar una fórmula que se satisface en un modelo, pero no en el otro, entonces esta fórmula, y su negación no podrían ser demostrables (si la lógica es sólida)".

es "¿Qué es un modelo?"

Algunas lógicas matemáticas anteriores a los años 50 fueron reconocidas posteriormente como teóricas de modelos. Pero la teoría de modelos no era una cosa hasta que Tarski y sus alumnos lo desarrollaron en los años 50 y 60.

El escenario del optimismo extremo de Hilbert se describe con cierto detalle en La filosofía de las matemáticas de Hilbert , especialmente la sección 5, "El programa de Hilbert y el positivismo lógico".

---

Añadido en la edición, 20180407.

Skolem, por ejemplo, no interpretó ninguno de sus Teoremas de Lowenheim-Skolem (la primera, con AC y la segunda, sin ella) en un sentido teórico del modelo. La primera vez que me expusieron esto fue en [G],

"Desde nuestra perspectiva, es obvio que la posesión de propiedades teóricas de conjuntos, si es relativa a algo, es relativa al modelo que uno está usando para interpretar el sistema formal. Varios escritores han señalado que esto quizás no era obvio para Skolem, quien, según ellos, a menudo interpretaba la LST como una demostración de la relatividad de las nociones teóricas de conjuntos con respecto al propio sistema de axiomas (véase, por ejemplo, su 1929b, 293 [sic]; y 1958, 635-637)." Estas referencias son

• 1929b "Uber einige Grundlagen fragen der Mathematik", Skrifrer, Vitenskapsakadernie I, 4, 1-49; reimpreso en Skolem 1970, 227-273.
• 1958 "Une relativisation des notions mathematiques fondamentales", en Colloque: nationaux du Centre National de Recherche Scientifique, París, 13-18; reimpreso en Skolem 1970, 633-638.
• 1970 Selected works in logic, editado por Fenstad, J.E., Oslo (Universitetsforlaget).

En resumen, cuando decimos que el teorema de Lowenheim-Skolem es un teorema sobre modelos, estamos poniendo palabras en la boca de Skolem. Él escribe como si los axiomas eligieran un modelo único, por lo que el estudio de los modelos sería redundante. También escribe como si la existencia de modelos no estándar de la aritmética fuera un defecto de la sistema lógico no de los sistemas de axiomas modelo propuestos. Véase

• Skolem, "On the Impossibility of a Complete Characterisation of the Number Series by Means of a Finite System of Axioms. Norsk Matematisk Forening, Skrifter, páginas 73-82, 1933 (reimpreso en Skolem 1970, 345-354).

• Skolem, "Uber de Nichtcharakterisierbar der Zahlenreihe mittels finito o contablemente infinito de proposiciones con variables exclusivamente numéricas. Fundamenta Mathematicae, 23:150-161, 1934 (reimpreso en Skolem 1970, 355-366).

Es fácil mirar hacia atrás en el tiempo y enmarcar el trabajo de otros en términos que no estaban disponibles y habrían sido ajenos a ellos. Cuando impulsamos las ideas y el lenguaje de la teoría de los modelos antes de mediados de la década de 1930, somos culpables de hacerlo. E incluso entonces, una vez que esos términos están disponibles, no lo están al instante para todos los profesionales; puede pasar más de una década para que las buenas ideas se comuniquen ampliamente y se expliquen con claridad.

[G] George, A., "Skolem y el teorema de Lowenheim-Skolem: A Case Study of the Philosophical Significance of Mathematical Results", History and Philosophy of Logic, 6 (1985), pp. 75-89, http://www.fitelson.org/140A/george.pdf .