色々な集合論の公理系 - 進捗置き場というわけでもない場所

この記事は TSG Advent Calendar 2020 の 19 日目の記事です。

序文

「集合論は現代の数学の基礎である」というのは大学数学に足を踏み入れた人の多くが一度は聞かされるセリフだと思います。一方でここで言われるような「集合論」は多くの場合暗黙に ZFC 公理系 (あるいは選択公理を抜いた ZF 公理系) を指していることが多いように見受けられます^[要出典]。

この ZFC は素朴集合論で発生することの多いカントールのパラドックスなどを回避するために慎重に作られていますが、その代償として(？)「全ての集合からなる集まり」や「全ての順序数からなる集まり」のような非常に大きい集まりを扱えない事が知られています。

その結果、例えば圏論において圏全体からなる圏のような非常に大きい対象を扱いたいと思った場合、その基礎を ZFC に置くことができず、「集まり」を扱う ZFC 以外の集合論の公理系が必要になることがあります。

この記事ではそんな日陰物の^[要出典] ZFC 以外の集合論の公理系について、僕が調べた事を書いていこうと思います。

備忘録のつもりで曖昧な理解で書いている箇所があり、間違いなどが多く含まれている可能性が高いです。明らかな誤りを見つけた際にはぜひ @azaika_ に教えて下さい。指摘内容が理解できた場合土下座して直します。理解できなかった場合は未熟を恥じて該当箇所を爆破します。

[追記 2020/12/19]

Twitter 上でめいぜんおーえす (@Meizen_OS) さんから誤りのご指摘とアドバイスをいただきましたので記述を一部書き換えました。

[追記 2020/12/21]

再び Twitter 上で Alwe (@Alwe_Logic) さんからいくつかのご指摘をいただきましたので記述を一部書き換えました。

ZF/ZFC

はじめに ZFC (Zermelo-Fraenkel [ツェルメロ=フレンケル] with the axiom of Choice) 公理系について復習しましょう。まず ZF 公理系とは以下の 8 つの公理からなる公理系です。

外延性公理 (等しさの定義) : $\forall A \forall B (\forall x (x \in A \Leftrightarrow x \in B) \Rightarrow A = B)$
空集合公理 :
- このような $E$ を空集合と呼び、通常 $\emptyset$ と書く
無限公理 (無限集合の存在) :
- これは自然数の存在を認めるもので、またこれにより自然数が最小の無限集合となっている
対の公理 ( $\{x, y\}$ の存在 ) : $\forall x \forall y \exists A \forall z (z \in A \Leftrightarrow z = x \vee z = y)$
和集合公理 ( $\bigcup X$ の存在 ) : $\forall X \exists A \forall a (a \in A \Leftrightarrow \exists x(x \in X \wedge a \in x))$
冪集合公理 ( $\mathcal{P} (X)$ の存在 ) : $\forall X \exists A \forall a(a \in A \Leftrightarrow a \subseteq X)$
置換公理 ( map() の存在 ) :
- $F$ は「集合から集合の特殊な関係」という意味での関数ではなくて、いわゆるクラス関数でも良いことに注意
- これは特にフランクな表現である。正しい表現は下に記述する記事など他の文献を当たって欲しい
正則性公理 :
- わかりにくいが、ここから無限降下列 $x_0 \ni x_1 \ni x_2 \ni \cdots$ が存在しない事が言える

簡略化のため、 $\notin,\subseteq,\cap$ などの一部の記号を定義なしに使用しており、また自由変数の扱いについてはあまり記事の本筋に関係ないと考えたため記述を省いています。あくまでお気持ちの一部を書いているものだと思ってください。正確な公理の記述に関してはめいぜんおーえすさんの記事などが参考になると思います。

ZFC 公理系とはこれに更に以下の公理を追加した公理系になっています。

選択公理 :
- これも特にフランクな表現である。正しい表現は上記記事など他の文献を当たって欲しい

ZF や ZFC においては (論理式以外の) 全ては集合です。現代数学の多くはこの公理系の上に成り立っており, 自然数や実数, 関数も特別な形をした集合として定義されます。

また重要なこととして、上のような公理で巧妙な制約がかけられていることにより ZF(C) では「集合全ての集まり」や「自身を含まない集合(？)の集まり」は構成できません。つまりそのような「集まり」は集合ではなく、ZF(C) の上で扱うことは出来ません。

以下ではこれをベースに色々弄り回したバリエーションを考えていきます。

Zermelo set theory

さて、この ZF(C) ですが、最初に Zermelo が提唱したときには少し違う形のものでした。この Zermelo が最初に提案した集合論 (を書き直したもの) は Zermelo set theory と呼ばれており, Z または Z^- と書かれます。

Z と ZF の本質的な違いは、置換公理の代わりに以下の分出公理を用いるという点です。

分出公理 ( filter( $\psi,X$ ) の存在 ) : $\forall X\exists A\forall x(x \in A\Leftrightarrow(x \in X \wedge \psi(x)))$

