構造(モデル)

1：$A$ の元 $a$ は変数 $x$ の値 $x^N[a]$ なので $A\subset\langle A\rangle$ であり、定数 $c^N$ は項 $c$ の値なので $\langle A\rangle$ に属する。仮定から $\langle A\rangle$ は空でない。関数で閉じていることを示す。$n$ 項関数記号 $f$ と $\langle A\rangle$ の元 $b_i=t_i^N[\bar a_i]$（$1\le i\le n$）をとる。変数の名前を付け替えても項の値は変わらない（一階述語論理 の記事の補題「代入補題」の 1）ので、$t_1,\dots,t_n$ の変数は互いに異なるとしてよい。すると $t:=f(t_1,\dots,t_n)$ は項で、その変数に $\bar a_1,\dots,\bar a_n$ を並べて割り当てると、一致補題により各 $t_i$ の値は $b_i$ のままなので、$t$ の値は $f^N(b_1,\dots,b_n)$ である。よって $f^N(b_1,\dots,b_n)\in\langle A\rangle$。def-str-substructure の後の注意により、$\langle A\rangle$ は部分構造の台集合である。
$B$ を $A$ を含む部分構造の台集合とする。項 $t$ の組み立て方についての帰納法で、$a_i\in A$ なら $t^N[\bar a]\in B$ を示す。変数の値は $A\subset B$ に、定数は $B$ に属し、$t=f(t_1,\dots,t_n)$ では帰納法の仮定と $B$ が $f^N$ で閉じていることから従う。よって $\langle A\rangle\subset B$ である。
2：$\kappa:=\lvert A\rvert+\lvert L\rvert+\aleph_0$ とおく。項は、$L$ の記号・可算個の変数・括弧とコンマからなる、濃度 $\lvert L\rvert+\aleph_0$ 以下の集合の上の有限列なので、項の全体の濃度は $\lvert L\rvert+\aleph_0\le\kappa$ 以下である。各項 $t(x_1,\dots,x_n)$ について、割り当てる組 $\bar a\in A^n$ は $\lvert A\rvert^n\le\kappa$ 個以下である。よって $\langle A\rangle$ は濃度 $\kappa$ 以下の集合を $\kappa$ 個以下集めた和集合であり、$\lvert\langle A\rangle\rvert\le\kappa\cdot\kappa=\kappa$ である（無限濃度の積は大きいほうに等しい。濃度 の記事）。$\square$

まず、すべての項 $t$ について $h(t^M[s])=t^N[h\circ s]$ である。これは 一階述語論理 の記事の定理「同型補題」の 1 と同じ項の帰納法で示され、その証明は $h$ が定数と関数を保つことしか使わない。
論理式の組み立て方についての帰納法で示す。

• $t_1=t_2$：$t_1^M[s]=t_2^M[s]$ なら、両辺を $h$ で写して上の等式を使えば $t_1^N[h\circ s]=t_2^N[h\circ s]$ である。
• $R(t_1,\dots,t_n)$：値の組が $R^M$ に属すれば、準同型の条件により $h$ で写した組は $R^N$ に属し、上の等式によりそれは $(t_1^N[h\circ s],\dots,t_n^N[h\circ s])$ である。
• $\psi\land\chi$、$\psi\lor\chi$：帰納法の仮定からただちに従う。
• $\exists x\,\psi$：ある $a\in M$ で $M\models\psi[s_x^a]$ とする。$h\circ s_x^a=(h\circ s)_x^{h(a)}$ なので、帰納法の仮定により $N\models\psi[(h\circ s)_x^{h(a)}]$、よって $N\models\exists x\,\psi[h\circ s]$ である。
• $\forall x\,\psi$（2 の場合）：すべての $a\in M$ で $M\models\psi[s_x^a]$ とする。$b\in N$ を任意にとると、$h$ が全射なので $b=h(a)$ となる $a$ があり、帰納法の仮定により $N\models\psi[(h\circ s)_x^{b}]$ である。よって $N\models\forall x\,\psi[h\circ s]$ である。$\square$

