3 votos

Deducción del teorema de compacidad a partir del teorema de completitud (en lógica de primer orden)

Dado que $\Sigma\vdash\phi \Leftrightarrow \Sigma\vDash\phi$ Quiero probar: $\Sigma \text{ satisfiable} \Leftrightarrow \text{ every finite subset of } \Sigma \text{ is satisfiable}$ .

Voy a publicar mi idea a continuación, pero no puedo terminar el $\Leftarrow$ dirección. Necesitaría que el conjunto que llamaré $\Delta$ es finito. ¿Puede alguien indicarme lo que me falta, por favor? Muchas gracias.

Prueba: El $\Rightarrow$ se mantiene porque si $\Sigma$ es satisfacible tiene un modelo, que a su vez es un modelo de cada subconjunto (especialmente de cada subconjunto finito) de $\Sigma$ .

$\Leftarrow$ : Prueba por contradicción. Si $\Sigma$ no es satisfacible, entonces no es consistente. Es decir $\Sigma \vdash \bot$ . Esto significa que hay un subconjunto $\Delta$ de $\Sigma$ de la cual $\bot$ es derivable. La corrección da entonces $\Delta \vDash\bot$ es decir, para cada modelo $\mathscr{A}$ uno tiene que $\mathscr{A}\vDash\Delta$ da $\mathscr{A}\vDash\bot$ . Pero la última afirmación es válida para ningún modelo, por lo que ya tenemos $\mathscr{A}\not\vDash\Delta$ por cada $\mathscr{A}$ , lo que significa que $\Delta$ no tiene ningún modelo. Si supiera que $\Delta$ fuera finito, entonces tendría una contradicción.

5voto

YoTengoUnLCD Puntos 4020

Sugerencia: llame a $n$ la longitud de una prueba de $\bot$ de $\Sigma$ . Entonces, como máximo $n$ fórmulas de $\Sigma$ aparecen en la prueba. Set $\Delta=\{\gamma\in\Sigma: \text{$\gamma$ appears in the given proof of $\bot$ from $\Sigma$}\}$ . Entonces $\Delta$ es finito y $\Delta\vdash\bot$ .

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