初等部分モデル

必要性。 $N\preccurlyeq M$ で $M\models\exists y\,\varphi(y,\bar a)$ とする。初等性により $N\models\exists y\,\varphi(y,\bar a)$ なので、ある $b\in N$ で $N\models\varphi(b,\bar a)$。再び初等性により $M\models\varphi(b,\bar a)$ である。

十分性。 条件を仮定し、論理式 $\psi(\bar x)$ の構成に関する帰納法で「任意の $\bar a\in N$ について $N\models\psi(\bar a)\iff M\models\psi(\bar a)$」を示す。結合子は $\lnot,\land$、量化記号は $\exists$ だけとしてよい。

• 原子論理式：$N$ は部分構造なので、項の値は $N$ で計算しても $M$ で計算しても同じであり（項の構成に関する帰納法）、$R^N=R^M\cap N^n$ と等号の意味から真偽が一致する。
• $\lnot\psi$、$\psi_1\land\psi_2$：帰納法の仮定からただちに従う。
• $\exists y\,\psi(y,\bar x)$：$N\models\exists y\,\psi(y,\bar a)$ なら、ある $b\in N$ で $N\models\psi(b,\bar a)$、帰納法の仮定で $M\models\psi(b,\bar a)$、よって $M\models\exists y\,\psi(y,\bar a)$。逆に $M\models\exists y\,\psi(y,\bar a)$ なら、仮定した条件により証人 $b$ を $N$ の中にとれて $M\models\psi(b,\bar a)$。帰納法の仮定で $N\models\psi(b,\bar a)$、よって $N\models\exists y\,\psi(y,\bar a)$。$\square$

論理式の構成に関する帰納法。

thm-elementary-submodel-tv の条件を確かめる。$a_1<\cdots< a_n$ を有理数（並べ替えと重複の除去をしてよい）、$b\in\mathbb R$ で $\mathbb R\models\varphi(b,\bar a)$ とする。$b$ が有理数なら証人はそれでよい。そうでなければ $b$ は区間 $(-\infty,a_1)$、$(a_i,a_{i+1})$、$(a_n,\infty)$ のどれかにあり、同じ区間の有理数 $q$ を選ぶ。$a_1,\ldots,a_n$ を固定し $b$ を $q$ に移す順序を保つ全単射 $\sigma\colon\mathbb R\to\mathbb R$ が作れる：例えば $b\in(a_i,a_{i+1})$ なら、$[a_i,b]$ を $[a_i,q]$ へ、$[b,a_{i+1}]$ を $[q,a_{i+1}]$ へそれぞれ一次関数で写し、それ以外では恒等写像とする（$b\in(a_n,\infty)$ なら $[a_n,b]$ を $[a_n,q]$ へ一次関数で写し、$[b,\infty)$ では $x\mapsto x-b+q$ とする。$(-\infty,a_1)$ も同様で、パラメータがなければ $x\mapsto x-b+q$ でよい）。$\sigma$ は $(\mathbb R,<)$ の自己同型なので、lem-elementary-submodel-automorphism により $\mathbb R\models\varphi(q,\bar a)$ である。よって証人 $q\in\mathbb Q$ がとれ、$\mathbb Q\preccurlyeq\mathbb R$ である。$\square$

$\bar a\in N$ と論理式 $\varphi$ をとる。(1) は $N\models\varphi(\bar a)\iff N'\models\varphi(\bar a)\iff M\models\varphi(\bar a)$ から、(2) は $N\models\varphi(\bar a)\iff M\models\varphi(\bar a)\iff N'\models\varphi(\bar a)$ から従う（$\bar a\in N\subseteq N'$ を使う）。$\square$

列は包含について増大する部分構造の鎖なので、$M$ の解釈は矛盾なく定まり、各 $M_\alpha$ は $M$ の部分構造である。論理式 $\psi$ の構成に関する帰納法で「任意の $\alpha$ と $\bar a\in M_\alpha$ について $M_\alpha\models\psi(\bar a)\iff M\models\psi(\bar a)$」を示す。原子論理式と $\lnot,\land$ は部分構造であることと帰納法の仮定から従う。$\psi=\exists y\,\chi(y,\bar x)$ とする。$M_\alpha\models\psi(\bar a)$ なら証人 $b\in M_\alpha$ に帰納法の仮定を使えば $M\models\psi(\bar a)$。逆に $M\models\chi(b,\bar a)$ となる $b\in M$ があれば、$b\in M_\beta$ となる $\beta\geq\alpha$ をとる。帰納法の仮定（$\beta$ について）により $M_\beta\models\chi(b,\bar a)$、よって $M_\beta\models\psi(\bar a)$。$M_\alpha\preccurlyeq M_\beta$ なので $M_\alpha\models\psi(\bar a)$ である。$\square$

選択公理により、各論理式 $\varphi(y,\bar x)$ と $\bar a\in M$ で $M\models\exists y\,\varphi(y,\bar a)$ となるものに対して、証人 $w(\varphi,\bar a)\in M$（$M\models\varphi(w(\varphi,\bar a),\bar a)$）を一つずつ選んでおく。
$$ A_0:=A\cup\{w(x=x)\},\qquad A_{k+1}:=A_k\cup\{w(\varphi,\bar a): \varphi,\ \bar a\in A_k,\ M\models\exists y\,\varphi(y,\bar a)\} $$
とおき、$N:=\bigcup_{k\in\mathbb N}A_k$ とする（$A_0$ は $A$ が空でも空でない）。

