Compactness theorem for sentential logic

Question

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$)?

Answer 1

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$.

Answer 2

You could give a different proof of compactness as follows: Somehow(!) prove soundness and completeness for some formal proof system: A set is satisfiable if and only if it is consistent. It's clear that $\sum$ is consistent if and only if every finite subset of $\sum$ is consistent: If $\sum\vdash\phi\land\lnot\phi$ then the proof of the contradiction uses only finitely many formulas in $\sum$ (since the proof has only finitely many steps), so there exists a finite set $F\subset\sum$ with $F\vdash\phi\land\lnot\phi$.

Of course that's harder than the proof you're asking about. One can use the Tychonoff theorem from topology to give a proof that's not harder, although it may be harder to see where the proof comes from:

First notation: If $v$ is a truth assignment, in other words a map from propositional variables to $B=\{0,1\}$, let $\overline v$ be the extension of $v$ to all formulas (so $\overline v(\phi\land\psi)=\overline v(\phi)\land\overline v(\psi)$, etc.). (I don't recall what notation Enderton uses for $\overline v$, although I suspect it's just $\overline v$.)

Let $L$ be the set of all wffs, and let $X=B^L$, with the product topology arising from the discrete topology on $B$. The Tychonoff theorem shows that $X$ is compact. Note that an element of $X$ is precisely a function $f:L\to B$.

Let $V$ be the set of $f\in X$ such that $f=\overline v$ for some assignment $v$. Show that given $f\in X$ we have $f\in V$ if and only if $f(\phi\land\psi)=f(\phi)\land f(\psi)$ for all $\phi$, $\psi$, and similarly for the other logical connectives. Hence $V$ is a closed subset of $X$, so $V$ is compact.

Now for $E\subset L$ let $S_L$ be the set of $f\in V$ such that $f(\phi)=1$ for all $\phi\in E$. Show that $S_E$ is closed, hence compact.

Say $\sum\subset L$ is finitely satisfiable. We need to show that $\sum$ is satisfiable, which is to say $S_\sum\ne\emptyset$. We're given that $S_F\ne\emptyset$ for every finite set $F\subset \sum$. Since $$\bigcap_{j=1}^nS_{F_j}=S_{\bigcup_{j=1}^nF_j}$$it follows that the intersection of finitely many $S_F$ is nonempty.

So compactness shows that the intersection of all the $S_F$, for $F\subset \sum$ finite, is nonempty. So $$S_\sum=\bigcap_{F\subset\sum}S_F\ne\emptyset,$$qed.

So yes, there are other proofs. I see that while I was typing this someone else posted an answer talking about maximal consistent sets, so I'll stop here.