Differences
This shows you the differences between two versions of the page.
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.** |