大きさ。 論理式は $L$ の記号と可算個の変数・論理記号の有限列なので、その個数は $\lvert L\rvert+\aleph_0\leq\kappa$ 以下である。$\lvert A_k\rvert\leq\kappa$ なら、$A_k$ の元の有限列も $\kappa$ 個以下なので、加える元は $\kappa\cdot\kappa=\kappa$ 個以下で $\lvert A_{k+1}\rvert\leq\kappa$。よって $\lvert N\rvert\leq\aleph_0\cdot\kappa=\kappa$。

部分構造。 定数記号 $c$ について $\exists y\,(y=c)$ の証人は $c^M$ しかないので $c^M\in A_1$。関数記号 $F$ と $\bar a\in A_k$ について $\exists y\,(y=F(\bar a))$ の証人は $F^M(\bar a)$ しかないので $F^M(\bar a)\in A_{k+1}$。よって $N$ は定数を含み関数で閉じ、部分構造になる。

初等性。 $\bar a\in N$ は有限個なので、ある $A_k$ に全部入る。$M\models\exists y\,\varphi(y,\bar a)$ なら $w(\varphi,\bar a)\in A_{k+1}\subseteq N$ が証人である。thm-elementary-submodel-tv により $N\preccurlyeq M$。$\square$

論理式の構成に関する帰納法。

thm-elementary-submodel-tv の後の注意により、$H(\theta)$ の中で $M$ の元をパラメータとする論理式で一意に定まる元は $M$ に属する。

1. $\emptyset$ は $\Delta_0$ 論理式 $\forall z\in y\,(z\neq z)$ で一意に定まるので $\emptyset=0\in M$。$n\in M$ なら $n+1=n\cup\{n\}$ は $n$ をパラメータとする $\Delta_0$ 論理式 $n\in y\land\forall z\in n\,(z\in y)\land\forall z\in y\,(z\in n\lor z=n)$ で一意に定まるので $n+1\in M$。よって $\omega\subseteq M$。$\omega$ は「$0$ でない極限順序数で、すべての元が $0$ か後続順序数」という $\Delta_0$ 論理式で一意に定まるので $\omega\in M$。$\omega_1$ は次の論理式 $\psi(x)$ で $H(\theta)$ の中で一意に定まる。

   詳細

   $\psi(x)$：「$x$ は $0$ でない順序数で、$\omega$ から $x$ への全射は存在せず、$x$ の各元 $\beta\neq0$ について $\omega$ から $\beta$ への全射が存在する」。$\omega_1\in H(\theta)$（$\operatorname{trcl}(\omega_1)=\omega_1$ の濃度は $\aleph_1<\theta$）。$0<\beta<\omega_1$ への全射 $f\subseteq\omega\times\beta$ は推移閉包が可算なので $H(\theta)$ に属し、全射であることは $\Delta_0$ なので $H(\theta)$ の中でも全射である。$\omega$ から $\omega_1$ への全射は宇宙に存在せず、したがって $H(\theta)$ にもない（lem-elementary-submodel-delta0）。よって $H(\theta)\models\psi(\omega_1)$。逆に $H(\theta)\models\psi(x)$ とする。$0< x<\omega_1$ なら $\omega$ から $x$ への全射が $H(\theta)$ にあって矛盾。$x>\omega_1$ なら $\omega_1$ は $x$ の $0$ でない元なので、$\psi$ により $\omega$ から $\omega_1$ への全射が $H(\theta)$ にあることになり、それは宇宙でも全射なので矛盾。よって $x=\omega_1$。

2. $x=\emptyset$ なら明らか。$x\neq\emptyset$ なら全射 $f\colon\omega\to x$ が存在する。$\operatorname{trcl}(f)\subseteq f\cup\bigcup f\cup\omega\cup\operatorname{trcl}(x)$ の濃度は $\aleph_0+\lvert\operatorname{trcl}(x)\rvert<\theta$ なので、$f\in H(\theta)$ である。「$f$ は $\omega$ から $x$ への全射」は $\omega,x\in M$ をパラメータとする $\Delta_0$ 論理式なので、$H(\theta)\models\exists f\,(\ldots)$ から Tarski–Vaught の条件により、そのような $f$ を $M$ の中にとれる（lem-elementary-submodel-delta0 により本当に全射）。各 $n\in\omega$ は (1) により $M$ に属し、$f(n)$ は $f,n$ をパラメータとする論理式「$(n,y)\in f$」で一意に定まるので $f(n)\in M$。$f$ は全射なので $x\subseteq M$。

3. $\alpha\in M\cap\omega_1$ なら $\alpha$ は可算なので (2) により $\alpha\subseteq M$、したがって $\alpha\subseteq M\cap\omega_1$。よって $M\cap\omega_1$ は推移的な順序数の集合、すなわち順序数 $\delta$ であり、$M$ が可算なので $\delta$ も可算、$\delta<\omega_1$ である。$\omega_1\in M$ は (1) による。$\square$