はじめに
超積によるコンパクト性定理の証明や超準モデルの構成が面白いので紹介します.超積とは,L-構造の族 が与えられたときに,その「殆んど至るところ」で成立するような性質を持つ L-構造を作る方法です.
フィルターとウルトラフィルター
超積を定義するため,まずウルトラフィルターの概念を定義する.任意のブール代数上で定義される概念だが,ここでは冪集合束上のもののみ考えれば十分なため,それに限定して話を進める.
(1) の の条件は, が と一致しないという事だ. をフィルターに含める場合, と異なるフィルターを固有フィルター(proper filter)と呼ぶことがある.以下では固有フィルターのみを考える.
がウルトラフィルター は極大なフィルター.即ち, なるフィルター が存在するなら, となる.
(⇒) を示す. を 上のウルトラフィルターとする. なるフィルター があったとする. とすると, をとれば である.すると,条件 (4) より となる. なので,条件 (3) より となるが,これは条件 (1) に反する.よって となるので, は極大フィルターである.
(⇒) を示す. を 上の極大フィルターであるとする. として, を示せば十分である.そこで,フィルター を次で定める. \[\mathcal{F} \mathrel{:=}\left\{ Y \subseteq I\ \ \middle|\ \ \exists Z \in \mathcal{M}\ [X \cap Z \subseteq Y]\right\}\] とすれば, であるので, である. とすると, となり,これは と同値であるので, となってしまう.よって .同様に (3) も証明出来, は を含むフィルターであることが判る.よって の極大性より である.また,任意の集合 について であるので .よって はウルトラフィルターである.
ウルトラフィルターには同値な特徴付けがあり,『ゲーデルと20世紀の論理学』[3]などでは次のものを定義として採用している.
が 上のウルトラフィルターである必要十分条件は,次が成立することである.
は有限交叉性を持つ.即ち, の任意の有限部分集合 に対し,.
は有限交叉性を持つ 上の冪集合族の中で極大である.即ち, に属さないような を取ってくると, は有限交叉性を持たない.
フィルターが有限交叉性を持つことは明らかである.ウルトラフィルター に属さない元を とすると, であるので, は有限交叉性を持たない.よって,ウルトラフィルターは有限交叉性を持つ極大な部分集合族である.
逆に を極大な有限交叉的部分集合族であるとする. がフィルターであることを示せば,任意のフィルターが有限交叉性を持つことから極大性は従う.(1) は明らか. かつ とする. とすると, の有限交叉性から .よって は有限交叉性を持ち,特に は極大であるので .よって (2) は成立.(3) についても, の有限交叉性より明らか.よって はフィルターである.
フィルターは「大きな部分集合の集まり」だと思っておけば大体間違いはない.大きい集合を含む集合は大きいだろうし,空集合は大きくない.大きい物の共通部分を取っても大きい,と云うのはちょっと直観的ではないかもしれないが,そういうものかなとも思える.ウルトラフィルターは,特にめいっぱいまでキメの細かいフィルターだと思えばよい.
以下では,単なるフィルターをウルトラフィルターに拡張して用いる.そういった事が出来る,というのが次のウルトラフィルターの補題である.
任意の 上のフィルター に対し,それを含むような 上のウルトラフィルター が存在する.
任意の有限交叉性を持つ の部分集合族 に対し,それを含む 上のウルトラフィルター が存在する.
証明には Zorn の補題を用いる.命題論理のコンパクト性定理を示した際の,極大無矛盾集合の存在定理と殆んど同じように証明出来るので,証明は省略する.
超積の定義と基本性質
いよいよ超積の概念を定義する.「はじめに」述べたように,超積は「殆んど至るところ」で成立する性質を取り出したものであり,フィルターは「大きな集合」の集まりだったから,これらを念頭に置けば次の定義は自然なものだと思えるだろう.以下,言語 を一つ固定する.
: -構造の族(),: 上のフィルターとする.この時, 上の二項関係 を次で定義する. このとき, は同値関係となっている. が「大きい集合で一致すれば」,つまり殆んど至るところで一致すれば, を等しいと見做すのである.
の による縮積(reduce product) とは, の による商集合のことである.即ち, の による同値類を と書けば, \[\left.{\prod_{i\in I} \mathfrak{A}_i}\middle/{\mathcal{F}}\right. = \left\{ [u]_\mathcal{F}\ \ \middle|\ \ u \in \prod_{i\in I} \left|\mathfrak{A}_i\right|\right\}\] のことである.このとき, の -構造としての述語記号,函数記号に関する解釈は次により定める.
\[\begin{gathered} P^\mathfrak{C} = \left\{([u_1], \dots, [u_n])\ \ \middle|\ \ \left\{i \in I\ \ \middle|\ \ (u_1(i), \dots, u_n(i)) \in P^{\mathfrak{A}_i}\right\} \in \mathcal{F}\right\}\\ f^\mathfrak{C}([u_1], \dots, [u_n]) = [u]\\ ただし u(i) = f^{\mathfrak{A}_i}(u_1(i), \dots, u_n(i)) \end{gathered}\]
特に,ウルトラフィルター に関する縮積を超積(ultraproduct)と云う.
上の が実際に同値関係となることは,フィルターの条件 (3) などからすぐに判る.また,上の縮積の定義が well-defined であることは本来ならば示すべきだが,面倒なのでやめる.
超積が「殆んど至るところで成立する性質を取り出したもの」ということを定式化したのが次の定理である1.
とすると,次が成立.
\[\mathfrak{C} \models A[\begin{smallmatrix} a_1 & \dots & a_n\\ {[u_1]} & \dots & [u_n] \end{smallmatrix}] \Leftrightarrow \left\{ i \in I\ \ \middle|\ \ \mathfrak{A}_i \models A[\begin{smallmatrix} a_1 & \dots & a_n\\ u_1(i) & \dots & u_n(i) \end{smallmatrix}]\right\} \in \mathcal{U}\]
定理の証明の為に,次の補題をまず示そう.
\(t: a_1, \dots, a_n \text{以外に自由変数を持たない} L\text{-論理式}, \tau(i) = (t_{}[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}])^{\mathfrak{A}_{i}}\) とする.このとき, \[(t[\begin{smallmatrix} a_1 & \dots & a_n \\ {[u_1]} & \dots & [u_n] \end{smallmatrix}])^{\mathfrak{C}} = [\tau]\]
の項の構成に関する帰納法で示す. を 以外に自由変数を持たない の項とし,\(\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]\) である. を -変数関数記号とすると,
\[\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}\]
よって示された.
の論理式の構造帰納法で示す.以下, の元と での名前を同一視する.
のとき. を -変数述語記号, を の項とすると,
\[\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}\]
のとき. は命題を満たす論理式であるとする(帰納法の仮定).
\[\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}\]
のとき.ここでウルトラフィルターであることが効いてくる.
\[\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}\]
のとき. の時は, を考えるか,ウルトラフィルターの性質から となることを使う. のときは定義から明らか.
のとき.(⇒) の方向は明らか.(⇐) の方向について. \(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\}\) とおく. を次のように構成する.まず, に対しては \(\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}]\) となるように適当な を取れる. の場合は適当に何でもよいから の元を取る.すると, が \(B[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1(i) & \dots & u_n(i) \end{smallmatrix}][\begin{smallmatrix}x \\ {[u]}\end{smallmatrix}]\) を満足する.
の場合も上と同様.
以上より示された.
Łośの定理の系として,次が得られる.
とするとき,
特に とする.このように,各 が等しい場合の超積を,特に超冪(ウルトラパワー;ultrapower)と呼ぶ.このとき, について により定数函数 を定める.このとき次が成立. \[\left.{\prod_{i \in I} \mathfrak{A}}\middle/{\mathcal{U}}\right. \models A[\begin{smallmatrix} a_1 & \dots & a_n \\ {[c_{u_1}]} & \dots & [c_{u_n}] \end{smallmatrix}] \Leftrightarrow \mathfrak{A} \models A[\begin{smallmatrix} a_1 & \dots & a_n \\ u_1 & \dots & u_n \end{smallmatrix}]\] 特に, が -閉論理式のとき次が成立.
超積によるコンパクト性定理の証明
有限交叉性を使った証明と,フィルターの性質を使った証明の二種類を紹介する.
を -閉論理式からなる集合とするとき,次は同値.
はモデルを持つ.
の任意の有限部分集合がモデルを持つ.
は明らか.逆を示す.
( の有限部分集合全体)と置く.このとき, より任意の に対し, となるような -構造 が取れる.今, とおけば, であり, となるので, \[\mathcal{F} \mathrel{:=}\left\{ Y \subseteq I\ \ \middle|\ \ \exists S \in I [V_S \subseteq Y] \right\}\] とおけば, はフィルターとなる.よってウルトラフィルターの補題より となるようなウルトラフィルター が取れる. が のモデルとなることを示そう.それには,Łośの補題より に対し, を示せば十分である.今, であり, とすると は有限部分集合なのでモデルを持ち, より .よって .今, はフィルターだったから,結局 となり,命題が示された.
を定めるところまでは上と同様である.次に, と置く. より特に なので, .よって \(\mathcal{E} \mathrel{:=}\left\{ A_\varphi\ \ \middle|\ \ \varphi \in \mathcal{T}\right\}\) とおけば, は有限交叉性を持つ.ウルトラフィルターの補題より はウルトラフィルター に拡張出来るので,これによる超積を考えてやると,Łośの定理から直ちに が従う.
自然数の超準モデル
ここでは,超冪を用いて自然数の超準モデルを構成する.超準モデル(non-standard model)というのは,通常期待されるような物と異なるモデルでありながら,一階述語論理の範囲内では全く同じ性質を持つようなモデルのことである.
まず,次の 上のフィルターを考える. これは Fréchet フィルターと呼ばれるものである.これが実際にフィルターであることは簡単に確かめられる.ウルトラフィルターの補題により,この を含むようなウルトラフィルター を取ることが出来る.このウルトラフィルターは一意なものではなく,複数のものがありうることを注意しておく.
以下では,順序環の言語 を考えて,順序環 の による超冪 を考える. を 以外に自由変数を持たない -論理式とすると,Łośの定理の系から次が成立した. 各整数 に対して定数函数 を考えてやると, は超冪の元である.これらは に元々属している整数 に対応するものとみることが出来る.また, 上の恒等写像 を考えると, より も上の超冪 の元であることがわかる.ではこれはどんな元だろうか?実は無限大の自然数(超有限自然数)とでも云うべきものになっている.
このことを詳しく見てみよう.Łośの定理より, は \(\left\{k \in \mathbb{N}\ \ \middle|\ \ \mathfrak{Z} \models c_n(k) \leq id(k)\right\} \in \mathcal{U}\) と同値である. の定義からこれは \(\left\{k \in \mathbb{N}\ \ \middle|\ \ \mathfrak{Z} \models n \leq k\right\} \in \mathcal{U}\) と同値である. は Fréchet フィルターを含み,\(\left\{k \in \mathbb{N}\ \ \middle|\ \ k < n\right\}\) は有限であるので,\(\left\{k \in \mathbb{N}\ \ \middle|\ \ \mathfrak{Z} \models n \leq k\right\} \in \mathcal{U}\) となる.よって,任意の「有限の」整数 に対し, 成立することがわかる.また,任意の整数 について なので となる.つまり,無限大の自然数は無数に存在することになる.また, となるので, は負の無限大の整数も持つことになる.
ところで,今,任意の整数 について, か のいずれかは偶数である.即ち, が成立するのであった.すると,Łośの定理の系から である.よって か のいずれかが で割れることになる2.割れる方を で割ってやると,これも超有限の自然数になっている.この手続を繰り返して, の元の狭義減少列 が得られる.これらはいずれも より大きい.よって自然数の狭義減少列が得られたことになる.
しかし,自然数の整列性から狭義減少列は存在しない筈だ.どういうことか?今我々が考えているのは,「一階述語論理」で書ける範囲の理論であった.つまり,「狭義減少列が存在しない」とか「自然数は整列する」といった概念は,一階述語論理では書けないと云うことが,この事実の伝える事なのである.自然数の整列性は,「任意の自然数からなる部分集合に最小値が存在する」という形で述べられるが,この「部分集合」に対する量化が一階述語論理では行えないのである3.このことは,「自然数の部分集合」全体は非可算無限個存在するが,自然数の理論自体は可算言語で記述されるため,高々可算個の部分集合しか扱えない,ということを考えるとちょっと分かり易いのではないだろうか.
おわりに
駆け足で超積とその応用を説明した.他にも色々な使いでがあって,Löwenheim-Skolem の定理の証明や,超準解析の公理を満たすモデルを構成するのにも用いる事ができる.Löwenheim-Skolem については江田[4] や田中・坪井・野本[3] が,超準解析については江田[4] や Keisler[2]が参考になるだろう.
参考文献
- Steve Awodey. Category Theory, Vol. 52 of Oxford Logic Guides. Oxford University Press, 2010.
- H. Jerome Keisler. Foundations of infinitesimal caculus, 2007.
- 田中一之, 坪井明人, 野本和幸. ゲーデルと 20 世紀の論理学(ロジック)2 完全性定理とモデル理論, ゲーデルと 20 世紀の論理学, 第 2 巻. 東京大学出版会, 2011.
- 江田勝哉. 数理論理学 ──使い方と考え方:超準解析の入口まで. 内田老鶴圃, 2010.
- 新井敏康. 数学基礎論. 岩波書店, 2011.
- 坪井明人. モデルの理論. 河合出版, 1997.