I've been reading D. Marker's book on Model theory. In the part dealing with quantifier elimination there's a corollary I've been trying to prove without any luck:

Corollary 3.1.6 Let $T$ be an $L$-theory. Suppose that for all quantifier-free formulas $\phi(\bar{v},w)$, if $M,N\models T$, $A$ is a common substructure of $M$ and $N$, $\bar{a} \in A$, and there is $b \in M$ such that $M\models \phi(\bar{a},b) $ then there is $c \in N$ such that $N\models \phi(\bar{a},c)$. Then T has quantifier elimination.

How can one prove this?

  • 4
    $\begingroup$ It might be helpful to add what this is a corollary to, for context $\endgroup$
    – Alan
    Mar 6 '15 at 14:22

This follows from Theorem 3.1.4 and Lemma 3.1.5, as follows.

We want to show that $T$ has quantifier elimination, given the hypotheses of the theorem. That is, given a formula $\varphi$, we want to find a quantifier-free formula $\psi$ such that $T\models\varphi\leftrightarrow\psi$. By Lemma 3.1.5, it suffices to assume that $\varphi=\varphi(\bar v)$ is of the form $\exists w\;\theta(w,\bar v)$.

To show that such a $\psi$ can be found, we use the criterion of Theorem 3.1.4. Namely, we need to check that if $M$ and $N$ are models of $T$ with a common substructure $A$ then, for every $\bar a\in A^n$, $M\models\varphi(\bar a)\iff N\models\varphi(\bar a)$. But, because of the structure of $\varphi$, this is the same as saying that there is an $b\in M$ such that $M\models\theta(b,\bar a)$ if and only if there is a $c\in N$ such that $M\models\theta(c,\bar a)$. And that hypothesis is precisely what we assumed for Corollary 3.1.6.


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.