§E19.14Löwenheim–Skolem の定理

§E19.11 補題 2.1により$|\operatorname{Sent}(L)|\leq\max(\aleph_0,|L|)$である。逆向きの単射を二つ作る。第一に、$\sigma_0=\forall x_0\,(x_0=x_0)$、$\sigma_{n+1}=\neg\sigma_n$と定めると、各$\sigma_n$は文であり、§E19.5 定理 3.1 (2)により$\sigma_{n+1}$の直下の論理式は$\sigma_n$だけであるから、$n$についての帰納法で$\sigma_n$は相異なる。よって$n\mapsto\sigma_n$は単射$\omega\to\operatorname{Sent}(L)$である。第二に、定数記号$c$を$c=c$へ、$n\geq1$項関数記号$f$を$\forall x_0\,(f(x_0,\ldots,x_0)=f(x_0,\ldots,x_0))$へ、零項関係記号$R$を原子文$R$へ、$n\geq1$項関係記号$R$を$\forall x_0\,R(x_0,\ldots,x_0)$へ送る。一意可読性により、得られる文から記号が復元されるので、この写像は単射$L\to\operatorname{Sent}(L)$である。

$\max(\aleph_0,|L|)$は$\aleph_0$と$|L|$のいずれかに等しいので、前段の単射のどちらかにより単射$\max(\aleph_0,|L|)\to\operatorname{Sent}(L)$が得られる。$\operatorname{Sent}(L)$から$\max(\aleph_0,|L|)$への単射もあるので、§E1.22 命題 2.5 (3)により$|\operatorname{Sent}(L)|=\max(\aleph_0,|L|)$である。

台集合を$\R$とし、$c_r$を$r$と解釈する構造は、$r\neq s$ならば$c_r$と$c_s$の値が異なるので$T$のモデルであり、無限である。$M$を$T$の任意のモデルとすると、$r\neq s$ならば$M\models\neg(c_r=c_s)$であるから、$r\mapsto c_r^M$は単射$\R\to|M|$である。$|M|=\aleph_0$ならば単射$|M|\to\N$が存在し、合成は単射$\R\to\N$となって§E1.19 定理 3.3に反する。よって$T$は濃度$\aleph_0$のモデルをもたない。

この$L$では$|L|=|\R|>\aleph_0$であり、$\lambda=\aleph_0$は$\lambda\geq\max(\aleph_0,|L|)$を満たさない。$T$は無限モデルをもつにもかかわらず濃度$\aleph_0$のモデルをもたないので、定理 3.1の結論は仮定$\lambda\geq\max(\aleph_0,|L|)$なしには成り立たない。

濃度$\lambda$の集合$I$を取り、各$i\in I$に新しい定数記号$c_i$を加えた言語を$L_\lambda$とする。§E19.11 系 2.2 (4)により$|L_\lambda|=\lambda$である。$L_\lambda$理論

を考える。$\Delta$の有限部分集合$\Delta_0$に現れる新定数を$c_{i_1},\ldots,c_{i_k}$（$k\geq0$）とする。$\varphi^N$は無限集合であるから、相異なる$a_0,a_1,\ldots,a_k\in\varphi^N$を取ることができる。$c_{i_m}$（$1\leq m\leq k$）を$a_m$と解釈し、残りの新定数を$a_0$と解釈した$N$の$L_\lambda$拡大は、$T$を満たし、§E19.7 系 5.3により各$\varphi(c_{i_m})$を満たし、$\Delta_0$に現れる不等式を満たす。よって$\Delta$の各有限部分集合は充足可能であり、§E19.13 定理 1.1により$\Delta$は充足可能である。

