第四回選択公理オフ：数理論理学の初歩の初歩の初歩の……

はじめに

この発表では，数理論理学の初歩的な知識から始まって，構造の濃度に関する Löwenheim-Skolem の定理や，超積に関する Łoś の定理¹と選択公理の関係について述べます．これらは，数理論理学と呼ばれる分野の初歩的な結果です．数理論理学は集合論やモデル理論，証明論，計算理論など幾つもの分野に別れていますが，ここで扱うのはややモデル理論よりの結果です．数理論理学は数学という営為じたいを数学的に分析してみよう！という分野ですので，はじめて見るぜ！という人に関しても，普段自分達がやっている数学がどのように形式化され扱われるのかを鑑賞して頂ければと思います．また，以下では本質に関わらない記号の選び方云々に関しては，意図的に適当に書いて目を瞑ったところがあります．また，この発表ではモデル理論的な側面を強調して，証明論的な側面は殆んど触れられていません．しっかりとした数理論理学の導入をするのであれば，形式的証明の概念をしっかりと定義して，完全性定理によって意味と構文の関係を確立するという事をするべきですが，発表の都合上省略せざるを得ませんでした．数理論理学の入門には田中 [1]や新井 [2]，江田 [3]，古森・小野 [4] などを，モデル理論の発展的な内容については坪井 [5]を読むと良いでしょう．

最初の内は無関係に見えるかもしれませんが，後程 @alg_d さんの発表との関係も判然としてくる予定です．

論理式と言語

数学を記述するのに我々は数式を使う．特に，定理や証明で条件を書き下したりするのに，しばしば論理式を使う．これから「数学」を数学的に記述するに当って，この数学で使われている言葉を，数学的に厳密に定義するところから始めよう．

それでは早速論理式の定義を……といきたいところだが，その前に幾つか定義しておかなくてはならない事がある．それは，今我々が考えている言語は何か？ということだ．つまり，どんな述語や関数，定数などを使うのか，ということを明らかにしておかなくてはならない．例えば，環の理論を考える²時は，二つの演算 $+, \cdot$ と定数 $0, 1$ を使うし，集合論を考える時は原理的には所属関係を表す $\in$ だけを使って議論することになる．このように，予め議論する対象をはっきりさせておかなければならないのだ．

言語 $\mathcal{L}$ とは，述語記号列 $\left\langle\: P_i \; \middle|\; i \in I \:\right\rangle$ ，関数記号列 $\left\langle\: f_j \; \middle|\; j \in J \:\right\rangle$ ，定数記号列 $\left\langle\: c_k \; \middle|\; k \in K \:\right\rangle$ の組の事である．また，各述語記号と関数記号には arity と呼ばれる自然数 $n_i, n_j$ が各々対応しており， $P_i$ は $n_i$ -変数述語記号であるとか， $f_j$ は $n_j$ -変数述語関数であるなどと云う．

このように，言語は述語記号だけであったり，関数記号だけであったりしてもよい．一般に，言語の記号を増やせば増やすほど記述出来る内容は増えるが，集合論のように $\in$ だけで全てを表現したりも出来るので，一概にはいえない．

次に， $\sin x$ とか $x^2$ ， $1+1$ といった論理式ではない「数式」に当るものとして， $\mathcal{L}$ -項を定義しよう．

次のようにして，言語 $\mathcal{L}$ の項を定める：

定数記号 $c$ は項である．
変数記号 $x_i$ は項である．
$f$ が $n$ -変数関数記号で， $\tau_1, \dots, \tau_n$ が項ならば， $f(\tau_1, \dots, \tau_n)$ も項である．
以上で作られるものだけが項である．

特に，変数記号の出現しない項を閉項と呼ぶ．

上の最後の「以上で作られるものだけが項である」という約束により，論理式の構成に関する帰納法を使うことが出来る．以後，こうした帰納的定義の最後に一々書くのも面倒なので，最後には「以上で作られるものだけが〜」と書かれていると読んで欲しい．

ここまで準備すれば，論理式を定義することが出来る．

言語 $\mathcal{L}$ の論理式を次のように定義する：

$\tau_1, \tau_2$ が項の時， $\tau_1 = \tau_2$ は論理式である．
$P$ が $n$ -変数述語記号で $\tau_1, \dots, \tau_n$ が項の時， $P \tau_1 \dots \tau_n$ は論理式である．

以上の二つを特に原子論理式と云う．

$\varphi, \psi$ が論理式の時， $\neg \varphi$ および $\varphi \vee \psi$ も論理式である．
$x$ が変数記号， $\varphi$ が論理式の時， $\exists x \varphi$ も論理式である．

記号はあくまで記号であって，意味はないのだが，それでも一応意図された意味というものがあるのでそれを説明しよう． $\varphi \vee \psi$ は「 $\varphi$ または $\psi$ 」を， $\neg \varphi$ は「 $\varphi$ でない」を， $\exists x \varphi$ は「 $\phi$ を満たすような $x$ が存在する」という意味を意図している．「かつ」とか「ならば」とか「任意の」などが抜けているが，これらの論理結合子は，上の三つの組合せで「定義」できることが知られている³ので，それぞれに対応する「略記」を次のように導入しておく： $\varphi \wedge \psi \mathrel{.{\equiv}.} \neg (\neg \varphi \vee \neg \psi), \qquad \varphi \rightarrow \psi \mathrel{.{\equiv}.} \neg \varphi \vee \psi, \qquad \forall x \varphi \mathrel{.{\equiv}.} \neg \exists x \neg \varphi$ $\wedge, \rightarrow, \forall$ なども予め定義にいれておいたほうが分かり易いかもしれないが，記号が多いと後々の証明が大変になるので必要最低限に限ったのである．

論理式の解釈と初等拡大

上では論理式を定義したが，あくまで文字列の構成法として定義しただけである．論理式は何らかの数学的な内容を意味するのだから，その解釈を定めてやらなければ意味がない．

$\mathcal{L}$ -構造 $\mathfrak{A} = \left\langle\: A, P_i^\mathfrak{A}, f_j^\mathfrak{A}, c_k^\mathfrak{A} \; \middle|\; i \in I, j \in J, k \in K \:\right\rangle$ とは，次を満たすものである：

$A$ は空でない集合である． $A = |\mathfrak{A}|$ などと表し， $\mathfrak{A}$ の議論領域などと呼んだりする．
$P_i$ が $n_i$ -変数述語記号の時， $P_i^\mathfrak{A}$ は $A$ 上の $n$ -項関係である．つまり $P_i^\mathfrak{A} \subseteq A^n$ ．
$f_j$ が $n_j$ -変数関数記号の時， $f_j^\mathfrak{A}: A^n \rightarrow A$ である．
$c_k$ が定数記号の時， $c_k^\mathfrak{A} \in A$ である．

