クラスと集合
NBGにはクラスと集合という 2 種類の対象がある。直感的には、どの集合も同時にクラスである。これを公理化する方法は 2 通り存在する。ベルナイスは 2 ソートの多ソート論理を用いた。[2] ゲーデルはソートの代わりに原始述語を用いた: を「 はクラスである」ことを、 を「 は集合である」ことを表す述語とする(ドイツ語では集合は Menge である)。ゲーデルは「すべての集合はクラスである」という公理と、「クラス がクラスの元であれば、 は集合である」という公理を導入した。[9] 述語はソートの回避のためによく使われる。 エリオット・メンデルソン (Elliott Mendelson) はゲーデルの考え方を元に、全てをクラスとした上で、 を表す述語 で集合を表すことで修正した。[10] この修正によって、ゲーデルのクラス述語と 2 つの公理は不要になる。
ベルナイスの 2 ソートのアプローチのほうが最初は自然に見えるかもしれないが、こちらは複雑な理論になる。[注釈 2] ベルナイスの理論では、どの集合も 2 種類の表現を持つ:一つは集合として、もう一つはクラスとしてである。同時に、2 つの 帰属関係がある:一つは "∈" で表される 2 つの集合間の関係、もう一つは "η" で表される集合とクラスの間の関係である。[2] 異なるソートの変数は議論領域中で互いに素な部分領域の元となるため、この冗長性は多ソート論理に必要になる。
これらの 2 つのアプローチで証明できるものは変わらないが、証明の書かれ方は変わってくる。ゲーデルのアプローチでは、 と がクラスであるとき は有効な表現である。ベルナイスのアプローチではこの表現は意味をなさない。しかし、 が集合であれば、等価な表現が存在する: 集合とクラスが同じ集合を元に持つならば、「集合 はクラス を代表する」と定義する。—すなわち、 。集合 がクラス を代表するという表現 は、ゲーデルの と等価である。[2]
本記事ではゲーデルのアプローチのメンデルソンによる修正版を用いて説明する。これは、NBG は等式を含む一階述語論理における公理系であることを意味し、(原始概念)(英語版)はクラスと帰属関係のみであることを意味する。
外延性の公理と対の公理の定義
集合は、少なくとも 1 つのクラスに属するクラスである: のとき、かつそのときに限り は集合である。 集合でないクラスは真のクラスと呼ぶ: のとき、かつそのときに限り は真のクラスである。[12] したがって、どのクラスも集合または真のクラスであり、両方同時に当てはまることはない。
ゲーデルは大文字の変数をクラス上の変数、小文字の変数を集合上の変数とした。[9] また、ゲーデルは、すべての集合からなるクラス上に定義された関数や関係を含む特定のクラスは、大文字から始まる名前で表した。本記事ではゲーデルのこの表記法に従う。すると以下のように書ける:
- 、 の代わりに。
- 、 の代わりに。
以下の公理と定義はクラス存在定理の証明に必要である。
外延性の公理. 2 つのクラスが同じ元を持っていれば、それらは等しい。
- [13]
この公理はZFCの外延性の公理をクラスに一般化したものである。
対の公理. と が集合であれば、元が と のみである集合 が存在する。
- [14]
ZFCのように、外延性の公理は集合 がただ一つであることを含意する。これによって という表記ができる。
順序対は以下のように定義される。
-
対は順序対を使って再帰的に定義される:
-
- [注釈 3]
クラス存在公理と正則性公理
クラス存在公理はクラス存在定理を証明するのに用いる:集合のみを量化する 個の集合の自由変数に関するすべての論理式について、その論理式を満たす -組のクラスが存在する。以下の例は、関数のクラスと合成関数を構築するクラスの 2 つのクラスから始める。この例はクラス存在定理を証明するのに必要な、クラス存在公理を導出する手法を説明する。
例 1: クラス と が関数であるならば、合成関数 は以下の論理式で定義される: この論理式は 2 つの集合に関する自由変数 と を持つため、クラス存在定理から以下の順序対のクラスの存在が導かれる: この論理式は論理積 と存在記号 を使って簡潔に構築されているので、簡潔な論理式を表すクラスを使って と を含む論理式を表すクラスを生成するクラス演算が必要である。 の論理式を表すクラスを作るには、 であることから共通部分を用いる。 の論理式を表すクラスを作るには、 であることから領域を用いる 共通部分を求める前に、 と にそれぞれ含まれる組において、共通した変数を持つように他の要素が必要になる。元 を の組に、 元 を の組に加える: の定義において、変数 は で制限されないため、 の定義域はすべての集合のクラス 上になる。同様に、 の定義において、変数 の定義域も 上になる。ここで与えられたクラスの組に( 上の)追加の元を加える公理が必要になる。 次に、共通部分をとる準備として、変数を同じ順序で並べる: から および から へは、2 種類の巡回が必要になる。ゆえに、組の元の巡回を扱う公理が必要になる。 と の共通部分は で表現される: は として定義されるので、 の領域は で表現され、合成関数を生成する: したがって、共通部分および領域の公理が必要である。 |
クラス存在公理は 2 つのグループに分かれる:述語に関する公理と、対に関する公理である。前者のグループには 4 つの公理が、後者のグループには 3 つの公理が含まれる。[注釈 4]
述語に関する公理:
帰属. 1番めの要素が 2 番めの要素の元になるような順序対すべてを含むクラス が存在する。
- [18]
共通部分(連言). 任意の 2 つのクラス と に対して、 と にそれぞれ属する集合のみからなるクラス が存在する。
- [19]
補集合(否定). 任意のクラス に対して、 に属さない集合のみからなるクラス が存在する。
- [20]
領域(存在量化子). 任意のクラス に対して、 の順序対の最初の要素からなるクラス が存在する。
- [21]
外延性の公理より、共通部分公理におけるクラス と補集合公理および領域公理におけるクラス はそれぞれただ一つ定まる。これらはそれぞれ以下のように表現される: and [注釈 5] 一方、帰属公理はクラス 上の順序対の集合のみを規定するため、外延性の公理は帰属公理におけるクラス には適用できない。
最初 3 つの公理は空クラスおよびすべての集合のクラスの存在を含意する:帰属公理はクラス の存在を含意する。共通部分公理および補集合公理は、空クラスである の存在を含意する。外延性の公理により、このクラスはただ一つ定まり、これを で表す。 の補集合はすべての集合のクラス であり、これも外延性の公理からただ一つ定まる。すると、 を表す集合述語 は、クラスを量化することなく と再定義される。
対に関する公理:
の直積. 任意のクラス に対して、最初の要素が に属する順序対からなるクラス が存在する。
- [23]
巡回置換. 任意のクラス に対して、 の 3-組に巡回置換 を適用して得られる 3-組からなるクラス が存在する。
- [24]
転置. 任意のクラス に対して、 の 3-組の後ろ 2 要素を入れ替えて得られる 3-組からなるクラス が存在する。
- [25]
外延性から、 の直積公理は で表されるただ一つのクラスの存在を含意する。この公理はすべての -組に対してクラス を定義するのにも用いる: そして 。 がクラスならば、外延性は が の -組からなるただ一つのクラスであることを含意する。たとえば、帰属公理から、クラス が順序対ではない元を含むが、共通部分 は の順序対のみからなるようにクラス を構成できる。
巡回置換公理と転置公理はクラス の 3-組であることのみを規定するため、ただ一つのクラスの存在を含意しない。 3-組を規定することで、これらの公理は に対して -組についても規定する。なぜならば:
対に関する公理と領域公理は以下の補題を含意する。この補題はクラス存在定理の証明に用いる。
組の補題 ―
証明 —
- クラス : の直積公理を に適用し、 を得る。
- クラス : 転置公理を に適用し、 を得る。
- クラス : 巡回置換公理を に適用し、 を得る。
- クラス : 巡回置換公理を に適用した上で領域公理を適用し、 を得る。
クラス存在定理の証明にはもう一つの公理、正則性公理が必要である。空クラスの存在が証明されるため、この公理のふつうの言明を用いる。[注釈 6]
正則性公理. 空でないどの集合も、共通部分の要素が空となる元を少なくとも 1 つ持つ。
この公理は集合が自分自身に属さないことを含意する: と仮定して と置く。すると であるので である。これは が の唯一の元であることから、正則性公理と矛盾する。したがって、 である。また、正則性公理は集合の無限降下関係列の存在を禁止する:
ゲーデルは、自身の1940年のモノグラフで、集合ではなくクラスに関して正則性公理を述べた。これは1938年の講義に基づいたものである。[26] 1939年、ゲーデルは集合の正則性公理がクラスの正則性公理を含意することを証明した。[27]クラス存在定理
クラス存在定理 ― を、集合を量化する論理式とする。この論理式は 以外に自由変数をもたないものとする(必ずしも すべてが自由変数でなくてもよい)。すると、すべての に対して、以下を満たす -組のクラス がただ一つ定まる:
クラス
は
で表すことができる。
[注釈 7] この定理の証明は 2 ステップからなる:
- 与えられた論理式 を証明の帰納部分を簡略化する(等価な)(英語版)論理式に変換するため、変換規則を用いる。例えば、帰納部分で 3 ケースの論理記号のみを扱うため、変換後の論理式に用いる論理記号は , , のみとする。
- 変換後の論理式に対して、クラス存在定理を帰納的に証明する。変換後の論理式の構造を用い、クラス存在公理から論理式を満たす唯一の -組を構成する。
変換規則. 以下の規則 1 と 2 において、 と はそれぞれ集合とクラスの変数を表す。これらの 2 つの規則で の前のすべてのクラス変数とすべての等号を除去する。規則 1 や 2 をサブ論理式に適用する際は、 が論理式中の他の変数と異なるように を選ぶ。3 つの規則はサブ論理式に適用できなくなるまで適用を繰り返す。これによって、 , , , 、 集合変数、 の前に現れないクラス変数 論理式のみからなる論理式を構成する。
- を に変換する。
- 外延性公理を用いて、 を に変換する。
- 論理的同一性を用いて、 and が含まれるサブ論理式を のみが含まれるサブ論理式に変換する。
変換規則:束縛変数. 例 1の合成関数論理式について、集合の自由変数を と に置き換えることを考える: 。帰納的証明で論理式 をなす が取り除かれる。しかし、クラス存在定理は添字つき変数を使って表されているため、この論理式は帰納法における仮定として期待される形式にならない。この問題は変数 を で置き換えることで解決できる。ネストされた量化子内の束縛変数を扱うには、量化子ごとに添字の数字を 1 ずつ増やしていけば良い。これによって規則 4 が導出される。規則 1 と 2 で量化された変数が増えるため、規則 4 はほかの規則よりもあとに適用しなければならない。
- 論理式に 以外の自由変数が含まれなければ、 個の量化子内にネストされた束縛変数を に置き換える。これらの変数は (量化子)ネスト深さ である。
例 2: の形のすべての集合からなるクラスを定義する論理式 に規則 4 を適用する。すなわち、少なくとも を含む集合と を含む集合— 例えば、 (ここで は集合である)。 が唯一の自由変数であるため、 である。量化された変数 がネスト深さ 2 の で 2 回現れる。 であるので、この下付き添字は 3 である。2 つの量化子の範囲が同じネスト深さの場合、それらは同一か互いに素である。 の 2 回の出現は量化子の範囲が互いに素であるためで、それゆえ互いに干渉することはない。 |
クラス存在定理の証明. 証明は与えられた論理式に変換規則を適用して、論理式を変換することから始める。この論理式は与えられた論理式と等価であるので、変換済みの論理式を証明すればクラス存在定理の証明が完了する。
変換後の論理式に対するクラス存在定理の証明 — 以下の補題を証明の中で用いる。
拡大の補題 ― と置き、 を、 を満たすすべての順序対 を含むクラスとする。すなわち、 である。すると は を満たす -組の唯一のクラス に拡張することができる。すなわち、 である。
証明:
- のとき、 とする。 のとき、 の前に成分が追加される:組の補題の言明 1 を with に適用する。この操作により、 を満たすすべての -組
を含むクラス が生成される。 - のとき、 とする。 のとき、 と の間に成分が追加される:組の補題の言明 2 を用いて を一つずつ追加する。この操作により、 を満たすすべての -組
を含むクラス が生成される。 - のとき、 とする。 のとき、 のあとに成分が追加される:組の補題の言明 3 を用いて を一つずつ追加する。この操作により、 を満たすすべての -組
を含むクラス が生成される。 - とする。外延性の公理から、 が を満たす -組の唯一のクラスであることが導かれる。
変換後の論理式に対するクラス存在定理 ― を、以下を満たす論理式とする:
- 以外に自由変数を持たない。
- 、 、 、 、 集合変数、クラス変数 のみからなる。ここで は より前には現れない。
- 集合変数 のみを量化する。ここで は変数の、量化子ネスト深さを表す。
すると、すべての に対して、以下を満たす -組のクラス がただ一つ存在する:
証明:基礎ステップ: は論理記号を含まない。定理の仮説は が または の形の原子論理式であることを含意する。
Case 1: が のとき、 を満たす -組の唯一のクラス を構成する。
Case a: が ( )のとき、帰属の公理より、 を満たすすべての順序対 を含むクラス を生成する。拡張の補題を に適用することで、 を得る。
Case b: が ( )のとき、帰属の公理より、 を満たすすべての順序対 を含むクラス を生成する。組の補題の言明 4 を に適用することで、 を満たすすべての順序対 を含むクラス を生成する。拡大の公理を に適用することで、 を得る。
Case c: が ( )のとき、正則性の公理よりこの論理式は偽であるため、これを満たす -組は存在せず、ゆえに である。
Case 2: が のとき、 を満たす -組の唯一のクラス を構成する。
Case a: が ( )のとき、 の直積公理を に適用してクラス を得る。拡大の補題を に適用して を得る。
Case b: が ( )のとき、 の直積公理を に適用してクラス を得る。組の補題の言明 4 を に適用して を得る。拡大の補題を に適用して を得る。
Case c: が ( )のとき、 である。
帰納ステップ: は 個の論理記号を含む。「 未満の個数の論理記号を含むすべての に対して、定理が真である」という、帰納の仮説を仮定する。この条件下で、 個の論理記号を含む に対して、定理が真であることを証明する。この証明において、クラス変数 を で略記する。すると例えば論理式 は のように書ける。
Case 1: のとき、 は 個の論理記号を含むため、帰納仮説は以下を満たす -組のクラス がただ一つ存在することを含意する:
補修号の公理より、
となるクラス
が存在する。しかし、
は
のとき
-組以外の元を含む。