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:16] vkuncak |
sav08:compactness_theorem [2012/05/06 00:23] vkuncak |
||
---|---|---|---|
Line 49: | Line 49: | ||
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. So, the infinite nature of $D$ breaks the argument that goes from arbitrarily long interpretations for each set to one interpretation for all 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 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. |