$|T|\leq\max(\aleph_0,|L|)\leq\lambda$であり、$\{\varphi(c_i)\mid i\in I\}$は高々$\lambda$個、不等式の全体は$I\times I$へ単射するので§E1.23 系 3.3により高々$\lambda$個である。同じ定理により三つの和集合は高々$\lambda$個であるから$|\Delta|\leq\lambda$である。定理 2.1により$|N_\lambda|\leq\max(\aleph_0,|L_\lambda|)=\lambda$を満たすモデル$N_\lambda\models\Delta$が存在する。$i\mapsto c_i^{N_\lambda}$は$I$から$\varphi^{N_\lambda}$への単射であるから$\lambda\leq|\varphi^{N_\lambda}|\leq|N_\lambda|\leq\lambda$である。$M=N_\lambda\mathbin{\upharpoonright}L$とおくと、$M$は台集合を変えずに$T$を満たし、$\varphi$は$L$論理式であるから$\varphi^M=\varphi^{N_\lambda}$である。したがって$|M|=|\varphi^M|=\lambda$である。

$A$の各元$a$に$L$に属さない相異なる定数記号$c_a$を加えた言語を$L_A$とする。$L_A$も集合サイズの有限項言語である。$L$と$A$はともに$\lambda$へ単射し、§E1.23 系 3.3により全単射$\lambda\sqcup\lambda\to\lambda$が存在するので、$|L_A|\leq\lambda$である。$c_a$を$a$と解釈した$N$の$L_A$拡大を$N_A$とし、$N_A$で真な$L_A$文の全体を$T_A$とする。$N_A\models T_A$であるから$T_A$は充足可能であり、定理 2.1により$|M_A|\leq\max(\aleph_0,|L_A|)\leq\lambda$を満たす$L_A$構造$M_A\models T_A$が存在する。$M_A$の解釈を$L$の記号に限った$L$構造を$M$とし、$e(a)=c_a^{M_A}$と定める。$|M|=|M_A|\leq\lambda$である。$L$論理式の充足は、台集合、$L$の記号の解釈、割当てだけから構造帰納法で定まるので、$L$論理式の真偽は、同じ割当てのもとで$N_A$と$N$、$M_A$と$M$のそれぞれで一致する。

$\varphi$と$a_1,\ldots,a_n$を問いのとおりに取り、$\sigma=\varphi[c_{a_1}/x_1]\cdots[c_{a_n}/x_n]$とおく。定数記号は変数を含まないので各代入は自由に代入可能であり、$\sigma$は$L_A$文である。$K$を$N_A$または$M_A$とし、$s$を$K$の台集合への割当てとする。§E19.7 系 5.3を$n$回用いると、$K,s\models\sigma$と$K,s[x_n\mapsto c_{a_n}^K]\cdots[x_1\mapsto c_{a_1}^K]\models\varphi$は同値であり、$x_i$は相異なるので更新の順序は真偽に影響しない。$N_A\models\sigma$ならば$\sigma\in T_A$であり、そうでなければ$\neg\sigma\in T_A$であるから、$M_A\models T_A$より$N_A\models\sigma\iff M_A\models\sigma$である。前段と合わせて、$N$で各$x_i$に$a_i$を割り当てたときと、$M$で各$x_i$に$e(a_i)$を割り当てたときとで、$\varphi$の真偽は一致する。§E19.6 定理 4.1により、残りの変数への割当てはこの真偽に影響しない。

$n=0$の場合から、$N$で真な$L$文はすべて$M$で真である。$\varphi$を$x_1=x_2$とすると、$a_1\neq a_2$ならば$N$でこの式は偽であるから$e(a_1)\neq e(a_2)$であり、$e$は単射である。

$L=\{<\}$、$N=(\R,<)$、$A=\R$とすると、$\max(\aleph_0,|L|)=\aleph_0$である。$|M|\leq\aleph_0$を満たす$M$と上の性質をもつ$e$があるとすると、単射$e:\R\to|M|$と単射$|M|\to\N$の合成は単射$\R\to\N$となり、§E1.19 定理 3.3に反する。よって上界$\lambda$の$|A|$を外すことはできない。