上で定めた $P_i^\mathfrak{A}, f_j^\mathfrak{A}, c_k^\mathfrak{A}$ などを， $\mathcal{L}$ の記号の $\mathfrak{A}$ での解釈と呼ぶ．

また， $\mathcal{L}$ の一般の閉項 $\tau$ に対し，関数記号とその「引数」となる項に対して繰り返し解釈を取ることにより， $\tau$ の $\mathfrak{A}$ での解釈 $\tau^\mathfrak{A}$ を帰納的に定義する．

ここで， $\mathcal{L}$ -構造 $\mathfrak{A}$ に対し， $\mathfrak{A}$ 自身を写し取ったような言語 $L(\mathfrak{A})$ を考えることが出来る．

$\mathcal{L}$ -構造 $\mathfrak{A}$ に対し，言語 $L(\mathfrak{A})$ を $\mathcal{L}(\mathfrak{A}) = \mathcal{L} \cup \left\{\: c_a \;\middle|\; a \in A \:\right\}$ で定義する．ここで $c_a$ は $\mathcal{L}$ に含まれないような，各 $a \in A$ ごとに異なる新しい定数記号であり， $a \in A$ の名前と呼ばれる． $c_a^\mathfrak{A} = a$ として解釈を定めてやることにより， $\mathfrak{A}$ は自然に $\mathcal{L}(\mathfrak{A})$ -構造と見ることが出来る．

さて， $\mathcal{L}$ -構造というのを考えるのは，論理式の「意味」を与えてやるためであった．そこで，次のようにして論理式の解釈を定めてやろう：

$\mathcal{L}$ -構造 $\mathfrak{A}$ と $\mathcal{L}(\mathfrak{A})$ -論理式 $\varphi$ に対し，関係 $\mathfrak{A} \models \varphi$ （ $\mathfrak{A}$ は $\varphi$ を満たすと読む）を次のように帰納的に定める：

$\mathfrak{A} \models \tau_1 = \tau_2 \Longleftrightarrow \tau_1^\mathfrak{A} = \tau_2^\mathfrak{A}$
$\mathfrak{A} \models P\tau_1 \dots \tau_n \Longleftrightarrow (\tau_1^\mathfrak{A}, \dots, \tau_n^\mathfrak{A}) \in P^\mathfrak{A}$
$\mathfrak{A} \models \varphi \vee \psi \Longleftrightarrow \mathfrak{A} \models \varphi$ または $\mathfrak{A} \models \psi$ の少なくとも一方が成立する．
$\mathfrak{A} \models \neg \varphi \Longleftrightarrow \mathfrak{A} \models \varphi$ でない
$\mathfrak{A} \models \exists x \varphi \Longleftrightarrow$ ある $a \in A$ が存在して， $\mathfrak{A} \models \varphi[\begin{smallmatrix}x\\c_a\end{smallmatrix}]$ となる．

ただし，ここで $\varphi[\begin{smallmatrix}x\\\tau\end{smallmatrix}]$ は， $\varphi$ の中に自由に出現する変数 $x$ を項 $\tau$ で置き換えたものである．

読み方通り， $\mathfrak{A} \models \varphi$ は構造 $\mathfrak{A}$ で $\varphi$ が成立することを示す物である．たとえば，群の公理を $\mathrm{Grp}$ と置くと， $(\mathbb{Z}, +) \models \mathrm{Grp}, (\mathbb{R}^\times, \cdot) \models \mathrm{Grp}$ だが， $(\mathbb{N}, +) \not\models \mathrm{Grp}$ である．こういったことをもっと通り良く述べるために，次のように定義をする．

$\mathcal{L}$ -閉論理式の集合 $\mathcal{T}$ の事を $\mathcal{L}$ -公理系とか $\mathcal{L}$ -理論などと呼ぶ
$\mathcal{L}$ -構造 $\mathfrak{A}, \mathfrak{B}$ が初等的同値（記号： $\mathfrak{A} \equiv \mathfrak{B}$ ）であるとは， $\mathrm{Th}_\mathcal{L}(\mathfrak{A}) = \mathrm{Th}_\mathcal{L}(\mathfrak{B})$ となることである．
$\mathcal{T}$ を $\mathcal{L}$ -理論とする． $\mathcal{L}$ -構造 $\mathfrak{A}$ が，任意の $\varphi \in \mathcal{T}$ に対し $\mathfrak{A} \models \varphi$ を満たすとき， $\mathfrak{A}$ は $\mathcal{T}$ のモデルであると云う．このとき， $\mathfrak{A} \models \mathcal{T}$ と書く．
論理式 $\varphi$ について，理論 $\mathcal{T}$ の任意のモデル $\mathfrak{A}$ で $\mathfrak{A} \models \varphi$ となる時， $\mathcal{T} \models \varphi$ と書く．
$\mathrm{Th}_\mathcal{L}(\mathfrak{A}) \mathrel{:=} \left\{\: \varphi : \mathcal{L}\text{-閉論理式} \;\middle|\; \mathfrak{A} \models \varphi \:\right\}$ を言語 $\mathcal{L}$ についての $\mathfrak{A}$ の公理系と云う．
$\mathrm{Diag}(\mathfrak{A}) \mathrel{:=} \mathrm{Th}_{\mathcal{L}(\mathfrak{A})} = \left\{\: \varphi : \mathcal{L}(\mathfrak{A})\text{-閉論理式} \;\middle|\; \mathfrak{A} \models \varphi \:\right\}$ を， $\mathfrak{A}$ の初等設計図と呼ぶ．
構造 $\mathfrak{A}, \mathfrak{B}$ が同型であるとは，全単射 $\sigma: A \rightarrow B$ が存在して， $\begin{gathered} \sigma(c^\mathfrak{A}) = c^\mathfrak{B}\qquad\sigma(f^\mathfrak{A}(u_1, \dots, u_n)) = f^{\mathfrak{B}}(\sigma(u_1), \dots, \sigma(u_n))\\ (u_1, \dots, u_n) \in P^\mathfrak{A} \Longleftrightarrow (\sigma(u_1), \dots, \sigma(u_n)) \in P^\mathfrak{B} \end{gathered}$ を満たすことである．このとき $\mathfrak{A} \cong \mathfrak{B}$ と書く．

構造と解釈に関する定義を幾つか済ませた所で，こんどは部分構造について定義しておこう．

