初等同値

1 ⇔ 2 は定義そのものである。2 ⇒ 3 は明らかで、3 と 4 は $\operatorname{Th}(\mathcal N)$ の定義により同じことを述べている。
3 ⇒ 2：$\sigma\in\operatorname{Th}(\mathcal N)$ とする。$\sigma\notin\operatorname{Th}(\mathcal M)$ と仮定すると、否定の充足の定義により $\lnot\sigma\in\operatorname{Th}(\mathcal M)$ であり、3 により $\lnot\sigma\in\operatorname{Th}(\mathcal N)$ となる。これは $\sigma\in\operatorname{Th}(\mathcal N)$ と両立しない。よって $\sigma\in\operatorname{Th}(\mathcal M)$ であり、$\operatorname{Th}(\mathcal N)\subset\operatorname{Th}(\mathcal M)$ が示された。
最後の主張は、2 の形にすれば集合の等号の性質である。$\square$

$M=\{a_1,\dots,a_n\}$（相異なる $n$ 個の元）とする。
段 1（元の個数）． 文
$$ \varepsilon_n:=\exists x_1\cdots\exists x_n\Bigl(\bigwedge_{1\le i< j\le n}\lnot(x_i=x_j)\land\forall y\,\bigvee_{i=1}^n y=x_i\Bigr) $$
は「元がちょうど $n$ 個ある」ことを表す。$\mathcal M\models\varepsilon_n$ なので $\mathcal N\models\varepsilon_n$ であり、$N$ もちょうど $n$ 個の元をもつ。
段 2（有限個の記号についての同型）． $L$ の記号の有限部分集合 $L_0$ をとる。次の有限個の原子論理式とその否定の連言を $\theta_{L_0}(x_1,\dots,x_n)$ とする。

• $L_0$ の $r$ 項関係記号 $R$ と $(i_1,\dots,i_r)\in\{1,\dots,n\}^r$ ごとに、$(a_{i_1},\dots,a_{i_r})\in R^{\mathcal M}$ なら $R(x_{i_1},\dots,x_{i_r})$、そうでなければその否定。
• $L_0$ の $r$ 項関数記号 $f$ と $(i_1,\dots,i_r)$ ごとに、$f^{\mathcal M}(a_{i_1},\dots,a_{i_r})=a_k$ となる $k$ について $f(x_{i_1},\dots,x_{i_r})=x_k$。
• $L_0$ の定数記号 $c$ ごとに、$c^{\mathcal M}=a_k$ となる $k$ について $c=x_k$。
  文 $\delta_{L_0}:=\exists x_1\cdots\exists x_n\bigl(\bigwedge_{i< j}\lnot(x_i=x_j)\land\theta_{L_0}\bigr)$ は、$x_i$ に $a_i$ を割り当てれば $\mathcal M$ で真なので、$\mathcal N$ でも真である。そこで $\mathcal N\models\theta_{L_0}[b_1,\dots,b_n]$ を満たす相異なる $b_1,\dots,b_n\in N$ をとる。段 1 により $N=\{b_1,\dots,b_n\}$ であり、$h(a_i):=b_i$ は全単射 $h\colon M\to N$ である。$\theta_{L_0}$ の各項により、$h$ は $L_0$ のすべての記号の解釈を保つ。すなわち $h$ は $L_0$ 構造としての同型である。

段 3（全部の記号を同時に）． $L_0$ ごとに、$M$ から $N$ への全単射で $L_0$ の記号の解釈をすべて保つものの集合を $S(L_0)$ とする。段 2 により $S(L_0)$ は空でなく、$M$ から $N$ への全単射は $n!$ 個しかないので有限集合である。また $L_0\subset L_1$ なら $S(L_1)\subset S(L_0)$ である。
$\lvert S(L_0)\rvert$ が最小になる有限部分集合 $L_0^\ast$ を 1 つとる（値は正の整数なので最小値がある）。任意の有限部分集合 $L_1$ について、$S(L_0^\ast\cup L_1)\subset S(L_0^\ast)$ で、左辺は空でなく、最小性から元の個数は右辺以上である。よって両辺は等しく、$S(L_0^\ast)=S(L_0^\ast\cup L_1)\subset S(L_1)$ となる。
$h\in S(L_0^\ast)$ を 1 つとる。$L$ のどの記号 $s$ についても、$L_1=\{s\}$ に上のことを当てはめれば $h\in S(\{s\})$、すなわち $h$ は $s$ の解釈を保つ。したがって $h$ は $L$ 構造としての同型である。$\square$

