Compactness of the Propositional Calculus
Here is the theorem and its proof from Mathematical and Philosophical Logic from Harrie de Swart (p.35).
Let $\Gamma$ be a (possibly infinite) set of formulas such that every finite subset of $\Gamma$ has a model[1]. Then $\Gamma$ has a model.
Proof:
Let $\Gamma$ be a (possibly infinite) set of formulas such that every finite subset of $\Gamma$ has a model. We will define an interpretation $i$ of the atomic propositional formulas $P_1, P_2, P_3, \dots$ such that for every natural number $n$, $\phi(n)$, where $\phi(n)$ := "every finite subset of $\Gamma$ has a model in which $P_1, P_2, \dots, P_n$ take the values $i(P_1), i(P_2), \dots, i(P_n)$". Once having shown this, it follows that $i(A) = 1$ for every formula $A$ in $\Gamma$. For given a formula $A$ in $\Gamma$, take $n$ so large that all atomic formulas occurring in $A$ are among $P_1, \dots, P_n$. Since $\{A\}$ is a finite subset of $\Gamma$ and because of $\phi(n)$, $A$ has a model in which $P_1, \dots, P_n$ take the values $i(P_1), \dots, i(P_n)$. So, $i(A) = 1$.
Let $i(P_1) = 0$ and suppose $\phi(1)$ does not hold. That is, there is a finite subset $\Gamma'$ of $\Gamma$ which has no model in which $P_1$ takes the value $i(P_1) = 0$. Then we define $i(P_1) = 1$[2] and show that $\phi(1)$, i.e., every finite subset of $\Gamma$ has a model in which $P_1$ takes the value $i(P_1) = 1$.[3] For let $\Delta$ be a finite subset of $\Gamma$. Then $\Delta \cup \Gamma'$ is a finite subset of $\Gamma$ and hence has a model $i$. Since $i$ is a model of $\Gamma'$, $i(P_1) = 1$.
Suppose we have defined $i(P_1), \dots, i(P_n)$ such that $\phi(n)$. Then we can extend the definition of $i$ to $P_{n+1}$ such that $\phi(n + 1)$. For suppose that $\phi(n + 1)$ does not hold if $i(P_{n+1}) = 0$. That is, there is a finite subset $\Gamma'$ of $\Gamma$ which has no model in which $P_1, \dots, P_n, P_{n+1}$ take the values $i(P_1), \dots, i(P_n), 0$. Then we define $i(P_{n+1}) = 1$ and show that $\phi(n + 1)$, i.e., every finite subset of $\Gamma$ has a model in which $P_1, \dots, P_n, P_{n+1}$ take the values $i(P_1), \dots, i(P_n), 1$. For let $\Delta$ be a finite subset of $\Gamma$. Then $\Delta \cup \Gamma'$ is a finite subset of $\Gamma$ and hence, by the induction hypothesis, $\Delta \cup \Gamma'$ has a model in which $P_1, \dots, P_n$ take the values $i(P_1), \dots, i(P_n)$. Since $i$ is a model of $\Gamma'$, $i(P_{n+1}) = 1$.
-
I understand the we have a common model for every subset Right? An interpretation corresponds to one line in the (possibly infinite) truth table of the atomic variables $P_1, \dots , P_n$ ... ↩︎
-
I don't understand what is this new remastered definition. If $i (P_1) = 0$, that is, the true value of $P_1$ is 'False', how can I change this? And if we change it from 'False' to 'True', we can destroy the model of an other formula e g. $A = \lnot P_1$. ↩︎
-
Note. Maybe I am beginning to understand. "If $i (P_1) = 0$, and if $\phi(1)$ does not hold" means that when the Truth Value 0 is assigned to $i(P_1)$,and the set $\Gamma$ has no model. That is, necessarily almost a part of it, that is, a subset $\Gamma'$ of formulas that hold the Truth Value 0 because of as a consequence of the value of $i(P_1)$. So for a good model, we decide to attribute the value 1 to $i(P_1)$.
I was expecting something as this. Say we have only $P_1$ and $P_2$ and formulas that are true when $P_1$ is false and $P_2$ is true. One subset is $\Gamma_1 = \{ P_1 \lor P_2, P_2 \lor P_1\}$, another is $\Gamma_2 = \{P_1 \to P_2, \lnot P_2 \to P_1\}$, another is $\Gamma_3 = \{\lnot P_1\}$. If $\Gamma$ contains a formula that is false under our interpretation, such as $P_1$, there is nothing to do, $\Gamma$ has no model, because if $P_1$ turns to be true, then $\Gamma_3$ has no model. In other words $\Gamma$ cannot have a model if it contains two contradictory formulas. ↩︎
2 answers
I think perhaps a visualization of this proof will be most useful. This is because the general theorem here can be understood as a straightforward consequence of Weak Kőnig's lemma: the lemma that every infinite binary tree has an infinite path.
In proving completeness, we'll be working with a subtree of the complete infinite binary tree of assignments of truth values to an initial segment of the propositions $P_1,P_2,P_3,…$. I illustrate this complete binary tree (of which the sets of statements consistent with $\Gamma$ is a subtree) below:
(Sorry, it gets very wide at the fifth level.)
The precise details are a bit tricky. Following the proof in the OP, what we can do is "prune" our binary tree and keep only those sets of propositions that are consistent with every finite subset of $\Gamma$. This tree can be shown to be infinite by a straightforward inductive argument.2 And then an infinite path in this tree corresponds to a model (a full assignment of truth-values to $P_1,P_2,…$) that is consistent with every finite subset of $\Gamma$, hence is a model of $\Gamma$ (it models all propositions of $\Gamma$, as de Swart's proof says).
So this is how I would visualize the problem. I feel that if it's intuited this way you don't need to worry about the details of conflicting models of $\Gamma$. Also, instead of imagining infinite truth-tables this approach allows you simply to imagine a "path" of ever-larger finite truth-tables that together constitute a model of $\Gamma$. I hope this helps with the difficulties you described regarding truth-tables, inconsistent assignments of truth-values to propositions, etc.
I would also say that I think there is a much simpler way of doing it. Take the subtree of our complete infinite binary tree that consists of those sets of truth-value assignments to $P_1,…,P_n$ that are consistent with the first $n$ propositions in $\Gamma$. This is clearly an infinite subtree. Then an infinite path in this subtree is a model (assignment of truth values to all propositions) that is consistent with the first $n$ propositions in $\Gamma$ for all $n$ and hence consistent with $\Gamma$. This seems to prove our result much more easily, but I may be wrong here.
1 We do not lose generality here by assuming that $\Gamma$ is countable. This is because $\Gamma$ is a set of propositions, and the propositions are countable by stipulation (we have already been given an enumeration $P_1,P_2,…$ of propositions). So $\Gamma$ is subcountable and therefore countable. (Note for the enthusiast: for very weak axiomatic systems like $RCA_0$, not all subcountable sets are countable, and, interestingly, this difference between subcountability and countability seems to play a great part in the reverse mathematics of the compactness of logic (at least this is my impression from the Wikipedia page!).
2 I give the case for the first level of the binary tree only; the other levels are exactly analogous. Suppose, then, for a contradiction, that, even though every finite subset of $\Gamma$ has a model, nevertheless there is a finite subset of $\Gamma \cup \{P_1\}$ that has no model and there is also a finite subset of $\Gamma \cup \{¬P_1\}$. Well, take the union of those two finite subsets and remove the elements $P_1$ and $¬P_1$; we get a finite subset of $\Gamma$ which clearly cannot have a model. But this is a contradiction. $\blacksquare$
0 comment threads
I think that now I understood a couple of points: The following statement is now clearer.
Let $i(P_1) = 0$ and suppose $\phi(1)$ does not hold. That is, there is a finite subset $\Gamma'$ of $\Gamma$ which has no model in which $P_1$ takes the value $i(P_1) = 0$. Then we define $i(P_1) = 1$ and show that $\phi(1)$, i.e., every finite subset of $\Gamma$ has a model in which $P_1$ takes the value $i(P_1) = 1$.
-
If, e.g., when $i(P_1) = 0$, $\phi(1)$ does not hold, then no formula that is true only when $i(P_1)$ is selected for the assemblage of subsets. Then we'll build an union of subsets of formulas such as $i(P_1) = 1$. One of those is $\Gamma$'. In the case in which at least one subset contains contradictory formulas, it's not Satisfiable, i.e. has no model.
-
If two subsets have models but those models are contradictory, since the union of those subsets is a subset, we need to choose one of them only.
-
How to build 'the line' in the whole possibly infinite truth table? This is at least one line corresponding to each formula P. Say $P_1$ $\land$ ..., $\land$ $P_n$.
0 comment threads
2 comment threads