If $T \models \phi$ then there is a finite subtheory $T' \subset T$ such that $T' \models \phi$

359 Views Asked by At

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

2

There are 2 best solutions below

9
On BEST ANSWER

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

3
On

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