En la teoría de modelos, ¿la compacidad implica fácilmente la exhaustividad?

Question

Recordemos los dos teoremas fundamentales siguientes de la lógica matemática:

Teorema de completitud: Una teoría T es sintácticamente consistente -- es decir, para ningún enunciado P puede deducirse formalmente de T el enunciado "P y (no P)" -- si y sólo si es semánticamente consistente: es decir, existe un modelo de T.

Teorema de la compacidad: Una teoría T es semánticamente consistente si todo subconjunto finito de T es semánticamente consistente.

Es bien sabido que el Teorema de la compacidad es una consecuencia casi inmediata del Teorema de la completitud: suponiendo la completitud, si T es inconsistente, entonces se puede deducir "P y (no P)" en un número finito de pasos, por lo tanto utilizando sólo finitamente muchas sentencias de T.

La demostración tradicional del teorema de completitud es bastante larga y tediosa: por ejemplo, el libro Modelos y ultraproductos de Bell y Slomson tarda dos capítulos en establecerse, y la de Marker Teoría de modelos: Una introducción omite por completo la prueba. Hay una prueba más rápida debida a Henkin (aparece, por ejemplo, en el blog de Terry Tao), pero sigue siendo relativamente complicada.

Por otro lado, existe una prueba breve y elegante del teorema de compacidad mediante ultraproductos (de nuevo en Bell y Slomson).

Así que me pregunto: ¿se puede deducir la completitud a partir de la compacidad mediante algún argumento que sea más fácil que la prueba de Henkin de la completitud?

Como observación, creo que estos dos teoremas son equivalentes en un sentido formal: es decir, cada uno de ellos es equivalente en ZF al Teorema del Ideal Primo Booleano. Yo pregunto por una noción más informal de equivalencia.

---

ACTUALIZACIÓN: He aceptado la respuesta de Joel David Hamkins porque era interesante e informativa. No obstante, sigo abierto a la posibilidad de que (alguna versión particular razonable de) el teorema de la completitud pueda deducirse fácilmente de la compacidad.

Answer 1

Creo que estás buscando la Escuela Fraïssé de Teoría de Modelos, que se basa estrictamente en estructuras y tipos como primitivos y evita toda sintaxis. No conozco una buena fuente para el "enfoque Fraïsseano extremista", pero "A Course in Model Theory" de Bruno Poizat es un buen puente (si puedes tolerar el estilo excéntrico, y a veces polémico, de Poizat).

Poizat empieza definiendo los tipos (a través de back & forth) en el capítulo 1, y luego introduce (apologéticamente) las fórmulas en el capítulo 2. En el Capítulo 4, demuestra el Teorema de la compacidad utilizando ultrapoderes y luego presenta el método de Henkin como una idea tardía. (Más adelante, en el capítulo 7, hace una deducción más formal, pero sólo para demostrar los Teoremas de Incompletitud). En las notas al final del capítulo 4, Poizat escribe:

El teorema de la compacidad, en las formas de los teoremas 4.5 y 4.6, se debe a Gödel; de hecho, como se explica al principio de la sección 4.3 [Método de Henkin], el teorema era para Gödel un simple corolario (incluso podríamos decir un corolario inesperado, ¡una observación bastante extraña!) de su "teorema de completitud" de la lógica, en el que mostraba que un sistema finito de reglas de inferencia es suficiente para expresar la noción de consecuencia (véase el capítulo 7). También podría haberse tomado de [Herbrand 1928] o [Gentzen 1934], en los que se demostraron resultados del mismo tipo.

Este desafortunado teorema de la compacidad fue introducido por la puerta de atrás, y podríamos decir que su modestia original todavía lo hace mal en los libros de texto de lógica. En mi opinión, es mucho más esencial y primordial (y, por tanto, también menos sofisticado) que el teorema de completitud de Gödel, que afirma que podemos formalizar la deducción de una determinada manera aritmética; es un error de método deducirlo de este último.

Si lo hacemos así, es por una fidelidad muy ciega a las condiciones históricas que la vieron nacer. El peso de esta tradición es evidente incluso en una obra como [Chang-Keisler 1973], que fue considerada una biblia de la teoría de modelos en los años setenta; comienza con desarrollos sintácticos que no tienen nada que ver con nada de lo que aparece en los capítulos siguientes. Este enfoque -educación de la compacidad a partir de la posibilidad de axiomatizar la noción de deducción-, una vez aplicado al cálculo proposicional, da la prueba más extraña de que se tenga constancia de la compacidad de $2^\omega$ ¡!

Sin duda es más "lógico", pero resulta inconveniente exigir al estudiante que asimile un sistema de deducción formal, en última instancia bastante arbitrario, que sólo podrá justificarse mucho más tarde, cuando podamos demostrar que efectivamente representa la noción de consecuencia semántica. No hay que perder de vista que los formalismos no tienen razón de ser más que en la medida en que son adecuados para representar nociones de sustancia.

Ahí hay dos puntos clave. El primero, que aparece con bastante claridad, es que la Teoría de Modelos podría hacerse en última instancia sin ninguna sintaxis formal ni reglas de deducción. El segundo punto, mucho más sutil, sólo está presente en la observación entre paréntesis "y, por tanto, también menos sofisticado" del segundo párrafo. Parece como si Poizat dijera que el Teorema de la Completitud no se deduce del Teorema de la Compactibilidad. Pero sí se deduce, al menos en cierto sentido abstracto. El teorema de la compacidad implica que existe un sistema de reglas finitas para la deducción que son completas para la consecuencia semántica. Lo único "sofisticado" que falta es que este conjunto de reglas tenga una descripción sencilla. En particular, los Teoremas de Incompletitud no son consecuencias del Teorema de la Compactibilidad.

Answer 2

Sobre la equivalencia de los teoremas de compacidad, completitud, ideal primo sobre ZF: lo que realmente importa aquí es el caso en que el lenguaje $L$ sobre la que la teoría $T$ no está bien ordenada. En caso contrario, la prueba de Henkin da un modelo de $T$ sin utilizar ninguna forma de axioma de elección. En particular, está bien cuando el lenguaje considerado es contable.

Ahora, la compacidad de implicación $\Rightarrow$ La completitud en el caso general es la siguiente (aunque sigue utilizando la completitud para teorías bien ordenadas, que es un teorema de ZF).

Fijar un lenguaje de primer orden $L$ . Sea $T$ sea una teoría sintácticamente consistente. Entonces cualquier $F\subseteq T$ es sintácticamente coherente. Defina $L_F$ el lenguaje cuyos símbolos operacionales y relacionales son los que aparecen en $F$ . Desde $F$ es finito, $L_F$ es finito. Entonces $F$ es una teoría sintácticamente consistente en el lenguaje $L_F$ . Tenemos completitud para los lenguajes contables, así que tenemos un modelo $M_F$ de $F$ tratada como una teoría sobre $L_F$ . El modelo $M_F$ puede ampliarse fácilmente a un modelo $M_F'$ de $F$ tratada como una teoría sobre $L$ (basta con dar a los símbolos no utilizados interpretaciones triviales: relaciones vacías y operaciones constantes). Por compacidad, ahora tenemos un modelo de $T$ .