ZFC 集合論

Basis
最終更新: タグ: Set Theory

前提知識

集合入門 以来、集合は何の問題もないかのように使ってきた――要素を波括弧で囲み、部分集合を作り、和集合を取る。日常的な数学ではこれで十分だ。しかし、一見無害な問いを立てた途端に崩れ去る。集合は自分自身の要素になれるのか？

その問いに制限なしの集合形成で答えようとすると、矛盾に直結する――微妙な矛盾ではなく、1行の論理的爆発だ。選択公理付きツェルメロ–フレンケル集合論 (Zermelo–Fraenkel set theory with the Axiom of Choice)、略して ZFC が、数学が落ち着いた答えだ。今日 ZFC は、実質的にすべての数学が依拠する標準的な基礎となっている。

素朴な集合論の問題

素朴な集合論 (naïve set theory) では、性質で記述できるものは何でも集合になる。任意の述語 φ(x)\varphi(x) に対して、

{x∣φ(x)}\{x \mid \varphi(x)\}

を自由に形成できる。この無制限の自由を無制限内包公理 (unrestricted comprehension) という。これは矛盾する。

ラッセルのパラドックス (Russell’s paradox)（1901年）はその最も簡単な証明だ。

R  ≔  {x∣x∉x}R \;\coloneqq\; \{x \mid x \notin x\}

と定義する。RR は自分自身の要素でない集合すべてを集めるはずだ。では R∈RR \in R だろうか？

  • R∈RR \in R ならば、RR は定義条件 x∉xx \notin x を満たすので R∉RR \notin R となる。矛盾。
  • R∉RR \notin R ならば、RR は x∉xx \notin x を満たさないので R∈RR \in R となる。矛盾。

一貫した答えはない。RR は存在できず、無制限内包公理は壊れている。

公理的アプローチ

修正方針は、無制限の自由を、慎重に選び抜かれた公理 (axioms)――真と宣言される基本命題――の短いリストに置き換え、それ以外のすべてをそこから導くことだ。公理は次を満たさなければならない。

  • 一貫性：矛盾を導かないこと（ZFC は一貫性があると信じられているが、ZFC の内部では証明できない――ゲーデルの不完全性定理がそれを禁じる）。
  • 十分な強さ：通常の数学をすべて再構築できるだけの強さを持つこと。

ZFC はツェルメロとフレンケルによる 9つの公理――そのうち2つは公理スキーマ (axiom schemas)、つまり述語ごとに1つの公理からなる無限の族を表す――と選択公理 (Axiom of Choice) からなる。

9つの ZF 公理

外延性公理

まったく同じ要素を持つ2つの集合は等しい。

∀A  ∀B  (∀x  (x∈A↔x∈B))  ⇒  A=B\forall A\;\forall B\;\bigl(\forall x\;(x \in A \leftrightarrow x \in B)\bigr) \;\Rightarrow\; A = B

この原則は 集合入門 ですでに知っている。{1,2,3}={3,1,2}\{1,2,3\} = \{3,1,2\} は順序によらず 11、22、33 をちょうど含むから。外延性公理はこれを等号の定義とする――集合はその要素によって完全に決まり、それ以外の何ものによっても決まらない。

空集合公理

要素を持たない集合が存在する。

∃A  ∀x  (x∉A)\exists A\;\forall x\;(x \notin A)

外延性公理によりそのような集合はただ1つで、∅\emptyset と表す。この公理がなければ、集合が1つでも存在することすら証明できない。

対公理

任意の2つの集合 aa、bb に対して、aa と bb だけを要素に持つ集合が存在する。

∀a  ∀b  ∃A  ∀x  (x∈A  ↔  x=a  ∨  x=b)\forall a\;\forall b\;\exists A\;\forall x\;\bigl(x \in A \;\leftrightarrow\; x = a \;\lor\; x = b\bigr)

これは順序なし対 (unordered pairs) {a,b}\{a, b\} を正当化する。特別なケースとして a=ba = b とすれば一点集合 {a}\{a\} が得られる。

対公理を使うと、新しい基本概念を導入せずに順序対 (ordered pairs) も定義できる。クラトフスキー (Kuratowski) のエンコードは次の通りだ。

