等号付き一階論理

$E:=E^{\mathcal M}$ と書く。広義の構造では、等号公理の各文は $E$ についての条件をそのまま述べている。1 は $E$ の反射律、2 は合同関係の条件 1、3 を $R$ に当てたものは「$\bar aE\bar b$ かつ $\bar a\in R^{\mathcal M}$ なら $\bar b\in R^{\mathcal M}$」、3 を等号に当てたものは「$a_1Eb_1$、$a_2Eb_2$、$a_1Ea_2$ なら $b_1Eb_2$」である。
$\mathcal M\models_0\mathrm{Eq}_L$ とする。$E$ は反射的である。$aEb$ とする。等号についての 3 で $a_1=a$、$b_1=b$、$a_2=b_2=a$ とすると、$aEb$、$aEa$、$aEa$ から $bEa$ を得るので、$E$ は対称である。$aEb$ かつ $bEc$ とする。同じ文で $a_1=b_1=a$、$a_2=b$、$b_2=c$ とすると、$aEa$、$bEc$、$aEb$ から $aEc$ を得るので、$E$ は推移的である。合同関係の条件 1 は 2 そのものである。条件 2 は、$\bar aE\bar b$ なら対称性により $\bar bE\bar a$ でもあるので、$R$ についての 3 を両方向に使えば得られる。
逆に $E$ が合同関係なら、1 と 2 と $R$ についての 3 は定義から成り立つ。等号についての 3 は、$a_1Eb_1$、$a_2Eb_2$、$a_1Ea_2$ のとき、対称性と推移性により $b_1Ea_1Ea_2Eb_2$ から $b_1Eb_2$ が従うことである。$\square$

まず、項 $t$ について $h(t^{\mathcal M}[s])=t^{\mathcal N}[h\circ s]$ を項の組み立てについての帰納法で示す。変数 $x$ なら両辺とも $h(s(x))$、定数記号なら 1 による。$t=g(t_1,\dots,t_n)$ なら、1 と帰納法の仮定により
$$ h(t^{\mathcal M}[s])=g^{\mathcal N}\bigl(h(t_1^{\mathcal M}[s]),\dots,h(t_n^{\mathcal M}[s])\bigr)=g^{\mathcal N}\bigl(t_1^{\mathcal N}[h\circ s],\dots,t_n^{\mathcal N}[h\circ s]\bigr)=t^{\mathcal N}[h\circ s]. $$
次に論理式の組み立てについての帰納法で示す。原子論理式 $R(t_1,\dots,t_n)$ では、項についての等式と 2 により
$$ \bigl(t_i^{\mathcal M}[s]\bigr)_i\in R^{\mathcal M}\iff\bigl(h(t_i^{\mathcal M}[s])\bigr)_i\in R^{\mathcal N}\iff\bigl(t_i^{\mathcal N}[h\circ s]\bigr)_i\in R^{\mathcal N} $$
である。後半の仮定のもとでは、$t_1=t_2$ も $E$ について同じ議論で扱える。$\lnot$ と $\land,\lor,\to$ の段は帰納法の仮定から直ちに従う。$\varphi=\forall x\,\psi$ とする。$a\in M$ について $h\circ(s_x^a)=(h\circ s)_x^{h(a)}$ なので、帰納法の仮定により
$$ \mathcal M\models\forall x\,\psi[s]\iff\text{すべての }a\in M\text{ で }\mathcal N\models\psi[(h\circ s)_x^{h(a)}]\iff\text{すべての }b\in N\text{ で }\mathcal N\models\psi[(h\circ s)_x^b] $$
である。2 つ目の同値で $h$ が全射であることを使った。右端は $\mathcal N\models\forall x\,\psi[h\circ s]$ である。$\exists$ も同様である。$\square$

