Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:compactness_theorem [2012/05/06 00:23] vkuncak |
sav08:compactness_theorem [2012/05/06 00:23] vkuncak |
||
|---|---|---|---|
| Line 34: | Line 34: | ||
| \] | \] | ||
| We next show by induction the following. | We next show by induction the following. | ||
| + | |||
| + | FIRST PART. | ||
| Claim: For every non-negative integer $k$, every finite subset $T \subseteq S$ has a $v_1,\ldots,v_k$-interpretation $I$ such that $I \models T$. | Claim: For every non-negative integer $k$, every finite subset $T \subseteq S$ has a $v_1,\ldots,v_k$-interpretation $I$ such that $I \models T$. | ||
| Line 41: | 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. | ||
| - | 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, we have $I^* \models F$. |
| **End of Proof.** | **End of Proof.** | ||