$\mathcal{L}$ -構造 $\mathfrak{A}, \mathfrak{B}$ について， $\mathfrak{A}$ が $\mathfrak{B}$ の部分構造であるとは， $A \subseteq B$ であり，以下の三つの条件が成立することである：
1. 定数記号 $c$ について， $c^\mathfrak{A} = c^\mathfrak{B}$
2. $n$ -変数述語記号 $P$ について， $P^\mathfrak{A} = P^\mathfrak{B} \cap A^n$
3. $n$ -変数関数記号 $f$ について， $f^\mathfrak{B} \upharpoonright A^n = f^\mathfrak{A}$
$\mathfrak{A}$ が $\mathfrak{B}$ の部分構造であるとする．任意の $\mathcal{L}(\mathfrak{A})$ -論理式 $\varphi$ が $\mathfrak{A} \models \varphi \Longleftrightarrow \mathfrak{B} \models \varphi$ を満たすとき， $\mathfrak{A}$ は $\mathfrak{B}$ の初等部分構造である，または $\mathfrak{B}$ は $\mathfrak{A}$ の初等拡大であると云い， $\mathfrak{A} \prec \mathfrak{B}$ と書く．先程の記号を使えば， $\mathfrak{A} \prec \mathfrak{B} \Leftrightarrow \mathrm{Diag}(\mathfrak{A}) = \mathrm{Th}_{\mathcal{L}(\mathfrak{A})}(\mathfrak{B})$ である．

例えば， $\mathfrak{N} = (\mathbb{N}, +)$ は $\mathfrak{Z} = (\mathbb{Z}, +)$ の部分構造であるが， $\mathcal{N} \prec \mathcal{Z}$ ではない． $\mathbb{Z}$ には逆元が存在するが， $\mathbb{N}$ はそもそも群ではないからである．また， $M_2(\mathbb{R})$ と $H = \left\{\: (\begin{smallmatrix}a & 0 \\ 0 & 0 \end{smallmatrix}) \;\middle|\; a \in \mathbb{R}^\times \:\right\}$ を考えると， $\left\langle H, +, \cdot \right\rangle$ は $\left\langle M_2(\mathbb{R}), +, \cdot \right\rangle$ の部分構造となり，乗法単位元はそれぞれ $(\begin{smallmatrix}1&0 \\ 0&1\end{smallmatrix})$ と $(\begin{smallmatrix}1&0 \\ 0&0\end{smallmatrix})$ である．部分環の定義に $0, 1$ を含めるかは流儀による．含めない場合は $\left\langle +, \cdot \right\rangle$ -部分構造が，含める場合は $\left\langle 1, \cdot, + \right\rangle$ -部分構造が部分環と一致する．

また，言語 $\mathcal{L} = \left\langle +, < \right\rangle$ について， $\mathfrak{A} = (\mathbb{N}, +, <)$ と $\mathfrak{B} = (\mathbb{N} \setminus \{0\}, +, <)$ は同型になる．しかし， $\mathcal{L}(\mathfrak{B})$ -論理式 $\psi \equiv \forall x \neg (x < 1)$ を考えると， $\mathfrak{B} \models \psi$ だが $\mathfrak{A} \not\models \psi$ なので， $\mathfrak{B} \prec \mathfrak{A}$ ではない．

初等部分構造となる例としては， $(\mathbb{Q}, \leq) \prec (\mathbb{R}, \leq)$ や， $(\bar{\mathbb{Q}}, +, \cdot) \prec (\mathbb{C}, +, \cdot)$ などが知られている．

より一般に，何らかの構造が与えられた際に，その非自明な初等拡大を構成する方法はあるのだろうか？その例の一つが，次節で扱う超積の特殊な場合である超冪である．

超積の定義と Łoś の定理，そして選択公理

$\mathcal{L}$ -構造の族が与えられた時に，その「殆んど至るところ」で成立する性質を取り出したものが超積である．午前中の発表でもあったように，フィルターの例として $[0,1]$ 上の測度 $1$ の集合全体の成すフィルターがある．測度 $1$ の集合は明らかに「大きな」集合である．ウルトラフィルターはその中でも更にキメが細かいフィルターであり，ウルトラフィルターに属する集合は「大きな集合」全体であると見做せる⁴．そこで，族の「大部分」で成り立つ性質を取り出すのに，ウルトラフィルターを使ってみよう，という訳である．

$\{\mathfrak{A}_i\}_{i\in I}$ を $\mathcal{L}$ -構造の族（ $I \neq 0$ ）， $\mathcal{F}$ を $I$ 上のフィルターとする．この時， $\prod_{i \in I} |\mathfrak{A}_i|$ 上の二項関係 $\sim_\mathcal{F}$ を次で定義する． $u \sim_\mathcal{F} v \xLeftrightarrow{\mathrm{def}} \left\{\: i \in I \;\middle|\; u(i) = v(i) \:\right\} \in \mathcal{F}\ \ \ \left(u, v \in \prod_{i \in I} |\mathfrak{A}_i|\right)$ このとき， $\sim_\mathcal{F}$ は同値関係となっている． $u, v$ が「大きい集合で一致すれば」，つまり殆んど至るところで一致すれば， $u, v$ を等しいと見做すのが，関係 $\sim_\mathcal{F}$ である．

$\{\mathfrak{A}_i\}_{i \in I}$ の $\mathcal{F}$ による縮積（reduce product） $\mathfrak{C} = \prod_{i \in I} \mathfrak{A}_i/\mathcal{F}$ とは， $\prod_{i\in I} |\mathfrak{A}_i|$ の $\sim_\mathcal{F}$ による商集合のことである．即ち， $u$ の $\sim_{\mathcal{F}}$ による同値類を $[u]_{\mathcal{F}}$ と書けば， $\prod_{i\in I} \mathfrak{A}_i/\mathcal{F} = \left\{\: [u]_\mathcal{F} \;\middle|\; u \in \prod_{i\in I} \left|\mathfrak{A}_i\right| \:\right\}$ のことである．このとき， $\mathfrak{C}$ の $\mathcal{L}$ -構造としての述語記号，関数記号に関する解釈は次により定める． $\begin{gathered} ([u_1], \dots, [u_n]) \in P^\mathfrak{C} \Leftrightarrow \left\{\: i \in I \;\middle|\; (u_1(i), \dots, u_n(i)) \in P^{\mathfrak{A}_i} \:\right\} \in \mathcal{F}\\ f^\mathfrak{C}([u_1], \dots, [u_n]) = [u] \quad (\text{ただし} u(i) = f^{\mathfrak{A}_i}(u_1(i), \dots, u_n(i)))\\ c^\mathfrak{C} = [c^{\mathfrak{A}_i}] \end{gathered}$

特に，ウルトラフィルター $\mathcal{U}$ に関する縮積を超積（ultraproduct）と云う．

上の $\sim_\mathcal{F}$ が実際に同値関係となることはすぐに判る．また，上の縮積の定義が well-defined であることは本来ならば示すべきだが，面倒なので各自の演習問題とする．

超積が「殆んど至るところで成立する性質を取り出したもの」ということを定式化したのが次の定理である．

$\mathcal{U}: I\text{上のウルトラフィルター},\quad \mathfrak{C} = \prod_{i \in I}\mathfrak{A}_i/\mathcal{U}$

$\varphi(a_1, \dots, a_n): \mathcal{L}\text{-論理式},\quad [u_1], \dots, [u_n] \in |\mathfrak{C}|$ とすると，次が成立．

