Proving corollary of compactness theorem

first-order-logiclogicmodel-theory

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$

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.

Related Question