# Proving Compactness Theorem

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!

• It seems that the lemma is the key here. Is it proved in your notes? Commented Oct 25, 2021 at 22:25
• Actually, I thought the lemma would be easily proven by using the fact that $\sigma$ only involves finitely many sentential letters, but I just noticed that the proof in my mind is wrong. In the lecture note, the lemma is proven using the Compactness theorem that I provided. Commented Oct 25, 2021 at 22:28
• Please share with me any of your ideas to prove that lemma if you have one! Commented Oct 25, 2021 at 22:28
• It seems kind of equivalent to the compactness theorem then. I think you can find a proof for that online, the proof I know uses ultraproducts. Are you familiar with that? Commented Oct 25, 2021 at 22:31
• Have you seen the soundness and completeness theorems yet? If you understand these then there is a very nice and intuitive proof of compactness. Commented Oct 26, 2021 at 10:01

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.