$\mathfrak{C} \models \varphi([u_1], \dots, [u_n]) \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \varphi(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U}$

定理の証明の為に，次の補題を使う．

$t(a_1, \dots, a_n)$ を $\mathcal{L}$ -項， $\tau(i) = (t(u_1(i), \dots, u_n(i)))^\mathfrak{A_i}$ とする．このとき， $(t([u_1], \dots, [u_n]))^{\mathfrak{C}} = [\tau]$

これは当然成り立つべき命題であるし，証明も単に帰納法で示せるのでここでは省略し，Łoś の定理を示す．

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

$\varphi \equiv P t_1 \dots t_n$ （原子論理式）のとき． $P$ を $m$ -変数述語記号， $t_1, \dots, t_m$ を $L(\mathfrak{C})$ の項とすると，

$\begin{alignedat}{2} & \mathfrak{C} \models (P t_1 \dots t_m)([u_1], \dots, [u_n])\\ & \Leftrightarrow \mathfrak{C} \models P t_1([u_1], \dots, [u_n])\dots t_m([u_1], \dots, [u_n])\\ & \Leftrightarrow (t_1([u_1], \dots, [u_n])^{\mathfrak{C}}, \dots, t_m([u_1], \dots, [u_n])^{\mathfrak{C}}) \in P^\mathfrak{C} & \quad (\models \text{の定義})\\ & \Leftrightarrow ([\tau_1], \dots, [\tau_m]) \in P^\mathfrak{C} & (\text{補題}\href{\#ultraproduct-term}{1}\text{；但し補題の記号を用いた})\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; (\tau_1(i), \dots, \tau_m(i)) \in P^{\mathfrak{A}_i} \:\right\} \in \mathcal{U}& (\text{超積の定義})\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models P(t_1(u_1(i), \dots, u_n(i)))\dots(t_m(u_1(i), \dots, u_n(i))) \:\right\} \in \mathcal{U} & (\models \text{の定義})\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models (P t_1 \dots t_m)(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} & (\models \text{の定義}) \end{alignedat}$
$\varphi \equiv \psi \vee \vartheta$ の時． $\psi, \vartheta$ は命題を満たす論理式であるとする（帰納法の仮定）． $\begin{alignedat}{2} &\mathfrak{C} \models (\psi \vee \vartheta)([u_1], \dots, [u_n])\\ &\Leftrightarrow \mathfrak{C} \models \psi([u_1], \dots, [u_n]) \vee \vartheta([u_1], \dots, [u_n])\\ &\Leftrightarrow \mathfrak{C} \models \psi([u_1], \dots, [u_n]) \mathbin{\text{または}} \mathfrak{C} \models \vartheta([u_1], \dots, [u_n]) &\quad(\models \text{の定義})\\ &\Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \psi(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} \text{または} \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \vartheta (u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} &\quad (\text{帰納法の仮定})\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \psi(u_1(i), \dots, u_n(i)) \:\right\} \cup \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \vartheta (u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U}& (\star)\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \psi(u_1(i), \dots, u_n(i)) \text{または} \mathfrak{A}_i \models \vartheta(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U}\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \psi(u_1(i), \dots, u_n(i)) \vee \vartheta(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} & (\models \text{の定義})\\ & \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models (\psi \vee \vartheta)(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} \end{alignedat}$ ただし， $(\star)$ では， $\mathcal{U}$ がウルトラフィルターの時， $A \cup B \in \mathcal{U} \rightarrow A \in \mathcal{U} \vee B \in \mathcal{U}$ となることを使った．
$\varphi \equiv \neg \psi$ の時． $\begin{alignedat}{2} \mathfrak{C} \models (\neg \psi)([u_1], \dots, [u_n]) &\Leftrightarrow \mathfrak{C} \models \psi([u_1], \dots, [u_n]) \text{でない}\\ &\Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \psi(u_1(i), \dots, u_n(i)) \:\right\} \notin \mathcal{U} &\quad (\text{帰納法の仮定})\\ &\Leftrightarrow I \setminus \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \psi(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} & \quad (\mathcal{U}:\text{ウルトラフィルター})\\ &\Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \not\models \psi(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U}\\ &\Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \neg \psi(u_1(i), \dots, u_n(i)) \:\right\} \in \mathcal{U} \end{alignedat}$
$\varphi \equiv \exists x \psi(x, [u_1], \dots, [u_n])$ の時．この証明に選択公理を使う． $(\Leftarrow)$ の方向について述べれば十分．

$S \mathrel{:=} \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \exists x \psi(x, u_1(i), \dots, u_n(i)) \:\right\}$ とおく． $u \in \prod_{i \in I} |\mathfrak{A}_i|$ を次のように構成する．まず， $i \in S$ に対しては，選択公理により $\mathfrak{A}_i \models \psi(u(i), u_1(i), \dots, u_n(i))$ となるように適当な $u(i) \in |\mathfrak{A}_i|$ を取れる． $i\notin S$ の場合は適当に何でもよいから $|\mathfrak{A}_i|$ の元を取る（選択公理！！！）．すると， $[u]$ が $\psi([u], [u_1], \dots, [u_n])$ を満足する．

以上より示された．

Łoś の定理の系として，次が得られる．

$\varphi: L\text{-閉論理式}$ とするとき， $\prod_{i \in I}\mathfrak{A}_i/\mathcal{U} \models \varphi \Leftrightarrow \left\{\: i \in I \;\middle|\; \mathfrak{A}_i \models \varphi \:\right\} \in \mathcal{U}$

特に $\mathfrak{A}_i = \mathfrak{A}$ とする．このように，各 $\mathfrak{A}_i$ が等しい場合の超積を，特に超冪（ウルトラパワー；ultrapower）と呼ぶ．このとき， $u \in |\mathfrak{A}|$ について $c_u(i) = u \quad (i \in I)$ により定数関数 $c_u \in {}^{I} {\mathfrak{A}}$ を定めれれば，写像 $u \mapsto [c_u]$ により $\mathfrak{A}$ は $\prod_{i \in I} \mathfrak{A} / \mathcal{U} = {}^{I} {\mathfrak{A}}/\mathcal{U}$ の部分構造と見做すことが出来る．

このとき， $\mathcal{L}$ -論理式 $\varphi(x_1, \dots, x_n)$ に対し次が成立する： ${}^{I} {\mathfrak{A}}/\mathcal{U} \models \varphi([c_{u_1}], \dots, [c_{u_n}]) \Leftrightarrow \mathfrak{A} \models \varphi(u_1, \dots, u_n)$ よって， $\mathfrak{A} \prec {}^{I} {\mathfrak{A}}/\mathcal{U}$ （初等拡大）である．特に， $\varphi$ が $\mathcal{L}$ -閉論理式のとき次が成立． ${}^{I} {\mathfrak{A}}/\mathcal{U} \models \varphi \Leftrightarrow \mathfrak{A} \models \varphi$ 即ち， ${}^{I} {\mathfrak{A}}/\mathcal{U} \equiv \mathfrak{A}$ （初等的同値）である．