lem-eq-congruence により $E$ は合同関係なので、商構造 $\mathcal M/E$ が定まる。これを等号を恒等関係と読む正規な構造と見る。$\pi$ は全射で、商構造の定義により lem-eq-strict-map の 1・2 を満たす。さらに $aEb\iff[a]=[b]\iff\pi(a)=\pi(b)$ なので、補題の後半の仮定も満たす（$\mathcal M/E$ の側の 2 項関係は恒等関係である）。補題の後半により結論を得る。$\square$

右から左：正規な構造では $E$ は恒等関係で、恒等関係は合同関係なので、lem-eq-congruence により正規な構造は $\mathrm{Eq}_L$ を満たす。よって右辺の条件を正規な構造に制限すれば左辺になる。
左から右：広義の構造 $\mathcal M$ と割り当て $s$ で、$\Gamma\cup\mathrm{Eq}_L$ のすべての元が $s$ のもとで成り立つとする（$\mathrm{Eq}_L$ は文なので、$\mathcal M\models_0\mathrm{Eq}_L$ である）。thm-eq-quotient により、$\Gamma$ のすべての元が正規な構造 $\mathcal M/E$ で割り当て $\pi\circ s$ のもとで成り立つ。左辺により $\mathcal M/E\models\varphi[\pi\circ s]$ であり、再び thm-eq-quotient により $\mathcal M\models_0\varphi[s]$ である。$\square$

元 $m_0\in M$ を 1 つ選び、$h$ を $M$ 上では恒等写像、$Y$ 上では値 $m_0$ の写像とする。$h$ は全射である。$\mathcal N$ を
$$ c^{\mathcal N}:=c^{\mathcal M},\qquad g^{\mathcal N}(\bar b):=g^{\mathcal M}(h(\bar b)),\qquad R^{\mathcal N}:=\{\bar b\mid h(\bar b)\in R^{\mathcal M}\} $$
で定める（$\bar b$ は $M\cup Y$ の元の組）。$g^{\mathcal N}(\bar b)\in M$ で $h$ は $M$ 上で恒等写像なので $h(g^{\mathcal N}(\bar b))=g^{\mathcal M}(h(\bar b))$ であり、$h(c^{\mathcal N})=c^{\mathcal M}$、$\bar b\in R^{\mathcal N}\iff h(\bar b)\in R^{\mathcal M}$ も定義から成り立つ。よって $h\colon\mathcal N\to\mathcal M$ は lem-eq-strict-map の仮定を満たし、補題の前半から結論を得る。文については、真偽が割り当てによらない（一階述語論理 の記事の系「文の真偽は割り当てによらない」）ことから従う。$\square$

1：$\mathcal M$ を $\Gamma$ の濃度 $\mu$ のモデル、$\kappa\ge\mu$ とする。$\kappa$ が有限なら $\kappa-\mu$ 個の元からなる集合を、無限なら濃度 $\kappa$ の集合を、$M$ と交わらないようにとって $Y$ とすると、$\lvert M\cup Y\rvert=\kappa$ である。thm-eq-inflation の $\mathcal N$ は $\Gamma$ のモデルで、濃度は $\kappa$ である。等号を含まない文 $\sigma$ が「元が $n$ 個以下」と同値なら、$\{\sigma\}$ は $n$ 個の元のモデルをもつので $n+1$ 個の元のモデルももち、矛盾する。「ちょうど $n$ 個」も同様である。
2：$\theta$ がどの $L$ 構造でも $x=y$ と同値だとする。任意の $L$ 構造 $\mathcal M$ と $Y=\{y_0\}$ について thm-eq-inflation の $\mathcal N$ をとる。$x,y$ にともに $m_0$ を割り当てる $s$ と、$x$ に $m_0$、$y$ に $y_0$ を割り当てる $s'$ について、$h\circ s=h\circ s'$ なので $\mathcal N\models\theta[s]\iff\mathcal N\models\theta[s']$ である。ところが $\mathcal N$ で $x=y$ は $s$ のもとで真、$s'$ のもとで偽であり、矛盾する。$\square$