0
$\begingroup$

Let $\Gamma$ be a theory that is closed under provability. That is, if there are sentences $\varphi_{1},...,\varphi_{n}$ in $\Gamma$ such that $\varphi_{1},...,\varphi_{n} \vdash \phi$ it applies that $\phi \in \Gamma$. Prove that $\Gamma$ has a model if and only if each set in $\Gamma$ has a model.

I want to prove the above statement and the only theorem I can think of to prove this is the compactness theorem, that a set of sentences $\Gamma$ where every finite subset of $\Gamma$ has a model, then there is a model for the whole $\Gamma$.

But this statement deals not only with finite sets in $\Gamma$ but all sentences, infinite and finite. But my question is, can I still use the compactness theorem to prove this statement? I reason that if all sets have a model, that means that all finite sets also has a model, which results in $\Gamma$ having a model?

Also, do I need to in any way take into account that the theory is closed under provability when I do this?

$\endgroup$
5
  • $\begingroup$ @RossMillikan Yes they should, thanks for noticing this! I have updated this now. $\endgroup$
    – idlatva
    Apr 15, 2021 at 13:56
  • $\begingroup$ Each sentence is always finite. Each proof of $\phi$ only uses finitely many of the sentences in $\Gamma$, so you can use compactness ignoring the infinite subsets of $\Gamma$. You need deductively closed because otherwise there could be a $\phi$ that you can prove that is not part of $\Gamma$ $\endgroup$ Apr 15, 2021 at 13:57
  • 2
    $\begingroup$ What do you mean by a "set in $\Gamma$"? Do you mean "sentence in $\Gamma$" instead? $\endgroup$ Apr 15, 2021 at 14:12
  • $\begingroup$ @EricWofsey Yes you are right, I made a mistake when translating the text. Thanks! $\endgroup$
    – idlatva
    Apr 15, 2021 at 17:30
  • $\begingroup$ @RossMillikan Thank you for your answer! I will do deductively closed. $\endgroup$
    – idlatva
    Apr 15, 2021 at 19:57

1 Answer 1

0
$\begingroup$

I assume that you meant to write the following:

Let $\Gamma$ be a theory that is closed under provability. Prove that $\Gamma$ has a model if and only if each sentence in $\Gamma$ has a model.

Suppose $\Gamma$ has a model $M$. Then by definition of $M\models \Gamma$, we have $M\models \varphi$ for each sentence $\varphi\in \Gamma$, so each sentence in $\Gamma$ has a mdoel.

Conversely, suppose that every sentence in $\Gamma$ has a model. By the compactness theorem, to show that $\Gamma$ has a model, it suffices to show that every finite subset of $\Gamma$ has a model. Let $\Delta\subseteq \Gamma$ be finite, and write $\Delta = \{\psi_1,\dots,\psi_n\}$. Then $T\vdash \bigwedge_{i=1}^n \psi_i$, so $\bigwedge_{i=1}^n \psi_i$ is in $T$, since $T$ is closed under provability. Thus $\bigwedge_{i=1}^n \psi_i$ has a model $M$. Now since $M\models \bigwedge_{i=1}^n \psi_i$, also $M\models \psi_i$ for each $i$, so $M\models \Delta$, as desired.


If instead you mean to write:

Let $\Gamma$ be a theory that is closed under provability. Prove that $\Gamma$ has a model if and only if each subset of $\Gamma$ has a model.

... then the proof is trivial.

Suppose $\Gamma$ has a model $M$. Let $\Gamma'\subseteq \Gamma$ be a subset. For all $\varphi\in \Gamma'$, $\varphi\in \Gamma$, so $M\models \varphi$, and hence $M\models \Gamma'$. So every subset of $\Gamma$ has a model.

Conversely, suppose every subset of $\Gamma$ has a model. Since $\Gamma\subseteq \Gamma$, $\Gamma$ has a model.

$\endgroup$

You must log in to answer this question.

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