(a,b)  ≔  {{a},  {a,b}}.(a, b) \;\coloneqq\; \bigl\{\{a\},\;\{a, b\}\bigr\}.

(a,b)=(c,d)(a, b) = (c, d) が成り立つのは a=ca = c かつ b=db = d のときだけであることを確認できるので、このエンコードは順序の概念を正しく捉えている。順序対から関係、関数、直積――すべて ZFC の内部で――を構築できる。

和公理

集合の族 F\mathcal{F} に対して、F\mathcal{F} の各要素の要素をちょうど含む集合が存在する。

∀F  ∃A  ∀x  (x∈A  ↔  ∃F∈F,  x∈F)\forall \mathcal{F}\;\exists A\;\forall x\;\bigl(x \in A \;\leftrightarrow\; \exists F \in \mathcal{F},\; x \in F\bigr)

得られる集合が和集合 (union) ⋃F\bigcup \mathcal{F} だ。F={A,B}\mathcal{F} = \{A, B\} とすれば馴染みの A∪BA \cup B が復元される。一般形は無限の族も扱える。⋃{A1,A2,A3,…}=A1∪A2∪A3∪⋯\bigcup \{A_1, A_2, A_3, \ldots\} = A_1 \cup A_2 \cup A_3 \cup \cdots。

冪集合公理

任意の集合 aa に対して、aa のすべての部分集合からなる集合が存在する。

∀a  ∃A  ∀x  (x∈A  ↔  x⊆a)\forall a\;\exists A\;\forall x\;\bigl(x \in A \;\leftrightarrow\; x \subseteq a\bigr)

これはまさに 冪集合 P(a)\mathcal{P}(a) だ。冪集合公理があるからこそ、より大きな無限集合へ登り続けられる。N\mathbb{N} から始めて P(N)\mathcal{P}(\mathbb{N}) を形成し、次に P(P(N))\mathcal{P}(\mathcal{P}(\mathbb{N})) を形成し、以下同様に続く――カントールの定理によって各ステップで真に大きくなる。

分離公理（スキーマ）

任意の集合 aa と任意の述語 φ\varphi に対して、φ\varphi を満たす aa の要素からなる部分集合が存在する。

∀a  ∃A  ∀x  (x∈A  ↔  x∈a  ∧  φ(x))\forall a\;\exists A\;\forall x\;\bigl(x \in A \;\leftrightarrow\; x \in a \;\land\; \varphi(x)\bigr)

これはスキーマだ。集合論の言語の述語 φ\varphi ごとに1つの公理があり、一度に無限に多くの公理を与える。

分離公理は無制限内包公理の安全な代替だ。{x∈a∣φ(x)}\{x \in a \mid \varphi(x)\} を形成できるが、必ず既存の集合 aa から始めなければならない。これがラッセルのパラドックスを防ぐ。任意の固定した集合 aa に対して {x∈a∣x∉x}\{x \in a \mid x \notin x\} は形成できるが、出発点として使える「すべての集合の集合」は存在しない。矛盾は消える。

集合入門における内包表記 {x∈S∣P(x)}\{x \in S \mid P(x)\} はまさにこの公理によって正当化される。

無限公理

∅\emptyset を含み、操作 x↦x∪{x}x \mapsto x \cup \{x\} で閉じた集合が存在する。

∃A  (∅∈A  ∧  ∀x∈A,  x∪{x}∈A)\exists A\;\Bigl(\emptyset \in A \;\land\; \forall x \in A,\; x \cup \{x\} \in A\Bigr)

これが無限集合の存在を保証する公理だ。集合 AA は以下の集合の連鎖を含まなければならない。

∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}},…\emptyset,\quad \{\emptyset\},\quad \bigl\{\emptyset, \{\emptyset\}\bigr\},\quad \bigl\{\emptyset, \{\emptyset\}, \{\emptyset,\{\emptyset\}\}\bigr\},\quad \ldots

これらがフォン・ノイマン自然数 (von Neumann natural numbers) だ。次のように同一視する。

0≔∅,1≔{0},2≔{0,1},3≔{0,1,2},…0 \coloneqq \emptyset, \qquad 1 \coloneqq \{0\}, \qquad 2 \coloneqq \{0,1\}, \qquad 3 \coloneqq \{0,1,2\}, \qquad \ldots

