Proving Compactness Theorem

Question

I am reading an introductory logic lecture notes, and found this theorem. This is not proven in the lecture note I am reading, so I am wondering if my proof is correct. I am not very comfortable with what I will say, but $L$ is first order language with the usual sentential connectives.

A set $\Sigma$ of $L$-formulas is Satisfiable iff there exists an evaluation $v$ of sentential letters such that $\overline{v}(\sigma)=1$ for all $\sigma\in \Sigma$, where $\overline{v}$ is the unique extension of $v$ on $\Sigma$.

Compactness Theorem: If every finite $\Delta\subset \Sigma$ is satisfiable, then $\Sigma$ is satisfiable.

Proof: We will use the following lemma to prove the theorem: If $\sigma$ is an $L$-formula and $\Sigma \models \sigma$, then there exists some finite set $\Delta\subset\Sigma$ such that $\Delta\models \sigma$.

Assume for contradiction that every finite $\Delta\subset \Sigma$ is satisfiable and $\Sigma$ is not satisfiable. Let $w$ be a sentential letter of $L$. Then $\Sigma\models (w\wedge \neg w)$ because there is no evaluation $v$ such that $\overline{v}(\sigma)=1$ for all $\sigma\in \Sigma$. Then by the lemma, there is some finite set $\Delta\subset \Sigma$ such that $\Delta\models (w\wedge\neg w)$. As we assumed every finite subset of $\Sigma$ is satisfiable, let $v$ be an evaluation such that $\overline{v}(\delta)=1$ for all $\delta\in \Delta$. Then we reach a contradiction as $\overline{v}(w\wedge\neg w)=0$ so $\Delta\models (w\wedge \neg w)$ is not true.

Please let me know if anything is incorrect. Any comments will be appreciated. Thank you!

Answer 1

Compactness follows nicely from the soundness and completeness theorems. Recall that together soundness and completeness state the following:

For any set of formulas $\Sigma$ and any formula $\sigma$ we have that $\Sigma \models \sigma$ if and only if $\Sigma \vdash \sigma$.

Here $\Sigma \models \sigma$ means that $\sigma$ is true in all models (valuations) where everything in $\Sigma$ is true. The notation $\Sigma \vdash \sigma$ means that there is some proof tree with assumptions contained in $\Sigma$ and conclusion $\sigma$.

The easiest will be to prove the contraposition of the compactness theorem: if $\Sigma$ is unsatisfiable then there must be finite $\Delta \subseteq \Sigma$ that is unsatisfiable. As you already noted, $\Sigma$ being unsatisfiable means that $\Sigma \models w \wedge \neg w$ for some $w$. So by completeness we get $\Sigma \vdash w \wedge \neg w$. That means that there must be a proof tree with assumptions in $\Sigma$ and conclusion $w \wedge \neg w$. However, proof trees are finite objects, so the assumptions of our proof tree must already appear in a finite $\Delta \subseteq \Sigma$. So we get $\Delta \vdash w \wedge \neg w$. Then by soundness we have $\Delta \vDash w \wedge \neg w$, which means that $\Delta$ is unsatisfiable as required.

So the nice intuition here is the following. A set $\Sigma$ is unsatisfiable precisely when we can derive a contradiction from it. That derivation is finite, so that means that the contradiction must already take place in a finite part of $\Sigma$. That means that if every finite part is satisfiable then no contradiction can take place, so $\Sigma$ must be satisfiable.