LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
sav08:compactness_theorem [2012/05/06 00:24]
vkuncak
sav08:compactness_theorem [2012/05/06 00:25]
vkuncak
Line 43: Line 43:
 Inductive step: Assume the claim for $k$: every finite subset $T \subseteq S$ has a $v_1,​\ldots,​v_k$-interpretation $I$ such that $I \models T$, we show that the statement holds for $k+1$. ​ If $v_{k+1}={\it false}$, the inductive statement holds by definition of $v_{k+1}$. ​ Let $v_{k+1}={\it true}$. ​  Then by definition of $v_{k+1}$, there exists a finite set $A \subseteq S$ that has no $v_1,​\ldots,​v_k,​{\it false}$ interpretation. ​ We wish to show that every finite set $B \subseteq T$ has a $v_1,​\ldots,​v_k,​{\it true}$ interpretation such that $I \models B$.  Take any such set $B$.  Consider the set $A \cup B$.  This is a finite set, so by inductive hypothesis, it has a $v_1,​\ldots,​v_k$-interpretation $I$.  Because $I \models A$ which has no $v_1,​\ldots,​v_k,​{\it false}$-interpretation,​ we have $I(p_{k+1})={\it true}$. Therefore, $I$ is a $v_1,​\ldots,​v_k,​{\it true}$-interpretation for $A \cup B$, and therefore for $B$.  This completes the inductive proof. Inductive step: Assume the claim for $k$: every finite subset $T \subseteq S$ has a $v_1,​\ldots,​v_k$-interpretation $I$ such that $I \models T$, we show that the statement holds for $k+1$. ​ If $v_{k+1}={\it false}$, the inductive statement holds by definition of $v_{k+1}$. ​ Let $v_{k+1}={\it true}$. ​  Then by definition of $v_{k+1}$, there exists a finite set $A \subseteq S$ that has no $v_1,​\ldots,​v_k,​{\it false}$ interpretation. ​ We wish to show that every finite set $B \subseteq T$ has a $v_1,​\ldots,​v_k,​{\it true}$ interpretation such that $I \models B$.  Take any such set $B$.  Consider the set $A \cup B$.  This is a finite set, so by inductive hypothesis, it has a $v_1,​\ldots,​v_k$-interpretation $I$.  Because $I \models A$ which has no $v_1,​\ldots,​v_k,​{\it false}$-interpretation,​ we have $I(p_{k+1})={\it true}$. Therefore, $I$ is a $v_1,​\ldots,​v_k,​{\it true}$-interpretation for $A \cup B$, and therefore for $B$.  This completes the inductive proof.
  
-SECOND PART. We finally show that $I^* \models S$.  Let $F \in S$.  Let $FV(F) = \{p_{i_1},​\ldots,​p_{i_k} \}$ and $M = \max(i_1,​\ldots,​i_k)$. Then $FV(F) \subseteq \{p_1,​\ldots,​p_M\}$. ​ The set $\{F\}$ is finite, so, by the Claim, it has a $v_1,​\ldots,​v_M$-interpretation $I$ such that $I \models F$.  Because $I^*$ is also a $v_1,​\ldots,​v_M$-interpretation,​ we have $I^* \models F$.+SECOND PART. We finally show that $I^* \models S$.  Let $F \in S$.  Let $FV(F) = \{p_{i_1},​\ldots,​p_{i_k} \}$ and $M = \max(i_1,​\ldots,​i_k)$. Then $FV(F) \subseteq \{p_1,​\ldots,​p_M\}$. ​ The set $\{F\}$ is finite, so, by the Claim, it has a $v_1,​\ldots,​v_M$-interpretation $I$ such that $I \models F$.  Because $I^*$ is also a $v_1,​\ldots,​v_M$-interpretation, and it agrees on all variables in $F$, we have $I^* \models F$.
  
 **End of Proof.** **End of Proof.**