すなわち各自然数は、それより小さいすべての自然数の集合だ。無限公理によって、N\mathbb{N} が非形式的な概念としてではなく、ZFC 内で完結した集合として存在することが証明できる。

置換公理（スキーマ）

φ(x,y)\varphi(x, y) が集合 aa 上の関数を定義するならば（各 x∈ax \in a に対して一意な yy が対応するならば）、φ\varphi による aa の像は集合である。

∀a  [(∀x∈a  ∃! y  φ(x,y))  ⇒  ∃B  ∀y  (y∈B  ↔  ∃x∈a,  φ(x,y))]\forall a\;\Bigl[\bigl(\forall x \in a\;\exists!\, y\;\varphi(x,y)\bigr) \;\Rightarrow\; \exists B\;\forall y\;\bigl(y \in B \;\leftrightarrow\; \exists x \in a,\;\varphi(x,y)\bigr)\Bigr]

分離公理と同様、置換公理もスキーマ――述語 φ\varphi ごとに1インスタンス――だ。

置換公理が言うのは、任意の集合を定義可能な関数で写した像もまた集合だということだ。これにより、以前の公理では届かない {ω,ω+1,ω+2,…}\{\omega, \omega+1, \omega+2, \ldots\}（ω\omega は最初の無限順序数）のような集合を構築できる。分離公理は集合を小さくすることしかできないが、置換公理は集合をまったく新しいオブジェクトに写せる。

正則性公理（基礎公理）

空でないすべての集合は、それと交わりを持たない要素を含む。

∀A  (A≠∅  ⇒  ∃x∈A,  x∩A=∅)\forall A\;\bigl(A \neq \emptyset \;\Rightarrow\; \exists x \in A,\; x \cap A = \emptyset\bigr)

正則性公理は循環的な帰属 (circular membership) を排除する。集合 aa が自分自身を含む――a∈aa \in a――とすると、一点集合 {a}\{a\} が正則性公理に違反する。唯一の要素は aa だが a∩{a}={a}≠∅a \cap \{a\} = \{a\} \neq \emptyset だからだ。より一般に、a0∋a1∋a2∋⋯a_0 \ni a_1 \ni a_2 \ni \cdots と永遠に降り続ける無限鎖も存在できない。

実際には、正則性公理に違反するような集合にはほとんど出会わない。この公理の主な目的は集合論的な宇宙を制御することで、帰属関係 ∈\in に関する整礎帰納法 (well-founded induction) による証明を可能にすることだ。

選択公理

上の9つの ZF 公理が系 ZF を形成する。選択公理 (Axiom of Choice, AC) を加えると完全な系 ZFC になる。

空でない集合の族 F\mathcal{F} に対して、F\mathcal{F} の各要素から1つずつ要素を選ぶ関数が存在する。

∀F  [(∀F∈F,  F≠∅)  ⇒  ∃f ⁣:F→⋃F,    ∀F∈F,  f(F)∈F]\forall \mathcal{F}\;\Bigl[ \bigl(\forall F \in \mathcal{F},\; F \neq \emptyset\bigr) \;\Rightarrow\; \exists f\colon\mathcal{F} \to \bigcup\mathcal{F},\;\; \forall F \in \mathcal{F},\; f(F) \in F \Bigr]

関数 ff を F\mathcal{F} の選択関数 (choice function) という。

有限の族に対しては、各集合から1つ要素を選ぶのは自明だ――有限個のステップで1つずつやるだけでいい。公理が必要なのは無限の族で、体系的な規則なしに無限に多くの選択を行うことはできないからだ。AC は明示的な規則が利用できないときでも、そのような関数が存在すると主張する。

AC が特別扱いされる理由

クルト・ゲーデルは1938年に AC が ZF と一貫していることを証明した。ZF 自体が一貫性を持つ限り、ZF + AC から矛盾を導くことはできない。ポール・コーエンは1963年に AC が ZF から独立していることを証明した。ZF だけからは AC を証明することもできない。これら2つの結果を合わせると、AC は他の9つの公理の帰結ではなく、真に追加的な仮定だということがわかる。

