Differences

This shows you the differences between two versions of the page.

--- sav08:compactness_theorem [2012/05/06 00:02]
vkuncak
+++ sav08:compactness_theorem [2012/05/06 00:23]
vkuncak
@@ Line 34: / Line 34: @@
 \]
 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$.
@@ 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.
-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.**
+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.