ここで「置換公理 + ZF のその他の公理」から分出公理を導出することは可能ですが、「分出公理 + ZF のその他の公理」から置換公理を導出することは出来ません (まあ filter より map のほうが強いよね) 。例えば順序数 $\omega\times 2$ は Z から導出できないことが ZF において示せます。

したがって、Z (もしくは Z + 選択公理) は ZF(C) より制約が厳しい、つまり扱える対象の少ない (記述能力が低い) 集合論になっています。

MacLane set theory

大きな集まりの話を導入に使っていてなんですが、まだ大きな集まりを扱わない公理系の話です。

Mac Lane set theory は圏論の祖として知られる Mac Lane が提案した公理系で、ほとんど Zermelo set theory と同じですが以下の点で違いがあります。

分出公理において、内の限量子は集合にしかわたってはならない
- $\Delta_0$ 論理式でなければならない。とも言いかえられる。

つまり分出公理中の $\psi(x)$ として $\psi(x) := \forall a(\varphi(a, x))$ のような「範囲が広い」量化子は使えません。

この制約を加えた MacLane set theory は Z より真に弱い事が知られており *1、Z や ZF においては全ての集合のあつまりは集合にならない事が知られているので、分出公理を使うときに全ての集合をわたるような量化子は使えないということになります。

ここまでは ZF(C) を制約を厳しくする方向に変えていく拡張を考えました。次からは ZF(C) を拡張して、集合より大きい集まりを考えられるようにした公理系について考えましょう。

Morse-Kelley set theory

MK, Kelly-Morse, KM などとも呼ばれます。ここでは MK と呼ぶことにしましょう。

ZF(C) では全ては集合でした。MK では全てはクラスと呼ばれる「集合より大きいかもしれない」ものとして、そのクラスを集合と集合ではない真の (proper な) クラスの2つに大別します。MK において、あるクラス $A$ が集合であるという述語 $\mathrm{set}(A)$ は以下のように定義されます。

集合の定義 : $\forall A(\mathrm{set}(A) \Leftrightarrow \exists X(A \in X))$

つまり、他のクラスの要素になっているようなものが集合で、そうでないものが真のクラスです。

MK の他の公理は ZFC とよく似ています。というかほぼ同じです。ただし、いくつかの公理に「集合に対して」という制約が付いていること、後述する内包性公理が入っているために対の公理と選択公理が不要になっている事に注意が必要です。

外延性公理 (等しさの定義) : $\forall A \forall B (\forall x (x \in A \Leftrightarrow x \in B) \Rightarrow A = B)$
和集合公理 ( $\bigcup X$ の存在 ) : $\forall X(\mathrm{set}(X) \Rightarrow \exists A \forall a (a \in A \Leftrightarrow \exists x(x \in X \wedge a \in x)))$
冪集合公理 ( $\mathcal{P} (X)$ の存在 ) : $\forall X(\mathrm{set}(X) \Rightarrow \exists A \forall a(a \in A \Leftrightarrow a \subseteq X))$
無限公理 (無限集合の存在) : $\exists A(\mathrm{set}(A) \wedge \emptyset \in A \wedge \forall a(a \in A \Rightarrow a \cup \{a\} \in A))$
正則性公理 : $\forall X(X\neq\emptyset \Rightarrow \exists x(x \in X \wedge x \cap X = \emptyset ))$

さて、クラスという新しい概念は導入されたものの、これだけだと MK が ZFC より嬉しい要素は特に見当たりません。MK の真価は、以下の内包性公理という「クラスの定義の幅広さ」にあります。

内包性公理 : 述語に対して
- 適当な論理式を満たす集合からなるクラスが構成できる
- 例によって自由変数に関する制約を省略している。正しい記述は英語版 Wikipediaなどを参照のこと

この内包性公理において $\varphi$ を集合について常に真になるような述語、例えば $\varphi(x) := (x=x)$ などとすれば、集合全てからなるクラス $V=\{x \mid x = x\}$ すらも作ることが出来ます。

このような $V$ を考えたときに素朴集合論のようなパラドックスが生じないのは、上で定めた公理の対象の多くを集合に限定しているためです。例えば $V$ は真のクラスであって、真のクラスである $V$ に対しては冪集合公理や和集合公理が適用できません。したがって少なくとも素朴集合論のときのように安易な論法では矛盾を導くことは出来ない事が分かるかと思います。

さて、このように相当強力に見える MK ですが、クラスを考える上で以下のような制約が設けられています。

大きさの制限 :
- 真のクラスならば $V$ との全単射がある

この制約によって、MK では真のクラスについて細かく考えることは出来なくなっています。

ただし逆にこの制約によって、真のクラスについてかなり強い定理が成り立つ事が知られています。例えば順序数全体からなる $\Omega$ は MK における真のクラスとなりますが、これと大きさの制限から、任意のクラスに $\Omega$ との全単射があることが従います。全ての集合からなるクラス $V$ との対応を考えると「全ての集合からなる集まりに順序が付けられる」事になりますから、これは選択公理よりも強い命題になっています。

またこの MK は ZFC より強く、ZFC の無矛盾性を証明できることが知られています。

