Let $\mathcal{M}_0$ and $\mathcal{M}_1$ be any interpretations. An embedding of $\mathcal{M}_0$ into $\mathcal{M}_1$ is a function $j:\mid\mathcal{M}_0\mid \rightarrow \mid \mathcal{M}_1\mid$ such that $j$ is injective and the following hold:
For all $a_0,a_1,...a_n\in\mid\mathcal{M}_0\mid$, $R^{\mathcal{M}_0}(a_0, a_1,...,a_n$) iff $R^{\mathcal{M}_1}(j(a_0),j(a_1),...,j(a_n))$.
For all $a_0,a_1,...a_n\in\mid\mathcal{M}_0\mid$, $f^{\mathcal{M}_0}( a_1,...,a_n) = f^{\mathcal{M}_1}(j(a_0),j(a_1),...,j(a_n)) = j(a_0)$.
For each individual constant $c$, $j(c^{\mathcal{M}_0})=c^{\mathcal{M}_1}$
A sentence is existential if it is in the form $\exists x_1,\exists x_2,...,\exists x_n G$ and universal if in the form $\forall x_1,\forall x_2,...,\forall x_nG$.
~~~~~
Show that when F is a quantifier free sentence and there exists an embedding from $\mathcal{M}_0$ to $\mathcal{M}_1$, $\mathcal{M}_0\models F$ iff $\mathcal{M}_1\models F$.
Suppose F is existential and there is the same embedding. Show if $\mathcal{M}_0\models F$ then $\mathcal{M}_1\models F$.
Suppose F is universal and there is the same embedding. Show if $\mathcal{M}_1\models F$ then $\mathcal{M}_0\models F$.
I think the proof is supposed to go something along the lines of the isomorphism lemma except for $j$ isn't a bijection. However I'm really struggling with applying induction on complexity to this. I need to prove all three properties for each question (right?) I'm especially confused about how to correctly go about proving the quantifier cases. I would really appreciate it if someone could start me off in the right direction.
Let $j \colon \mathcal M_0 \to \mathcal M_1$ be an embedding. We first prove that $j(t^{\mathcal M_0}) = t^{\mathcal M_1}$ for all terms $t$ that don't contain any free variables, by induction on the complexity of $t$.
[I leave it up to you to check, that the following actually yields $$j(t^{\mathcal M_0}[a_1, \ldots, a_k]) = t^{\mathcal M_1}[j(a_1), \ldots, j(a_k)]$$ for all $a_1, \ldots, a_k \in \mathcal M_0$.]
If $t \equiv c$ for some constant symbol, then $j(c^{\mathcal M_0}) = c^{\mathcal M_1}$ and thus $j(t^{\mathcal M_0}) = t^{\mathcal M_1}$.
Now suppose that $t = f(t_1, \ldots, t_k)$ for some function symbol $f$ and terms $t_1, \ldots, t_k$ such that $j(t_1^{\mathcal M_0}) = t_1^{\mathcal M_1}, \ldots, j(t_k^{\mathcal M_0}) = t_k^{\mathcal M_1}$. Then $$ \begin{align*} j( \left(f(t_1, \ldots, t_k) \right)^{\mathcal M_0} ) &= j(f^{\mathcal M_0}(t_1^{\mathcal M_0}, \ldots, t_k^{\mathcal M_0}) \\ &= f^{\mathcal M_1}(j(t_1^{\mathcal M_0}), \ldots, j(t_k^{\mathcal M_0})) \\ &= f^{\mathcal M_1}(t_1^{\mathcal M_1}, \ldots, t_1^{\mathcal M_k}) \\ &= \left(f(t_1, \ldots, t_k) \right)^{\mathcal M_1}, \end{align*} $$ i.e. $j(t^{\mathcal M_0}) = t^{\mathcal M_1}$.
Now let $F$ be a sentence without quantifiers. We prove $$\mathcal M_0 \models F \text{ iff } \mathcal M_1 \models F$$ by induction on the complexity of $F$. If $F \equiv R(t_1, \ldots, t_k)$ for some $k$-ary relation symbol $R$ and terms $t_1, \ldots, t_k$, then $$ \begin{align*} \mathcal M_0 \models F &\Leftrightarrow R^{\mathcal M_0}(t_1^{\mathcal M_0}, \ldots, t_k^{\mathcal M_0}) \\ &\Leftrightarrow R^{\mathcal M_1}(j(t_1^{\mathcal M_0}), \ldots, j(t_k^{\mathcal M_0})) \\ &\Leftrightarrow R^{\mathcal M_1}(t_1^{\mathcal M_1}, \ldots, t_k^{\mathcal M_1}) \\ &\Leftrightarrow \mathcal M_1 \models F \end{align*} $$ If $F \equiv t = s$ for terms $t,s$, then $$ \begin{align*} \mathcal M_0 \models F &\Leftrightarrow t^{\mathcal M_0} = s^{\mathcal M_0} \\ &\Leftrightarrow t^{\mathcal M_1} = j(t^{\mathcal M_0}) = j(s^{\mathcal M_0}) = s^{\mathcal M_1} \\ &\Leftrightarrow \mathcal M_1 \models F \end{align*} $$ If $F \equiv \neg G$ and the claim holds for $G$, then $$ \begin{align*} \mathcal M_0 \models F &\Leftrightarrow \mathcal M_0 \not \models G \\ &\Leftrightarrow \mathcal M_1 \not \models G \\ &\Leftrightarrow \mathcal M_1 \models F \end{align*} $$
If $F \equiv G \wedge H$ and the claim holds for $G$ and $H$, then $$ \begin{align*} \mathcal M_0 \models F &\Leftrightarrow \mathcal M_0 G \wedge \mathcal M_0 \models H \\ &\Leftrightarrow \mathcal M_1 \models G \wedge \mathcal M_1 \models H \\ &\Leftrightarrow \mathcal M_1 \models F. \end{align*} $$
If $F \equiv G \vee H$ and the claim holds for $G$ and $H$, then $$ \begin{align*} \mathcal M_0 \models F &\Leftrightarrow \mathcal M_0 G \vee \mathcal M_0 \models H \\ &\Leftrightarrow \mathcal M_1 \models G \vee \mathcal M_1 \models H \\ &\Leftrightarrow \mathcal M_1 \models F. \end{align*} $$
This finishes the proof for quantifier free sentences.
Now let $F = \exists x_1 \ldots \exists x_k G$ for some formula $G$ that contains at most $x_1, \ldots, x_k$ as variables and is quantifier free.
If $\mathcal M_0 \models F$, then there are $m_1, \ldots, m_k$ such that $\mathcal M_0 \models G(m_1, \ldots, m_k)$. Repeat the arguments that I gave for terms (or add new constant symbols $c_1, \ldots, c_k$ and interpret them by $c_1^{\mathcal M_0} = m_1, \ldots, c_k^{\mathcal M_0} = m_k, c_1^{\mathcal M_1} = j(m_1), \ldots, c_k^{\mathcal M_1} = j(m_k)$) to see that this implies $\mathcal M_1 \models G(j(m_1), \ldots, j(m_k))$, i.e. $\mathcal M_1 \models F$.
If $F$ is universal, then $\neg F$ is equivalent to an existential formula. Now
$$ \begin{align*} \mathcal M_1 \models F &\Leftrightarrow \mathcal M_1 \not \models \neg F \\ &\Rightarrow \mathcal M_0 \not \models \neg F \\ &\Leftrightarrow \mathcal M_0 \models F \end{align*} $$
[To see why "$\Rightarrow$" holds: Suppose that $\mathcal M_0 \models \neg F$. Since $F$ is equivalent to an existential formula, we know that this implies $\mathcal M_1 \models \neg F$. Contradiction!]