Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
sav08:compactness_theorem [2012/05/06 00:02] vkuncak |
sav08:compactness_theorem [2012/05/06 00:23] vkuncak |
||
---|---|---|---|
Line 45: | Line 45: | ||
**End of Proof.** | **End of Proof.** | ||
+ | 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 | ||
+ | \[ | ||
+ | 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. | ||