2
$\begingroup$

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!

$\endgroup$
10
  • 1
    $\begingroup$ It seems that the lemma is the key here. Is it proved in your notes? $\endgroup$
    – Berci
    Oct 25 at 22:25
  • $\begingroup$ 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. $\endgroup$ Oct 25 at 22:28
  • $\begingroup$ Please share with me any of your ideas to prove that lemma if you have one! $\endgroup$ Oct 25 at 22:28
  • $\begingroup$ 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? $\endgroup$
    – Berci
    Oct 25 at 22:31
  • 2
    $\begingroup$ Have you seen the soundness and completeness theorems yet? If you understand these then there is a very nice and intuitive proof of compactness. $\endgroup$ Oct 26 at 10:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.