# Preservation theorem of $\exists \forall$ sentences

This is actually parts of an exercise I found in W.Hodges' shorter model theory (P.147):

Let $\mathcal{L}$ be a first-order language and T a theory in $\mathcal{L}$. Also let $\mathcal{A}$ and $\mathcal{B}$ are models of T and $\mathcal{C}$ is an $\mathcal{L}$-structure such that $\mathcal{A} \subseteq \mathcal{C} \subseteq \mathcal{B}$. If T is equivalent to a set of $\exists \forall$-sentences and $\mathcal{A} \preccurlyeq_2 \mathcal{B}$ (i.e. for every $\exists \forall$-formula $\phi(\bar{x})$ of $\mathcal{L}$ and every tuple $\bar{a}$ of elements of $\mathcal{A}$, $\mathcal{B} \models \phi(\bar{a})$ implies $\mathcal{A} \models\phi(\bar{a})$), then $\mathcal{C}$ is also a model of T.

I think if we can show that $\mathcal{C}\models \exists \bar{x}\forall\bar{y} \phi(\bar{x},\bar{y})$ whenever $\mathcal{A},\mathcal{B} \models\exists \bar{x}\forall\bar{y} \phi(\bar{x},\bar{y})$ with $\mathcal{A} \subseteq \mathcal{C} \subseteq \mathcal{B}$, then we are done.

But I have no idea how to get this conclusion.

Any hints/helps are welcomed. Thank you !

You're moving in the right direction; let me sketch how to keep going.

Suppose $\varphi=\exists x\forall y\theta(x, y)$ is an $\exists\forall$-sentence (so $\theta$ is quantifier-free). For a structure $\mathcal{M}$ in the relevant language, say that $m\in \mathcal{M}$ is an $\mathcal{M}$-witness to $\varphi$ if $\mathcal{M}\models\forall y\theta(m, y)$.

The following is easy to prove, and probably you've already done it or seen it:

Suppose $\mathcal{M}\subseteq\mathcal{N}$ and $m\in\mathcal{M}$ is an $\mathcal{N}$-witness to $\varphi$. Then $m$ is an $\mathcal{M}$-witness to $\varphi$.

Basically, universal formulas which hold "up above" continue to hold "down below."

Fix $\mathcal{A},\mathcal{B},\mathcal{C}$ as in the problem, and an $\exists\forall$-sentence $\varphi(x, y)=\exists x\forall y\theta(x, y)$ in the relevant language such that $\mathcal{A},\mathcal{B}\models\varphi$. Since $\mathcal{A}\models\varphi$, let $a\in\mathcal{A}$ be an $\mathcal{A}$-witness to $\varphi$. You now can easily show:

If we can show that $a$ is also a $\mathcal{B}$-witness to $\varphi$, we'll be done.

This is where elementarity comes in:

Show that since $\mathcal{A}\preccurlyeq_2\mathcal{B}$, $a$ is indeed a $\mathcal{B}$-witness to $\varphi$.

HINT: find the right formula to describe what's going on in $\mathcal{A}$ ...

(Incidentally, unless I'm missing something we don't need $\preccurlyeq_2$; just being able to transfer $\Pi_1$-formulas from $\mathcal{A}$ to $\mathcal{B}$ should be enough.)

• Thanks for your hint! But I still cannot see why $\mathcal{A}\preccurlyeq_2 \mathcal{B}$ implies the preservation of $\Pi_1$-formulas from $\mathcal{A}$ to $\mathcal{B}$ since $\mathcal{A}\preccurlyeq_2 \mathcal{B}$ is a downward condition about $\exists \forall$-sentence with $\mathcal{A}$-witness. – Max CYLin Feb 1 '18 at 3:47
• @MaxCYLin Note that a downwards preservation for a $\Gamma$-formula is equivalent to an upwards presentation for a $\neg\Gamma$-formula for a complexity class $\Gamma$. We want upwards preservation for $\forall$, and we have downwards preservation for $\exists\forall$ ... – Noah Schweber Feb 5 '18 at 17:41