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!
Best Answer
Compactness follows nicely from the soundness and completeness theorems. Recall that together soundness and completeness state the following:
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.