超積によるコンパクト性定理の証明と超準モデル ──君の知らない自然数── konn-san.com

(⇒) を示す．$\mathcal{U}$ を $I$ 上のウルトラフィルターとする．$\mathcal{U} \subseteq \mathcal{F}$ なるフィルター $\mathcal{F}$ があったとする．$\mathcal{F} \neq \mathcal{U}$ とすると，$X \in \mathcal{F} \setminus \mathcal{U}$ をとれば $X \notin \mathcal{U}$ である．すると，条件 (4) より $I \setminus X \in \mathcal{U} \subset \mathcal{F}$ となる．$X, I\setminus X\in \mathcal{F}$ なので，条件 (3) より $\emptyset = X \cap (I \setminus X) \in \mathcal{F}$ となるが，これは条件 (1) に反する．よって $\mathcal{U} = \mathcal{F}$ となるので，$\mathcal{U}$ は極大フィルターである．

(⇒) を示す．$\mathcal{M}$ を $I$ 上の極大フィルターであるとする．$I \setminus X \notin \mathcal{M}$ として，$X\in\mathcal{M}$ を示せば十分である．そこで，フィルター $\mathcal{F}$ を次で定める． $$\mathcal{F} \mathrel{:=}\left\{ Y \subseteq I\ \ \middle|\ \ \exists Z \in \mathcal{M}\ [X \cap Z \subseteq Y]\right\}$$ $Z \in \mathcal{M}$ とすれば，$X \cap Z \subseteq Z$ であるので， $\mathcal{M} \subseteq \mathcal{F}$ である．$\emptyset \in \mathcal{F}$ とすると，$\exists Z \in \mathcal{M}\ [X \cap Z \subseteq \emptyset]$ となり，これは $Z \subseteq I \setminus X$ と同値であるので，$I \setminus X \in \mathcal{M}$ となってしまう．よって $\emptyset \notin \mathcal{F}$．同様に (3) も証明出来，$\mathcal{F}$ は $\mathcal{M}$ を含むフィルターであることが判る．よって $\mathcal{M}$ の極大性より $\mathcal{F} = \mathcal{M}$ である．また，任意の集合 $A$ について $X \cap A \subseteq X$ であるので $X \in \mathcal{F} = \mathcal{M}$．よって $\mathcal{M}$ はウルトラフィルターである．

フィルターが有限交叉性を持つことは明らかである．ウルトラフィルター $\mathcal{U}$ に属さない元を $X$ とすると，$I \setminus X \in \mathcal{U}$ であるので，$\mathcal{U} \cup \left\{X\right\}$ は有限交叉性を持たない．よって，ウルトラフィルターは有限交叉性を持つ極大な部分集合族である．

逆に $\mathcal{U}$ を極大な有限交叉的部分集合族であるとする．$\mathcal{U}$ がフィルターであることを示せば，任意のフィルターが有限交叉性を持つことから極大性は従う．(1) は明らか．$X \in \mathcal{U}$ かつ $X \subseteq Y$ とする．$A_1, \dots, A_n \in \mathcal{U}$ とすると，$\mathcal{U}$ の有限交叉性から $Y \cap A_1 \cap \dots \cap A_n \supseteq X \cap A_1 \cap \dots A_n \neq \emptyset$．よって $\mathcal{U} \cup \left\{Y\right\}$ は有限交叉性を持ち，特に $\mathcal{U}$ は極大であるので $Y \in \mathcal{U} \cup \left\{Y\right\} = \mathcal{U}$．よって (2) は成立．(3) についても，$\mathcal{U}$ の有限交叉性より明らか．よって $\mathcal{U}$ はフィルターである．

$L(\mathfrak{C})$ の項の構成に関する帰納法で示す．$t_1, \dots, t_n$ を $a_1, \dots, a_n$ 以外に自由変数を持たない $L(\mathfrak{C})$ の項とし，$\tau_j(i) = (t_{j}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_{i}}$ とする．帰納法の仮定は $(t_j[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}])^{\mathfrak{C}} = [\tau_j]$ である．$f$ を $n$-変数関数記号とすると，

