Properties of quantifiers on embeddings and interpretations 
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.
 A: 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!]
