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

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?

## 3 Answers

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

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

• To be fair, bringing the completeness theorem into a purely semantic problem is a bit overkill given that compactness can be proved without it. – Noah Schweber Dec 8 '18 at 20:28
• @NoahSchweber I thought this is a purely syntactic problem, and bringing in models would make it semantic, now? – Mike Dec 8 '18 at 20:31
• @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. – Noah Schweber Dec 8 '18 at 20:32
• @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. – Mike Dec 8 '18 at 20:36
• @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 ... – Henning Makholm Dec 8 '18 at 20:51

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

• So does Doets assume that $\Sigma$ has a model? – Mike Dec 8 '18 at 20:32
• 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$ – Holo Dec 8 '18 at 20:35
• @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. – Noah Schweber Dec 8 '18 at 20:38
• @NoahSchweber that is true.. but this is the easiest way to look at this(at least the easiest from the ways I know) – Holo Dec 8 '18 at 20:50
• @Holo I disagree - $\vdash$ isn't needed at all, this is just a direct application of the basic definition of $\models$. – Noah Schweber Dec 8 '18 at 20:51