フォン・ノイマン＝ベルナイス＝ゲーデル集合論
クラス存在公理はクラス存在定理を証明するのに用いる:集合のみを量化する n {\displaystyle n} 個の集合の自由変数に関するすべての論理式について、その論理式を満たす n {\displaystyle n} -組のクラスが存在する。以下の例は、関数のクラスと合成関数を構築するクラスの 2 つのクラスから始める。この例はクラス存在定理を証明するのに必要な、クラス存在公理を導出する手法を説明する。
クラス存在公理は 2 つのグループに分かれる:述語に関する公理と、対に関する公理である。前者のグループには 4 つの公理が、後者のグループには 3 つの公理が含まれる。
述語に関する公理:
帰属. 1番めの要素が 2 番めの要素の元になるような順序対すべてを含むクラス E {\displaystyle E} が存在する。
∃ E ∀ x ∀ y [ ( x , y ) ∈ E ⟺ x ∈ y ] {\displaystyle \exists E\,\forall x\,\forall y\,[(x,y)\in E\iff x\in y]\!}
共通部分(連言). 任意の 2 つのクラス A {\displaystyle A} と B {\displaystyle B} に対して、 A {\displaystyle A} と B {\displaystyle B} にそれぞれ属する集合のみからなるクラス C {\displaystyle C} が存在する。
NBGにはクラスと集合という 2 種類の対象がある。直感的には、どの集合も同時にクラスである。これを公理化する方法は 2 通り存在する。ベルナイスは 2 ソートの多ソート論理を用いた。 ゲーデルはソートの代わりに原始述語を用いた: C l s ( A ) {\displaystyle {\mathfrak {Cls}}(A)} を「 A {\displaystyle A} はクラスである」ことを、 M ( A ) {\displaystyle {\mathfrak {M}}(A)} を「 A {\displaystyle A} は集合である」ことを表す述語とする(ドイツ語では集合は Menge である)。ゲーデルは「すべての集合はクラスである」という公理と、「クラス A {\displaystyle A} がクラスの元であれば、 A {\displaystyle A} は集合である」という公理を導入した。 述語はソートの回避のためによく使われる。 エリオット・メンデルソン (Elliott Mendelson) はゲーデルの考え方を元に、全てをクラスとした上で、 ∃ C ( A ∈ C ) {\displaystyle \exists C(A\in C)} を表す述語 M ( A ) {\displaystyle M(A)} で集合を表すことで修正した。 この修正によって、ゲーデルのクラス述語と 2 つの公理は不要になる。
ベルナイスの 2 ソートのアプローチのほうが最初は自然に見えるかもしれないが、こちらは複雑な理論になる。 ベルナイスの理論では、どの集合も 2 種類の表現を持つ:一つは集合として、もう一つはクラスとしてである。
クラス B 4 {\displaystyle B_{4}} : 巡回置換公理を B 2 {\displaystyle B_{2}} に適用した上で領域公理を適用し、 B 4 {\displaystyle B_{4}} を得る。
クラス存在定理の証明にはもう一つの公理、正則性公理が必要である。空クラスの存在が証明されるため、この公理のふつうの言明を用いる。
正則性公理. 空でないどの集合も、共通部分の要素が空となる元を少なくとも 1 つ持つ。
この公理は集合が自分自身に属さないことを含意する: x ∈ x {\displaystyle x\in x} と仮定して a = { x } {\displaystyle a=\{x\}} と置く。すると x ∈ x ∩ a {\displaystyle x\in x\cap a} であるので x ∩ a ≠ ∅ {\displaystyle x\cap a\neq \emptyset } である。これは x {\displaystyle x} が a {\displaystyle a} の唯一の元であることから、正則性公理と矛盾する。したがって、 x ∉ x {\displaystyle x\notin x} である。また、正則性公理は集合の無限降下関係列の存在を禁止する:
ゲーデルは、自身の1940年のモノグラフで、集合ではなくクラスに関して正則性公理を述べた。これは1938年の講義に基づいたものである。 1939年、ゲーデルは集合の正則性公理がクラスの正則性公理を含意することを証明した。
{\displaystyle u\in C\iff \psi _{C}(u).}
演算 P {\displaystyle P} を以下のように定義する: u ∈ P ( Z 1 , ... , Z k ) ⟺ ψ P ( u , Z 1 , ... , Z k ) . {\displaystyle u\in P(Z_{1},\dots ,Z_{k})\iff \psi _{P}(u,Z_{1},\dots ,Z_{k}).}
項(en:Term (logic))は以下のように定義される:
変数と特別なクラスは項である。
P {\displaystyle P} が k {\displaystyle k} 変数の演算でかつ Γ 1 , ... , Γ k {\displaystyle \Gamma _{1},\dots ,\Gamma _{k}} が項であるならば、 P ( Γ 1 , ... , Γ k ) {\displaystyle P(\Gamma _{1},\dots ,\Gamma _{k})} は項である。
以下の変換規則は、関係、特別なクラス、演算を消去する。規則 2b, 3b, 4 をサブ論理式に適用する際は、 z i {\displaystyle z_{i}} が論理式中の他の変数と異なるように i {\displaystyle i} を選ぶ。規則はサブ論理式に適用できなくなるまで適用を繰り返す。 Γ 1 , ...
クラスの概念により、NBG では ZFC より強い選択公理が許容される。 選択関数は、空でない集合の集合 s {\displaystyle s} 上の関数 f {\displaystyle f} であり、 x ∈ s {\displaystyle x\in s} で f ( x ) ∈ x {\displaystyle f(x)\in x} を満たすものとして定義される。ZFC の選択公理は、すべての空でない集合の集合に対する選択関数が存在することを述べる。 大域選択関数はすべての空でない集合のクラス上で定義された関数 G {\displaystyle G} であり、すべての空でない集合 x {\displaystyle x} に対して G ( x ) ∈ x {\displaystyle G(x)\in x} を満たすものとして定義される。大域選択公理は大域選択関数が存在することを述べる。この公理は ZFC の選択公理を含意する。なぜならば空でない集合のすべての集合 s {\displaystyle s} に対して、 G | s {\displaystyle G\vert _{s}} ( G {\displaystyle G} の s {\displaystyle s} への制限)は s {\displaystyle s} の選択関数となるからである。
∀ A ∀ B ∃ C ∀ x [ x ∈ C ⟺ ( x ∈ A ∧ x ∈ B ) ] {\displaystyle \forall A\,\forall B\,\exists C\,\forall x\,[x\in C\iff (x\in A\,\land \,x\in B)]}
補集合(否定). 任意のクラス A {\displaystyle A} に対して、 A {\displaystyle A} に属さない集合のみからなるクラス B {\displaystyle B} が存在する。
∀ A ∃ B ∀ x [ x ∈ B ⟺ ¬ ( x ∈ A ) ] {\displaystyle \forall A\,\exists B\,\forall x\,[x\in B\iff \neg (x\in A)]}
領域(存在量化子). 任意のクラス A {\displaystyle A} に対して、 A {\displaystyle A} の順序対の最初の要素からなるクラス B {\displaystyle B} が存在する。
∀ A ∃ B ∀ x [ x ∈ B ⟺ ∃ y ( ( x , y ) ∈ A ) ] {\displaystyle \forall A\,\exists B\,\forall x\,[x\in B\iff \exists y((x,y)\in A)]}
外延性の公理より、共通部分公理におけるクラス C {\displaystyle C} と補集合公理および領域公理におけるクラス B {\displaystyle B} はそれぞれただ一つ定まる。