0
$\begingroup$

Compactness Theorem: If every finite subset of $\Gamma$ has a model, then $\Gamma$ has a model too.

I want to ask whether I proved correctly the corollary which says that If $\Gamma\vDash\phi$, then for some finite $\Delta\subseteq\Gamma$, $\Delta\vDash\phi$. Someone told me I could do a contrapositive proof, but wasn't sure how to do it.

My proof/reasoning:

If $\phi$ is a logical consequence of $\Gamma$, then $\Gamma\cup\{\lnot\phi\}$ is inconsistent. By the Compactness Theorem, there is a finite subset of $\Gamma\cup\{\lnot\phi\}$ that is inconsistent. So there is a finite subset $\Delta$ of $\Gamma$ such that $\Delta\cup\{\lnot\phi\}$

Thus, $\Delta\vDash\phi$

$\endgroup$

2 Answers 2

2
$\begingroup$

You did use the contrapositive here, but of the compactness theorem itself. Your proof is fine like this (although the last bit of the last sentence is missing: "... such that $\Delta \cup \{\neg \phi\}$ is inconsistent").

The other approach would be to prove the contrapositive of the statement you wish to prove. That is: if for no finite $\Delta \subseteq \Gamma$ we have $\Delta \models \phi$, then $\Gamma \not \models \phi$. To do this we claim that $\Gamma \cup \{ \neg \phi \}$ is consistent, which we prove by using the compactness theorem. Let $\Delta \subseteq \Gamma$ be finite, then by our assumption $\Delta \not \models \phi$, so $\Delta \cup \{\neg \phi\}$ is consistent. Hence every finite subset of $\Gamma \cup \{ \neg \phi \}$ is consistent and we are done.

$\endgroup$
2
  • $\begingroup$ thank you so much :) $\endgroup$ Apr 24, 2020 at 17:24
  • 1
    $\begingroup$ @nerdfighter If this answers your question, can you accept it. That way other users know this no longer needs an answer (or that they will find an answer here, if they have the same question). $\endgroup$ Apr 24, 2020 at 17:29
0
$\begingroup$

I think there's an even shorter proof.

By Completeness Theorem, $\Gamma \vdash \varphi$. Every derivation is finite, so for some finite $\Delta \subseteq \Gamma$, $\Delta \vdash \varphi$. Then by Soundness Theorem, $\Delta \models \varphi$.

$\endgroup$
2
  • $\begingroup$ You have mixed up soundness and completeness. But if you switch them then yes, this woud be correct. Note that this is actually one way to prove the compactness theorem: it is an easy consequence once we have soundness and completeness. $\endgroup$ Apr 25, 2020 at 22:38
  • $\begingroup$ @MarkKamsma Ah yes, you're right. $\endgroup$
    – user770683
    Apr 26, 2020 at 10:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .