Brecha en el lema: la teoría satisfacible implica una teoría libre de contradicciones

Question

Brecha en el lema: la teoría satisfacible implica una teoría libre de contradicciones

lógica
Matemáticas
teoría de modelos

tema

Tengo una pregunta sobre una brecha en el lema. Primero, cómo se definieron las cosas en el curso que estoy tomando (lamento hacer que los lectores revisen esta lista de definiciones, pero no sé cómo acortarla):

Dejar $\sigma$ ser una firma y $T$ a $\sigma$ -teoría. Hemos definido esta teoría como satisfactoria si existe un modelo $M$ tal que para cada oración de la teoría $M$ satisface las oraciones. Hemos definido que las oraciones son demostrables si pertenecen al conjunto más pequeño que satisface una lista de propiedades y universales si para cada modelo $M$ están satisfechos. Más adelante, hemos definido que la teoría está libre de contradicciones si no hay oraciones $\alpha_1,\ldots,\alpha_n \in T$ tal que $\neg ( \alpha_1 \wedge \ldots \wedge \alpha_n)$ es comprobable

Luego probamos que todo enunciado demostrable es universal y luego se mencionó (sin una demostración completa) que por la proposición anterior toda teoría satisfacible está libre de contradicciones. Mi pregunta es: ¿Cómo puede usarse la proposición de que toda oración demostrable es universal para probar eso?

Arturo Magidín

Si

T

$T$ no está libre de contradicciones, entonces tienes oraciones

α_{1}, \dots, α_{n} \in T

$\alpha_1,\ldots,\alpha_n\in T$ tal que

\neg (α_{1} \land \dots \land α_{n})

$\neg(\alpha_1\land\cdots\land\alpha_n)$ es comprobable Pero desde

T

$T$ es satisfacible, tiene un modelo

M

$M$ ; desde

M

$M$ es un modelo,

α_{1}, \dots, α_{n}

$\alpha_1,\ldots,\alpha_n$ están satisfechos en

M

$M$ . Desde

\neg (α_{1} \land \dots \land α_{n})

$\neg(\alpha_1\land\cdots\land\alpha_n)$ es demostrable, es universal, por lo tanto se satisface en

M

$M$ . Entonces

M

$M$ satisface cada uno de

α_{i}

$\alpha_i$ , y satisface al menos en

\neg α_{j}

$\neg\alpha_j$ , lo cual es imposible (

M

$M$ es un modelo).

Respuestas (2)

Brecha en el lema: la teoría satisfacible implica una teoría libre de contradicciones

Si $T$ no está libre de contradicciones, entonces tienes oraciones $\alpha_1,\ldots,\alpha_n\in T$ tal que $\neg(\alpha_1\land\cdots\land\alpha_n)$ es comprobable Pero desde $T$ es satisfacible, tiene un modelo $M$ ; desde $M$ es un modelo, $\alpha_1,\ldots,\alpha_n$ están satisfechos en $M$ . Desde $\neg(\alpha_1\land\cdots\land\alpha_n)$ es demostrable, es universal, por lo tanto se satisface en $M$ . Entonces $M$ satisface cada uno de $\alpha_i$ , y satisface al menos en $\neg\alpha_j$ , lo cual es imposible ( $M$ es un modelo).

yuval filmus · Answer 1

Suponer $T$ es una teoría satisfactoria. Elige algún modelo $M$ para ello. Si $C$ es una contradicción demostrable en $T$ , entonces por su propuesta $C$ debe sostener para $M$ . Sin embargo, $C$ no es lógicamente válido, y en particular la definición recursiva de validez muestra que no puede sostenerse. Entonces $C$ no debe haber sido demostrable en $T$ después de todo.

En otras palabras, $M$ es una prueba de que $T$ es una teoría "razonable". Es testigo de la consistencia de $T$ -¡Ciertamente, es un ejemplo de ello! - y así demuestra que $T$ no puede contener contradicciones "inherentes".

carl mummert · Answer 2

Otra forma de decir lo mismo: dejar $T$ sé tu teoría y deja $M$ ser un modelo de $T$ . Dejar $S$ sea el conjunto de todas las oraciones que son verdaderas en $M$ (simbólicamente, $S = \{ \phi : M \vDash \phi\}$ ). Entonces:

$S$ extiende $T$ , porque $M \vDash T$ .
$S$ es cerrado bajo demostrabilidad: si $\psi_1, \ldots, \psi_k \in S$ y $\psi_1, \ldots, \psi_k \vdash \phi$ entonces $\phi \in S$ . Esto se sigue de la solidez del sistema de prueba.
$S$ es consistente: para ninguna oración $\phi$ hace $S$ contener $\phi \land \lnot \phi$ . Esto se desprende de la definición de la $\vDash$ relación.

Estas tres viñetas juntas implican $T$ es consistente.

Como bono, $S$ también es completo: para cualquier $\phi$ , cualquiera $\phi \in S$ o $\lnot \phi \in S$ , de nuevo debido a la definición de la $\vDash$ relación. Entonces, la existencia de un modelo es, en cierto sentido, una prueba muy fuerte de que la teoría es consistente: no solo prueba la consistencia de $T$ , también proporciona una finalización consistente de $T$ .

Brecha en el lema: la teoría satisfacible implica una teoría libre de contradicciones

tema

Arturo Magidín

Respuestas (2)

yuval filmus

carl mummert

¿Es la teoría de los lenguajes formales regulares finitamente axiomatizable?

Encontrar un universo adecuado para una estructura dada

Paradoja aparente de tipo principal 1

¿Cómo se especifica la semántica completa de SOL y HOL?

Un número finito de modelos contables implica decidibilidad

Cada modelo de ZFC tiene un elemento que es un modelo de ZFC

Modelos de aritmética sucesora

Un modelo que tiene solo un elemento indefinible sobre un lenguaje con solo un número finito de símbolos

¿Por qué los modelos de ZF que no son ωω\omega-modelos tienen fórmulas no estándar cuya longitud es "números naturales infinitamente grandes"?

No axiomatizabilidad y ultraproductos