proving corollary of compactness theorem

406 Views Asked by At

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$

2

There are 2 best solutions below

2
On BEST ANSWER

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.

2
On

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$.