Embedding and existentially quantified formula

Question

I wanted to prove that given an existentially quantified formula $\varphi(\bar{y})=\exists\bar{x}\psi(\bar{x}, \bar{y})$ and an embedding $f : \mathfrak{M} \hookrightarrow \mathfrak{N}$ between two $\mathscr{L}$-structures $\mathfrak{M}$ and $\mathfrak{N}$, there is for any $\bar{a} \in M^k$, $$\mathfrak{M} \models \varphi(\bar{a}) \Rightarrow \mathfrak{N} \models \varphi(f(\bar{a})). \tag{*}$$

($f(\bar{a})$ denotes $f(a_1), \ldots, f(a_n)$).

I already proven that given a quantifier-free formula $\psi$, $$\mathfrak{M} \models \psi(\bar{a}) \iff \mathfrak{N} \models \varphi(f(\bar{a})) \tag{**}.$$ I have a wrong proof for (*) but wasn't able to figure out wherever was erroneous:

$$ \begin{align*} \mathfrak{M} \models \exists \bar{x} \psi(\bar{x}, \bar{a}) &\iff \textrm{exists $\bar{b} \in M^k$, s.t. $\mathfrak{M} \models \psi(\bar{b}, \bar{a})$} \tag{Definition}\\ &\iff \textrm{exists $f(\bar{b}) \in N^k$, s.t. }\mathfrak{N} \models \psi(f(\bar{b}), f(\bar{a})) \tag{**}\\ & \iff \mathfrak{N} \models \exists\bar{x} \psi(\bar{x}, f(\bar{a})) \tag{Definition} \end{align*} $$

I'm not sure which logical equivalence is wrong.

Answer 1

First let's show that the converse $$\mathfrak{N}\models\varphi(f(\overline{a}))\quad\implies\quad\mathfrak{M}\models\varphi(\overline{a})$$ is false in general; this will help uncover the issue with your proof.

Working in the empty language for simplicity, let $\mathfrak{M}$ be a one-element structure and let $\mathfrak{N}$ be a two-element structure. Let $a$ be the unique element of $\mathfrak{M}$ and fix some $f:\mathfrak{M}\rightarrow\mathfrak{N}$; note that any such $f$ is an embedding. Then we have $$\mathfrak{N}\models\exists x(x\not=f(a))\quad\mbox{but}\quad \mathfrak{M}\models\neg\exists x(x\not=a).$$ So $\exists$-sentences are only "upwards absolute" in general.

---

OK, so based on this where is the issue in your argument?

Well, the problem above was that the witness to the existential statement holding in $\mathfrak{N}$ was not itself in the image of $f$, so it couldn't be "pulled down" to a witness in $\mathfrak{M}$. This shows us the problem in reversing the final implication:

We do have $$\mathfrak{N}\models\varphi(f(\overline{a}))\quad\implies\quad \exists \overline{c}\in\mathfrak{N}\mbox{ such that }\mathfrak{N}\models\psi(\overline{c},f(\overline{a})),$$ but we cannot assume that there is $\overline{b}\in\mathfrak{M}$ such that $f(\overline{b})=\overline{c}$. So we do not have $$\mathfrak{N}\models\varphi(f(\overline{a}))\quad\implies\quad \exists \overline{b}\in\mathfrak{M}\mbox{ such that }\mathfrak{N}\models\psi(f(\overline{b}),f(\overline{a}))$$ in general.