1

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?

Asaf Karagila
  • 393,674
GJBehar
  • 33

1 Answers1

2

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.

David E
  • 338
user134824
  • 12,212