20 votos

Exhaustividad frente a compacidad en lógica

Un enfoque estándar para demostrar la compacidad de la lógica de primer orden es demostrar la completitud, de la que la compacidad es un corolario fácil. Me han dicho que este enfoque está en desuso hoy en día, ya que la compacidad se considera el resultado "más profundo".

¿Podría alguien explicar esta intuición? En particular, ¿existen sistemas lógicos que sean compactos pero no completos?

EDIT: Andreas ha planteado una cuestión excelente: el teorema de la exhaustividad es en realidad una combinación de dos resultados muy importantes pero casi sin relación entre sí. En primer lugar, el teorema de la compacidad. Segundo, la enumerabilidad recursiva de las valideces lógicas. Nótese que ninguno de estos resultados depende de los detalles del sistema sintáctico o axiomático.

¿Qué relación existe entre estos dos aspectos de la exhaustividad? ¿Existen sistemas lógicos que tengan una de estas propiedades pero no la otra?

9voto

Andreas Blass Puntos 45666

Debido a mi inclinación natural hacia la semántica más que hacia la sintaxis, tiendo a considerar que el teorema de completitud (para la lógica de primer orden) es esencialmente la conjunción de dos hechos bastante diferentes. Uno es el teorema de la compacidad. El otro es la enumerabilidad recursiva del conjunto de oraciones válidas (digamos en cualquier vocabulario finito). Ambos hechos se deducen a menudo del teorema de completitud, aunque también pueden demostrarse por otros métodos (me gusta una versión del teorema de Herbrand que no menciona ningún axioma o regla). Pero también existe una especie de inversa, si uno está dispuesto a aceptar una noción de deducción poco ortodoxa (pero, en mi opinión, bastante razonable). A saber, fijar un algoritmo $A$ enumerar las sentencias válidas, y definir una "deducción" de una conclusión $\phi$ de un conjunto $H$ de hipótesis sea una conjunción finita $\eta$ de los miembros de $H$ junto con un cálculo que demuestre que $\eta\to\phi$ se enumera mediante $A$ . La completitud de este sistema "deductivo" es una consecuencia inmediata del teorema de la compacidad más el hecho de que $A$ enumera las sentencias válidas.

6voto

Eduard Wirch Puntos 199

He aquí una cita interesante del "Curso de teoría de modelos" de Bruno Poizat:

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 que 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 sigue haciéndolo 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 lo 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$ ¡!

Es sin duda más "lógico", pero es 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.

Véase también antigua respuesta mía donde aparece la misma cita.

3voto

Amir Puntos 3237

Iba a decir que las respuestas dadas hasta ahora son todas erróneas y engañosas, pero gracias a Dios recordé que no soy matemático :-)

Existen principalmente dos enfoques del concepto de "lógica".

  1. El enfoque clásico (o matemático) de la lógica. A grandes rasgos, una lógica consta de dos clases: un conjunto de fórmulas y una clase de modelos, junto con una relación de satisfacibilidad que dice qué fórmulas son verdaderas en qué modelos. A continuación, podemos desarrollar un sistema de pruebas (o varios sistemas de pruebas) para la lógica, que nos ayude, de forma sistemática y coherente, a deducir la satisfacción de las fórmulas. Las propiedades deseables de estos sistemas de demostración son la solidez (lo que hemos deducido es cierto) y la completitud (podemos deducir lo que es cierto). También existe la compacidad (si algo se sigue de una teoría, entonces se sigue de un subconjunto finito de la teoría) que se refiere a la propia lógica (aquí: relación de satisfacibilidad). Así es como se enseña lógica a los matemáticos.

  2. Enfoque moderno (o informático) de la lógica. La lógica es un tipo de sistema formal (sistema deductivo). Para ayudar a demostrar hechos sobre dicho sistema, podemos introducir el concepto de "modelos" (o varios conceptos de modelos) para la lógica. Las propiedades deseables de tales clases de modelos son que el sistema deductivo sobre ellos sea sólido y completo (es decir, para un sistema dado, desarrollamos el concepto apropiado de modelos, de modo que el sistema de prueba sea sólido y completo; si añadimos/eliminamos algunos axiomas/reglas al sistema, entonces tenemos que restringir/ampliar nuestra clase de modelos; esto se ve más fácilmente en las lógicas temporales; por ejemplo, LTL es sólido y completo en los sistemas lógicos temporales. lineal modelos). También hay compacidad (si algo sigue una teoría, entonces sigue de un subconjunto finito de la teoría) que se refiere a la lógica en sí (aquí: sistema de pruebas; si una lógica sólo permite pruebas finitas, entonces es obviamente compacta). Simplemente, en este enfoque, el sistema es aquí fundamental. Así es como se enseña lógica a los informáticos.

Por supuesto, en presencia de solidez y completitud, la compacidad clásica y la compacidad moderna coinciden.

