フォン・ノイマン＝ベルナイス＝ゲーデル集合論
数学基礎論において、フォン・ノイマン=ベルナイス=ゲーデル集合論 (NBG) とはツェルメロ=フレンケル集合論+選択公理 (ZFC)の保存拡大である公理的集合論である。NBGでは、量化子の範囲を集合に限定した論理式によって定義される集合の集まりとして、クラスの概念を導入する。NBGは、すべての集合というクラスやすべての順序数というクラスといった、集合よりも大きいクラスを定義できる。モース=ケリー集合論 (MK) は量化子の範囲がクラスである論理式によるクラスの定義を許容する。NBGは有限公理化できる一方、ZFCやMKではできない。
NBGのキーとなる定理はクラスの存在定理である。クラスの存在定理は、量化子の範囲を集合に限定した論理式それぞれに対して、論理式を満たす集合からなるクラスの存在を述べる。クラスは、クラスの論理式を一つずつ構築することで構成される。すべての集合論的な論理式は2種類の原子論理式(所属関係と等式)と有限個の論理記号から構築されるため、論理式を満足するクラスを構築するには有限個の公理があればよい。NBGが有限公理化できるのは、こうした理由による。クラスは他の概念の構築にも用いられ、集合論的パラドックスへの対処や、ZFCの選択公理より強い大域選択公理の説明に用いられる。
ジョン・フォン・ノイマンは1925年に集合論にクラスを導入した。彼の理論の原始概念は関数と引数であった。これらの概念を用いて、フォン・ノイマンはクラスと集合を定義した。 パウル・ベルナイスはクラスと集合を原始概念とすることで、フォン・ノイマンの理論を再定式化した。 クルト・ゲーデルは、選択公理の相対的無矛盾性の証明と一般連続体仮説を用いてベルナイスの理論を単純化した。
NBGにおいてクラスはいくつかの使用例がある:
クラスによって集合論を有限公理化する。
"非常に強い形の選択公理"を表現するのに用いられる。—すなわち、大域選択公理のことである。大域選択公理の内容は以下の通り:すべての空でない集合 x に対して G(x) \in x である、すべての空でない集合のクラス上に定義された大域選択関数 G が存在する。大域選択公理はZFCの選択公理よりも強い。ZFCの選択公理の内容は以下の通り:任意の空でない集合の集合 s について、すべての x \in s に対して f(x) \in x である s 上の選択関数 f が存在する。なぜ「強い」かは大域選択公理の節で説明する。
集合でないクラスが存在することを認めると、集合論的パラドックスは解決される。例えば、すべての順序数のクラス Ord を集合であると仮定する。すると、 Ord は \in で整列された推移的集合となる。すなわち、定義から Ord は順序数である。したがって、 Ord \in Ord であるが、これは Ord が \in で整列されていることに矛盾する。したがって、 Ord は集合ではない。集合ではないクラスを真のクラスと呼ぶため、 Ord は真のクラスである。
ゲーデルの関数真のクラスは集合などの作成に便利である。 大域選択公理と一般連続体仮説の相対的非矛盾性の証明において、ゲーデルは構成可能集合を作るのに真のクラスを用いた。ゲーデルはすべての順序数のクラス上の関数を構成した。すなわち、各順序数について、構成済の集合に対して集合を作る処理を適用することで構成可能集合を作った。構成可能集合はこの関数の像である。
ZFCの言葉にクラスが加えられれば、ZFCをクラス付きの集合論に変換するのが容易になる。まず、クラス解釈の公理型を加える。この公理型は以下の通り:量化子の範囲を集合に限定したすべての論理式 \phi(x_1, \ldots, x_n) に対して、論理式を満たす n-組からなるクラス A が存在する—すなわち、 \forall x_1 \cdots \,\forall x_n [(x_1, \ldots , x_n) \in A \iff \phi(x_1, \ldots, x_n)] である。すると置換公理はクラスを用いる一つの公理で置き換えられる。最後に、ZFCの外延性の公理はクラスを扱う形に修正される:2 つのクラスが同じ元を持つならば、それらのクラスは等しい。ほかのZFCの公理は修正されない。
この理論は有限公理化されない。ZFCの置換公理型は一つの公理で置き換えられるが、クラス解釈の公理はZFCに導入されていないからである。
この理論を有限個の公理で構築するには、まずクラス解釈の公理を有限個のクラス外延性の公理で置き換える。するとこれらの公理は、公理系中のどの公理をも含意するクラス存在定理に用いられる。 この理論の証明には 7 つのクラス存在公理があれば十分である。これらのクラス存在公理は、論理式の構成から論理式を満たすクラスの構成へ変換するのに用いられる。
NBGにはクラスと集合という 2 種類の対象がある。直感的には、どの集合も同時にクラスである。これを公理化する方法は 2 通り存在する。ベルナイスは 2 ソートの多ソート論理を用いた。 ゲーデルはソートの代わりに原始述語を用いた: \mathfrak{Cls}(A) を「 A はクラスである」ことを、 \mathfrak{M}(A) を「 A は集合である」ことを表す述語とする(ドイツ語では集合は Menge である)。ゲーデルは「すべての集合はクラスである」という公理と、「クラス A がクラスの元であれば、 A は集合である」という公理を導入した。 述語はソートの回避のためによく使われる。 エリオット・メンデルソン (Elliott Mendelson) はゲーデルの考え方を元に、全てをクラスとした上で、 \exists C(A \in C) を表す述語 M(A) で集合を表すことで修正した。 この修正によって、ゲーデルのクラス述語と 2 つの公理は不要になる。
ベルナイスの 2 ソートのアプローチのほうが最初は自然に見えるかもしれないが、こちらは複雑な理論になる。歴史的な経緯として、当初は2 ソートのアプローチのほうが一般的に見られた。ベルナイスが自身の理論を展開するにあたり、以下のように述べている。「フォン・ノイマン集合論の考えによると、「集合」と「クラス」という 2 種類のものを扱う必要がある」 ベルナイスの理論では、どの集合も 2 種類の表現を持つ:一つは集合として、もう一つはクラスとしてである。同時に、2 つの 帰属関係がある:一つは "∈" で表される 2 つの集合間の関係、もう一つは "η" で表される集合とクラスの間の関係である。 異なるソートの変数は議論領域中で互いに素な部分領域の元となるため、この冗長性は多ソート論理に必要になる。
これらの 2 つのアプローチで証明できるものは変わらないが、証明の書かれ方は変わってくる。ゲーデルのアプローチでは、 A と C がクラスであるとき A \in C は有効な表現である。ベルナイスのアプローチではこの表現は意味をなさない。しかし、 A が集合であれば、等価な表現が存在する:  集合とクラスが同じ集合を元に持つならば、「集合 a はクラス A を代表する」と定義する。—すなわち、 \forall x(x \in a \iff x \;\eta \;A)。集合 a がクラス A を代表するという表現 a \;\eta \;C は、ゲーデルの A \in C と等価である。
本記事ではゲーデルのアプローチのメンデルソンによる修正版を用いて説明する。これは、NBG は等式を含む一階述語論理における公理系であることを意味し、原始概念はクラスと帰属関係のみであることを意味する。
集合は、少なくとも 1 つのクラスに属するクラスである: \exist C(A \in C) のとき、かつそのときに限り A は集合である。
集合でないクラスは真のクラスと呼ぶ:\forall C(A \notin C) のとき、かつそのときに限り A は真のクラスである。
したがって、どのクラスも集合または真のクラスであり、両方同時に当てはまることはない。
ゲーデルは大文字の変数をクラス上の変数、小文字の変数を集合上の変数とした。 また、ゲーデルは、すべての集合からなるクラス上に定義された関数や関係を含む特定のクラスは、大文字から始まる名前で表した。本記事ではゲーデルのこの表記法に従う。すると以下のように書ける:Plainlist
\exist x\, \phi(x)、\exist x \bigl(\exist C (x \in C) \land \phi(x)\bigr)の代わりに。
\forall x\, \phi(x)、\forall x \bigl(\exist C (x \in C) \implies \phi(x)\bigr)の代わりに。
Endplainlist以下の公理と定義はクラス存在定理の証明に必要である。
外延性の公理.thin 2 つのクラスが同じ元を持っていれば、それらは等しい。
\forall A \,\forall B \,[\forall x(x \in A \iff x \in B) \implies A = B]hair
この公理はZFCの外延性の公理をクラスに一般化したものである。
対の公理.thin x と y が集合であれば、元が x と y のみである集合 p が存在する。
\forall x \,\forall y \,\exists p \,\forall z \,[z \in p \iff (z = x \,\lor\, z = y)]hair
ZFCのように、外延性の公理は集合  p がただ一つであることを含意する。これによって \{x, y\} という表記ができる。
順序対は以下のように定義される。
(x, y) = \{\{x\}, \{x, y\}\}
対は順序対を使って再帰的に定義される:
(x_1) = x_1,
\text{For } n > 1\!: (x_1, \ldots, x_{n-1}, x_n) = ((x_1, \ldots, x_{n-1}), x_n). (x_1, (x_2, \ldots, x_n)) と定義した。 これによって定義や公理、定理の書かれ方が変わるものがある。本記事ではメンデルソンの定義にしたがう。
クラス存在公理はクラス存在定理を証明するのに用いる:集合のみを量化する n 個の集合の自由変数に関するすべての論理式について、その論理式を満たす n-組のクラスが存在する。以下の例は、関数のクラスと合成関数を構築するクラスの 2 つのクラスから始める。この例はクラス存在定理を証明するのに必要な、クラス存在公理を導出する手法を説明する。
クラス存在公理は 2 つのグループに分かれる:述語に関する公理と、対に関する公理である。前者のグループには 4 つの公理が、後者のグループには 3 つの公理が含まれる。ベルナイスのクラス存在公理ではクラスがただ一つ定まる。ゲーデルは、ベルナイスの公理のうち3つ(共通部分、補集合、領域)を除くすべてで、双条件を論理包含で置き換えることで条件を弱めた。これはクラスの順序対または 3-組のみ特定することを意味する。本節の公理はベルナイスが(順序対のクラスをただ一つ定めるという点で)強めたVの直積以外はゲーデルのものである。ベルナイスの公理によってクラス存在定理の証明が簡単になる。ゲーデルの公理 B6 は組の補題の4番目として現れる。のちにベルナイスは自身の公理の一つが冗長であると気づいた。つまり、ゲーデルの公理の一つも冗長であることが導かれる。ほかの公理を使って、公理 B6 を公理 B8 から証明することができ、また B8 は B6 から証明することができ、これらは互いに冗長な公理とみなせる。 対に関係する公理の名前はフランス語版Wikipediaの記事にならったThéorie des ensembles de von Neumann。
述語に関する公理:
帰属.thin 1番めの要素が 2 番めの要素の元になるような順序対すべてを含むクラス E が存在する。
\exists E \,\forall x \,\forall y \,[(x,y) \in E \iff x \in y]\!hair
共通部分(連言).thin 任意の 2 つのクラス A と B に対して、 A と B にそれぞれ属する集合のみからなるクラス C が存在する。
\forall A \,\forall B \,\exists C \,\forall x \,[x \in C \iff (x \in A \,\land\, x \in B)]hair
補集合(否定).thin 任意のクラス A に対して、 A に属さない集合のみからなるクラス B が存在する。
\forall A \,\exists B \,\forall x \,[x \in B \iff \neg(x \in A)]hair
領域(存在量化子).thin 任意のクラス A に対して、 A の順序対の最初の要素からなるクラス B が存在する。
\forall A \,\exists B \,\forall x \,[x \in B \iff \exists y((x,y) \in A)]hair
外延性の公理より、共通部分公理におけるクラス C と補集合公理および領域公理におけるクラス B はそれぞれただ一つ定まる。これらはそれぞれ以下のように表現される:A \cap B, \complement A, and Dom(A). \complement A \cap Xを用いた。 相対補集合は、クラス存在定理で論理否定(\neg) を反転させるために使っている。 一方、帰属公理はクラス E 上の順序対の集合のみを規定するため、外延性の公理は帰属公理におけるクラス E には適用できない。
空クラス最初 3 つの公理は空クラスおよびすべての集合のクラスの存在を含意する:帰属公理はクラス E の存在を含意する。共通部分公理および補集合公理は、空クラスである E \cap \complement E の存在を含意する。外延性の公理により、このクラスはただ一つ定まり、これを \empty で表す。 \empty の補集合はすべての集合のクラス V であり、これも外延性の公理からただ一つ定まる。すると、 \exists C(A \in C) を表す集合述語 M(A) は、クラスを量化することなく A \in V と再定義される。
対に関する公理:
Vの直積公理V の直積.thin 任意のクラス A に対して、最初の要素が A に属する順序対からなるクラス B が存在する。
\forall A \,\exists B \,\forall u \,[u \in B \iff \exists x \, \exists y \,(u = (x, y) \land x \in A)]
巡回置換.thin 任意のクラス A に対して、A の 3-組に巡回置換 (y,z,x) \mapsto (x,y,z) を適用して得られる 3-組からなるクラス B が存在する。
\forall A \,\exists B \,\forall x \,\forall y \,\forall z \,[(x,y,z) \in B \iff (y,z,x) \in A]
転置.thin 任意のクラス A に対して、 A の 3-組の後ろ 2 要素を入れ替えて得られる 3-組からなるクラス B が存在する。
\forall A \,\exists B \,\forall x \,\forall y \,\forall z \,[(x,y,z) \in B \iff (x,z,y) \in A]
外延性から、 V の直積公理は A \times V で表されるただ一つのクラスの存在を含意する。この公理はすべての n-組に対してクラス V^n を定義するのにも用いる: V^1 = V そして V^{n+1} = V^n \times V。 A がクラスならば、外延性は A \cap V^n が A の n-組からなるただ一つのクラスであることを含意する。たとえば、帰属公理から、クラス E が順序対ではない元を含むが、共通部分 E \cap V^2 は E の順序対のみからなるようにクラス E を構成できる。
巡回置換公理と転置公理はクラス B の 3-組であることのみを規定するため、ただ一つのクラスの存在を含意しない。 3-組を規定することで、これらの公理は n \ge 4 に対して n-組についても規定する。なぜならば: (x_1, \ldots, x_{n-2}, x_{n-1}, x_n) = ((x_1, \ldots, x_{n-2}), x_{n-1}, x_n).対に関する公理と領域公理は以下の補題を含意する。この補題はクラス存在定理の証明に用いる。
組の補題 組の補題
クラス B_3: V の直積公理を A に適用し、 B_3 を得る。
クラス B_2: 転置公理を B_3 に適用し、 B_2 を得る。
クラス B_1: 巡回置換公理を B_3 に適用し、 B_1 を得る。
クラス B_4: 巡回置換公理を B_2 に適用した上で領域公理を適用し、 B_4 を得る。
クラス存在定理の証明にはもう一つの公理、正則性公理が必要である。空クラスの存在が証明されるため、この公理のふつうの言明を用いる。ゲーデルは、空集合の存在を証明する前にこの公理に言及しているため、空集合を使わずに述べている。
正則性公理正則性公理.thin 空でないどの集合も、共通部分の要素が空となる元を少なくとも 1 つ持つ。\forall a\,[a \neq \empty \implies \exists u(u \in a \land u \cap a = \empty)].
この公理は集合が自分自身に属さないことを含意する: x \in x と仮定して a = \{x\} と置く。すると x \in x \cap a であるので x \cap a \ne \empty である。これは  x が a の唯一の元であることから、正則性公理と矛盾する。したがって、 x \notin x である。また、正則性公理は集合の無限降下関係列の存在を禁止する:\cdots \in x_{n+1} \in x_n \in \cdots \in x_1 \in x_0.ゲーデルは、自身の1940年のモノグラフで、集合ではなくクラスに関して正則性公理を述べた。これは1938年の講義に基づいたものである。 1939年、ゲーデルは集合の正則性公理がクラスの正則性公理を含意することを証明した。
この定理の証明は 2 ステップからなる:
与えられた論理式 \phi を証明の帰納部分を簡略化する論理的等価性論理式に変換するため、変換規則を用いる。例えば、帰納部分で 3 ケースの論理記号のみを扱うため、変換後の論理式に用いる論理記号は \neg, \land, \exists のみとする。
変換後の論理式に対して、クラス存在定理を帰納的に証明する。変換後の論理式の構造を用い、クラス存在公理から論理式を満たす唯一の n-組を構成する。
変換規則.thin 以下の規則 1 と 2 において、 \Delta と \Gamma はそれぞれ集合とクラスの変数を表す。これらの 2 つの規則で \in の前のすべてのクラス変数とすべての等号を除去する。規則 1 や 2 をサブ論理式に適用する際は、 z_i が論理式中の他の変数と異なるように i を選ぶ。3 つの規則はサブ論理式に適用できなくなるまで適用を繰り返す。これによって、 \neg, \land, \exists, \in、 集合変数、 \in の前に現れないクラス変数 Y_k論理式のみからなる論理式を構成する。
\,Y_k \in \Gamma を \exists z_i(z_i = Y_k \,\land\, z_i \in \Gamma) に変換する。
外延性公理を用いて、 \Delta = \Gamma を \forall z_i(z_i \in \Delta \iff z_i \in \Gamma) に変換する。
論理的同一性を用いて、\lor, \implies, \iff, and \forall が含まれるサブ論理式を \neg, \land, \exists のみが含まれるサブ論理式に変換する。
変換規則:束縛変数.thin 例 1の合成関数論理式について、集合の自由変数を x_1 と x_2 に置き換えることを考える: \exists t[(x_1, t) \in F \,\land\, (t, x_2) \in G]。帰納的証明で論理式 (x_1, t) \in F \land (t, x_2) \in G をなす \exists t が取り除かれる。しかし、クラス存在定理は添字つき変数を使って表されているため、この論理式は帰納法における仮定として期待される形式にならない。この問題は変数 t を x_3 で置き換えることで解決できる。ネストされた量化子内の束縛変数を扱うには、量化子ごとに添字の数字を 1 ずつ増やしていけば良い。これによって規則 4 が導出される。規則 1 と 2 で量化された変数が増えるため、規則 4 はほかの規則よりもあとに適用しなければならない。
論理式に x_1, \dots, x_n 以外の自由変数が含まれなければ、 q 個の量化子内にネストされた束縛変数を x_{n+q} に置き換える。これらの変数は (量化子)ネスト深さ q である。
クラス存在定理の証明.thin 証明は与えられた論理式に変換規則を適用して、論理式を変換することから始める。この論理式は与えられた論理式と等価であるので、変換済みの論理式を証明すればクラス存在定理の証明が完了する。
1 のとき、 P_1 = P とする。pbi > 1のとき、x_iの前に成分が追加される:組の補題の言明 1 を P with z = (x_1, \dots, x_{i-1}) に適用する。この操作により、R(x_i, x_j) を満たすすべての (i+1)-組 ((x_1, \dots, x_{i-1}), x_i, x_j) = (x_1, \dots, x_{i-1}, x_i, x_j) を含むクラス P_1 が生成される。
j = i + 1 のとき、 P_2 = P_1 とする。pbj > i + 1 のとき、x_i と x_j の間に成分が追加される:組の補題の言明 2 を用いて x_{i+1}, \dots, x_{j-1} を一つずつ追加する。この操作により、R(x_i, x_j). を満たすすべての j-組 (((\cdots((x_1, \dots, x_i), x_{i+1}), \cdots), x_{j-1}), x_j) = (x_1, \dots, x_j) を含むクラス P_2 が生成される。
j = n のとき、 P_3 = P_2とする。pb j < n のとき、x_jのあとに成分が追加される:組の補題の言明 3 を用いて x_{j+1}, \dots, x_n を一つずつ追加する。この操作により、 R(x_i, x_j). を満たすすべての n-組 ((\cdots((x_1, \dots, x_j), x_{j+1}), \cdots), x_n) = (x_1, \dots, x_n) を含むクラス P_3 が生成される。
Q = P_3 \cap V^n とする。外延性の公理から、 Q が R(x_i, x_j). を満たす n-組の唯一のクラスであることが導かれる。
証明:基礎ステップ:\phi は論理記号を含まない。定理の仮説は \phi が x_i \in x_j または x_i \in Y_k の形の原子論理式であることを含意する。
Case 1: \phi が x_i \in x_j のとき、x_i \in x_j. を満たす n-組の唯一のクラス E_{i,j,n} = \{(x_1, \ldots, x_{n}): x_i \in x_j\} を構成する。
Case a: \phi が x_i \in x_j(i < j)のとき、帰属の公理より、 x_i \in x_j を満たすすべての順序対 (x_i, x_j) を含むクラス P を生成する。拡張の補題を P に適用することで、 E_{i,j,n} = \{(x_1, \ldots, x_{n}): x_i \in x_j\} を得る。
Case b: \phi が x_i \in x_j(i > j)のとき、帰属の公理より、 x_i \in x_j を満たすすべての順序対 (x_i, x_j) を含むクラス P を生成する。組の補題の言明 4 を P に適用することで、 x_i \in x_j を満たすすべての順序対 (x_j, x_i) を含むクラス P' を生成する。拡大の公理を P' に適用することで、 E_{i,j,n} = \{(x_1, \ldots, x_{n}): x_i \in x_j\} を得る。
Case c: \phi が x_i \in x_j (i = j)のとき、正則性の公理よりこの論理式は偽であるため、これを満たす n-組は存在せず、ゆえに E_{i,j,n} = \empty である。
Case 2: \phi が x_i \in Y_k のとき、 x_i \in Y_k. を満たす n-組の唯一のクラス E_{i,Y_k,n} = \{(x_1, \ldots, x_{n}): x_i \in Y_k\} を構成する。
Case a: \phi が x_i \in Y_k(i < n)のとき、 V の直積公理を Y_k に適用してクラス P = Y_k \times V = \{(x_i, x_{i+1}): x_i \in Y_k\} を得る。拡大の補題を P に適用して E_{i,Y_k,n} = \{(x_1, \ldots, x_{n}): x_i \in Y_k\} を得る。
Case b: \phi が x_i \in Y_k(i = n > 1)のとき、 V の直積公理を Y_k に適用してクラス P = Y_k \times V = \{(x_i, x_{i-1}): x_i \in Y_k\} を得る。組の補題の言明 4 を P に適用して P' = V \times Y_k = \{(x_{i-1}, x_i): x_i \in Y_k\} を得る。拡大の補題を P' に適用して E_{i,Y_k,n} = \{(x_1, \ldots, x_{n}): x_i \in Y_k\} を得る。
Case c: \phi が x_i \in Y_k(i = n = 1)のとき、 E_{i,Y_k,n} = Y_k である。
帰納ステップ:\phi は k(>0) 個の論理記号を含む。「k 未満の個数の論理記号を含むすべての \psi に対して、定理が真である」という、帰納の仮説を仮定する。この条件下で、 k 個の論理記号を含む \phi に対して、定理が真であることを証明する。この証明において、クラス変数 Y_1, \dots, Y_m を \vec{Y} で略記する。すると例えば論理式 \phi(x_1, \dots, x_n, Y_1, \dots, Y_m) は \phi(x_1, \dots, x_n, \vec{Y}) のように書ける。
Case 1: \phi(x_1, \ldots, x_n, \vec{Y}) = \neg \psi(x_1, \ldots, x_n, \vec{Y}) のとき、 \psi は k-1 個の論理記号を含むため、帰納仮説は以下を満たすn-組のクラス A がただ一つ存在することを含意する:
\quad(x_1, \ldots , x_n) \in A \iff \psi(x_1, \ldots, x_n, \vec{Y}).