1：$\operatorname{Diag}(M)$ の文は、$L$ の原子論理式 $\varphi(x_1,\dots,x_n)$ を使って $\varphi(c_{a_1},\dots,c_{a_n})$ または $\lnot\varphi(c_{a_1},\dots,c_{a_n})$ と書ける。代入補題により、$M_M\models\varphi(c_{a_1},\dots,c_{a_n})$ は $M\models\varphi[a_1,\dots,a_n]$ と、$N_j\models\varphi(c_{a_1},\dots,c_{a_n})$ は $N\models\varphi[j(a_1),\dots,j(a_n)]$ と同値である。埋め込みは原子論理式の真偽を両方向に保つ（def-str-maps の後の注意。等号は単射性、関係は両方向の条件による）ので、両者は同値であり、$\operatorname{Diag}(M)$ の文は $N_j$ でも真である。
2：$\operatorname{Diag}(M)$ の次の文を使う。

• 定数記号 $c$：$M_M$ で $c=c_{c^M}$ は真なので $N'$ でも真で、$c^N=c_{c^M}^{N'}=j(c^M)$ である。
• 関数記号 $f$ と $\bar a\in M^n$：$f(c_{a_1},\dots,c_{a_n})=c_{f^M(\bar a)}$ が真なので、$f^N(j(a_1),\dots,j(a_n))=j(f^M(\bar a))$ である。
• 関係記号 $R$：$\bar a\in R^M$ なら $R(c_{a_1},\dots,c_{a_n})$、そうでなければ $\lnot R(c_{a_1},\dots,c_{a_n})$ が $\operatorname{Diag}(M)$ に入るので、$\bar a\in R^M\iff(j(a_1),\dots,j(a_n))\in R^N$ である。
• 単射性：$a\ne b$ なら $\lnot(c_a=c_b)$ が入るので、$j(a)\ne j(b)$ である。
  よって $j$ は埋め込みである。$\square$

$M$ が $T$ のモデル $N$ に埋め込めるとする。$\forall\bar x\,\psi\in T_\forall$ は $N$ で真であり、埋め込みは量化記号を含まない論理式の真偽を保つ（初等埋め込み の記事の命題「埋め込みが保つ式」の (i)）ので、$M$ の元をどう割り当てても $\psi$ は $M$ で真である。
逆に $M\models T_\forall$ とし、$T\cup\operatorname{Diag}(M)$ がモデルをもたないと仮定する。コンパクト性定理(一階論理) により、有限個の $\delta_1,\dots,\delta_m\in\operatorname{Diag}(M)$ で $T\cup\{\delta_1,\dots,\delta_m\}$ がモデルをもたないものがある。$\delta_1\land\cdots\land\delta_m$ に現れる新しい定数を $c_{a_1},\dots,c_{a_k}$（$a_i$ は相異なる）とし、それを新しい変数に置き換えた論理式を $\theta(x_1,\dots,x_k)$ と書く。$\theta$ は量化記号を含まない $L$ の論理式である。$T$ の任意のモデル $N$ と $b_1,\dots,b_k\in N$ をとり、$N$ を $c_{a_i}\mapsto b_i$（ほかの $c_a$ は任意の元）で $L_M$ 構造 $N'$ に拡張する。$N'$ は $T$ のモデルである（$L$ の文の真偽は簡約で変わらない）から、$\delta_1\land\cdots\land\delta_m$ は $N'$ で偽であり、代入補題により $N\models\lnot\theta[b_1,\dots,b_k]$ である。よって $\forall\bar x\,\lnot\theta\in T_\forall$ で、$M\models\lnot\theta[a_1,\dots,a_k]$ となる。ところが $\delta_i$ は $M_M$ で真なので $M\models\theta[a_1,\dots,a_k]$ であり、矛盾する。
したがって $T\cup\operatorname{Diag}(M)$ はモデル $N'$ をもち、thm-str-diagram-lemma の 2 により $M$ は $N'|_L$ に埋め込める。$N'|_L$ は $T$ のモデルである。$\square$

$\sigma=\forall\bar x\,\exists\bar y\,\psi(\bar x,\bar y)$ とし、$\bar a\in M^m$ を任意にとる。上の注意により $\bar a\in M_i^m$ となる $i$ がある。$M_i\models\sigma$ なので、ある $\bar b\in M_i^n$ で $M_i\models\psi[\bar a,\bar b]$ である。包含写像 $M_i\to M$ は埋め込みで、埋め込みは量化記号を含まない論理式の真偽を保つ（初等埋め込み の記事の命題「埋め込みが保つ式」の (i)）ので、$M\models\psi[\bar a,\bar b]$ である。よって $M\models\exists\bar y\,\psi[\bar a]$ で、$\bar a$ は任意だったので $M\models\sigma$ である。$\square$