2
$\begingroup$

Use the Compactness Theorem to show: if $T \models \varphi$ then there is a finite subtheory $T' \subset T$ such that $T' \models \varphi$.

I don't see how I can use the compactness theorem here. Particularly, since the proposition seems to be some kind of weak reverse implication. Apparently the general compactness theorem goes both ways meaning: A theory $T$ is consistent if and only if every finite subtheory $T' \subset T$ is consistent. However I only know a version with just one implication: If every finite $T' \subset T$ is consistent, then so is $T$.

$\endgroup$
  • 1
    $\begingroup$ Apropos of the last line in the Question: If $T$ is consistent, so is every "subtheory" of $T$ (finite or not). Thus the converse of what you've stated as "known" is the easier direction. $\endgroup$ – hardmath Jan 1 '15 at 20:15
  • $\begingroup$ Yeah, I see now. $\endgroup$ – Leo Jan 1 '15 at 20:22
6
$\begingroup$

HINT: If $S$ is a theory, and $\psi$ is a statement such that $S\not\models\psi$, then $S\cup\{\lnot\psi\}$ is consistent.

$\endgroup$
  • 2
    $\begingroup$ I will be very happy to hear actual criticism. I can't read minds, you know. $\endgroup$ – Asaf Karagila Jan 1 '15 at 19:51
  • $\begingroup$ It's not my criticism if you're wondering: I'm still thinking about your hint :). I was thinking about something like this: If $T$ is consistent and models $\varphi$ then $T \not\models \lnot \varphi$. Compactness now gives me that there exists some finite subtheory of $T \cup \{\lnot \varphi \}$ that is not consistent. But since $T$ is consistent this subtheory must contain $\lnot \varphi$. Am I on the right track? $\endgroup$ – Leo Jan 1 '15 at 19:59
  • $\begingroup$ Of course I don't know whether $T$ is consistent or not, do I? Since for it to be consistent, it needs a model, and I don't know a model for $T$. $\endgroup$ – Leo Jan 1 '15 at 20:02
  • 1
    $\begingroup$ If $T$ is inconsistent then the compactness theorem tells you there is a finite subtheory which is inconsistent and that solves that case. (Note that this is subsumed into my previous comment.) $\endgroup$ – Asaf Karagila Jan 1 '15 at 20:03
  • 1
    $\begingroup$ Oh, it's my pleasure! $\endgroup$ – Asaf Karagila Jan 1 '15 at 20:20
3
$\begingroup$

$T \models \phi$ means that every model of $T$ is also a model of $\phi$. The compactness theorem states that if every finite subset of $T$ has a model, then $T$ has a model. $T$ is consistent means that there is some formula $\phi$ such that $T \not\vdash \phi$ where $T \vdash \phi$ means that $\phi$ has a proof using axioms drawn from $T$. The soundness and completeness theorems together state that $T \models \phi$ iff $T \vdash \phi$. So your attempt to restate the problem in terms of consistency is implicitly using soundness and completeness.

It is trivial that if $T \vdash \phi$ then there is a finite subset $T'$ of $T$ such that $T' \vdash \phi$: you just take $T'$ to be the set of axioms that are used in some proof of $\phi$. So you can prove the statement in your subject line without using the compactness theorem directly (but it is used in the proof of the completeness theorem).

Alternatively, you can apply the compactness theorem directly to the statement about models, using the hint that Asaf Karagila kindly supplied in his answer.

$\endgroup$
  • $\begingroup$ I really love your answer as well, but since Asaf's approach was more elementary, I took that one. $\endgroup$ – Leo Jan 1 '15 at 20:19
  • 1
    $\begingroup$ @Leo: I agree with your choice: Asaf Karagila got you to the intended proof, while I was just pointing out that you were implicitly switching between $\models$ and $\vdash$. $\endgroup$ – Rob Arthan Jan 1 '15 at 20:22
  • $\begingroup$ That's why I like your answer. It is quite illuminating to look at things that way. $\endgroup$ – Leo Jan 1 '15 at 20:25

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.