ここで $\mathcal M\models\varphi[a_1,\dots,a_k]$ は、$x_i$ に $a_i$ を割り当てて $\varphi$ が充足されることを表す（残りの変数への割り当てによらないことは 一階述語論理 の記事の補題「一致補題」）。$a_i$ に重複があってもよい。論理式は $\lnot,\land$ と $\exists$ から作られるとしてよい。ほかの結合子と $\forall$ は、充足の定義の上でこれらと同値な形（$\forall y\,\psi$ は $\lnot\exists y\,\lnot\psi$）に置き換えられるからである。主張を、すべての $p\in I$ と $\operatorname{dom}p$ の元の組について同時に、$\varphi$ の組み立てに関する帰納法で示す。
原子論理式． $\varphi$ が $R(x_{i_1},\dots,x_{i_r})$ なら、部分同型の定義そのものである。$\varphi$ が $x_i=x_j$ なら、$p$ が単射なので $a_i=a_j\iff p(a_i)=p(a_j)$ である。言語に定数記号・関数記号がないので、原子論理式はこの 2 つの形に限る。
結合子． $\lnot\psi$ と $\psi\land\chi$ の場合は、同じ $p$ と同じ元の組に帰納法の仮定を当てはめ、充足の定義を使えばよい。
存在量化． $\varphi=\exists y\,\psi$ とする。束縛変数の名前を付け替えて（一階述語論理 の記事の系「束縛変数の付け替え」）、$y$ は $x_1,\dots,x_k$ と異なるとしてよい。$\psi$ の自由変数は $x_1,\dots,x_k,y$ の中にある。
$\mathcal M\models\varphi[\bar a]$ とすると、ある $c\in M$ で $\mathcal M\models\psi[\bar a,c]$ である。（行き）により、$p\subset q$ かつ $c\in\operatorname{dom}q$ となる $q\in I$ がある。$a_i\in\operatorname{dom}p$ なので $q(a_i)=p(a_i)$ である。$q$ と組 $(\bar a,c)$ に帰納法の仮定を当てはめると $\mathcal N\models\psi[p(\bar a),q(c)]$ となり、$\mathcal N\models\varphi[p(\bar a)]$ である。
逆に $\mathcal N\models\varphi[p(\bar a)]$ とすると、ある $d\in N$ で $\mathcal N\models\psi[p(\bar a),d]$ である。（帰り）により、$p\subset q$ かつ $d=q(c)$ となる $q\in I$ と $c\in\operatorname{dom}q$ がある。帰納法の仮定により $\mathcal M\models\psi[\bar a,c]$ となり、$\mathcal M\models\varphi[\bar a]$ である。
文の場合． $k=0$ とすれば、$\operatorname{dom}p$ の元を選ぶ必要がない。$I$ は空でないので $p\in I$ を 1 つとれば、すべての文 $\sigma$ について $\mathcal M\models\sigma\iff\mathcal N\models\sigma$ である。$\square$

2 ⇒ 1：初等埋め込みは文の真偽を保つので $\mathcal M\equiv\mathcal K$、$\mathcal N\equiv\mathcal K$ であり、prop-ee-equivalent の推移性と対称性により $\mathcal M\equiv\mathcal N$ である。
1 ⇒ 2：$M$ の各元 $a$ に新しい定数記号 $c_a$ を、$N$ の各元 $b$ に新しい定数記号 $d_b$ を用意する（互いに異なり、$L$ の記号とも異なるものとする）。$L_M:=L\cup\{c_a\mid a\in M\}$、$L_N:=L\cup\{d_b\mid b\in N\}$、$L^\ast:=L_M\cup L_N$ とおく。Löwenheim–Skolemの定理 の記事の定義「初等図式」の $\operatorname{Eldiag}(\mathcal M)$（$L_M$ の文）と、$d_b$ を使って同様に作った $\operatorname{Eldiag}(\mathcal N)$（$L_N$ の文）をとり、
$$ T:=\operatorname{Eldiag}(\mathcal M)\cup\operatorname{Eldiag}(\mathcal N) $$
とおく。
段 1（$T$ は有限充足可能）． $T$ の有限部分集合 $T_0$ をとる。$T_0\cap\operatorname{Eldiag}(\mathcal N)$ の文に現れる記号 $d_b$ を $d_{b_1},\dots,d_{b_m}$（$b_i$ は相異なる）とすると、これらの文は $L$ の論理式 $\theta_1(y_1,\dots,y_m),\dots,\theta_l(y_1,\dots,y_m)$ の $y_i$ に $d_{b_i}$ を代入した形をしている。$\theta:=\theta_1\land\cdots\land\theta_l$ とおくと（$l=0$ なら $m=0$ で、$\theta$ は恒真な文 $\forall x\,(x=x)$ とする）、各文が $\mathcal N$ の初等図式に属することから $\mathcal N\models\theta[b_1,\dots,b_m]$ であり、$L$ の文 $\exists y_1\cdots\exists y_m\,\theta$ が $\mathcal N$ で真である。$\mathcal M\equiv\mathcal N$ なので、これは $\mathcal M$ でも真であり、$\mathcal M\models\theta[a'_1,\dots,a'_m]$ となる $a'_1,\dots,a'_m\in M$ がある。
$\mathcal M$ を $L^\ast$ 構造 $\mathcal K_0$ に拡張する。$c_a$ は $a$ と解釈し、$d_{b_i}$ は $a'_i$ と解釈し、そのほかの $d_b$ は $M$ の任意の 1 つの元と解釈する。$\mathcal K_0$ の $L_M$ への簡約は $\operatorname{Eldiag}(\mathcal M)$ のモデルであり、$\mathcal K_0\models\theta_i(d_{b_1},\dots,d_{b_m})$ は代入補題（一階述語論理 の記事の補題「代入補題」）により $\mathcal M\models\theta_i[a'_1,\dots,a'_m]$ と同値で成り立つ。よって $\mathcal K_0$ は $T_0$ のモデルである。
段 2（モデルを作る）． コンパクト性定理(一階論理) の記事の定理「一階論理のコンパクト性定理」により、$T$ はモデル $\mathcal K^\ast$（$L^\ast$ 構造）をもつ。$\mathcal K:=\mathcal K^\ast|_L$ とし、$j(a):=c_a^{\mathcal K^\ast}$、$k(b):=d_b^{\mathcal K^\ast}$ とおく。$\mathcal K^\ast|_{L_M}$ は $\operatorname{Eldiag}(\mathcal M)$ のモデルなので、Löwenheim–Skolemの定理 の記事の補題「初等図式の補題」により $j\colon\mathcal M\to\mathcal K$ は初等埋め込みである。同じ補題を $\mathcal K^\ast|_{L_N}$ と $\operatorname{Eldiag}(\mathcal N)$ に当てはめれば、$k\colon\mathcal N\to\mathcal K$ も初等埋め込みである。$\square$