most recent 30 from http://mathoverflow.net 2013-05-24T12:57:10Z http://mathoverflow.net/feeds/question/84481 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84481/does-model-complete-in-a-language-with-a-constant-symbol-imply-eq atonaltensor 2011-12-28T22:01:32Z 2011-12-29T12:19:26Z

<p>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 </p> <p>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?</p>

http://mathoverflow.net/questions/84481/does-model-complete-in-a-language-with-a-constant-symbol-imply-eq/84488#84488 Ed Dean 2011-12-29T03:00:08Z 2011-12-29T03:45:18Z

<p>Per JDH's suggestion, I'll turn my earlier comment into an answer.</p> <hr> <p>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$.</p> <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Schanuel%27s_conjecture" rel="nofollow">Schanuel's conjecture</a>. (This nicely succinct <a href="http://math.usask.ca/~skuhlman/Encsels.ps" rel="nofollow">postscript file</a> of Kuhlmann's contains handy references.)</p>