実は，「Łoś の定理 + ウルトラフィルターの補題」と選択公理は同値であることが知られている：

$\mathrm{AC} \Longleftrightarrow$ Łoś + ウルトラフィルターの補題

Proof. 証明から $\Rightarrow$ は明らかなので， $\Leftarrow$ を示す．

$\{X_i\}_{i \in I}$ を互いに交わらない非空集合の族とし， $X = \bigcup_{i \in I} X_i$ とする．適当に添字を付け替えることで， $X \cap I = \emptyset$ として良い．そこで $A \mathrel{:=} X \sqcup I$ と置く．この時，二項関係 $\mathrel{\tilde{\epsilon}}$ を $a \mathrel{\tilde{\epsilon}} b \xLeftrightarrow{\mathrm{def}} (a \in X \wedge b \in I \wedge a \in X_b) \vee a = b \in X$ により定め，構造 $\mathfrak{A} = \left\langle A, \mathrel{\tilde{\epsilon}} \right\rangle$ を考える．族 $\{X_i\}_{i \in I}$ が選択関数を持たないと仮定する．このとき， $\mathcal{I} \mathrel{:=} \left\{\: J \subseteq I \;\middle|\; \{X_j\}_{j \in J} \text{は選択関数を持つ} \:\right\}$ は $I$ 上のイデアルとなる．イデアル $\mathcal{I} \subseteq \mathop{\mathcal{P}}(I)$ とは次を満たす部分集合族のことである⁵：

$\emptyset \in \mathcal{I}, I \notin \mathcal{I}$
$A \in \mathcal{I} \wedge B \subseteq A \Rightarrow B \in \mathcal{I}$
$A, B \in \mathcal{I} \Rightarrow A \cup B \in \mathcal{I}$

定義を見ても判る通り，イデアルはフィルターの双対概念であり，「小さな集合」の集まりになっている． $\{X_i\}_{i \in I}$ は選択関数を持たないので， $I \notin \mathcal{I}$ であり，選択関数を持つ族の部分族はやはり選択関数を持つので最初の二つの条件は大丈夫である．また，各々の選択関数の和を考えれば， $\mathcal{I}$ の二つの元に対応する和も再び選択関数を持つことがわかる．

ここで， $\mathcal{I}$ がイデアルの時， $\mathcal{F} = \left\{\: X^c \subseteq I \;\middle|\; X \in \mathcal{I} \:\right\}$ と置けば $\mathcal{F}$ は $I$ 上のフィルターとなる．よって，対応する族が選択関数を持たない $J \subseteq I$ の全体は $I$ 上のフィルターとなる．そこで，ウルトラフィルターの補題により $\mathcal{F} \subseteq \mathcal{U}$ となるウルトラフィルター $\mathcal{U}$ を取ろう．

この時，超冪 ${}^{I} {\mathfrak{A}}/\mathcal{U}$ を考えよう．今， $A$ および $\mathrel{\tilde{\epsilon}}$ の定義より $\mathfrak{A} \models \forall u \exists v(v \mathrel{\tilde{\epsilon}} u)$ が成立している．Łoś の定理より， $\mathfrak{A} \equiv {}^{I} {\mathfrak{A}}/\mathcal{U}$ であるので， ${}^{I} {\mathfrak{A}}/\mathcal{U} \models \forall u \exists v(v \mathrel{\tilde{\epsilon}} u)$ となる．そこで，特に $u = [\mathrm{id}_I]$ と置けば，ある $v \in {}^{I} {\mathfrak{A}}$ が存在して $[v] \mathrel{\tilde{\epsilon}} [\mathrm{id}_I]$ となる．すると，超積の定義から， $J \mathrel{:=} \left\{\: i \in I \;\middle|\; v(i) \mathrel{\tilde{\epsilon}} \mathrm{id}_I(i) \:\right\} \in \mathcal{U}$ となる．すると， $\mathrel{\tilde{\epsilon}}$ の定義より $v(i) \mathrel{\tilde{\epsilon}} i \Leftrightarrow v(i) \in X_i$ であるので， $J = \left\{\: i \in I \;\middle|\; v(i) \in X_i \:\right\} \in \mathcal{U}$ となる．よって， $f \upharpoonright J$ は $\{X_j\}_{j \in J}$ の選択関数である⁶．従って $J \in \mathcal{I}$ であり， $I \setminus J \in \mathcal{F} \subseteq \mathcal{U}$ となる．すると $(1)$ と合わせて $\emptyset = J \cap (I \setminus J) \in \mathcal{U}$ となり， $\mathcal{U}$ がフィルターであることに矛盾する．

自然数の超準モデルと超準解析

ここでは，超冪を用いて自然数の超準モデルを構成する．超準モデル（non-standard model）というのは，通常期待されるような物と異なるモデルでありながら，一階述語論理の範囲内では全く同じ性質を持つようなモデルのことである．また，「超準」という言葉からもわかるように，午前中に扱った超準解析とも関係のある話題である．

まず，午前中 [6]にも出て来た $\mathbb{N}$ 上の Fréchet フィルターを考える． $\mathcal{F}_0 \mathrel{:=} \left\{\: X \subseteq \mathbb{N} \;\middle|\; \mathbb{N} \setminus X \text{は有限集合} \:\right\}$ ウルトラフィルターの補題により，この $\mathcal{F}_0$ を含むようなウルトラフィルター $\mathcal{U}$ を取ることが出来る．このウルトラフィルターはウルトラフィルターの補題によって取り，その証明には選択公理が使われるので，一意なものではなく複数のものがありうることを注意しておく．

以下では，順序環の言語 $\mathcal{L}_{\mathrm{OR}} = \left\langle +, \cdot, \leq \right\rangle$ を考えて，順序環 $\mathfrak{Z} = \left\langle \mathbb{Z}, +, \cdot, \leq \right\rangle$ の $\mathcal{U}$ による超冪 ${}^{*} {\mathfrak{Z}} = {}^{\mathbb{N}} {\mathfrak{Z}}/\mathcal{U}$ を考える． Łoś の定理の系より $\mathfrak{Z} \prec {}^{*} {\mathfrak{Z}}$ であった．即ち， $\varphi$ を $\mathcal{L}_{\mathrm{OR}}(\mathfrak{Z})$ -論理式とすると， ${}^{\mathbb{N}} {\mathfrak{Z}}/\mathcal{U} \models \varphi \Leftrightarrow \mathfrak{Z} \models \varphi$ が成立するのだった． $\mathbb{N}$ 上の恒等写像 $id_\mathbb{N}$ を考えると，午前中の議論と同様にして $\omega \mathrel{:=} [id_\mathbb{N}]$ は無限大の自然数となっていることがわかり，他にも $[id - 1]$ や $[id^2]$ などを考えれば，こうした無限大の自然数は無数に存在するのだった．このような無限大の自然数のことを，超有限自然数と呼ぶ．また， $-[id] < -n$ となるので， $\mathfrak{Z}$ は負の無限大の整数も持つことになる．午前中の超準解析の導入においては，ここでの $\mathfrak{Z}$ の代わりに $\mathbb{R} = \left\langle \mathbb{R}, \mathbb{N}, \mathbb{Z}, \mathbb{Q}, <, \leq, +, \cdot , |\cdot|, \sin, \dots \right\rangle$ というような構造の超冪 ${}^{*} {\mathbb{R}}$ を取ったと考えることが出来る⁷．ここで， $\mathbb{N}, \mathbb{Z}, \mathbb{Q}$ はそれぞれ自然数，整数，有理数を表す一変数述語記号であり， $\sin$ 以降は必要な「関数」に対応する記号を列挙していると思えばよい．

