Comments on Compactness of the Propositional Calculus
Post
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. ↩︎
2 comment threads