0
$\begingroup$

My book on logic says that there are two equivalent compactness theorems:

  1. Let $\Gamma$ be a set of propositional formulas, and let $\phi$ be a formula. If $\Gamma\models \phi$, then there is a finite subset $\Gamma_0\subset\Gamma$ such that $\Gamma_0\models\phi$.

  2. If for each finite $\Gamma_0\subset\Gamma$ we have a model, then for $\Gamma$ we have a model.

Now for $2\implies 1$, my book writes the following: Suppose 2. is true. Let $\Gamma$ be a set of propositional formulas, and let $\phi$ be a formula such that $\Gamma\models\phi$. Then there is no model for $\Gamma\cup\{\neg\phi\}$, and because of our assumption, there exists a finite $\Gamma_0\subset\Gamma$ such that there is no model for $\Gamma_0\cup\{\neg\phi\}$. But then we have $\Gamma_0\models\phi$.

I don't understand how our assumption leads to the existence of $\Gamma_0\subset\Gamma$ such that $\Gamma_0\cup\{\neg\phi\}\models\perp$. I'm confused, because $\Gamma_0\cup\{\neg\phi\}$ has no model, so it seems like we can't apply the assumption, except for $\Gamma$ separately, but I don't see how.

$\endgroup$
0
$\begingroup$

Suppose 2. is true.

Let $\Gamma$ be a set of propositional formulas, and let $\phi$ be a formula such that $\Gamma\models\phi$.

Then there is no model for $\Gamma\cup\{\neg\phi\}$, and because of our assumption, there exists a finite $\Gamma_0\subset\Gamma$ such that there is no model for $\Gamma_0\cup\{\neg\phi\}$.

Otherwise, consider the finite subsets of $\Gamma \cup \{\phi\}$.

If it is $\Gamma_0 \subset \Gamma$, if it does not have a model, then $\Gamma_0 \vDash \phi$ vacuously.

If it is in the form of $\Gamma_0 \cup \{\neg \phi\}$, then by "otherwise", it has a model.

So by 2, $\Gamma \cup \{\neg \phi\}$ would have a model, contradiction.

But then we have $\Gamma_0\models\phi$.

$\endgroup$
1
$\begingroup$

Since your $\Gamma_0 \cup \{\neg \phi\}$ has no model we have $\Gamma_0 \cup \{\neg \phi\} \models \bot$ (remind that $\Theta\models\varphi$ if every model of $\Theta$ is a model of $\varphi$ and that $\bot$ has no model by definition).

Since $\Gamma_0 \cup \{\neg \phi\}$ has no model it follows that every model of $\Gamma_0$ is not a model of $\neg \phi$, it makes $\phi$ false. So every such model must make $\phi$ true, hence $\Gamma_0 \models \phi$.

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