Algunas versiones diferentes de la completitud de un sistema formal, de una lógica y de una teoría

Question

He visto que la gente habla de los teoremas completos de Gödel y de los teoremas incompletos de Gödel en math.SE. Tengo curiosidad por saber de qué tratan realmente, así que primero intento entender el significado de la completitud.

Mis preguntas son:

1. En las siguientes versiones diferentes de la exhaustividad, ¿algunas de ellas son realmente el mismo concepto?

2. Cuando se habla de exhaustividad, algunos se refieren a integridad de un sistema formal Algunos usos la exhaustividad de una teoría y algunos usos la exhaustividad de una lógica . ¿Son equivalentes?

   Sé que todo sistema formal tiene una teoría como componente, pero no estoy seguro de que todo sistema formal tenga una lógica como componente.

   Obsérvese que un sistema formal consta de un lenguaje, un conjunto de axiomas, un conjunto de reglas de inferencia y un conjunto de teoremas (que se derivan de los axiomas y las reglas de inferencia), denominado teoría.

3. Hay algunas cuestiones específicas sobre cada versión de la exhaustividad a continuación.

Diferentes versiones de la exhaustividad:

1. Desde Wikipedia

   A sistema formal S es sintácticamente completo o completar deductivamente o máximo de completo o simplemente completo si y sólo si para cada fórmula del lenguaje del sistema o ¬ es un teorema de S. Esto también se llama Completitud de la negación .

   En otro sentido, un sistema formal es sintácticamente completo si y sólo si no se puede añadir ningún axioma indemostrable puede ser añadido como axioma sin introducir una inconsistencia.

   ¿"Cualquiera o ¬ es un teorema de S" permite que ambos y ¬ sean teoremas de S?

   ¿Significa "para cada fórmula del lenguaje del sistema..." que no hay ninguna fórmula en el lenguaje del sistema formal tal que ni ¬ es un teorema de S?

2. Desde Wikipedia :

   a teoría es completa si es un conjunto coherente máximo de es decir, si es consistente y ninguna de sus extensiones propias es consistente. extensiones propias es consistente.

   ¿Se trata de un concepto de exhaustividad diferente al de la primera parte? Creo que son el mismo, porque la parte 2 parece igual que "ningún axioma indemostrable puede ser añadido como axioma sin introducir una inconsistencia" en la parte 1.

3. Desde Wikipedia

   A sistema formal S es semánticamente completo o simplemente completo si toda tautología de S es un teorema de S.

   Desde Wikipedia

   a lógica completa que afirma que para cada teoría que puede formularse en la lógica, todos los enunciados semánticamente válidos son teoremas demostrables (para un sentido apropiado de "semánticamente válido"). El teorema de exhaustividad de Gödel se refiere a este tipo de exhaustividad.

   Me pregunto si los "enunciados semánticamente válidos" y las "tautologías" son el mismo concepto?

   ¿Son los dos anteriores "completos" el mismo concepto?

4. Desde Wikipedia :

   A sistema formal S es fuertemente completo o completa en el sentido fuerte si y sólo si para cada conjunto de premisas , cualquier fórmula que se sigue semánticamente de es derivable de .

   Un sistema formal tiene su propio conjunto fijo de axiomas. Así que me pregunto si "todo conjunto de premisas" significa todo subconjunto del conjunto de axiomas del sistema formal?

Gracias y saludos.

Answer 1

Como se desprende de las citas, se trata efectivamente de dos nociones diferentes.

1 y 2 van juntos. A teoría formal $T$ es completa en cuanto a la negación si para cualquier frase de $T$ El lenguaje de la gente, ya sea $T$ prueba $\varphi$ o $T$ prueba $\neg\varphi$ (en símbolos, ya sea $T \vdash \varphi$ entonces $T \vdash \neg\varphi$ ).

La 3 y la 4 van juntas. A sistema lógico (por ejemplo, para la lógica cuantitativa) es completa si siempre que las premisas $\Gamma$ conllevan semánticamente la conclusión $\varphi$ hay una deducción formal en el sistema de $\varphi$ de las premisas en $\Gamma$ . (En símbolos, si siempre que $\Gamma \vDash \varphi$ entonces $\Gamma \vdash \varphi$ .)

Así que son ideas muy diferentes: una tiene que ver con cómo se relaciona una lógica deductiva con la noción relevante de vinculación semántica; la otra es una noción puramente sintáctica. Se pueden tener teorías de negación-incompleta con lógicas completas, y teorías de negación-completa con lógicas incompletas (así como las otras dos combinaciones).

Es famoso que Gödel demostrara que, esencialmente, la versión axiomática de Hilbert/Ackermann de la lógica cuantificadora es completa: toda consecuencia cuantificadora semánticamente válida (suponiendo una semántica clásica) puede derivarse formalmente en ese sistema axiomático. Por lo tanto, Gödel integridad teorema (sobre un sistema de lógica).

Es famoso que Gödel demostró que esencialmente una versión reducida de Principia La teoría formal de la empresa es no Completa en cuanto a la negación: hay sentencias que no pueden ser decididas en un sentido o en otro por los axiomas. Y la prueba se generaliza a cualquier teoría formal consistente que pueda "hacer suficiente aritmética" (y que satisfaga otra condición que no importa aquí). De ahí que Gödel incompleto teorema (sobre las teorías que contienen suficiente aritmética).

Dos resultados gödelianos diferentes sobre nociones diferentes (por tanto, ¡no hay tensión entre ellos!).