1
$\begingroup$

This is an easy consequence (Doets calls it Compactness Theorem (version 2)) in Kees Doets' Basic Model theory:

Let $\Sigma$ a set of sentences and $\phi$ a sentence.

If $\Sigma \models \phi$, then for some finite $\Delta \subset\Sigma$, $\Delta \models \phi$.

The proof by contradiction reads:

"If $\phi$ does not logically follow from some $\Delta \subset \Sigma$, then the set $\Sigma \cup \{\neg \phi\}$ is finitely satisfiable and therefore, by compactness, satisfiable."

How do we know that $\Sigma \cup \{\neg \phi\}$ is finitely satisfiable?

From the fact that $\phi$ does not logically follow from some $\Delta$, we know that $\neg \phi$ follows from every $\Delta \subset \Sigma$. But how does this imply that there's a model for every finite subset of the set of sentences?

$\endgroup$
3
$\begingroup$

First, a quick comment. Your statement "From the fact that $\varphi$ does not logically follow from some $\Delta$, we know that $\neg\varphi$ follows from every $\Delta\subseteq \Sigma$." is incorrect: when $A$ is a set of sentences, "$A\not\models b$" is different from "$A\models\neg b$." We could have $b$ be independent of $A$ - that is, $A\not\models b$ and $A\not\models\neg b$.

What is true is that since $\varphi$ isn't entailed by any finite $\Delta\subseteq\Sigma$, $\neg\varphi$ must be compatible with every finite $\Delta\subseteq\Sigma$ in the sense that, for every $\Delta\subseteq\Sigma$, the set $\Delta\cup\{\neg\varphi\}$ will be satisfiable. (It's arguably more natural to say "consistent with" instead of "compatible with," but consistency is a syntactic property which isn't needed in this purely semantic question, so I want to avoid using language which might bring in confusion.)


This is in fact the crux of the problem!

Saying "$\Sigma\cup\{\neg\varphi\}$ is finitely satisfiable" just means "$\Delta\cup\{\neg\varphi\}$ is satisfiable for every finite $\Delta\subseteq\Sigma$." But "$\Delta\cup\{\neg\varphi\}$ is satisfiable" just means "there is some model of $\Delta\cup\{\neg\varphi\}$," which is to say $$\Delta\not\models\varphi$$ ("$\Delta\models\varphi$" means exactly "every model of $\Delta$ satisfies $\varphi$," which can't be true if there is some model of $\Delta\cup\{\neg\varphi\}$).


All that is to say that the statement "$\Sigma\cup\{\neg\varphi\}$ is finitely satisfiable" is equivalent to "For every finite $\Delta\subseteq\Sigma$, we have $\Delta\not\models\varphi$." But this latter statement is precisely our hypothesis "$\varphi$ does not logically follow from some [finite] $\Delta\subseteq\Sigma$!"

Note that the phrase "logically follow from" could confuse things here: it's meant in the semantic sense ($\models$), not the syntactic sense ($\vdash$).

$\endgroup$
3
$\begingroup$

My intuition about this does not (directly) use contradiction. Rather, it follows from the soundness and completeness of first-order logic:

If $\Sigma\vDash\phi$, then there is a proof of $\Sigma\vdash\phi$ (completeness), and since that proof is a finite object it mentions at most finitely many of the axioms of $\Sigma$. Therefore the same proof proves $\Delta\vdash\phi$ for some finite $\Delta\subseteq\Sigma$, and thus $\Delta\vDash\phi$ (soundness).

$\endgroup$
  • $\begingroup$ To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it. $\endgroup$ – Noah Schweber Dec 8 '18 at 20:28
  • $\begingroup$ @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now? $\endgroup$ – Mike Dec 8 '18 at 20:31
  • $\begingroup$ @Craig You have things backwards. "$\models$" is a purely semantic notion ($\Sigma\models\varphi$ iff every model of $\Sigma$ satisfies $\varphi$); "$\vdash$" is syntactic ($\Sigma\vdash\varphi$ iff there is a proof of $\varphi$ from $\Sigma$). Since the problem involves only "$\models$," it is (a priori) purely semantic. $\endgroup$ – Noah Schweber Dec 8 '18 at 20:32
  • $\begingroup$ @NoahSchweber Ohhh, I thought that $\models$ was interpreted as logical deduction when used in relation to sets of formulas. That should clear everything up, thanks. $\endgroup$ – Mike Dec 8 '18 at 20:36
  • $\begingroup$ @NoahSchweber: Well, this is the only way I could think about proving compactness either. But I'll admit to a strong bias in favor of proof theory ... $\endgroup$ – Henning Makholm Dec 8 '18 at 20:51
1
$\begingroup$

Every $\Delta$ finite have $\Delta\vDash\lnot\varphi$, so every model of $\Delta$ is a model of $\Delta\cup\{\lnot\varphi\}$, and there is a model for every $\Delta$, namely, the model of $\Sigma$

$\endgroup$
  • 1
    $\begingroup$ So does Doets assume that $\Sigma$ has a model? $\endgroup$ – Mike Dec 8 '18 at 20:32
  • $\begingroup$ If there is no model to $\Sigma$, there is finite deduction sequence that proves contradiction, take $\Delta$ be all the elements of $\Sigma$ that appear in that sequence and you got a finite subset of $\Sigma$ that proves $\varphi$ $\endgroup$ – Holo Dec 8 '18 at 20:35
  • $\begingroup$ @Holo "If there is no model to $\Sigma$, there is finite deduction sequence that proves contradiction" This uses the completeness theorem, which is overkill here. $\endgroup$ – Noah Schweber Dec 8 '18 at 20:38
  • $\begingroup$ @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know) $\endgroup$ – Holo Dec 8 '18 at 20:50
  • $\begingroup$ @Holo I disagree - $\vdash$ isn't needed at all, this is just a direct application of the basic definition of $\models$. $\endgroup$ – Noah Schweber Dec 8 '18 at 20:51

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.