von Neumann, Bernays, Gödel set theory

NBG, NGB, VBG, VGB, GBC などとも呼ばれます。ここでは NBG と呼ぶことにしましょう。

NBG はほとんど MK と同様ですが、MK よりも ZF(C) に対して保守的な公理系です。MK に対する NBG の関係は、Z に対する MacLane のような関係で、MK と NBG の違いは以下の一点のみです。

内包性公理において、論理式 $\varphi$ は $\Delta_0$ でなければならない

たったこれだけの違いですが、NBG は MK より真に弱い公理系になっています。例えば MK では選択公理は内包性公理によって導出されますが、NBG では上の制約によって少なくとも同様の論法では選択公理を導出することはできません。NBG で選択公理を用いる場合は、選択公理をクラスに拡張した大域選択公理と呼ばれるものを追加した公理系を考えることになります。

また、NBG (または NBG + 大域選択公理) で ZF(C) の無矛盾性を示す方法は知られていません (これが単に不可能なのか、それとも知られていないだけなのか曖昧なのは私の勉強不足によるものです)。

[追記 2020/12/21]

Twitter 上で Alwe (@Alwe_Logic) さんから

NBGではZFCの無矛盾性は示せませんね。NBGで証明可能なZFの文は全てZFで証明可能、NBGがZFの無矛盾性を示せばZFCでも示すことができ、またGodelの構成可能集合の理論からZFとZFCの無矛盾性は同値であるから第2不完全性に矛盾します

との情報をいただけました。ありがとうございます。(追記終わり)

更に MK と NBG の大きな違いとして、MK は有限公理化可能ではない事が知られていますが、NBG は有限公理化可能らしいです。気になる方は調べてみてください。

Ackermann set theory

さて、ここまではクラスのある集合論として MK と NBG を見てきましたが、これらは大きさの制限という公理がありました。このような大きさの制限がない公理が Ackermann set theory です。

Ackermann set theory では、全てがクラスであり、集合が特殊な性質を満たすクラスとして定義される点は MK 同じですが、その公理系は MK と (つまり ZFC と) 少し変わっています。まずは公理を列挙してしまいましょう。

外延性公理 (等しさの定義) : $\forall A \forall B (\forall x (x \in A \Leftrightarrow x \in B) \Rightarrow A = B)$
内包性公理 : 述語 $\varphi$ に対して $\exists A \forall x (x \in A \Leftrightarrow (\mathrm{set}(x) \wedge \varphi(x)))$
要素公理 (集合の要素は集合) : $\forall A \forall x( (\mathrm{set}(A) \wedge x \in A) \Rightarrow \mathrm{set}(x))$
部分公理 (集合の部分は集合) : $\forall A \forall B ( (\mathrm{set}(A) \wedge B \subseteq A) \Rightarrow \mathrm{set}(B))$
集合の内包性公理 : 述語がその中に述語を含まず、ならば
- 「集合である」という命題を直接を使わずに集合であることを示せるものの集まりは集合
- 例によって自由変数に関する制約を(ry 他のサイトを(ry

正則性公理や選択公理を入れる場合もあるようですが、今回はそれらなしのバージョンを考えます。また $\mathrm{set}(A)$ は $A$ が集合であることを表す述語です。

この公理を見ると、MK と異なり別のクラスの要素になるクラスが存在しても良いことが分かります。例えば順序数全体のクラス $\Omega$ に対して、それを含む $\Omega + 1$ というクラスを考えることも出来ます。

また、ZF などに比べると随分公理が少ないのが分かります。しかし公理が少ないからと言って Ackermann set theory が弱いというわけではなく、全ての集合のクラス $V$ の存在や空集合の存在は示すことが出来ますし、Z における対の公理や和集合公理、冪集合公理、無限公理、置換公理に対応する命題をそれぞれ示すことが出来ます。

さらに簡単な対応により、対象を集合に限った命題については Ackermann set theory + 正則性公理は ZF と同等の強さがあることが知られています。

時間がなくて書けなかった公理系

時間が無くて書けなかった公理系です。これについて後に記事をひっそりと加筆する可能性があります。

Typed Set Theory (TST)
Pocket set theory
New Foundations

調べられなかった公理系

見たけどよく分からなかった公理系です。これについて後に記事を加筆する可能性は薄いです。

ZFC + グロタンディーク宇宙
ETCS (Elementary Theory of the Category of Sets)

最後に

…いかがでしたか？結局集合論についてはよく分かりませんでした！

このあたりの話は英語の資料がちらほらある割に日本語の資料を目にする機会が少なく、調べていると結構目新しいことがあって楽しかったです *2。繰り返しになりますが、理解があやふやなまま楽しむだけ楽しんでいる疑惑があるので、怪しい箇所はぶっ叩いてくれると嬉しいです。

あと、みなさんも色々な公理系について調べて記事を書いてくれると僕が嬉しいです。

次は domperor さんの「２段抜きと３段抜きの並存」です。

*1:残念ながら私自身は証明を追えていません

*2:これは僕の見聞が狭いことに由来する楽しさかもしれませんが…