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:25] vkuncak |
sav08:compactness_theorem [2015/04/21 17:30] (current) |
||
|---|---|---|---|
| Line 28: | Line 28: | ||
| We will define interpretation $I^*(p_k) = v_k$ where the sequence of values $v_1,v_2,\ldots$ is given as follows: | We will define interpretation $I^*(p_k) = v_k$ where the sequence of values $v_1,v_2,\ldots$ is given as follows: | ||
| - | \[ | + | \begin{equation*} |
| v_{k+1} = \left\{\begin{array}{l} | v_{k+1} = \left\{\begin{array}{l} | ||
| {\it false}, \mbox{ if for every finite } T \subseteq S, \mbox{ there exists a } v_1,\ldots,v_k,{\it false}-\mbox{interpretation } I \mbox{ such that } I \models T \\ | {\it false}, \mbox{ if for every finite } T \subseteq S, \mbox{ there exists a } v_1,\ldots,v_k,{\it false}-\mbox{interpretation } I \mbox{ such that } I \models T \\ | ||
| {\it true}, \mbox{otherwise} | {\it true}, \mbox{otherwise} | ||
| - | \] | + | \end{equation*} |
| We next show by induction the following. | We next show by induction the following. | ||
| Line 48: | Line 48: | ||
| How does this proof break if we allow infinite disjunctions? Consider the above example $S = \{ D, p_1, p_2, p_3, \ldots \}$ where $D = \bigvee\limits_{i=1}^{\infty} \lnot p_i$. The inductively proved claim still holds, and the sequence defined must be $true, true, true, \ldots$. Here is why the claim holds for every $k$. Let $k$ be arbitrary and $T \subseteq S$ be finite. Define | How does this proof break if we allow infinite disjunctions? Consider the above example $S = \{ D, p_1, p_2, p_3, \ldots \}$ where $D = \bigvee\limits_{i=1}^{\infty} \lnot p_i$. The inductively proved claim still holds, and the sequence defined must be $true, true, true, \ldots$. Here is why the claim holds for every $k$. Let $k$ be arbitrary and $T \subseteq S$ be finite. Define | ||
| - | \[ | + | \begin{equation*} |
| m = \max(k, \max \{i \mid p_i \in T \}) | m = \max(k, \max \{i \mid p_i \in T \}) | ||
| - | \] | + | \end{equation*} |
| 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. | 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. | ||