Löwenheim–Skolemの定理

1 は 初等部分モデル の記事の定理「下向き Löwenheim–Skolem の定理」による。同記事の定理は、$A\subset M$ を含み濃度が $\lvert A\rvert+\lvert L\rvert+\aleph_0$ 以下の初等部分モデルの存在を述べている。$\lvert A\rvert=\kappa$ となる $A\subset M$ を選んで適用すれば、得られる $N$ は $\kappa=\lvert A\rvert\le\lvert N\rvert\le\kappa$ を満たす。2 は下の節の thm-ls-upward である（$\kappa\ge\lvert M\rvert$ と $\kappa\ge\lvert L\rvert$ から $\kappa\ge\lvert M\rvert+\lvert L\rvert$）。最後の主張は、$T$ の無限モデル $M$ に、$\kappa\le\lvert M\rvert$ なら 1 を、$\kappa\ge\lvert M\rvert$ なら 2 を適用すればよい。初等部分モデルや初等拡大は $M$ と同じ文を満たすので、$T$ のモデルである。$\square$

$L$ の論理式 $\varphi(x_1,\dots,x_n)$ と $\bar a\in M^n$ をとる。代入補題と、$L$ の論理式の充足が簡約で変わらないことから、$N'\models\varphi(c_{a_1},\dots,c_{a_n})$ は $N\models\varphi[j(a_1),\dots,j(a_n)]$ と同値である。
$N'\models\operatorname{Eldiag}(M)$ とする。$M\models\varphi[\bar a]$ なら $\varphi(c_{\bar a})\in\operatorname{Eldiag}(M)$ なので $N\models\varphi[j(\bar a)]$ である。$M\models\varphi[\bar a]$ でないなら $\lnot\varphi(c_{\bar a})\in\operatorname{Eldiag}(M)$ なので $N\models\varphi[j(\bar a)]$ でない。よって $M\models\varphi[\bar a]\iff N\models\varphi[j(\bar a)]$ であり、$j$ は初等埋め込みである（初等埋め込み の記事の定義「埋め込みと初等埋め込み」の (ii)）。
逆に $j$ が初等埋め込みなら、$\operatorname{Eldiag}(M)$ の文 $\varphi(c_{\bar a})$ について $M\models\varphi[\bar a]$ なので $N\models\varphi[j(\bar a)]$、すなわち $N'\models\varphi(c_{\bar a})$ である。$\square$

要点：$N$ のうち $j(M)$ の元は対応する $M$ の元に、残りの元は $M$ と交わらない新しい元に名前を付け替え、構造を写し取る。

段 1（大きなモデルを作る）． 新しい定数記号 $d_\alpha$（$\alpha<\kappa$）を用意し、$L':=L_M\cup\{d_\alpha\mid\alpha<\kappa\}$ とおく。$L'$ の文の集合
$$ \Sigma:=\operatorname{Eldiag}(M)\cup\{\lnot(d_\alpha=d_\beta)\mid\alpha<\beta<\kappa\} $$
を考える。$\Sigma$ の有限部分集合 $\Sigma_0$ に現れる $d_\alpha$ は有限個 $d_{\alpha_1},\dots,d_{\alpha_n}$ である。$M$ は無限なので相異なる元 $b_1,\dots,b_n\in M$ がとれ、$M_M$ を $d_{\alpha_i}\mapsto b_i$（ほかの $d_\alpha$ は任意の元）で $L'$ 構造に拡張すると、$\operatorname{Eldiag}(M)$ の文は $M_M$ で真なのでそのまま真であり、$\Sigma_0$ の不等式も真である。よって $\Sigma$ は有限充足可能で、コンパクト性定理(一階論理)（言語の大きさに制限はない）によりモデル $N_1$ をもつ。$N_1$ では $d_\alpha$ の値が互いに異なるので、$\lvert N_1\rvert\ge\kappa$ である。
段 2（ちょうど $\kappa$ に縮める）． $A:=\{c_a^{N_1}\mid a\in M\}\cup\{d_\alpha^{N_1}\mid\alpha<\kappa\}$ とおくと $\lvert A\rvert\le\lvert M\rvert+\kappa=\kappa$ であり、$\lvert L'\rvert=\lvert L\rvert+\lvert M\rvert+\kappa=\kappa$ である。初等部分モデル の記事の定理「下向き Löwenheim–Skolem の定理」を $L'$ 構造 $N_1$ と $A$ に適用すると、$A\subset N_2\preccurlyeq N_1$（$L'$ 構造として）かつ $\lvert N_2\rvert\le\lvert A\rvert+\lvert L'\rvert+\aleph_0=\kappa$ となる $N_2$ がある。$d_\alpha^{N_2}=d_\alpha^{N_1}$ は相異なる $\kappa$ 個の元なので $\lvert N_2\rvert=\kappa$ である。
段 3（$M$ を含む形に直す）． $N_2\preccurlyeq N_1$ なので $N_2$ と $N_1$ は同じ $L'$ の文を満たし、$N_2\models\operatorname{Eldiag}(M)$ である。lem-ls-elementary-diagram を $N_2$ の $L_M$ への簡約に適用すると、$j(a):=c_a^{N_2}$ は初等埋め込み $M\to N_2|_L$ である。lem-ls-replace により、$M\preccurlyeq N$ かつ $\lvert N\rvert=\lvert N_2\rvert=\kappa$ となる $N$ がある。$\square$

$\kappa:=\max(\lvert M\rvert,\lvert L\rvert+\aleph_0)^+$（その次の基数）とおく。thm-ls-upward により、$M\preccurlyeq N$、$\lvert N\rvert=\kappa$ となる $N$ がある。$N\equiv M$ だが、$\lvert N\rvert=\kappa>\lvert M\rvert$ なので $N$ と $M$ の間に全単射はなく、同型でない。$\square$

$T$ が完全でないとすると、ある文 $\sigma$ について、$\sigma$ が偽になる $T$ のモデル $M_1$ と、$\lnot\sigma$ が偽になる $T$ のモデル $M_2$ がある。すなわち $M_1$ は $T\cup\{\lnot\sigma\}$ の、$M_2$ は $T\cup\{\sigma\}$ のモデルである。$T$ は有限のモデルをもたないので $M_1,M_2$ は無限であり、thm-ls-main により $T\cup\{\lnot\sigma\}$ と $T\cup\{\sigma\}$ はそれぞれ濃度 $\kappa$ のモデル $N_1,N_2$ をもつ。$N_1,N_2$ はどちらも $T$ の濃度 $\kappa$ のモデルなので、$\kappa$-範疇性により同型である。同型な構造は同じ文を満たす（一階述語論理 の記事の定理「同型補題」）が、$N_1\models\lnot\sigma$、$N_2\models\sigma$ なので矛盾する。$\square$