2
$\begingroup$

Consider a set of L-sentences $\Sigma$ and a set of complete L-theories $T_i$ containing $\Sigma$ i.e. $\Sigma \subseteq T_i$.

Why is it that for each complete L-theory $T_i$ containing $\Sigma$ are exactly the the theories $Th(\mathcal A)$ of models of $\Sigma$?


I also want to make explicit what I believe the question is asking because I got confused after reading the answer. So I believe the question/natural language means:

If ( $T_i$ is complete & $\Sigma \subseteq T_i$) THEN ($T_i = Th(\mathcal A_i$) for some $\mathcal A \models \Sigma$)


Assume:

  • $ \mathcal A $ is an L-structure in some language L
  • I'm assuming $Th(\mathcal A) = \{ \sigma : \mathcal A \models \sigma \}$
  • recall an L-theory is closed under provability i.e. $T \vdash \sigma \implies \sigma \in T$

Honestly my thoughts on this are very limited except that I guess completeness theorem should play a role?

$$ \Sigma \vdash \sigma \iff \forall \mathcal A \models \Sigma, \mathcal A \models \sigma$$

I'm not even sure how $Th(\mathcal A)$ relates to $T_i$. This makes it seem all the L-theories are the same when they are not the same by assumption...

$\endgroup$
  • $\begingroup$ Does your concept of a "complete" theory include a hidden requirement that the theory is consistent? Otherwise the claim you want an explanation for is not true. $\endgroup$ – Henning Makholm Dec 25 '18 at 19:02
  • $\begingroup$ Yes it does. The formalization Im familiar with assumes complete theories are built from consistent theories by lindenbaum. $\endgroup$ – Pinocchio Dec 25 '18 at 19:04
4
$\begingroup$

If $\mathcal A\vDash\Sigma$ then $\mathrm{Th}(\mathcal A)$ clearly contains $\Sigma$ so this proves one inclusion.

For the reverse inclusion suppose we have a complete theory $T$ containing $\Sigma$, we want to show that it is of the form $\mathrm{Th}(\mathcal A)$ where $\mathcal A$ is a model of $\Sigma$. Since $T$ is complete any two models of $T$ are elementarily equivalent so they all have the same complete theory and $T=\mathrm{Th}(\mathcal A)$ where $\mathcal A$ is any model of $T$. Note that $\Sigma\subseteq T$, so $\mathcal A\vDash\Sigma$, as desired

$\endgroup$
  • $\begingroup$ Im confused are they all the same theory? $\endgroup$ – Pinocchio Dec 25 '18 at 18:58
  • 1
    $\begingroup$ Not necessarily, in general given $\Sigma$ there are many complete theories extending it $\endgroup$ – Alessandro Codenotti Dec 25 '18 at 19:05
  • $\begingroup$ so for each $T_i$ we have a corresponding $ Th( \mathcal A_i ) $? $\endgroup$ – Pinocchio Dec 25 '18 at 19:42
  • 1
    $\begingroup$ @Pinocchio This is the precise statement I'm proving: Let $\Sigma$ be a set of $L$-sentences and let $T$ be an $L$-theory. Then $T$ is a complete theory extending $\Sigma$ if and only if $T=\mathrm{Th}(\mathcal A)$ for some $\mathcal A$ which is a model of $\Sigma$. Note that if $\Sigma=\varnothing$ we recover the usual result that a theory is complete iff it is the theory of some structure $\endgroup$ – Alessandro Codenotti Dec 25 '18 at 20:55
  • 2
    $\begingroup$ @Pinocchio "Is it just because it's complete?" No, it's because it's consistent! "How do you know any two models of $T$ are elementarily equivalent?" Because it's complete! $\endgroup$ – Alex Kruckman Dec 26 '18 at 4:51
0
$\begingroup$

Let me try to answer it, as an exercise and to make sure I understood it.

Theorem: Let $\Sigma$ be a set of L-sentences and $T$ be an L-theory. Then $T$ is a complete theory extending $\Sigma$ if and only if there is some model $\mathcal A$ of $\Sigma $ s.t. $T = Th(\mathcal A)$.

$(\Rightarrow)$ (this is the hard direction) Suppose $\Sigma \subseteq T$ and $T$ is complete (so $T \vdash \sigma $ or $T \vdash \neg \sigma$ and the definition of complete I know and like includes consistency automatically). Consider any two models of $T$ call them $\mathcal B_1, \mathcal B_2$ (Note such a model satisfies $\Sigma$ because $T$ extends $\Sigma$). Recall the completeness theorem:

For any consistent $\Sigma$ set of L-sentences, for each $\sigma$ L-sentence, $$ \Sigma \vdash \sigma \iff \forall \mathcal A \models \Sigma, \mathcal A \models \sigma $$

Thus because of completeness of $T$ we have for all L-sentences $\sigma$:

  1. $T \vdash \sigma \implies $ all its models $\mathcal B \models \sigma$
  2. $T \vdash \neg \sigma \implies $ all its models $\mathcal B \models \neg \sigma$

we have a decision from $T$ which implies a decision on every model of it. Since this holds for all sentences then any two models satisfy the same set of L-sentences and thus are elementarily equivalent. So pick any model of $T$ and define $Th(\mathcal B) = \{ \sigma : \mathcal B \models \sigma \}$. Since 1) and 2) are actually IFF's then we have the things $T$ proves are the same as the things true in it's models. Since $T$ is an L-theory then all it proves it contains. Thus, these two facts together means that $T = Th(\mathcal B)$.

($\Leftarrow$) Suppose $\mathcal A \models \Sigma$ and $T = Th(\mathcal A)$. We want to show $T=Th(\mathcal A)$ extends $\Sigma$ and is complete. Since $T$ is defined in terms of a model and models always yield a truth value either $\mathcal A \models \sigma$ (true) or $\mathcal A \models \neg \sigma$ (false), then we have have $T=Th(\mathcal A)$ is complete.

Now we need to show $\Sigma \subseteq T = Th(\mathcal A)$ (extends $\Sigma$). Since $\mathcal A \models \Sigma$ then by definition $\forall \sigma \in \Sigma, \mathcal A \models \sigma$. The condition $\mathcal A \models \sigma $ is the condition we need for being in $Th(\mathcal A)$. Thus, we have $\Sigma \subseteq Th(\mathcal A)$.

$\endgroup$

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.