$$\begin{aligned} (f(t_1, \dots, t_n)[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}])^{\mathfrak{C}} &\equiv (f(t_1[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}], \dots, t_n[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]))^{\mathfrak{C}} & (\text{置換の定義})\\ &\equiv f^{\mathfrak{C}}(t_1[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]^{\mathfrak{C}}, \dots, t_n[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]^{\mathfrak{C}}) & (\text{解釈の定義})\\ &\equiv f^{\mathfrak{C}}([\tau_1],\dots,[\tau_n]) & (\text{帰納法の仮定})\\ &\equiv [i \mapsto f^{\mathfrak{A}_i}(\tau_1(i), \dots, \tau_n(i))] & (\text{超積の定義})\\ &\equiv [i \mapsto f^{\mathfrak{A}_i}((t_{1}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_{i}}, \dots, (t_{1}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_{i}})] & (\tau_j \text{の定義})\\ &\equiv [i \mapsto (f(t_1, \dots, t_n)[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_i}] \end{aligned}$$

よって示された．

$L(\mathfrak{C})$の論理式の構造帰納法で示す．以下，$|\mathfrak{C}|$ の元と $L(\mathfrak{C})$ での名前を同一視する．

1. $A \equiv P t_1 \dots t_n$ のとき．$P$ を $n$-変数述語記号，$t_1, \dots, t_n$ を $L(\mathfrak{C})$ の項とすると，

   $$\begin{aligned} & \mathfrak{C} \models (P t_1 \dots t_n)[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]\\ & \Leftrightarrow \mathfrak{C} \models P(t_1[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}])\dots(t_n[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}])\\ & \Leftrightarrow (t_1[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]^{\mathfrak{C}}, \dots, t_n[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]^{\mathfrak{C}}) \in P^\mathfrak{C} & \quad (\models \text{の定義})\\ & \Leftrightarrow ([\tau_1], \dots, [\tau_n]) \in P^\mathfrak{C} & (\text{補題}；但し補題の記号を用いた)\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ (\tau_1(i), \dots, \tau_n(i)) \in P^{\mathfrak{A}_i}\right\} \in \mathcal{U}& (超積の定義)\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ ((t_{1}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_{i}}, \dots, (t_{n}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_{i}}) \in P^{\mathfrak{A}_i}\right\} \in \mathcal{U}\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models P(t_{1}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])\dots(t_{n}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])\right\} \in \mathcal{U} & (\models \text{の定義})\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models (P t_1 \dots t_n)[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} & (\models \text{の定義}) \end{aligned}$$

2. $A \equiv B \wedge C$ のとき．$B, C$ は命題を満たす論理式であるとする（帰納法の仮定）．

   $$\begin{aligned} &\mathfrak{C} \models (B \wedge C)[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]\\ &\Leftrightarrow \mathfrak{C} \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}] \wedge C[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]\\ &\Leftrightarrow \mathfrak{C} \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}] \mathbin \mathfrak{C} \models C[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}] &\quad(\models \text{の定義})\\ &\Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} \text{かつ} \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models C[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} &\quad (\text{帰納法の仮定})\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \cap \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models C[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} & (\text{フィルターの定義} (3))\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}] \text{かつ} \mathfrak{A}_i \models C[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U}\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}] \wedge C[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} & (\models \text{の定義})\\ & \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models (B \wedge C)[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} \end{aligned}$$

3. $A \equiv \neg B$ のとき．ここでウルトラフィルターであることが効いてくる．

   $$\begin{aligned} \mathfrak{C} \models (\neg B)[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]&\Leftrightarrow \mathfrak{C} \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}]\text{でない}\\ &\Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \notin \mathcal{U} &\quad (\text{帰納法の仮定})\\ &\Leftrightarrow I \setminus \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} & \quad (\mathcal{U}:\text{ウルトラフィルター})\\ &\Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \not\models B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U}\\ &\Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models \neg B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U} \end{aligned}$$

4. $A \equiv B \vee C, B \rightarrow C$ のとき．$B \vee C$ の時は，$\neg (\neg B \wedge \neg C)$ を考えるか，ウルトラフィルターの性質から $X \cup Y \in \mathcal{U} \Rightarrow X \in \mathcal{U} \vee Y \in \mathcal{U}$ となることを使う．$B \to C$ のときは定義から明らか．

