6
$\begingroup$

Marker Theorem 3.1.4 says: Suppose $T$ is a theory in a language with at least one constant symbol. Then an $L$-formula $\phi(x)$ is $T$-equivalent to a quantifier-free formula iff, whenever $M$ and $N$ are models of $T$, $A \subseteq M$ and $A \subseteq N$, then $M \models \phi(a)$ iff $N \models \phi(a)$ for any $a$ from $A$. -end of theorem

Thus, if we further assume that $T$ is model-complete, then it must follow that $T$ eliminates quantifiers? Where am I going wrong, if it is wrong?

Improve this question
$\endgroup$
3
  • $\begingroup$ Note that in the condition Marker gives as being equivalent to having elimination of quantifiers, $A$ can be any L-structure; in particular, while $M$ and $N$ are required to be models of $T$, $A$ is not. Thus model-completeness of $T$ would not yield this (stronger) condition. $\endgroup$
    – Ed Dean
    Commented Dec 28, 2011 at 23:02
  • $\begingroup$ Ah! I missed that part. This has been bothering me all day, so thank you for the correction. I guess this provides yet another perspective on how/why a model complete theory may fail to eliminate quantifiers: for model complete theories, the above statement only holds whenever A also models T. For theories with qe, the above statement holds for all such substructures A. $\endgroup$
    – atonaltensor
    Commented Dec 28, 2011 at 23:18
  • 2
    $\begingroup$ Ed, why not provide your answer as an answer? The site works best that way. $\endgroup$
    – Joel David Hamkins
    Commented Dec 29, 2011 at 2:16

1 Answer 1

Reset to default
7
$\begingroup$

Per JDH's suggestion, I'll turn my earlier comment into an answer.

Assuming $T$ to be model-complete, then whenever $M$, $N$ and $A$ are all models of $T$, it would certainly follow from $A \subseteq M$ and $A \subseteq N$ that $M \models \phi(a)$ iff $N \models \phi(a)$ for any $a$ from $A$ (as whenever one model of $T$ is a substructure of another, it is in fact an elementary substructure). But in Marker's condition, $A$ can be any $L$-structure and is not required to be a model of $T$.

Any theory that has elimination of quantifiers is model-complete, but the converse is not true. Note that while Marker's Theorem 3.1.4 is stated for a theory in a language with at least one constant symbol, he notes afterward that the proof can be adapted to cover the case in which $L$ has no constant symbols; so if model-completeness were to have sufficed here, it would've implied that the false converse were true.

Incidentally, one very interesting theory which is model-complete yet does not admit elimination of quantifiers is the theory of the real field with exponentiation. This theory isn't known to be decidable, but MacIntyre and Wilkie showed that its decidability is implied by the real version of Schanuel's conjecture. (This nicely succinct postscript file of Kuhlmann's contains handy references.)

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ A simpler (and less interesting) theory which is model complete yet does not admit elimination of quantifiers is the theory of this model $N$ with universe $\mathbb N$: The constant 0 is interpreted as 0, and the relation $R(x,y)$ holds iff $x=1$ and $y>1$. Then the property $x=1$ can be expressed as $\exists y (R(x,y))$, or $x\not=0 \wedge \forall z(\lnot R(z,x))$, but not without quantifiers. With $A=\{0,5\}$, you could imagine a model $M$ containing $A$, where $5$ plays the role of $1$ (i.e., satisfies the formula "$x=1$" given above). $\endgroup$
    – Goldstern
    Commented Dec 29, 2011 at 10:46
  • 1
    $\begingroup$ A corollary of the two characterizations is that a universal theory is model-complete iff it has elimination of quantifiers. $\endgroup$
    – Emil Jeřábek
    Commented Dec 29, 2011 at 12:22
  • 3
    $\begingroup$ A couple of comments: In 3.1.4 the constant is needed if we want our new formula to have the same free variables as the old formula. This is only an issue if the original formula is a sentence and there are no quantifier free sentences in the language. One consequence of model completeness is that the theory has a $\forall\exists$ axiomatization. For the reals with exponentiation it is wide open (even assuming Schanuel's Conjecture) what this axiomatization is. $\endgroup$
    – Dave Marker
    Commented Dec 29, 2011 at 20:31
  • $\begingroup$ A belated comment: as for simpler but still interesting theories that are model-complete but do not admit quantifier elimination, one can take the real field itself (in the language of rings, i.e., without an ordering symbol), or Presburger’s arithmetic (in various variants: the theory of $(\mathbb N,+)$, or $(\mathbb N,+,\le)$, or $(\mathbb Z,+,\le)$, with or without constants $0,1$ or subtraction). $\endgroup$
    – Emil Jeřábek
    Commented Nov 1, 2012 at 15:02

You must log in to answer this question.

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