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 \land P_2, P_2 \land 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. ↩︎
1 answer
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 assembling 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.
-
How to build 'the line' in the whole possibly infinite truth table? This is at least one line corresponding to ewach formula P. Say $P_1$ $\land$ ..., $\land$ $P_n$.
0 comment threads
2 comment threads