すると，例えば最大値の原理の証明の部分は次のように考えることが出来る．午前中では，まず連続であるということの超実数を使った特徴付けを行い，それを用いた超準的な議論により最大値の原理が ${}^{*} {\mathbb{R}}$ で成立する事を証明した．より詳しく述べよう．まず，Łoś の定理の系より $\mathbb{R} \prec {}^{*} {\mathbb{R}}$ なので， $\mathcal{L}(\mathbb{R})$ -論理式が $\mathbb{R}$ で成り立つことと ${}^{*} {\mathbb{R}}$ で成り立つことは同値である．数列を自然数以外では値 $0$ を取る関数だと思えば，各数列 $a$ に対して「有限列 $a$ は最大値を持つ」という事を $\mathcal{L}(\mathbb{R})$ -論理式で書ける．これは $\mathbb{R}$ で明らかに成立するので， ${}^{*} {\mathbb{R}}$ にもっていっても真である．特に， ${}^{*} {\mathbb{R}}$ での超有限の長さの有限列も最大値を持つことになる．この事を使うと，各関数記号 $f$ について， $f$ が ${}^{*} {[0,1]}$ で連続関数ならばある点で最大値を持つことが（ ${}^{*} {\mathbb{R}}$ で）示せる．ここで，各々の関数 $f$ が「連続である」「最大値を取る」といった事も言語 $\mathcal{L}(\mathbb{R})$ で書ける条件式であるので，今度は同じことが $\mathbb{R}$ でも成り立つ．このように，通常の実数や関数に関する命題である限り，超実数を使って ${}^{*} {\mathbb{R}}$ でその命題を証明したとしても， $\mathbb{R}$ でもその定理が成立するのだ．『《ある意味》で $\mathbb{R}$ で成り立つことは ${}^{*} {\mathbb{R}}$ で成り立ち， ${}^{*} {\mathbb{R}}$ で成り立つことは $\mathbb{R}$ で成り立つ』の「ある意味」というのはこういう意味である．

