Compactness theorem - misundarstanding consequences of this theorem.

232 Views Asked by At

We are working in first order world.
Our assumption is $\Gamma\models\Delta$, where both sets are infinity and $\Delta=\{\phi_1,\phi_2,...\}$.
I know that for each $i$ we have $\Gamma\models \phi_i$.
However, I don't understand why:

Thanks to compactness theorem there exists finity subset $\Gamma_i\subseteq \Gamma$ such that $\Gamma_i\models\phi_i$.

Can you explain it me ? I know compactness theorem. After all it is possible that forcing $\phi_i$ may require entire set $\Gamma$ not only finite subset.

2

There are 2 best solutions below

1
On BEST ANSWER

HINT: Show (using Compactness) that if no finite subset of $\Gamma$ implied $\varphi_i$, then $\Gamma\cup\{\neg\varphi_i\}$ is satisfiable - but that contradicts the claim that $\Gamma\models\varphi_i$ . . .

0
On

The fact is that (semantic version of) the compactness theorem is equivalent to the statement $$\Gamma \models \phi \iff \exists \Gamma_i \subseteq_{finite} \Gamma\, (\Gamma_i \models \phi)$$ this can be easily proven by contradiction.

The $(\Leftarrow)$ part is trivial. Let focus on the $(\Rightarrow)$ part.

We proceed by contradiction, we assume that $\Gamma \models \phi$ but for every $\Gamma_i \subseteq_{finite} \Gamma$ it happens that $\Gamma_i \not\models \phi$ this implies that for every $\Gamma_i \subseteq_{finite} \Gamma$ the theory $\Gamma_i \cup\{\neg \phi\}$ is satisfiable (i.e. it has a model).

From this it trivially follows that every finite subset of $\Gamma\cup\{\neg \phi\}$ is satisfiable and so by compactness $\Gamma \cup \{\neg \phi\}$ has a model, let call it $M$.

Then $M \models \Gamma$ and so by hypothesis $M \models \phi$, but at the same time $M \models \neg \phi$ by construction, this is an absurd so we have to conclude that if $\Gamma \models \phi$ is not possible that for some $\Gamma_i \subseteq_{finite} \Gamma$ we have $\Gamma_i \not \models \phi$.

Hope this helps.