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?

  • $\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 Dec 28 '11 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 Dec 28 '11 at 23:18
  • 2
    $\begingroup$ Ed, why not provide your answer as an answer? The site works best that way. $\endgroup$ – Joel David Hamkins Dec 29 '11 at 2:16

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.)

  • 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 Dec 29 '11 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 supports Monica Dec 29 '11 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 Dec 29 '11 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 supports Monica Nov 1 '12 at 15:02

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.