[proofplan] Apply first-order compactness to the $L^*$-theory $\operatorname{Diag}_{\mathrm{el}}(M) \cup \Gamma$. A model of this theory interprets all constants $c_a$ and all additional symbols of $L^*$. The elementary diagram forces the interpretation map $a \mapsto c_a^{N^*}$ to preserve and reflect every $L$-formula with parameters from $M$, hence gives an elementary embedding of $M$ into the $L$-reduct of $N^*$. Finally, the same model satisfies every sentence in $\Gamma$. [/proofplan]

[step:Use compactness to obtain a model of the full expanded theory]Define the $L^*$-theory \begin{align*} T := \operatorname{Diag}_{\mathrm{el}}(M) \cup \Gamma. \end{align*} By hypothesis, every finite subset of $T$ has an $L^*$-model. Therefore, by the [Compactness Theorem](/theorems/2748) (citing a result not yet in the wiki: Compactness Theorem), there exists an $L^*$-structure $N^*$ such that \begin{align*} N^* \models T. \end{align*} In particular, \begin{align*} N^* \models \operatorname{Diag}_{\mathrm{el}}(M) \qquad\text{and}\qquad N^* \models \Gamma. \end{align*}[/step]

[guided]We package all requirements into one first-order theory: \begin{align*} T := \operatorname{Diag}_{\mathrm{el}}(M) \cup \Gamma. \end{align*} This is a set of $L^*$-sentences because $L^*$ expands $L(M)$, so every sentence of the elementary diagram and every sentence in $\Gamma$ belongs to the same language $L^*$. The hypothesis says exactly that every finite subset of this theory has a model. The Compactness Theorem states that if every finite subset of a first-order theory is satisfiable, then the whole theory is satisfiable. Applying compactness to $T$, we obtain an $L^*$-structure $N^*$ satisfying \begin{align*} N^* \models T. \end{align*} Since $T$ is the union of $\operatorname{Diag}_{\mathrm{el}}(M)$ and $\Gamma$, this means \begin{align*} N^* \models \operatorname{Diag}_{\mathrm{el}}(M) \qquad\text{and}\qquad N^* \models \Gamma. \end{align*} The first part will build the elementary copy of $M$; the second part records that all additional requirements imposed by $\Gamma$ are satisfied in the same expanded structure.[/guided]

[step:Define the candidate elementary embedding using the named constants]Let $N$ be the $L$-reduct of $N^*$. Define the map \begin{align*} j: M &\to N \\ a &\mapsto c_a^{N^*}. \end{align*} This map is injective. Indeed, if $a,b \in M$ and $a \neq b$, then the $L(M)$-sentence $c_a \neq c_b$ belongs to $\operatorname{Diag}_{\mathrm{el}}(M)$, because it is true in the canonical $L(M)$-expansion of $M$. Since $N^* \models \operatorname{Diag}_{\mathrm{el}}(M)$, we have \begin{align*} c_a^{N^*} \neq c_b^{N^*}. \end{align*} Thus $j(a) \neq j(b)$ whenever $a \neq b$.[/step]

[guided]The constants in the language $L(M)$ are designed to name the elements of $M$. Since $N^*$ is an $L^*$-structure and $L^*$ contains $L(M)$, each symbol $c_a$ has an interpretation $c_a^{N^*}$ in the universe of $N^*$. Let $N$ be the $L$-reduct of $N^*$. This means that $N$ has the same underlying set as $N^*$ but remembers only the symbols from $L$. We define \begin{align*} j: M &\to N \\ a &\mapsto c_a^{N^*}. \end{align*} We must first check that this map does not collapse two different elements of $M$. Suppose $a,b \in M$ with $a \neq b$. In the canonical $L(M)$-expansion of $M$, the constants $c_a$ and $c_b$ are interpreted as distinct elements, so the sentence $c_a \neq c_b$ is true there. Hence \begin{align*} c_a \neq c_b \in \operatorname{Diag}_{\mathrm{el}}(M). \end{align*} Because $N^*$ satisfies the elementary diagram, it satisfies this sentence: \begin{align*} N^* \models c_a \neq c_b. \end{align*} Equivalently, \begin{align*} c_a^{N^*} \neq c_b^{N^*}. \end{align*} Therefore $j(a) \neq j(b)$, so $j$ is injective.[/guided]