Volviendo a tu pregunta, estoy de acuerdo con otras respuestas que afirman que la completitud y la compacidad son conceptos muy diferentes, por lo que ninguno de los dos es "más profundo". Sin embargo, no creo que la clasificación de lo que pertenece a los modelos y lo que pertenece a las pruebas sea tan obvia; todo depende de cómo se conciba la lógica.

1voto

Justin Dearing Puntos 695

Creo que todo lo importante que se puede decir sobre el diferencias entre los teoremas de compacidad y completitud y sus desde el punto de vista técnico. (También me gusta la respuesta detallada y esclarecedora de Joel David Hamkins (en En la teoría de modelos, ¿la compacidad implica fácilmente la exhaustividad? )). En otra parte, una de las diferencias más importantes entre estos teoremas no es técnica y, de hecho, algunas respuestas anteriores contienen pistas en este sentido. De hecho, el Teorema de Completitud tiene una tiene un evidente sabor metamatemático (o incluso filosófico), a diferencia del teorema de Teorema de la compacidad. En realidad, se trata de la relación entre dos nociones matemáticas más importantes, es decir, las de prueba y verdad.

Y aquí me gustaría discutir con aquellos (Carl Mummert y Stefan Geschke) que afirman que a veces el Teorema de Completitud se utiliza en matemáticas cotidianas. En realidad, tal como yo lo veo, es acerca de todos los días matemáticas, pero no pertenece a las matemáticas cotidianas.

En realidad, contrariamente a lo que dice Carl Mummert, dudo que, en matemáticas cotidianas, nadie en ningún momento utilice el teorema de completitud en forma explícita o implícita. Obviamente, se puede trabajar con éxito trabajar en cualquier campo de las matemáticas (que no estén íntimamente con la lógica) sin ningún conocimiento de lógica matemática. (Es evidente que sentido de la lógica, pero esto es una cuestión completamente diferente. diferente). En otras palabras (a diferencia de Carl Mummert), no puedo dificultades en un mundo alternativo en el que los matemáticos matemáticos tengan que distinguir entre "verdadero en todos los grupos los axiomas de un grupo". La razón es sencilla. No creo que nadie demuestre "que una identidad de grupo es derivable de los axiomas de un grupo trabajando semánticamente y mostrando que la identidad se mantiene en todos los grupos". Aunque no soy teórico de grupos, creo que ningún teórico de grupos está interesado en las afirmaciones demostrables a partir de los axiomas de la teoría de grupos solo . (Por otra parte, por supuesto, la enunciados elementales más importantes necesarios para empezar la teoría de grupos suelen derivarse directamente de los axiomas). La mayoría de los matemáticos trabajan en la teoría intuitiva de conjuntos y utilizan libremente las diferentes posibilidades que ofrece esta rica teoría (independientemente del hecho de que de que sea consciente de la existencia de ZFC). (En realidad, la noción misma de grupo se define como un modelo, es decir, generalmente en términos de conjuntos en lugar de una teoría de primer orden. Y, por supuesto, este definición es muy práctica, ya que, de lo contrario, cada curso sobre grupos tendría que ir precedido de una introducción a la lógica). Creo que la teoría pura de primer orden de los grupos sólo tiene un significado teórico o didáctico teórica o didáctica por ser un buen ejemplo de teoría de primer orden. de primer orden.

Tampoco estoy de acuerdo con Stefan Geschke en que "el teorema de la exhaustividad explica por qué podemos hacer matemáticas como las hacemos". Sólo al revés. Evidentemente, la metamatemática es el estudio de las verdaderas matemáticas reales por medios matemáticos exactos. Por lo tanto, sus nociones pretenden imitar las de la matemática informal cotidiana tan fielmente lo más fielmente posible. Así pues, un resultado metamatemático no puede explicar ni justificar nada. Lo que sí puede hacer es describir en términos exactos y describir en términos exactos y aclarar la forma en que se hacen normalmente las matemáticas (y, por supuesto, extraer consecuencias). consecuencias acerca de matemáticas cotidianas a partir de los resultados descripción). Pero sus resultados no afectan a la forma en que las matemáticas se matemáticas. Obviamente, haríamos matemáticas cotidianas exactamente de la siguiente manera exactamente igual si no existiera el Teorema de la Completitud. Igual que hacen matemáticos que nunca han oído hablar de este teorema. Y de hecho hacemos aritmética exactamente de la misma manera que los matemáticos antes de Gödel (que bien podían pensar que la verdadera aritmética era axiomatizable recursivamente).

0voto

Michael Hardy Puntos 4554

La compacidad es un teorema "semántico", cuyo enunciado no implica conceptos "sintácticos" como pruebas o demostrabilidad. Por tanto, parece que no se necesitan estos últimos conceptos para demostrar la compacidad (y, por supuesto, no es así).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X