[proofplan] We prove both implications using the preservation behaviour of existential formulas under embeddings. If $T$ is model complete, then every formula is preserved under embeddings between models of $T$, so the existential preservation theorem relative to $T$ gives an existential formula equivalent to it modulo $T$. Conversely, if every formula is equivalent modulo $T$ to an existential one, then an embedding between models of $T$ preserves truth of every formula; applying the same hypothesis to negations gives reflection of truth, hence elementarity. [/proofplan] [step:Use model completeness to obtain preservation under embeddings] Assume that $T$ is model complete. Let $x = (x_1,\dots,x_n)$ be a finite tuple of variables, and let $\varphi(x)$ be an $L$-formula. Let $M$ and $N$ be models of $T$, let \begin{align*} f: M &\to N \end{align*} be an $L$-embedding, and let $a = (a_1,\dots,a_n) \in M^n$. Since $T$ is model complete, the embedding $f$ is elementary. Therefore, by the definition of elementary embedding, \begin{align*} M \models \varphi(a) \quad\Longleftrightarrow\quad N \models \varphi(f(a)), \end{align*} where $f(a) := (f(a_1),\dots,f(a_n)) \in N^n$. In particular, the class of pointed models $(M,a)$ with $M \models T$ and $M \models \varphi(a)$ is preserved under $L$-embeddings between models of $T$. [guided] Assume that $T$ is model complete. We must show that an arbitrary formula $\varphi(x)$ is equivalent modulo $T$ to an existential formula. Fix a finite tuple of variables $x = (x_1,\dots,x_n)$ and an $L$-formula $\varphi(x)$. Consider two models $M \models T$ and $N \models T$, an $L$-embedding \begin{align*} f: M &\to N, \end{align*} and a tuple $a = (a_1,\dots,a_n) \in M^n$. The phrase “$T$ is model complete” means exactly that every such embedding between models of $T$ is elementary. Thus $f$ preserves and reflects the truth of every first-order formula with parameters from $M$. Applying this to the formula $\varphi(x)$ and the tuple $a$, we get \begin{align*} M \models \varphi(a) \quad\Longleftrightarrow\quad N \models \varphi(f(a)), \end{align*} where $f(a) := (f(a_1),\dots,f(a_n))$. This is the preservation condition needed for the next step: the definable class determined by $\varphi$ is stable under embeddings between models of $T$. [/guided] [/step] [step:Apply the existential preservation theorem relative to $T$] By the existential preservation theorem relative to a theory, a formula is equivalent modulo $T$ to an existential formula if and only if its truth is preserved under embeddings between models of $T$ (citing a result not yet in the wiki: Existential Preservation Theorem relative to a theory). The preservation condition was verified in the previous step for $\varphi(x)$. Hence there exists an existential $L$-formula $\psi(x)$ such that \begin{align*} T \models \forall x\,\bigl(\varphi(x) \leftrightarrow \psi(x)\bigr). \end{align*} This proves condition $2$. [guided] We now use the model-theoretic preservation theorem appropriate to existential formulas. The theorem says: for an $L$-theory $T$ and an $L$-formula $\varphi(x)$, the formula $\varphi(x)$ is equivalent modulo $T$ to an existential $L$-formula if and only if, whenever $f: M \to N$ is an $L$-embedding between models of $T$ and $a \in M^n$, truth of $\varphi(a)$ in $M$ implies truth of $\varphi(f(a))$ in $N$. The previous step verifies this hypothesis, and in fact proves the stronger equivalence \begin{align*} M \models \varphi(a) \quad\Longleftrightarrow\quad N \models \varphi(f(a)). \end{align*} Therefore the preservation theorem applies to $\varphi(x)$. We obtain an existential $L$-formula $\psi(x)$ satisfying \begin{align*} T \models \forall x\,\bigl(\varphi(x) \leftrightarrow \psi(x)\bigr). \end{align*} Since $\varphi(x)$ was arbitrary, every formula is equivalent modulo $T$ to an existential formula. [/guided] [/step] [step:Use existential equivalents to prove preservation of all formulas] Assume condition $2$. Let $M \models T$ and $N \models T$, and let \begin{align*} f: M &\to N \end{align*} be an $L$-embedding. We prove that $f$ is elementary. Let $x = (x_1,\dots,x_n)$ be a finite tuple of variables, let $\varphi(x)$ be an $L$-formula, and let $a = (a_1,\dots,a_n) \in M^n$. By condition $2$, choose an existential $L$-formula $\psi(x)$ such that \begin{align*} T \models \forall x\,\bigl(\varphi(x) \leftrightarrow \psi(x)\bigr). \end{align*} If $M \models \varphi(a)$, then $M \models \psi(a)$. Existential formulas are preserved under $L$-embeddings, so $N \models \psi(f(a))$. Since $N \models T$, the displayed $T$-equivalence gives $N \models \varphi(f(a))$. Thus \begin{align*} M \models \varphi(a) \quad\Longrightarrow\quad N \models \varphi(f(a)). \end{align*} [guided] Now assume that every formula is equivalent modulo $T$ to an existential formula. We must prove that an arbitrary embedding between models of $T$ is elementary. Let $M \models T$ and $N \models T$, and let \begin{align*} f: M &\to N \end{align*} be an $L$-embedding. Fix a finite tuple of variables $x = (x_1,\dots,x_n)$, an $L$-formula $\varphi(x)$, and a tuple $a = (a_1,\dots,a_n) \in M^n$. By the hypothesis, there is an existential $L$-formula $\psi(x)$ such that \begin{align*} T \models \forall x\,\bigl(\varphi(x) \leftrightarrow \psi(x)\bigr). \end{align*} Because $M \models T$, this equivalence holds in $M$; because $N \models T$, it also holds in $N$. Suppose first that $M \models \varphi(a)$. Then $M \models \psi(a)$. Since $\psi$ is existential, it has the form $\exists y\,\theta(x,y)$ with $\theta$ quantifier-free, after renaming bound variables if necessary. Thus there is a tuple $b \in M^m$ such that \begin{align*} M \models \theta(a,b). \end{align*} An $L$-embedding preserves quantifier-free formulas, so \begin{align*} N \models \theta(f(a),f(b)). \end{align*} Hence $N \models \psi(f(a))$. Using the equivalence between $\psi$ and $\varphi$ in the model $N$, we conclude \begin{align*} N \models \varphi(f(a)). \end{align*} So $f$ preserves truth of $\varphi$ from $M$ to $N$. [/guided] [/step] [step:Apply the hypothesis to negations to reflect all formulas] Apply condition $2$ to the formula $\neg\varphi(x)$. Choose an existential $L$-formula $\chi(x)$ such that \begin{align*} T \models \forall x\,\bigl(\neg\varphi(x) \leftrightarrow \chi(x)\bigr). \end{align*} Suppose $N \models \varphi(f(a))$ and, toward a contradiction, $M \not\models \varphi(a)$. Then $M \models \neg\varphi(a)$, so $M \models \chi(a)$. Since $\chi$ is existential and $f$ is an $L$-embedding, existential preservation gives $N \models \chi(f(a))$. Since $N \models T$, this implies $N \models \neg\varphi(f(a))$, contradicting $N \models \varphi(f(a))$. Therefore \begin{align*} N \models \varphi(f(a)) \quad\Longrightarrow\quad M \models \varphi(a). \end{align*} Together with the previous step, \begin{align*} M \models \varphi(a) \quad\Longleftrightarrow\quad N \models \varphi(f(a)). \end{align*} [guided] Preservation alone is not enough for elementarity: an elementary embedding must preserve and reflect truth. To get reflection, we use the same existential-equivalence hypothesis on the negation of the formula. Apply condition $2$ to $\neg\varphi(x)$. There is an existential $L$-formula $\chi(x)$ such that \begin{align*} T \models \forall x\,\bigl(\neg\varphi(x) \leftrightarrow \chi(x)\bigr). \end{align*} Assume $N \models \varphi(f(a))$. We prove $M \models \varphi(a)$. Suppose instead that $M \not\models \varphi(a)$. Since first-order satisfaction is two-valued, \begin{align*} M \models \neg\varphi(a). \end{align*} Because $M \models T$, the displayed equivalence gives \begin{align*} M \models \chi(a). \end{align*} The formula $\chi$ is existential, and existential formulas are preserved under $L$-embeddings. Therefore \begin{align*} N \models \chi(f(a)). \end{align*} Since $N \models T$, the equivalence for $\chi$ in $N$ gives \begin{align*} N \models \neg\varphi(f(a)). \end{align*} This contradicts the assumption $N \models \varphi(f(a))$. Hence the supposition was false, and $M \models \varphi(a)$. Combining this reflection implication with preservation from the previous step, we have \begin{align*} M \models \varphi(a) \quad\Longleftrightarrow\quad N \models \varphi(f(a)). \end{align*} [/guided] [/step] [step:Conclude that every embedding between models of $T$ is elementary] The formula $\varphi(x)$ and tuple $a \in M^n$ were arbitrary. Hence for every $L$-formula $\varphi(x)$ and every tuple $a$ from $M$ of the same length, \begin{align*} M \models \varphi(a) \quad\Longleftrightarrow\quad N \models \varphi(f(a)). \end{align*} By the definition of elementary embedding, $f: M \to N$ is elementary. Since $M$, $N$, and $f$ were arbitrary, every embedding between models of $T$ is elementary. Therefore $T$ is model complete. [/step]