モデル理論

各 $a\in M$（$A$ の元に限らずすべて）に新しい定数記号 $c_a$ を対応させ $L_M:=L\cup\{c_a\mid a\in M\}$ とし、$M^+$ を $c_a^{M^+}:=a$ で解釈した $L_M$-構造とする。非標準モデルにおける初等拡大の存在定理の証明にならい、$M$ の初等図式 $\mathrm{ElDiag}(M):=\{\sigma \mid \sigma\text{ は }L_M\text{-文},\ M^+\models\sigma\}$ を用いる。
さらに $\bar x=(x_1,\ldots,x_n)$ に対応する新しい定数記号 $\bar d=(d_1,\ldots,d_n)$ を用意し、$L^+:=L_M\cup\{\bar d\}$ とする。$p(\bar x)$ は $A\subset M$ 上の $L_A$-論理式の集合であり $L_A\subset L_M$ なので、$p(\bar d):=\{\varphi(\bar d)\mid\varphi(\bar x)\in p(\bar x)\}$（各 $x_i$ を $d_i$ に、各パラメータ $a\in A$ を $c_a$ に置き換えたもの）は $L^+$-文の集合になる。
$$ \Gamma:=\mathrm{ElDiag}(M)\cup p(\bar d) $$
とおく。
有限充足可能性。 $\Gamma$ の任意の有限部分集合 $\Gamma_0$ は、$\mathrm{ElDiag}(M)$ からの有限個の文 $T_0$ と、$p(\bar d)$ からの有限個の文 $p_0(\bar d)$（$p_0(\bar x)\subset p(\bar x)$ は有限）からなる。$p$ は $M$ における $A$ 上の型なので、$p_0$ の有限充足可能性の定義により、ある $\bar b\in M^n$ が存在して $M\models\bigwedge p_0(\bar b)$ となる。$M^+$ をさらに $d_i^{M^+}:=b_i$（$i=1,\ldots,n$）と解釈して $L^+$-構造に拡張すれば、$T_0\subset\mathrm{ElDiag}(M)$ の文はすべて $M^+$ で真であり（$\mathrm{ElDiag}(M)$ の定義そのもの）、$p_0(\bar d)$ の各文も $\bar d$ を $\bar b$ と解釈した下で $M\models\bigwedge p_0(\bar b)$ から真になる。よって $\Gamma_0$ はこの拡張された $M^+$ によりモデルを持つ。
$\Gamma$ の任意の有限部分集合がモデルを持つので、コンパクト性定理により $\Gamma$ 自身がある $L^+$-構造 $N^+$ のモデルを持つ。$N$ を $N^+$ の $L$-簡約とし、$h:M\to N$ を $h(a):=c_a^{N^+}$ で定める。$h$ が初等埋め込みであることを示す。$\bar a\in M^n$、$L$-論理式 $\varphi(\bar x)$ とする。$M\models\varphi(\bar a)$ なら $\varphi(\bar c_{\bar a})\in\mathrm{ElDiag}(M)\subset\Gamma$ であり $N^+\models\Gamma$ だから $N^+\models\varphi(\bar c_{\bar a})$、すなわち $N\models\varphi(h(\bar a))$ である。逆に $M\not\models\varphi(\bar a)$ なら $M\models\lnot\varphi(\bar a)$ だから $\lnot\varphi(\bar c_{\bar a})\in\mathrm{ElDiag}(M)\subset\Gamma$ となり、同様に $N\models\lnot\varphi(h(\bar a))$、すなわち $N\not\models\varphi(h(\bar a))$ である。よって $M\models\varphi(\bar a)\iff N\models\varphi(h(\bar a))$ が成り立つ。$h$ の単射性は、$a\neq a'$（$a,a'\in M$）なら $\mathrm{ElDiag}(M)$ に文 $c_a\neq c_{a'}$ が含まれるので $N^+\models c_a\neq c_{a'}$、すなわち $h(a)\neq h(a')$ となることによる。以上より $h$ は初等埋め込みである。$h$ を通じて $M$ を $h(M)\subset N$ と同一視すれば $M\prec N$ である。
最後に $\bar b:=(d_1^{N^+},\ldots,d_n^{N^+})\in N^n$ とおく。$p(\bar d)\subset\Gamma$ かつ $N^+\models\Gamma$ なので、$p(\bar x)$ の各論理式 $\varphi(\bar x)$ について $N^+\models\varphi(\bar d)$、すなわち $\bar d$ を $\bar b$ と、$L_A$ の定数 $c_a$（$a\in A$）を $h(a)$ と対応づければ $N\models\varphi(\bar b)$（パラメータを $A\subset M$ から $h(A)\subset N$ へ、$M\prec N$ の同一視のもとで読み替えたもの）が成り立つ。ゆえに $N$ において $p$ は $\bar b$ により実現される。

$g\circ f$ は単射どうしの合成なので単射である。任意の $L$-論理式 $\varphi(\bar x)$ と $\bar a\in M^n$ を取る。$f$ が初等埋め込みであることから
$$ M\models\varphi(\bar a)\iff N\models\varphi(f(\bar a)) $$
が成り立つ。$f(\bar a)\in N^n$ であり、$g$ が初等埋め込みであることから
$$ N\models\varphi(f(\bar a))\iff P\models\varphi(g(f(\bar a))) $$
が成り立つ。二つの同値をつなげると
$$ M\models\varphi(\bar a)\iff P\models\varphi\bigl((g\circ f)(\bar a)\bigr) $$
を得る。$\varphi,\bar a$ は任意だったから、$g\circ f$ は初等埋め込みである。