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

2 Answers 2

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$
3
  • $\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, 2018 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$ Dec 15, 2018 at 23:54
  • $\begingroup$ @StefanH Yes, that was a typo! I misunderstood what you were referring to at first. Fixed. $\endgroup$ Dec 16, 2018 at 1:52
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$
3
  • $\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, 2018 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$ Dec 15, 2018 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, 2018 at 21:09

You must log in to answer this question.

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