Compactness theorem for sentential logic

logicmodel-theoryproof-explanationpropositional-calculus

I am reading proof of compactness theorem for sentential logic in Enderton's book, A mathematical introduction to logic.

(Compactness theorem) A set of wffs is satisfiable iff every finite subset is satisfiable.

He wrote a strategy before the proof:

1) we take our given finitely satisfiable set $\Sigma$ and extend it to a maximal such set $\Delta$,

2) we utilize $\Delta$ to make a truth assignment that satisfies $\Delta$.

I am struggling why we extend the given satisfiable set $\Sigma$ to a maximal such set $\Delta$, is it there any intuation under this idea? Or generally, why we define different set and on the set we define a truth assignment? Is there a proof that take a finitely satisfiable set $\Sigma$ and show that it is also satisfiable (without defining some set, such $\Delta$)?

Best Answer

The intuition is that only a maximal (and finitely satisfiable) set of formulas induces (univocally) the definition of a truth assignment which satisfies such a set.

The maximal extension $\Delta$ of the finitely satisfiable set $\Sigma$ of formulas plays the role of a guidance on how to build the truth assignment that satisfies $\Sigma$. Of course, it is not necessary to appeal for $\Delta$ to build a truth assignment that satisfies $\Sigma$: you can just look at the formulas in $\Sigma$ (possibly they are infinitely many) and try to build a truth assignment that satisfies $\Sigma$, for instance by trials and errors, but can you generalize this method to any finitely satisfiable set $\Sigma$ of formulas? In the proof of the compactness theorem we look for a ''procedure'' that allows us to prove that any finitely satisfiable set $\Sigma$ of formulas is satisfiable by showing a truth assignment that satisfies $\Sigma$, and the ''rules'' of this procedure do not depend on $\Sigma$.

Indeed, a crucial point in the proof of compactness is the property that, given a set $\Delta$ of formulas that is maximal (i.e. for every formula $\alpha$, either $\alpha \in \Delta$ or $\lnot \alpha \in \Delta$) and finitely satisfiable, and given a truth assignment $v$ such that, for any propositional variable $X$: \begin{align} v(X) = \begin{cases} \top &\text{if } X \text{ occurs in } \Delta \\ \\ \bot &\text{otherwise,} \end{cases} \end{align} we have that $\overline{v}(\alpha) = \top$ for every formula $\alpha \in \Delta$ (and hence $\Delta$ is satisfiable).

If $\Delta$ is not maximal, you cannot prove the property above, or at least you cannot prove that by simple induction on the formula $\alpha$. Suppose that $\Delta$ is not maximal and contain the formula $X \lor Y$ but neither $X$ nor $\lnot X$ nor $Y$ nor $\not Y$ are in $\Delta$ ($X$ and $Y$ are distinct propositional variables). So, which is a truth assignment that satisfies $\Delta$?

  • Maybe a truth assignment $v_1$ such that $v_1(X) = \top$ and $v_1(Y) = \bot$?
  • Maybe a truth assignment $v_2$ such that $v_2(X) = \bot$ and $v_2(Y) = \top$?
  • Maybe a truth assignment $v_3$ such that $v_3(X) = \top$ and $v_1(Y) = \top$?

For each choice, we have to check if it is compatible with the other formulas in $\Delta$. If instead $\Delta$ is maximal, we immediately know which is the good choice (we have just to check whether $X$ and $Y$ are in $\Delta$ or not) and we are guaranteed that such a choice is compatible with the other formulas in $\Delta$ because of the (strong) hypothesis of finite satisfiability.


Summing up, the approach followed by Enderton's textbook to prove compactness theorem is the following (it is not the only one, for instance you can derive compactness from the completeness theorem as well):

  1. We want to prove that every finitely satisfiable set $\Sigma$ of formulas is satisfiable.

  2. We have an easy proof (by induction on the definition of formula) of Point 1 if we add the hypothesis that the set is not only finitely satisfiable but also maximal.

  3. We find a way to extend the finitely satisfiable set $\Sigma$ to a maximal finitely satisfiable set $\Delta$ of formulas, so that we can apply the method of Point 2, which is also a proof of Point 1 since $\Sigma \subseteq \Delta$.

Related Question