この独立性ゆえに、数学のテキストでは AC を必要とする定理に特別な印をつけることがあり、AC なしの ZF でどれほどのことが壊れるかを見るために意図的に ZF の枠内で研究する数学者もいる。

AC の同値命題

ZF の中で、多くの原理が AC とまったく同じ強さを持つことがわかっている――それぞれが AC を含意し、かつ AC に含意される。

原理非形式的な内容
整列順序定理すべての集合は整列順序を持てる
ツォルンの補題すべての鎖が上界を持つ半順序集合には極大元がある
チコノフの定理コンパクトな位相空間の任意の積はコンパクト
すべてのベクトル空間は基底を持つ無限次元のものも含めすべてのベクトル空間はハメル基底を持つ

整列順序定理は 整列順序のチェックポイント ですでに見た。これらの同値命題の中で、ツォルンの補題 (Zorn’s lemma) は「選択をする」こととの関係が表面上わかりにくいにもかかわらず、代数や解析で最も頻繁に出会うものだ。

ZFC が構築するもの

10個の公理と ∅\emptyset から出発して、標準的な数学のすべてを体系的な順序で構築できる。

  1. 自然数 N\mathbb{N} ― 無限公理によるフォン・ノイマンエンコード。
  2. 整数 Z\mathbb{Z} ― a−ba - b を表す対 (a,b)∈N2(a, b) \in \mathbb{N}^2 の同値類。
  3. 有理数 Q\mathbb{Q} ― p/qp/q を表す対 (p,q)∈Z×(Z∖{0})(p, q) \in \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}) の同値類。
  4. 実数 R\mathbb{R} ― デデキント切断（Q\mathbb{Q} の部分集合）またはコーシー列の同値類。
  5. 複素数 C\mathbb{C} ― 適切な演算を持つ実数の対。
  6. 関数と関係 ― クラトフスキー順序対の集合として。
  7. 順序数 (ordinals) ― あらゆる可能な順序型を代表する正準的な整列集合。
  8. 基数 (cardinals) ― 無限集合の「大きさ」を測り、ℵ0<ℵ1<ℵ2<⋯\aleph_0 < \aleph_1 < \aleph_2 < \cdots という階層を形成する。

解析学、代数学、位相幾何学、計算機科学で出会うであろうすべての数学的対象は、原理的には ZFC の公理を使って ∅\emptyset から構築された純粋な集合に還元できる。

まとめ

  • 素朴な集合論は矛盾する。無制限内包公理はラッセルのパラドックス（R={x∣x∉x}R = \{x \mid x \notin x\} から R∈R↔R∉RR \in R \leftrightarrow R \notin R）を導く。
  • ZFC は無制限の自由を10個の明示的な公理で置き換える。ツェルメロ–フレンケルの9つの公理と選択公理だ。
  • 外延性公理は帰属によって集合の等号を定義し、空集合公理は ∅\emptyset の存在を保証し、対公理は {a,b}\{a, b\} とクラトフスキー順序対を構築する。
  • 和公理は集合の族の要素を集め、冪集合公理は P(a)\mathcal{P}(a) を生成してより大きな無限への登攀を可能にする。
  • 分離公理（スキーマ）は無制限内包の安全な代替だ。既存の集合から部分集合を切り出すことしかできず、ラッセルのパラドックスを防ぐ。
  • 無限公理はフォン・ノイマンエンコード n={0,1,…,n−1}n = \{0, 1, \ldots, n-1\} によって集合論の内部で N\mathbb{N} を構築する。
  • 置換公理（スキーマ）は定義可能な関数によって集合を新しい集合に写し、分離公理だけでは届かない先へ進める。
  • 正則性公理は循環的な帰属の鎖を禁じ、∈\in に関する整礎帰納法を支える。
  • 選択公理は空でない集合の任意の族に対して選択関数が存在すると主張する。ZF から独立しており、整列順序定理とツォルンの補題に同値だ。
  • これら10個の公理と ∅\emptyset から、標準的な数学のすべて――N\mathbb{N}、Z\mathbb{Z}、Q\mathbb{Q}、R\mathbb{R}、C\mathbb{C}、関数、順序数、基数――を構築できる。