[step:Show that the constant map preserves every formula with parameters from $M$]Let $\varphi(x_1,\dots,x_n)$ be an $L$-formula, and let $a_1,\dots,a_n \in M$. Consider the $L(M)$-sentence \begin{align*} \varphi(c_{a_1},\dots,c_{a_n}). \end{align*} If \begin{align*} M \models \varphi(a_1,\dots,a_n), \end{align*} then $\varphi(c_{a_1},\dots,c_{a_n}) \in \operatorname{Diag}_{\mathrm{el}}(M)$, so \begin{align*} N^* \models \varphi(c_{a_1},\dots,c_{a_n}). \end{align*} Since $\varphi$ is an $L$-formula and $N$ is the $L$-reduct of $N^*$, this is equivalent to \begin{align*} N \models \varphi(j(a_1),\dots,j(a_n)). \end{align*} Conversely, if \begin{align*} M \not\models \varphi(a_1,\dots,a_n), \end{align*} then \begin{align*} M \models \neg \varphi(a_1,\dots,a_n), \end{align*} so $\neg\varphi(c_{a_1},\dots,c_{a_n}) \in \operatorname{Diag}_{\mathrm{el}}(M)$. Hence \begin{align*} N^* \models \neg\varphi(c_{a_1},\dots,c_{a_n}), \end{align*} and therefore \begin{align*} N \not\models \varphi(j(a_1),\dots,j(a_n)). \end{align*} Thus, for every $L$-formula $\varphi(x_1,\dots,x_n)$ and every tuple $(a_1,\dots,a_n) \in M^n$, \begin{align*} M \models \varphi(a_1,\dots,a_n) \iff N \models \varphi(j(a_1),\dots,j(a_n)). \end{align*}[/step]

[guided]To prove that $j$ is elementary, we must show that it preserves and reflects truth of all $L$-formulas with parameters from $M$. Let $\varphi(x_1,\dots,x_n)$ be an arbitrary $L$-formula, and choose elements $a_1,\dots,a_n \in M$. The corresponding $L(M)$-sentence is \begin{align*} \varphi(c_{a_1},\dots,c_{a_n}). \end{align*} If this formula is true of the tuple $(a_1,\dots,a_n)$ in $M$, then this sentence is true in the canonical expansion of $M$ by the constants $c_a$. By the definition of the elementary diagram, it belongs to $\operatorname{Diag}_{\mathrm{el}}(M)$. Since $N^*$ satisfies the elementary diagram, we get \begin{align*} N^* \models \varphi(c_{a_1},\dots,c_{a_n}). \end{align*} Because $\varphi$ uses only symbols from $L$, its truth is unchanged when passing from the expanded structure $N^*$ to its $L$-reduct $N$. Therefore \begin{align*} N \models \varphi(j(a_1),\dots,j(a_n)). \end{align*} For the reverse implication, suppose $\varphi(a_1,\dots,a_n)$ is not true in $M$. Then its negation is true: \begin{align*} M \models \neg \varphi(a_1,\dots,a_n). \end{align*} Thus the sentence \begin{align*} \neg\varphi(c_{a_1},\dots,c_{a_n}) \end{align*} belongs to $\operatorname{Diag}_{\mathrm{el}}(M)$. Since $N^*$ satisfies the elementary diagram, \begin{align*} N^* \models \neg\varphi(c_{a_1},\dots,c_{a_n}), \end{align*} and again reducing to the $L$-structure $N$ gives \begin{align*} N \not\models \varphi(j(a_1),\dots,j(a_n)). \end{align*} Combining the two directions, we have shown that for every $L$-formula $\varphi(x_1,\dots,x_n)$ and every tuple $(a_1,\dots,a_n) \in M^n$, \begin{align*} M \models \varphi(a_1,\dots,a_n) \iff N \models \varphi(j(a_1),\dots,j(a_n)). \end{align*} This is exactly the Tarski criterion for $j$ to be an elementary embedding.[/guided]

[step:Identify $M$ with its elementary image and retain the additional requirements] The preceding step shows that $j: M \to N$ is an elementary embedding. Since $j$ is injective, its image $j(M) \subset N$ is an elementary copy of $M$ inside the $L$-structure $N$. Identifying each $a \in M$ with $j(a) = c_a^{N^*}$, we may regard $M$ as an elementary substructure of $N$ and write \begin{align*} N \succeq M. \end{align*} Moreover, from the construction of $N^*$ we already have \begin{align*} N^* \models \Gamma. \end{align*} Thus the expanded structure $N^*$ realizes all additional constants, relations, functions, and sentence requirements imposed by $\Gamma$, while its $L$-reduct contains an elementary copy of $M$. [/step]