La prueba del Teorema de Compacidad para la Lógica Proposicional

Question

Tengo un problema de comprensión de la prueba del teorema de compacidad para la lógica proposicional en mi lógica curso.

El teorema de compacidad, declara que no es un modelo para un conjunto infinito $S$ de fórmulas proposicionales, si y sólo si, existe un modelo para cada subconjunto finito de $S$.

El siguiente (bastante largo) croquis de la prueba que nos fue dada en clase: La premisa es que tenemos un modelo para cada subconjunto finito de $S$, así que tenemos que construir a partir de estos modelos, un modelo para el conjunto total $S$.

Primero, notamos que para cualquier (posiblemente infinita), un conjunto de fórmulas de $S_n \subseteq S$ $n$ proposicional variables hay en el max $2^{2^n}$ equivalente fórmulas con $n$ variables, que es finito. Así, por cada finito de equivalencia de la clase $E_n$ $S_n$ no es un modelo de $m_n$, que es también un modelo para el infinito $S_n$. Además, $m_n$ también es un modelo para todos los conjuntos de $S_1 \subseteq S_2 \subseteq \cdots \subseteq S_{n-1}$.

Ahora, de todos los modelos de $m_1, m_2, \ldots$ que se derivan de un modelo de $m$ para el conjunto total $S$. Comenzamos con un modelo vacío $m=\{\}$. Podemos iterar sobre todas las variables proposicionales $p_1, p_2, \ldots$ y asignar un valor de verdad a cada uno de ellos y agregarlos a $m$ como sigue:$p_1 = \textrm{TRUE}$, si hay infinitamente muchos conjuntos de $S_i$, cuyo modelo también asigna a $\textrm{TRUE}$$p_1$. Ahora que eliminar todos los conjuntos de $S_j$, en el que $p_1 = \textrm{FALSE}$. Repita el procedimiento para todos los $p_2, p_3, \ldots~$.

La prueba pasa a la prueba de que el modelo así construido $m$ es de hecho un modelo para $S$.

Lo tengo problemas con la comprensión es ¿cómo sabemos que hay infinidad de modelos que asignar un valor de verdad a una de las variables. Así que, no me parece que esta prueba convincente en absoluto.

Answer 1

El argumento es básicamente correcto, pero podría ser elaboraron un poco. Por comodidad voy a escribir $\mathbf{T}$ $\mathbf{F}$ en lugar de $\text{TRUE}$$\text{FALSE}$. Yo también voy a escribir $m(p_k)=\mathbf{T}$ para indicar que $p_k$ es verdadera en el modelo de $m$.

Deje $S_n$ ser el conjunto de todas las fórmulas en $S$ contiene en la mayoría de las variables proposicionales $p_1,\dots,p_n$. Hay un conjunto finito $E_n\subseteq S_n$ de manera tal que cada fórmula en $S_n$ es equivalente a uno en $E_n$, lo $S_n$ tiene un modelo de $m_n$. Tenga en cuenta que para cualquier $n\in\Bbb Z^+$, cada modelo de $m_k$ $k\ge n$ asigna $p_n$ un valor de verdad.

Deje $N_1=\Bbb Z^+$. Cada una de las $m_n$ $n\in N_1$ asigna $p_1$ un valor de verdad. Deje $T_1=\{n\in N_1:m_n(p_1)=\mathbf{T}\}$. Si $T_1$ es infinito, establezca $m(p_1)=\mathbf{T}$, y deje $N_2=\{k\in T_1:k\ge 2\}$. De lo contrario, establezca $m(p_1)=\mathbf{F}$, y deje $N_2=\{k\in N_1\setminus T_1:k\ge 2\}$. Tenga en cuenta que en ambos casos $N_2$ es infinito, $m_k(p_1)=m(p_1)$ todos los $k\in N_2$, e $m_k(p_2)$ se define para cada una de las $k\in N_2$.

Ahora repita el proceso. Deje $T_2=\{n\in N_2:m_n(p_2)=\mathbf{T}\}$. Si $T_2$ es infinito, establezca $m(p_2)=\mathbf{T}$, y deje $N_3=\{k\in T_2:k\ge 3\}$. De lo contrario, establezca $m(p_2)=\mathbf{F}$, y deje $N_3=\{k\in N_2\setminus T_2:k\ge 3\}$. En ambos casos $N_3$ es infinito, $m_k(p_2)=m(p_2)$ por cada $k\in N_3$, e $m_k(p_3)$ se define para cada una de las $k\in N_3$.

Para el gran paso, dado un infinito $N_n\subseteq\Bbb Z^+$ tal que $m_k(p_n)$ se define para cada una de las $k\in N_n$, vamos a $T_n=\{k\in N_n:m_k(p_n)=\mathbf{T}\}$. Si $T_n$ es infinito, establezca $m(p_n)=\mathbf{T}$, y vamos a $$N_{n+1}=\{k\in T_n:k\ge n+1\}\;.$$ Otherwise, set $m(p_n)=\mathbf{F}$, and let $$N_{n+1}=\{k\in N_n\setminus T_n:k\ge n+1\}\;.$$ As before, in both cases $N_{n+1}$ is by construction infinite, $m_k(p_n)=m(p_n)$ for each $k\N_{n+1}$, and $m_k(p_{n+1})$ is defined for each $k\N_{n+1}$, por lo que la recursivo de construcción puede proceder.

Esta construcción se define un modelo de $m$ que asigna un valor de verdad a cada una de las $p_k$. Tomar cualquier fórmula $\varphi$$S$; pertenece a $S_n$. Elija cualquiera de los $k\in N_{n+1}$; a continuación, $m_k$ es un modelo para $S_n$ y, por tanto, para $\varphi$. Por otra parte, la construcción se asegura de que $m_k(p_i)=m(p_i)$$i=1,\dots,n$, lo $m$ es también un modelo para $S_n$ y, por tanto, para $\varphi$.

Answer 2

Su construcción es un poco off o no la entiendo. No reclamo se construye un modelo de S' en la configuración siguiente: Vamos a $S$ ser cualquier conjunto arbitrario de fórmulas proposicionales, vamos a $p$ ser un nuevo símbolo no aparece en $S$, y deje $S' = \{p\} \cup \{\lnot p \land \phi | \phi \in S\}$. Creo que si usted aplica su construcción, usted podría conseguir a $S_1 = \{p\}$, $m_1$ establece el $p$ a true, el resto de $S'$ es rápidamente desechados (o "eliminado"), cada variable puede, a continuación, de forma segura se establece en true, y $S'$ está satisfecho por el ajuste del todo a la verdad. Algo está podrido aquí.

Hay un montón de pruebas en línea que usted puede intentar el examen. Esta prueba es más bien la jerga libre.

Answer 3

No es una manera más simple de demostrar el teorema de compacidad uso de los siguientes módulos tollens la prueba?

Una dirección es trivial ya que si $\Sigma$ es válido, entonces, ciertamente, $\Sigma_0 \subseteq \Sigma$ es válido para algunos finito $\Sigma_0$.

En el otro sentido, decir $\Sigma$ es un conjunto de oraciones que no es válido. Entonces, por el teorema de completitud, existe un subconjunto finito de ese conjunto que es incompatible $-$ es decir, $\exists \ \Sigma_0 \subseteq \Sigma$ tal que $\Sigma_0$ es finito y es una proposición de la forma $P \ \& \sim P $. Por lo $\Sigma_0$ no debe ser válido.

O me estoy perdiendo algo aquí?