Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
sav08:compactness_theorem [2012/05/06 00:23] 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.** | ||
| Line 51: | Line 51: | ||
| m = \max(k, \max \{i \mid p_i \in T \}) | m = \max(k, \max \{i \mid p_i \in T \}) | ||
| \] | \] | ||
| - | Then consider interpretation that assigns to true all $p_j$ for $j \le m$ and sets the rest to false. Such interpretation makes $D$ true, so if it is in the set $T$, then interpretation makes it true. Moreover, all other formulas in $T$ are propositional variables set to true, so the interpretation makes $T$ true. Thus, we see that the inductively proved statement holds even in this case. What the infinite formula $D$ breaks is the second argument, that from arbitrarily long interpretations we can derive an interpretation for infinitely many variables. Indeed, this part of the proof explicitly refers to a finite number of variables in the formula. | + | Then consider interpretation that assigns to true all $p_j$ for $j \le m$ and sets the rest to false. Such interpretation makes $D$ true, so if it is in the set $T$, then interpretation makes it true. Moreover, all other formulas in $T$ are propositional variables set to true, so the interpretation makes $T$ true. Thus, we see that the inductively proved statement holds even in this case. What the infinite formula $D$ breaks is the second part, which, from the existence of interpretations that agree on an arbitrarily long finite prefix we can derive an interpretation for infinitely many variables. Indeed, this part of the proof explicitly refers to a finite number of variables in the formula. |