0
$\begingroup$

$T$ is a theory and $\phi$ is a sentence with $T \models \phi$. I read notes with a quote like this:

By Compactness Theorem, a finite subset $T_0 \subseteq T$ has $T_0 \models \phi$.

I thought the Compactness Theorem was something like "a theory has a model iff every subset of the theory has a model". That is $M \models T \implies M \models T_0$. (I believe it follows from Completeness of FOL and proofs being finite). So how do we show the claim with compactness? I think it has something to do with $\phi$ being a sentence. If we replaced $\phi$ with an infinite theory $T'$ then we cannot claim $T_0 \models T'$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Your statement of compactness is not quite right (your statement is true, just not very strong, since $T$ is a subset of itself!). A correct statement is: Let $T$ be a first-order theory. Then $T$ has a model if and only if every finite subset of $T$ has a model.

Now to your actual question. Since $T \models \phi$, the theory $T \cup \{\neg\phi\}$ has no models. Thus, by compactness, there is a finite subset $\Delta \subseteq T \cup \{\neg\phi\}$ that has no models. Let $T_0 \subseteq T$ be the finitely many sentences from $T$ that appear in $\Delta$. Then $T_0 \cup \{\neg\phi\}$ has no models, so every model of $T_0$ is not a model of $\neg\phi$, and hence $T_0 \models \phi$.

$\endgroup$
4
  • $\begingroup$ oops you are right. I meant to write the finite part. but every finite subset is a subset right? $\endgroup$
    – qwr
    Apr 10, 2020 at 0:24
  • 3
    $\begingroup$ @qwr Perhaps a more instructive way to phrase the compactness theorem would be 'if every finite subset of a theory has a model, then the theory has a model'. That's the hard direction of the iff. The other way is immediate from the definitions. You see how deleting the word 'finite' reduces its strength? (And as Chris has indicated, trivializes it.) $\endgroup$ Apr 10, 2020 at 0:46
  • $\begingroup$ I think I have reasoned that it does not matter if $\Delta$ picked contains or does not contain $\neg \phi$, correct? $\endgroup$
    – qwr
    Apr 10, 2020 at 4:03
  • $\begingroup$ Yes, that's correct. $\endgroup$ Apr 10, 2020 at 15:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .