0
$\begingroup$

Let $T$ be a theory in first order logic over some language $L$. Let $\mathfrak A$ be some structure over $L$ with $\mathfrak A \models T$ and with $A$ be its universe. Then consider every $a \in A$ as a constant and look at the enriched language $L(A) = L \cup A$ with the $L(A)$-structure $\mathfrak A_A = (\mathfrak A, a)_{a\in A}$. A formula over $L(A)$ is called basic if it is an atomic formula. The set $$ \operatorname{Diag}(\mathfrak A) = \{ \varphi \mbox{ is a basic $L(A)$-sentence } \mid \mathfrak A_A \models \varphi \} $$ is called the atomic diagram of $\mathfrak A$.

A theory $T$ is called model-complete if every substructure relation between two models is actually an elementary embedding.

Then $T$ is model-complete if and only if for any $\mathfrak A \models T$ the theory $T \cup \operatorname{Diag}(\mathfrak A)$ is complete.

These definitions are from A course in model theory by K.Tent/M.Zeigler.

I do not understand the quoted statement. For let $t_1 = t_2$ and $t_3 \ne t_4$ be two atomic sentences for terms $t_1, t_2,t_3,t_4$ in $L(A)$. Then Set $\varphi = (t_1 = t_2) \land (t_3 \ne t_4)$. Now suppose in the terms we have some constants from $A$. Then neither $\varphi$ nor $\neg \varphi$ is in $T \cup \operatorname{Diag}(\mathfrak A)$ as it is not in $\operatorname{Diag}(\mathfrak A)$ for it is not atomic, nor is it in $T$ as it is a statement over the enrichted language $L(A)$, but not over $L$. Could someone please explain the above statement (and what I oversee here...)?

$\endgroup$
2
$\begingroup$

Complete means for any sentence $\varphi,$ either $T\vdash \varphi$ or $T\vdash \lnot \varphi,$ not $\varphi\in T$ or $\lnot\varphi\in T.$

If $\mathfrak A,\mathfrak B\models T$ and $\mathfrak A\subseteq \mathfrak B,$ then both are models of $T\cup Diag(\mathfrak A).$ If $T\cup Diag(\mathfrak A)$ is complete, then they must agree on all $L(A)$-sentences, and hence the embedding is elementary. On the other hand if $T\cup Diag(\mathfrak A)$ is not complete for some $\mathfrak A\models T,$ then we can find a $\mathfrak B\models T$ with $\mathfrak A\subseteq \mathfrak B$ that differs from $\mathfrak A$ on some $L(A)$-sentence (just let it be a model of the negation of some $\varphi$ that is true in $\mathfrak A$ but that $T\cup Diag(\mathfrak A)$ does not decide). Hence this embedding is not elementary.

$\endgroup$
  • $\begingroup$ What makes you sure that such a model $\mathfrak B$ of $T \cup Diag(\mathfrak A) \cup \{\neg \varphi\}$ exists that contains $\mathfrak A$ as an $L$-structure? $\endgroup$ – StefanH Dec 15 '18 at 17:58
  • $\begingroup$ @StefanH The whole point of the diagram of $A$ is that any model of it contains an isomorphic copy of $A$ as a substructure (via the interpretation of the constant symbols). $\endgroup$ – Alex Kruckman Dec 15 '18 at 18:12
  • $\begingroup$ Got it, just needs additionally that completeness of a theory is equivalent with the property that all models are elementary equivalent, then surely non-completeness lets us choose such a model. $\endgroup$ – StefanH Dec 16 '18 at 21:09
4
$\begingroup$

You have two errors here:

  1. "$T$ is complete" means that for every sentence $\varphi$, $T\models \varphi$ or $T\models \lnot\varphi$. It does not mean that $\varphi\in T$ or $\lnot \varphi\in T$.

  2. A basic formula is not just an atomic formula. It is an atomic formula or a negation of an atomic formula.

In your example, if $\mathfrak{A}\models \varphi$, then $t_1 = t_2\in \text{Diag}(\mathfrak{A})$ and $t_3\neq t_4\in \text{Diag}(\mathfrak{A})$, so $T\cup \text{Diag}(\mathfrak{A})\models \varphi$. Otherwise, if $\mathfrak{A}\not\models \varphi$, then either $t_1\neq t_2\in \text{Diag}(\mathfrak{A})$ or $t_3 = t_4\in \text{Diag}(\mathfrak{A})$, and in either case $T\cup \text{Diag}(\mathfrak{A})\models \lnot \varphi$.

It's an easy exercise to show that for any structure $\mathfrak{A}$ and any quantifier-free $L(A)$-sentence $\varphi$, either $\text{Diag}(\mathfrak{A})\models \varphi$ or $\text{Diag}(\mathfrak{A})\models \lnot \varphi$. The interesting fact is that $T$ is model complete if and only if $T\cup\text{Diag}(\mathfrak{A})$ decides the truth of all $L(A)$-formulas, even those with quantifiers. The answer by spaceisdarkgreen explains the easy proof of this fact.

$\endgroup$
  • $\begingroup$ Guess you mean $T \cup \operatorname{Diag}(\mathfrak A)$ decides the truth of all $L(A)$-formulas, not just $\operatorname{Diag}(\mathfrak A)$? $\endgroup$ – StefanH Dec 15 '18 at 17:52
  • 1
    $\begingroup$ @StefanH "All extensions of $\mathfrak A$ are elementary" means exactly the same thing as "$Diag(\mathfrak A)$ is complete." If this holds and $\mathfrak A\models T,$ then all the extensions are models of $T$ as well. "$T$ is model complete" means all models of $T$ have this property. $\endgroup$ – spaceisdarkgreen Dec 15 '18 at 23:54
  • $\begingroup$ @StefanH Yes, that was a typo! I misunderstood what you were referring to at first. Fixed. $\endgroup$ – Alex Kruckman Dec 16 '18 at 1:52

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.