8.3 集合論理

8.3.1 Russel のパラドックス

集合に関する議論を直感的に進めるのは危険である。論理学者 Gottlobゴットローブ Fregeフレーゲ は十九世紀後半に集合を定義する厳密な公理を見つける研究に取り組んだものの、Russelラッセル のパラドックス (Russel's paradox) と呼ばれるわずか三行の議論を解決できず行き詰まってしまった¹。Cantor の定理 (定理 8.1.12) の証明で見た議論と似た構造を持つ Russel のパラドックスは、数学に公理的基礎を与える試みに対する非常に大きな一撃となった:

集合に関するこれほどに単純な議論で数学が壊れてしまった！ Russell と彼の同僚 Whiteheadホワイトヘッド は、数学のあらゆる分野の論理的基礎として全幅の信頼を置くことができ、それでいて矛盾を起こさない集合論を構築する研究に長く取り組んだ。

実は、パラドックスを回避する方法自体は Russell と同時代の数学者にも明らかだった: \(W\) が集合という仮定が正当化されないのである。\(S\) は集合を表すので、\(S\) を \(W\) としていい理由が存在しない。つまり、このパラドックスは \(W\) が集合であってはいけないことを示している！

しかし、\(W\) は集合でないとするとき、数学的に well-defined な集合の集まりは必ず集合だという非常に自然な公理を拒否しなければならない。Frege をはじめとする論理学者が直面したのは「集合の集合は、どんなとき集合となるのか？」という問題だった。Russell と Whitehead もこの問題に取り組んだ。彼らは十年以上の時間をかけて巨大な公理系を新たに考案し、それを Principiaプリンキピア Mathematicaマテマティカ と呼ばれる長大な書籍にまとめた。しかし、彼らのアプローチは実質的な失敗に終わった: あまりにも冗長で、誰も利用しなかったのである。後に Zermeloツェルメロ と Fraenkelフレンケル という二人の論理学者が考案した集合論の公理化に取り込まれ、現在ではそれが広く受け入れられている。

8.3.2 ZFC 公理による集合論

Zermeloツェルメロ-Fraenkelフレンケル 集合論と選択公理 (Zermelo Fraenkel set theory with the axiom of choice, ZFC) と呼ばれる集合に関する一連の公理、そして単純な論理的推論規則が一通りあれば、数学の事実上全ての結果が導けると一般に考えられている。

ZFC は文字通りの「無」から構築される純粋集合 (pure set) に関する公理である。最初にあるのは要素を持たない集合 \(\varnothing\) だけであり、他の全ての集合はそこから構築される。例えば \(\varnothing\) からは \(\varnothing\) だけを要素に持つ集合 \(\left\{ \varnothing \right\}\) が構築できる。これで二つの集合が手に入ったので、さらに二つの集合を新しく作成できる:

同様の操作を続けると、次に示す単純な集合の列を作成できる。この列では先頭要素を除く任意の要素が一つ前の要素を唯一の要素に持つ集合となっている:

これは、この列の要素からなる無限集合 \(N\) を構築できることを意味する。

もちろん、純粋集合の他にも数学的オブジェクトは多くある ── 例えば \(\mathbb{N}\) や \(\mathbb{R}\) といった集合、実数を引数に取る関数全体の集合、\(\left\{ 0, 1\right\}^{\ast}\) や \(\left\{ 0, 1 \right\}^{\omega}\) といった列の集合、グラフの集合がある。しかし実際には、純粋集合さえあれば他の種類のオブジェクトを完全にモデル化できる。

例えば、上記の無限集合 \(N\) は非負整数全体の集合 \(\mathbb{N}\) のコピーとみなせる: 任意の要素 \(s \in N\) に「\(1\) を足す」と \(\left\{ s \right\}\) になる。さらに、\((a, b) \in N \times (N - \left\{ \varnothing \right\})\) の形をした組全体の集合は、非負整数の分子と正整数の分母を持つ有理数全体の集合のコピーとみなせる²。有理数があれば、任意の実数 \(r \in \mathbb{R}\) を \(r\) より大きい有理数全体の集合でモデル化することで、実数全体の集合のコピーとみなせる集合を構築できる。他の数学的オブジェクトについても同様となる。重要なのは次の点である: 純粋集合を正しく扱える規則があれば、他の数学的オブジェクトに対する完全な基礎付けも完了する。

話を戻すと、ZFC の議論領域は純粋集合であり、ZFC ではいくつかの公理から始めて論理的推論規則を使って純粋集合の性質が証明される。ZFC の公理そのものは集合論の純粋一階述語論理式として表現される。言い換えれば、論理結合子と量化子の他には \(x \in y\) の形をした式だけを含む述語論理式が ZFC の公理を表現する。ここで \(x \in y\) は「\(x\) と \(y\) が純粋集合であり、\(x\) は \(y\) の要素である」を意味する。集合論の純粋一階述語論理式を今後は集合論の論理式 (formula of set theory) と呼ぶ。

集合論の論理式は等号 \(=\) を持つことさえ許されていない。しかし、二つの集合が等しいのは同じ要素を持つとき、かつそのときに限るので、純粋集合の等価性は \(\in\) を使って簡単に表現できる:

同様に、包含関係を表す記号 \(\subseteq\) も 集合論の論理式に含まれないものの、\(\in\) を使って定義できる:

よって \(\in\) の他に \(=\) と \(\subseteq\) を使う論理式は、\(\in\) だけを使う論理式の省略記法と理解できる。以降は論理式と論理式の省略記法を区別せず、どちらも単に「集合論の論理式」と呼ぶ。例えば、次に示すのは集合の等価性と集合の包含関係の関係を示す集合論の論理式である:

本章では集合論についてこれ以上深く議論しないものの、興味のある読者に向けて実際の ZFC の公理を次に示す ── 述語論理式の読み書きの練習がてら簡単に目を通してみるとよい。

ZFC の公理

外延性の公理 (axiom of extensionality)

二集合が等しいのは、それらが同じ集合を要素に持つとき、かつそのときに限る:

\[ x = y \ \operatorname{\text{\footnotesize IFF}}\ (\forall z.\ z \in x \ \operatorname{\text{\footnotesize IFF}}\ z \in y) \]

対の公理 (axiom of pairing)

任意の集合 \(x\), \(y\) に対して、\(x\) と \(y\) だけを要素に持つ集合 \(\left\{ x, y \right\}\) が存在する:

\[ \forall x,y\, \exists u\, \forall z.\ (z \in u \ \operatorname{\text{\footnotesize IFF}}\ (z = x \ \operatorname{\text{\footnotesize OR}}\ z = y)) \]

和集合の公理 (axiom of union)

集合の集合 \(z\) に対して、\(z\) の要素の要素全体からなる集合が存在する:

\[ \forall z\, \exists u\, \forall x.\ (x \in u) \ \operatorname{\text{\footnotesize IFF}}\ (\exists y.\ x \in y \ \operatorname{\text{\footnotesize AND}} \ y \in z) \]

無限公理 (axiom of infinity)

無限集合が存在する。具体的には、非空集合 \(x\) であって、任意の集合 \(y \in x\) に対して集合 \(\left\{ y \right\}\) が \(x\) の元であるような集合が存在する。

部分集合の公理 (axiom of subset)

任意の \(x\) と集合に対する定義可能な性質に対して、その性質を満たす \(x\) の要素全体からなる集合 \(y\) が存在する:

\[ \forall x\, \exists y\, \forall z.\ z \in y \ \operatorname{\text{\footnotesize IFF}}\ (z \in x \ \operatorname{\text{\footnotesize AND}} \ \phi(z)) \]

ここで \(\phi(z)\) は集合論の論理式を表す³。

冪集合の公理 (axiom of power set)

任意の集合に対して、その部分集合全体の集合が存在する:

\[ \forall x\, \exists p\, \forall u.\ u \in p \ \operatorname{\text{\footnotesize IFF}}\ u \subseteq x \]

置換公理 (axiom of replacement)

集合論の論理式 \(\phi\) が集合 \(s\) 上の関数のグラフを定義すると仮定する。つまり、次の条件が満たされるとする:

\[ \forall x \in s\, \forall y, z.\ (\phi(x, y) \ \operatorname{\text{\footnotesize AND}} \ \phi(x, z)) \ \operatorname{\text{\footnotesize IMPLIES}}\ y = z \]

このとき、その関数による \(s\) の像 \(t\) は集合である。つまり:

\[ \exists t\; \forall y.\ y \in t \ \operatorname{\text{\footnotesize IFF}}\ (\exists x \in s.\ \phi(x, y)) \]

基礎の公理 (axiom of foundation)

この公理は、次の形をした無限列を禁じるためにある:

\[ \cdots \in x_{n} \in \cdots \in x_{1} \in x_{0} \]

この列に含まれる任意の集合は右隣の集合の要素である。この規則を表現するために、「要素関係において最小 (member-minimal)」を意味する述語を定義する:

\[ \text{member-minimal}(m, x) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ (m \in x \ \operatorname{\text{\footnotesize AND}} \ \forall y \in x.\ y \notin m) \]

基礎の公理⁴は任意の非空集合が「要素関係において最小」な要素を持つと定める:

\[ \forall x.\ x \neq \varnothing \ \operatorname{\text{\footnotesize IMPLIES}}\ \exists m.\ \text{member-minimal}(m, x) \]

8.3.3 Russell のパラドックスの回避

現代的な ZFC 公理による集合論は、Russell のパラドックスを回避するために Russell と Whitehead が最初に考案したシステムより格段に単純である。実は、ZFC は Frege が最初に考案した公理系と同程度に単純かつ直感的であり、本質的な違いは一つしかない: 基礎の公理である。この公理は、集合は「より単純な」集合から特定の標準的な手法で構築されなければならないと定める。特に、Russell のパラドックスで利用される集合の集まり \(W ::= \left\{ S \; | \; S \notin S \right\}\) は基礎の公理があると集合でなくなるので、Russell の「パラドックス」は回避される。細かく言えば、基礎の公理から任意の集合 \(S\) で \(S \notin S\) が成り立つと分かり、全ての集合の集まり \(W\) が集合だとしたら \(W \in W\) が成り立って基礎の公理と矛盾する。

構造的帰納法を使った集合に関する性質の証明の正当化でも基礎の公理は使われる。まず、集合の集まり \(\text{RecSet}\) を定義する:

\(\text{RecSet}\) は再帰的に定義されるので、その性質は構造的帰納法で証明できる。次に示すように、基礎の公理があれば任意の集合が再帰集合だと示せるので、集合に関する性質は構造的帰納法で証明できると分かる:

証明 \(\text{RecSet}\) の任意の要素は定義より集合なので、後は任意の集合が \(\text{RecSet}\) に属すると示せばよい。

背理法で示す。集合 \(S\) が \(\text{RecSet}\) に含まれないと仮定する。このとき \(S\) は \(\text{RecSet}\) に属さない要素 \(N_{0}\) を持つ (そうでなければ \(S\) は定義より \(\text{RecSet}\) に属してしまう)。同様に、\(N_{0}\) は \(\text{RecSet}\) に属さない要素 \(N_{1}\) を持ち、\(N_{1}\) は \(\text{RecSet}\) に属さない要素 \(N_{2}\) を持つ。以下同様であり、次の無限列が存在する:

よって集合⁵

は「要素関係において最小」な要素を持たず、基礎の公理を満たさない。 ■