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

  • $\begingroup$ 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. $\endgroup$ – Max CYLin Feb 1 '18 at 3:47
  • $\begingroup$ @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$ ... $\endgroup$ – Noah Schweber Feb 5 '18 at 17:41

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.