ところで，このような無限大の自然数が存在するような体系では面白いことが起こる．再び $\mathfrak{Z}$ とその超冪で考えよう．今，任意の整数 $n$ について， $n$ か $n-1$ のいずれかは偶数である．即ち， $\mathfrak{Z} \models \forall n \exists m (n = 2 \cdot m \vee n - 1 = 2\cdot m)$ が成立するのであった．すると，Łoś の定理の系 $\href{\#los-power}{2}$ から ${}^{*} {\mathfrak{Z}} \models \forall n \exists m (n = 2 \cdot m \vee n - 1 = 2\cdot m)$ である．よって $[id]$ か $[id]-1$ のいずれかが $2$ で割れることになる⁸．割れる方を $2$ で割ってやると，これも超有限の自然数になっている．この手続を繰り返して， ${}^{*} {\mathfrak{Z}}$ の元の狭義減少列 $\alpha_0 > \alpha_1 > \dots > \alpha_n > \cdots$ が得られる．これらはいずれも $0$ より大きい．よって自然数の狭義減少列が得られたことになる．

しかし，自然数の整列性から狭義減少列は存在しない筈だ．どういうことか？今我々が考えているのは，「一階述語論理」で書ける範囲の理論であった．つまり，「狭義減少列が存在しない」とか「自然数は整列する」といった概念は，言語 $\mathcal{L}_{\mathrm{OR}}$ を使った一階述語論理では書けないと云うことが，この事実の伝える事なのである⁹．自然数の整列性は，「任意の自然数からなる部分集合に最小値が存在する」という形で述べられるが，この「部分集合」に対する量化が一階述語論理では行えないのである．このことは，「自然数の部分集合」全体は非可算無限個存在するが，自然数の理論自体は可算言語で記述されるため，高々可算個の部分集合しか扱えない，ということを考えるとちょっと分かり易いのではないだろうか．

そうはいっても，「集合と位相」などの講義でそういったことを証明したぞ，と思われるかもしれない．それに，部分集合も扱えないのであればイデアルなどを考えることも出来ず，一階述語論理など考えても仕方がないのではないか？と云う疑問も出て来るだろう．それにもかかわらず数理論理学が主に一階述語論理を対象としているのは概ね次のような事情による．

環や群の公理といったものは，対応する一階述語論理上の理論を定める．こうした理論をZFC集合論の中で解釈して，その内部で様々な操作や議論を行う，というのが普段我々が「数学」でやっていることなのである．その意味で，現代数学は実質的に一階述語論理とその上のZFC集合論の内部で展開出来るということが知られている．「選択公理より極大イデアルが存在するので〜」というような言明の意味は，そういったことである．論理学的にも，一階述語論理は完全性やコンパクト性など扱い易い性質を持っているため，モデル理論や集合論は一階述語論理を使って展開されているのである．また，一階述語論理でその「部分集合」を直に扱うことが出来ないとしても，上の超準解析の議論でやったように，必要な定数や関数などを予め言語に付け加えてしまえば大体おなじようなことが出来る場合が多い¹⁰．

Löwenheim-Skolem の定理

最後に，モデルの濃度に関わる Löwenheim-Skolem の定理を紹介して終わりにしよう．いきなり主張を述べてしまおう．

$\mathcal{L}$ を可算言語， $\mathfrak{B}$ を無限 $\mathcal{L}$ -構造とする．

無限基数 $\kappa \leq \mathop{\mathrm{card}}(\mathfrak{B})$ と $\mathop{\mathrm{card}}(S) \leq \kappa$ となる $S \subseteq |\mathfrak{B}|$ に対し， $S$ を含み濃度 $\kappa$ となるような初等部分構造 $\mathfrak{A} \prec \mathfrak{B}$ が存在する．
$\mathop{\mathrm{card}}(\mathfrak{B}) \leq \kappa$ ならば，濃度 $\kappa$ となるような初等拡大 $\mathfrak{A} \succ \mathfrak{B}$ が存在する．

証明のため，次の初等部分構造の判定条件をまず証明しておく：

$\mathfrak{B}: \mathcal{L}$ -構造， $A \subseteq B$ とする．この時，次は同値：

$A$ に自然な構造を入れることで $\mathfrak{A} \prec \mathfrak{B}$ となる．
任意の $\mathcal{L}(\mathfrak{A})$ -論理式 $\varphi(x)$ に関して， $\mathfrak{B} \models \exists x \varphi(x) \Longrightarrow$ ある $a \in A$ があって $\mathfrak{B} \models \varphi(a)$

Proof. $1 \Longrightarrow 2$ は自明なので， $2 \Longrightarrow 1$ を示す．まずは部分構造となることを示す．

$\mathfrak{B}$ は $\mathcal{L}$ -論理式なので，定数記号 $c$ に対し， $\mathfrak{B} \models \exists x (x = c)$ となる．すると $2$ よりある $a \in A$ が存在して $\mathfrak{B} \models a = c$ となる．よって $c^\mathfrak{A} = a \in A$ である．関数記号の場合についても同様である．

そこで，初等部分構造となる事を示す． $\varphi$ を $\mathcal{L}(\mathfrak{A})$ -論理式として， $\mathfrak{A} \models \varphi \Leftrightarrow \mathfrak{B} \models \varphi\label{eqn:elementary}$ を示せばよい． $\varphi$ の構成に関する帰納法で証明する． $\varphi$ が原子論理式であれば， $\mathfrak{A}$ が $\mathfrak{B}$ の部分構造であることから $(2)$ は成立する．また， $\varphi$ が Boole 結合の形になっているときも明らかである． $\varphi \equiv \exists x \psi(x)$ の時は， $\begin{alignedat}{2} \mathfrak{B} \models \exists x \psi(x) &\Leftrightarrow \text{ある} a \in A \text{があって} \mathfrak{B} \models \psi(a) &\qquad& (\text{仮定})\\ & \Leftrightarrow \text{ある} a \in A \text{があって} \mathfrak{A} \models \psi(a) && (\text{帰納法の仮定}) \\ & \Leftrightarrow \mathfrak{A} \models \exists x \psi(x) \end{alignedat}$

よって示された

この条件が述べているのは，「部分構造が初等部分構造になれないのは，論理式を満たす『解』が足りないからである」ということである．そこで，元となる $S$ に足りない解を付け足していくことで Löwenheim-Skolem の定理を証明しよう．

Löwenheim-Skolem の定理の証明.

これは特に下方 Löwenheim-Skolem の定理 と呼ばれる．また，単に Löwenheim-Skolem の定理と云った場合こちらだけを指すことも多い．

先の宣言通り， $S$ に足りない元を付け加えていって，それが高々 $\kappa$ 個で足りることを示す． $B$ の部分集合の上昇列 $A_i (i \leq \omega)$ を次のようにして構成する．

まず， $A_0 = S$ とする．今， $\mathcal{L}(A_n)$ 論理式は $\mathcal{L}$ の記号と $A_n$ の元の有限列で書けるので，その個数は高々 $(\mathop{\mathrm{card}}(L) + \mathop{\mathrm{card}}(A_n) + \aleph_0)^{<\omega} \leq \kappa^{<\omega} = \kappa$ となる．ここで選択公理を使っている．任意の無限基数 $\kappa$ に対し，その有限列全体の濃度 $\kappa^{<\omega}$ が $\kappa$ と一致することは選択公理と同値である．

そこで， $\mathcal{L}(A_n)$ -論理式 $\varphi(x)$ について， $a_\varphi \in B$ を次のように定める： $a_\varphi = \begin{cases} \mathfrak{B} \models \varphi(a) \text{となるような} a \in B & (\mathfrak{B} \models \exists x \varphi(x))\\ \text{適当な} B \text{の元} & (\text{otherwise}) \end{cases}$ 再び，ここで $a_\varphi$ を取るときにも選択公理を使っている．これを用いて， $A_{n+1} = A_n \cup \left\{\: a_\varphi \;\middle|\; \varphi(x): \mathcal{L}(A_n)\text{-論理式} \:\right\}$ と定め， $A = \bigcup_{n < \omega} A_n$ と置く．明らかに， $\mathop{\mathrm{card}}(A) \leq \kappa$ である．後は， $A \subseteq \mathfrak{B}$ が Tarski-Vaught の判定条件を満たすことを云えばよい． $\varphi(x)$ を $\mathcal{L}({\mathfrak{A}})$ -論理式として， $\mathfrak{B} \models \exists x \varphi(x)$ とする．この時， $A$ の作り方よりある $n < \omega$ が存在し， $\varphi(x)$ は $\mathcal{L}(\mathfrak{A}_n)$ -論理式となる． $A_n$ の構成の仕方より， $\varphi(x)$ は $A_{n+1}$ に解 $a_\varphi \in A_{n+1} \subseteq A$ を持つ．よって $\mathfrak{B} \models \varphi(a_\varphi)$ となるので， $\mathfrak{A} \prec \mathfrak{B}$ である．特に， $\mathop{\mathrm{card}}(S) = \kappa$ とすれば， $\mathfrak{A}$ の濃度は $\kappa$ となる．
こちらは上昇 Löwenheim-Skolem の定理と呼ばれ．証明には次のコンパクト性定理¹¹を使う：

理論 $\mathcal{T}$ の任意の有限部分集合がモデルを持つなら， $\mathcal{T}$ もモデルを持つ．

この事の証明は Łoś の定理を使うととても鮮かに出来るので，各自で証明してみて欲しい（ここではやらない）．これさえ認めれば，次のようにして示せる．

$c_\alpha \, (\alpha < \kappa)$ を $\mathcal{L}(\mathfrak{B})$ に含まれない互いに異なる定数記号とし， $\mathcal{L}' = \mathcal{L}(\mathfrak{B}) \cup \left\{\: c_\alpha \;\middle|\; \alpha < \kappa \:\right\}$ とする．ここで， $\mathcal{T} = \mathrm{Diag}(\mathfrak{B}) \cup \left\{\: c_\alpha \neq c_\beta \;\middle|\; \alpha < \beta < \kappa \:\right\}$ と置く． $\mathcal{T}$ の任意の有限部分集合 $T \subseteq \mathcal{T}$ がモデルを持つことを示す．

まず，初等設計図の定義から $\mathfrak{B} \models T \cap \mathrm{Diag}(\mathfrak{B})$ である． $T$ の残りは $\{c_{\alpha_0} \neq c_{\beta_0}, \dots, c_{\alpha_n} \neq c_{\beta_n}\}$ の形である．今， $\mathfrak{B}$ は無限構造であるので，各 $c_{\alpha_k}, c_{\beta_k}$ が異なるように上手く元を取ってくることが出来る．よって $\mathfrak{B} \models T$ ．従って $\mathcal{T}$ の任意の有限部分集合がモデルを持つので， $\mathfrak{A} \models \mathcal{T}$ となるような $\mathcal{L}'$ -構造 $\mathfrak{C}$ が得られる． $a \in B$ と， $\mathfrak{C}$ での名前の解釈 $c_a^\mathfrak{C}$ を同一視してやることにより $\mathfrak{B} \prec \mathfrak{C}$ となり，更に $\mathcal{T}$ のモデルである事から $\mathfrak{C}$ は $\kappa$ 個の異なる元を持つので， $\kappa \leq\mathop{\mathrm{card}}(C)$ である．そこで，下方 Löwenheim-Skolem を適用して濃度 $\kappa$ となるモデル $\mathfrak{A}$ を取れば，これが求めるものとなる．

実は，Löwenheim-Skolem の定理は選択公理と同値である．詳しい証明は第一回選択公理オフの際に非公式にやったらしいので，今から @alg_d氏が一分で証明してくれます．

Löwenheim-Skolem の定理は，一階述語論理ではモデルの濃度を限定出来ないという主張である．これは単なる選択公理にまつわる不思議現象ではなく，しっかりとした応用がある．

ZF が無矛盾だとすると，Gödel の完全性定理により $V \models \mathrm{ZF}$ となるようなモデル $V$ が存在する．無限公理があるので，特に $V$ は無限モデルである．よって，Löwenheim-Skolem の定理より，集合論の可算モデル $U \subseteq V$ を取ることが出来る．えっ，でも Cantor の対角線論法によれば， $\aleph_0 < 2^{\aleph_0}$ だよね？モデルが可算だったら，実数のような連続体濃度の集合は存在しなくなっちゃうんじゃないの？？矛盾だ！！！という声が聞こえてきそうだ．しかし，これは矛盾ではない．そもそも「可算」などの濃度の概念がどのようにして定義されたか思い出そう．集合 $X$ と $Y$ の濃度が等しいというのは， $X$ と $Y$ の間に全単射が存在するということであった．つまり，集合の濃度はその濃度の証拠となる関数の存在に依存するのだ．この場合， $U$ が可算であることを保証する全単射は $V$ には属するが， $U$ には存在しないのだ．よって， $V$ から見れば $U$ は可算集合だが， $U$ の中から見れば全体は可算ではないし，それどころか「集合」ですらない，ということになる．

こんな可算モデルを取って何が嬉しいのだろうか．集合論ではある命題が ZF から独立であることを示す為に強制法という手法が良く使われる¹²．選択公理も，この強制法を用いて独立性が示される重要な例である．強制法で用いられる道具の存在を示すために，ZF の可算モデルが取れるという事は非常に重要な前提条件になっているのである．

参考文献

[1]

田中一之, 坪井明人, and 野本和幸, ゲーデルと20世紀の論理学（ロジック）2 完全性定理とモデル理論, vol. 2. 東京大学出版会, 2011.

[2]

新井敏康, 数学基礎論. 岩波書店, 2011.

[3]

江田勝哉, 数理論理学 ──使い方と考え方：超準解析の入口まで. 内田老鶴圃, 2010.

[4]

古森雄一 and 小野寛晰, 現代数理論理学序説. 日本評論社, 2010.

[5]

坪井明人, モデルの理論. 河合出版, 1997.

[6]

@alg_d, “第四回選択公理オフ.”

[7]

H. J. Keisler, Foundations of infinitesimal caculus. http://www.math.wisc.edu/keisler/foundations.html, 2007.

[8]

R. Goldblatt, Lectures on the hyperreals: An introduction to nonstandard analysis. 1998.

[9]

齋藤正彦, 〔増補新版〕超積と超準解析ノンスタンダード・アナリシス. 東京図書株式会社, 1992.

[10]

田中尚夫, 選択公理と数学【増訂版】──発生と論争，そして確立への道. 遊星社, 2005.

[11]

K. Kunen, Set theory, vol. 34. College Publications, 2011.

[12]

@alg_d, “選択公理｜壱大整域.” http://alg-d.com/math/ac/.

[13]

竹内外史, 新装版集合とはなにか. 講談社ブルーバックス, 2001.

[14]

S. Awodey, Category theory, vol. 52. Oxford University Press, 2010.

Łは “w” と “l” の中間音らしい．カタカナでは「ウォッシュの定理」という表記が一般的なようだ．↩︎
今 $^{\text{[いつ？]}}$ 気付いたけどこれは駄洒落ではない．↩︎
直観主義論理がどうのとかいう玄人はいいから黙っててください．↩︎
離散的な値を取る測度と，ウルトラフィルターは本質的に同じものである．↩︎
イデアルは冪集合 Boole 代数だけでなく一般の Boole 代数上で定義される概念であり，可換環のイデアルとは全く無関係と云う訳ではない．Boole 代数のイデアルは「小さな元」の集まりであり，可換環のイデアルは準同型の核，つまり「ゼロの集まり」と見做せることを思い出せば，両者が同じ名前を持っているのも不自然なことではないだろう．更に，Boole 代数には自然に可換環としての構造が入り，この時Boole 代数のイデアルと可換環としてのイデアルは一致する．↩︎
ここで「従って $J \notin \mathcal{U}$ でなくてはならず矛盾．証明終了」としてはいけない． $\mathcal{F}$ の定義は確かに「対応する族が選択関数を持たない添字集合全体」であったが，ウルトラフィルターの補題によりそれを拡大したものが $\mathcal{U}$ なので， $\mathcal{U}$ には選択関数を持つものが入っているかもしれないからである．↩︎
より厳密に数理論理学の知識を使う場合は，集合論のユニヴァースを考えて云々するのだが，話が難しくなるのでここでは最初から全ての関数などを言語に加えた構造を考えている．厳密な取り扱いについては Keisler [7] や Goldblatt [8]，齋藤 [9]などを参照されたい．↩︎
どちらが割れるかは，ウルトラフィルターの取り方によってかわってくる↩︎
他方，上の ${}^{*} {\mathbb{R}}$ では有限列ということを書くことが出来た．しかし， ${}^{*} {\mathbb{R}}$ での有限は超有限も含んでしまうので，結局標準的な意味での有限列であるという条件にはならない．より一般に，超準元の存在するモデルでは，そのモデル内で標準元と超準元の区別を付けることは出来ないことが証明出来る．↩︎
もちろん，可算言語でなくなるとか，公理が煩雑になるとかといった欠点もある．↩︎
この定理の名前の由来は，「任意の開被覆が有限部分開被覆を持つ」という位相空間のコンパクト性と単に似ているためだと思われがちである．しかし，論理式の間に適当な位相を入れることで，コンパクト性定理は実際にその空間のコンパクト性と同値となる [2, 演習問題 1.8.4] [10, 補遺VI]．↩︎
強制法については，Kunen [11] やその旧版の日本語訳が標準的な教科書として挙げられる↩︎

第四回選択公理オフ：数理論理学の初歩の初歩の初歩の…… konn-san.com