5. $A \equiv \exists x B$ のとき．(⇒) の方向は明らか．(⇐) の方向について． $S \mathrel{:=}\left\{i \in I\ \ \middle| \mathfrak{A}_i \models (\exists x B) [\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\}$ とおく．$u \in \prod_{i \in I} |\mathfrak{A}_i|$ を次のように構成する．まず， $i \in S$ に対しては $\mathfrak{A}_i \models B\genfrac{[}{]}{0pt}{}{x}{u(i)}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]$ となるように適当な $u(i) \in |\mathfrak{A}_i|$ を取れる．$i\notin S$ の場合は適当に何でもよいから $|\mathfrak{A}_i|$ の元を取る．すると，$[u]$ が $B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}][\begin{smallmatrix}x \\ {[u]}\end{smallmatrix}]$ を満足する．

6. $A \equiv \forall x B$ の場合も上と同様．

以上より示された．

$1 \Rightarrow 2$ は明らか．逆を示す．

$I = \mathfrak{P}_{\mathrm{fin}}(\mathcal{T})$ （$\mathcal{T}$ の有限部分集合全体）と置く．このとき，$2$ より任意の $S \in I$ に対し，$\mathfrak{A}_S \models S$ となるような $L$-構造 $\mathfrak{A}_S$ が取れる．今，$V_S \mathrel{:=}\left\{X \in I\ \ \middle|\ \ S \subseteq X\right\}$ とおけば，$V_S \neq \emptyset$ であり， $V_{S_1} \cap V_{S_2} = V_{S_1 \cup S_2}$ となるので， $$\mathcal{F} \mathrel{:=}\left\{ Y \subseteq I\ \ \middle|\ \ \exists S \in I [V_S \subseteq Y] \right\}$$ とおけば，$\mathcal{F}$ はフィルターとなる．よってウルトラフィルターの補題より $\mathcal{F} \subseteq \mathcal{U}$ となるようなウルトラフィルター $\mathcal{U}$ が取れる．$\mathfrak{C} = \left.{\prod_{S \in I} \mathfrak{A}_S}\middle/{\mathcal{U}}\right.$ が $\mathcal{T}$ のモデルとなることを示そう．それには，Łośの補題より $\varphi \in \mathcal{T}$ に対し， $\left\{S \in I\ \ \middle|\ \ \mathfrak{A}_S \models \varphi\right\} \in \mathcal{U}$ を示せば十分である．今，$V_{\left\{\varphi\right\}} \in \mathcal{U}$ であり，$S \in V_{\left\{\varphi\right\}}$ とすると $S$ は有限部分集合なのでモデルを持ち，$\varphi \in S$ より $\mathfrak{A}_S \models \varphi$．よって $V_{\left\{\varphi\right\}} \subseteq \left\{S \in I\ \ \middle|\ \ \mathfrak{A}_S \models \varphi\right\}$．今，$\mathcal{U}$ はフィルターだったから，結局 $\left\{S \in I\ \ \middle|\ \ \mathfrak{A}_S \models \varphi\right\} \in \mathcal{U}$ となり，命題が示された．

$I, \mathfrak{A}_S$ を定めるところまでは上と同様である．次に，$A_\varphi \mathrel{:=}\left\{S \in I\ \ \middle| \mathfrak{A}_S \models \varphi\right\}$ と置く．$2$ より特に $\mathfrak{A}_{\left\{\varphi, \psi\right\}} \models \varphi, \psi$ なので， $\mathfrak{A}_{\left\{\varphi, \psi\right\}} \in A_\varphi \cap A_\psi$．よって $\mathcal{E} \mathrel{:=}\left\{ A_\varphi\ \ \middle|\ \ \varphi \in \mathcal{T}\right\}$ とおけば，$\mathcal{E}$ は有限交叉性を持つ．ウルトラフィルターの補題より $\mathcal{E}$ はウルトラフィルター $\mathcal{U}$ に拡張出来るので，これによる超積を考えてやると，Łośの定理から直ちに $1$ が従う．