外延性の公理と対の公理の定義
集合は、少なくとも 1 つのクラスに属するクラスである:
∃
C
(
A
∈
C
)
{\displaystyle \exists C(A\in C)}
のとき、かつそのときに限り
A
{\displaystyle A}
は集合である。
集合でないクラスは真のクラスと呼ぶ:
∀
C
(
A
∉
C
)
{\displaystyle \forall C(A\notin C)}
のとき、かつそのときに限り
A
{\displaystyle A}
は真のクラスである。[12]
したがって、どのクラスも集合または真のクラスであり、両方同時に当てはまることはない。
ゲーデルは大文字の変数をクラス上の変数、小文字の変数を集合上の変数とした。[9] また、ゲーデルは、すべての集合からなるクラス上に定義された関数や関係を含む特定のクラスは、大文字から始まる名前で表した。本記事ではゲーデルのこの表記法に従う。すると以下のように書ける:
∃
x
ϕ
(
x
)
{\displaystyle \exists x\,\phi (x)}
、
∃
x
(
∃
C
(
x
∈
C
)
∧
ϕ
(
x
)
)
{\displaystyle \exists x{\bigl (}\exists C(x\in C)\land \phi (x){\bigr )}}
の代わりに。
∀
x
ϕ
(
x
)
{\displaystyle \forall x\,\phi (x)}
、
∀
x
(
∃
C
(
x
∈
C
)
⟹
ϕ
(
x
)
)
{\displaystyle \forall x{\bigl (}\exists C(x\in C)\implies \phi (x){\bigr )}}
の代わりに。
以下の公理と定義はクラス存在定理の証明に必要である。
外延性の公理. 2 つのクラスが同じ元を持っていれば、それらは等しい。
∀
A
∀
B
[
∀
x
(
x
∈
A
⟺
x
∈
B
)
⟹
A
=
B
]
{\displaystyle \forall A\,\forall B\,[\forall x(x\in A\iff x\in B)\implies A=B]}
[13]
この公理はZFCの外延性の公理 をクラスに一般化したものである。
対の公理 .
x
{\displaystyle x}
と
y
{\displaystyle y}
が集合であれば、元が
x
{\displaystyle x}
と
y
{\displaystyle y}
のみである集合
p
{\displaystyle p}
が存在する。
∀
x
∀
y
∃
p
∀
z
[
z
∈
p
⟺
(
z
=
x
∨
z
=
y
)
]
{\displaystyle \forall x\,\forall y\,\exists p\,\forall z\,[z\in p\iff (z=x\,\lor \,z=y)]}
[14]
ZFCのように、外延性の公理は集合
p
{\displaystyle p}
がただ一つであることを含意する。これによって
{
x
,
y
}
{\displaystyle \{x,y\}}
という表記ができる。
順序対 は以下のように定義される。
(
x
,
y
)
=
{
{
x
}
,
{
x
,
y
}
}
{\displaystyle (x,y)=\{\{x\},\{x,y\}\}}
対は順序対を使って再帰的に定義 される:
(
x
1
)
=
x
1
,
{\displaystyle (x_{1})=x_{1},}
For
n
>
1
:
(
x
1
,
…
,
x
n
−
1
,
x
n
)
=
(
(
x
1
,
…
,
x
n
−
1
)
,
x
n
)
.
{\displaystyle {\text{For }}n>1\!:(x_{1},\ldots ,x_{n-1},x_{n})=((x_{1},\ldots ,x_{n-1}),x_{n}).}
[注釈 3]
クラス存在公理と正則性公理
クラス存在公理はクラス存在定理を証明するのに用いる:集合のみを量化する
n
{\displaystyle n}
個の集合の自由変数 に関するすべての論理式について、その論理式を満たす
n
{\displaystyle n}
-組のクラスが存在する。以下の例は、関数 のクラスと合成関数 を構築するクラスの 2 つのクラスから始める。この例はクラス存在定理を証明するのに必要な、クラス存在公理を導出する手法を説明する。
例 1: クラス
F
{\displaystyle F}
と
G
{\displaystyle G}
が関数であるならば、合成関数
G
∘
F
{\displaystyle G\circ F}
は以下の論理式で定義される:
∃
t
[
(
x
,
t
)
∈
F
∧
(
t
,
y
)
∈
G
]
.
{\displaystyle \exists t[(x,t)\in F\,\land \,(t,y)\in G].}
この論理式は 2 つの集合に関する自由変数
x
{\displaystyle x}
と
y
{\displaystyle y}
を持つため、クラス存在定理から以下の順序対のクラスの存在が導かれる:
G
∘
F
=
{
(
x
,
y
)
:
∃
t
[
(
x
,
t
)
∈
F
∧
(
t
,
y
)
∈
G
]
}
.
{\displaystyle G\circ F\,=\,\{(x,y):\exists t[(x,t)\in F\,\land \,(t,y)\in G]\}.}
この論理式は論理積
∧
{\displaystyle \land }
と存在記号
∃
{\displaystyle \exists }
を使って簡潔に構築されているので、簡潔な論理式を表すクラスを使って
∧
{\displaystyle \land }
と
∃
{\displaystyle \exists }
を含む論理式を表すクラスを生成するクラス演算 が必要である。
∧
{\displaystyle \land }
の論理式を表すクラスを作るには、
x
∈
A
∩
B
⟺
x
∈
A
∧
x
∈
B
{\displaystyle x\in A\cap B\iff x\in A\land x\in B}
であることから共通部分 を用いる。
∃
{\displaystyle \exists }
の論理式を表すクラスを作るには、
x
∈
D
o
m
(
A
)
⟺
∃
t
[
(
x
,
t
)
∈
A
]
.
{\displaystyle x\in Dom(A)\iff \exists t[(x,t)\in A].}
であることから領域 を用いる
共通部分を求める前に、
F
{\displaystyle F}
と
G
{\displaystyle G}
にそれぞれ含まれる組において、共通した変数を持つように他の要素が必要になる。元
y
{\displaystyle y}
を
F
{\displaystyle F}
の組に、 元
x
{\displaystyle x}
を
G
{\displaystyle G}
の組に加える:
F
′
=
{
(
x
,
t
,
y
)
:
(
x
,
t
)
∈
F
}
{\displaystyle F'=\{(x,t,y):(x,t)\in F\}\,}
G
′
=
{
(
t
,
y
,
x
)
:
(
t
,
y
)
∈
G
}
{\displaystyle \,G'=\{(t,y,x):(t,y)\in G\}}
F
′
{\displaystyle F'}
の定義において、変数
y
{\displaystyle y}
は
(
x
,
t
)
∈
F
{\displaystyle (x,t)\in F}
で制限されないため、
y
{\displaystyle y}
の定義域はすべての集合のクラス
V
{\displaystyle V}
上になる。同様に、
G
′
{\displaystyle G'}
の定義において、変数
x
{\displaystyle x}
の定義域も
V
{\displaystyle V}
上になる。ここで与えられたクラスの組に(
V
{\displaystyle V}
上の)追加の元を加える公理が必要になる。
次に、共通部分をとる準備として、変数を同じ順序で並べる:
F
″
=
{
(
x
,
y
,
t
)
:
(
x
,
t
)
∈
F
}
{\displaystyle F''=\{(x,y,t):(x,t)\in F\}\,}
G
″
=
{
(
x
,
y
,
t
)
:
(
t
,
y
)
∈
G
}
{\displaystyle \,G''=\{(x,y,t):(t,y)\in G\}}
F
′
{\displaystyle F'}
から
F
″
{\displaystyle F''}
および
G
′
{\displaystyle G'}
から
G
″
{\displaystyle G''}
へは、2 種類の巡回 が必要になる。ゆえに、組の元の巡回を扱う公理が必要になる。
F
″
{\displaystyle F''}
と
G
″
{\displaystyle G''}
の共通部分は
∧
{\displaystyle \land }
で表現される:
F
″
∩
G
″
=
{
(
x
,
y
,
t
)
:
(
x
,
t
)
∈
F
∧
(
t
,
y
)
∈
G
}
{\displaystyle F''\cap G''=\{(x,y,t):(x,t)\in F\,\land \,(t,y)\in G\}}
(
x
,
y
,
t
)
{\displaystyle (x,y,t)}
は
(
(
x
,
y
)
,
t
)
{\displaystyle ((x,y),t)}
として定義されるので、
F
″
∩
G
″
{\displaystyle F''\cap G''}
の領域は
∃
t
{\displaystyle \exists t}
で表現され、合成関数を生成する:
G
∘
F
=
D
o
m
(
F
″
∩
G
″
)
=
{
(
x
,
y
)
:
∃
t
(
(
x
,
t
)
∈
F
∧
(
t
,
y
)
∈
G
)
}
{\displaystyle G\circ F=Dom(F''\cap G'')=\{(x,y):\exists t((x,t)\in F\,\land \,(t,y)\in G)\}}
したがって、共通部分および領域の公理が必要である。
クラス存在公理は 2 つのグループに分かれる:述語に関する公理と、対に関する公理である。前者のグループには 4 つの公理が、後者のグループには 3 つの公理が含まれる。[注釈 4]
述語に関する公理:
帰属. 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]\!}
[18]
共通部分(連言). 任意の 2 つのクラス
A
{\displaystyle A}
と
B
{\displaystyle B}
に対して、
A
{\displaystyle A}
と
B
{\displaystyle B}
にそれぞれ属する集合のみからなるクラス
C
{\displaystyle C}
が存在する。
∀
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)]}
[19]
補集合 (否定). 任意のクラス
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)]}
[20]
領域(存在量化子). 任意のクラス
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)]}
[21]
外延性の公理より、共通部分公理におけるクラス
C
{\displaystyle C}
と補集合公理および領域公理におけるクラス
B
{\displaystyle B}
はそれぞれただ一つ定まる。これらはそれぞれ以下のように表現される:
A
∩
B
,
{\displaystyle A\cap B,}
∁
A
,
{\displaystyle \complement A,}
and
D
o
m
(
A
)
.
{\displaystyle Dom(A).}
[注釈 5] 一方、帰属公理はクラス
E
{\displaystyle E}
上の順序対の集合のみを規定するため、外延性の公理は帰属公理におけるクラス
E
{\displaystyle E}
には適用できない。
最初 3 つの公理は空クラスおよびすべての集合のクラスの存在を含意する:帰属公理はクラス
E
{\displaystyle E}
の存在を含意する。共通部分公理および補集合公理は、空クラスである
E
∩
∁
E
{\displaystyle E\cap \complement E}
の存在を含意する。外延性の公理により、このクラスはただ一つ定まり、これを
∅
{\displaystyle \emptyset }
で表す。
∅
{\displaystyle \emptyset }
の補集合はすべての集合のクラス
V
{\displaystyle V}
であり、これも外延性の公理からただ一つ定まる。すると、
∃
C
(
A
∈
C
)
{\displaystyle \exists C(A\in C)}
を表す集合述語
M
(
A
)
{\displaystyle M(A)}
は、クラスを量化することなく
A
∈
V
{\displaystyle A\in V}
と再定義される。
対に関する公理:
V
{\displaystyle V}
の直積 . 任意のクラス
A
{\displaystyle A}
に対して、最初の要素が
A
{\displaystyle A}
に属する順序対からなるクラス
B
{\displaystyle B}
が存在する。
∀
A
∃
B
∀
u
[
u
∈
B
⟺
∃
x
∃
y
(
u
=
(
x
,
y
)
∧
x
∈
A
)
]
{\displaystyle \forall A\,\exists B\,\forall u\,[u\in B\iff \exists x\,\exists y\,(u=(x,y)\land x\in A)]}
[23]
巡回置換 . 任意のクラス
A
{\displaystyle A}
に対して、
A
{\displaystyle A}
の 3-組に巡回置換
(
y
,
z
,
x
)
↦
(
x
,
y
,
z
)
{\displaystyle (y,z,x)\mapsto (x,y,z)}
を適用して得られる 3-組からなるクラス
B
{\displaystyle B}
が存在する。
∀
A
∃
B
∀
x
∀
y
∀
z
[
(
x
,
y
,
z
)
∈
B
⟺
(
y
,
z
,
x
)
∈
A
]
{\displaystyle \forall A\,\exists B\,\forall x\,\forall y\,\forall z\,[(x,y,z)\in B\iff (y,z,x)\in A]}
[24]
転置 . 任意のクラス
A
{\displaystyle A}
に対して、
A
{\displaystyle A}
の 3-組の後ろ 2 要素を入れ替えて得られる 3-組からなるクラス
B
{\displaystyle B}
が存在する。
∀
A
∃
B
∀
x
∀
y
∀
z
[
(
x
,
y
,
z
)
∈
B
⟺
(
x
,
z
,
y
)
∈
A
]
{\displaystyle \forall A\,\exists B\,\forall x\,\forall y\,\forall z\,[(x,y,z)\in B\iff (x,z,y)\in A]}
[25]
外延性から、
V
{\displaystyle V}
の直積公理は
A
×
V
{\displaystyle A\times V}
で表されるただ一つのクラスの存在を含意する。この公理はすべての
n
{\displaystyle n}
-組に対してクラス
V
n
{\displaystyle V^{n}}
を定義するのにも用いる:
V
1
=
V
{\displaystyle V^{1}=V}
そして
V
n
+
1
=
V
n
×
V
{\displaystyle V^{n+1}=V^{n}\times V}
。
A
{\displaystyle A}
がクラスならば、外延性は
A
∩
V
n
{\displaystyle A\cap V^{n}}
が
A
{\displaystyle A}
の
n
{\displaystyle n}
-組からなるただ一つのクラスであることを含意する。たとえば、帰属公理から、クラス
E
{\displaystyle E}
が順序対ではない元を含むが、共通部分
E
∩
V
2
{\displaystyle E\cap V^{2}}
は
E
{\displaystyle E}
の順序対のみからなるようにクラス
E
{\displaystyle E}
を構成できる。
巡回置換公理と転置公理はクラス
B
{\displaystyle B}
の 3-組であることのみを規定するため、ただ一つのクラスの存在を含意しない。 3-組を規定することで、これらの公理は
n
≥
4
{\displaystyle n\geq 4}
に対して
n
{\displaystyle n}
-組についても規定する。なぜならば:
(
x
1
,
…
,
x
n
−
2
,
x
n
−
1
,
x
n
)
=
(
(
x
1
,
…
,
x
n
−
2
)
,
x
n
−
1
,
x
n
)
.
{\displaystyle (x_{1},\ldots ,x_{n-2},x_{n-1},x_{n})=((x_{1},\ldots ,x_{n-2}),x_{n-1},x_{n}).}
対に関する公理と領域公理は以下の補題を含意する。この補題はクラス存在定理の証明に用いる。
組の補題 ―
∀
A
∃
B
1
∀
x
∀
y
∀
z
[
(
z
,
x
,
y
)
∈
B
1
⟺
(
x
,
y
)
∈
A
]
{\displaystyle \forall A\,\exists B_{1}\,\forall x\,\forall y\,\forall z\,[(z,x,y)\in B_{1}\iff (x,y)\in A]}
∀
A
∃
B
2
∀
x
∀
y
∀
z
[
(
x
,
z
,
y
)
∈
B
2
⟺
(
x
,
y
)
∈
A
]
{\displaystyle \forall A\,\exists B_{2}\,\forall x\,\forall y\,\forall z\,[(x,z,y)\in B_{2}\iff (x,y)\in A]}
∀
A
∃
B
3
∀
x
∀
y
∀
z
[
(
x
,
y
,
z
)
∈
B
3
⟺
(
x
,
y
)
∈
A
]
{\displaystyle \forall A\,\exists B_{3}\,\forall x\,\forall y\,\forall z\,[(x,y,z)\in B_{3}\iff (x,y)\in A]}
∀
A
∃
B
4
∀
x
∀
y
∀
z
[
(
y
,
x
)
∈
B
4
⟺
(
x
,
y
)
∈
A
]
{\displaystyle \forall A\,\exists B_{4}\,\forall x\,\forall y\,\forall z\,[(y,x)\in B_{4}\iff (x,y)\in A]}
クラス存在定理の証明にはもう一つの公理、正則性公理 が必要である。空クラスの存在が証明されるため、この公理のふつうの言明を用いる。[注釈 6]
正則性公理 . 空でないどの集合も、共通部分の要素が空となる元を少なくとも 1 つ持つ。
∀
a
[
a
≠
∅
⟹
∃
u
(
u
∈
a
∧
u
∩
a
=
∅
)
]
.
{\displaystyle \forall a\,[a\neq \emptyset \implies \exists u(u\in a\land u\cap a=\emptyset )].}
この公理は集合が自分自身に属さないことを含意する:
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}
である。また、正則性公理は集合の無限降下関係列の存在を禁止する:
⋯
∈
x
n
+
1
∈
x
n
∈
⋯
∈
x
1
∈
x
0
.
{\displaystyle \cdots \in x_{n+1}\in x_{n}\in \cdots \in x_{1}\in x_{0}.}
ゲーデルは、自身の1940年のモノグラフで、集合ではなくクラスに関して正則性公理を述べた。これは1938年の講義に基づいたものである。[26] 1939年、ゲーデルは集合の正則性公理がクラスの正則性公理を含意することを証明した。[27]
クラス存在定理
クラス存在定理 ―
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
{\displaystyle \phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})}
を、集合を量化する論理式とする。この論理式は
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
{\displaystyle x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m}}
以外に自由変数 をもたないものとする(必ずしも
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
{\displaystyle x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m}}
すべてが自由変数でなくてもよい)。すると、すべての
Y
1
,
…
,
Y
m
{\displaystyle Y_{1},\dots ,Y_{m}}
に対して、以下を満たす
n
{\displaystyle n}
-組のクラス
A
{\displaystyle A}
がただ一つ定まる:
∀
x
1
⋯
∀
x
n
[
(
x
1
,
…
,
x
n
)
∈
A
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
]
.
{\displaystyle \forall x_{1}\cdots \,\forall x_{n}[(x_{1},\dots ,x_{n})\in A\iff \phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})].}
クラス
A
{\displaystyle A}
は
{
(
x
1
,
…
,
x
n
)
:
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
}
{\displaystyle \{(x_{1},\dots ,x_{n}):\phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})\}}
で表すことができる。[注釈 7]
この定理の証明は 2 ステップからなる:
与えられた論理式
ϕ
{\displaystyle \phi }
を証明の帰納 部分を簡略化する等価な (英語版 ) 論理式に変換するため、変換規則を用いる。例えば、帰納部分で 3 ケースの論理記号のみを扱うため、変換後の論理式に用いる論理記号は
¬
{\displaystyle \neg }
,
∧
{\displaystyle \land }
,
∃
{\displaystyle \exists }
のみとする。
変換後の論理式に対して、クラス存在定理を帰納的に証明する。変換後の論理式の構造を用い、クラス存在公理から論理式を満たす唯一の
n
{\displaystyle n}
-組を構成する。
変換規則. 以下の規則 1 と 2 において、
Δ
{\displaystyle \Delta }
と
Γ
{\displaystyle \Gamma }
はそれぞれ集合とクラスの変数を表す。これらの 2 つの規則で
∈
{\displaystyle \in }
の前のすべてのクラス変数とすべての等号を除去する。規則 1 や 2 をサブ論理式に適用する際は、
z
i
{\displaystyle z_{i}}
が論理式中の他の変数と異なるように
i
{\displaystyle i}
を選ぶ。3 つの規則はサブ論理式に適用できなくなるまで適用を繰り返す。これによって、
¬
{\displaystyle \neg }
,
∧
{\displaystyle \land }
,
∃
{\displaystyle \exists }
,
∈
{\displaystyle \in }
、 集合変数、
∈
{\displaystyle \in }
の前に現れないクラス変数
Y
k
{\displaystyle Y_{k}}
論理式のみからなる論理式を構成する。
Y
k
∈
Γ
{\displaystyle \,Y_{k}\in \Gamma }
を
∃
z
i
(
z
i
=
Y
k
∧
z
i
∈
Γ
)
{\displaystyle \exists z_{i}(z_{i}=Y_{k}\,\land \,z_{i}\in \Gamma )}
に変換する。
外延性公理を用いて、
Δ
=
Γ
{\displaystyle \Delta =\Gamma }
を
∀
z
i
(
z
i
∈
Δ
⟺
z
i
∈
Γ
)
{\displaystyle \forall z_{i}(z_{i}\in \Delta \iff z_{i}\in \Gamma )}
に変換する。
論理的同一性を用いて、
∨
,
⟹
,
⟺
,
{\displaystyle \lor ,\implies ,\iff ,}
and
∀
{\displaystyle \forall }
が含まれるサブ論理式を
¬
,
∧
,
∃
{\displaystyle \neg ,\land ,\exists }
のみが含まれるサブ論理式に変換する。
変換規則:束縛変数 . 例 1の合成関数論理式について、集合の自由変数を
x
1
{\displaystyle x_{1}}
と
x
2
{\displaystyle x_{2}}
に置き換えることを考える:
∃
t
[
(
x
1
,
t
)
∈
F
∧
(
t
,
x
2
)
∈
G
]
{\displaystyle \exists t[(x_{1},t)\in F\,\land \,(t,x_{2})\in G]}
。帰納的証明で論理式
(
x
1
,
t
)
∈
F
∧
(
t
,
x
2
)
∈
G
{\displaystyle (x_{1},t)\in F\land (t,x_{2})\in G}
をなす
∃
t
{\displaystyle \exists t}
が取り除かれる。しかし、クラス存在定理は添字つき変数を使って表されているため、この論理式は帰納法における仮定 として期待される形式にならない。この問題は変数
t
{\displaystyle t}
を
x
3
{\displaystyle x_{3}}
で置き換えることで解決できる。ネストされた量化子内の束縛変数を扱うには、量化子ごとに添字の数字を 1 ずつ増やしていけば良い。これによって規則 4 が導出される。規則 1 と 2 で量化された変数が増えるため、規則 4 はほかの規則よりもあとに適用しなければならない。
論理式に
x
1
,
…
,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
以外の自由変数が含まれなければ、
q
{\displaystyle q}
個の量化子内にネストされた束縛変数を
x
n
+
q
{\displaystyle x_{n+q}}
に置き換える。これらの変数は (量化子)ネスト深さ
q
{\displaystyle q}
である。
例 2:
{
∅
,
{
∅
,
…
}
,
…
}
{\displaystyle \{\emptyset ,\{\emptyset ,\dots \},\dots \}}
の形のすべての集合からなるクラスを定義する論理式
ϕ
(
x
1
)
{\displaystyle \phi (x_{1})}
に規則 4 を適用する。すなわち、少なくとも
∅
{\displaystyle \emptyset }
を含む集合と
∅
{\displaystyle \emptyset }
を含む集合— 例えば、
{
∅
,
{
∅
,
a
,
b
,
c
}
,
d
,
e
}
{\displaystyle \{\emptyset ,\{\emptyset ,a,b,c\},d,e\}}
(ここで
a
,
b
,
c
,
d
,
e
{\displaystyle a,b,c,d,e}
は集合である)。
ϕ
(
x
1
)
=
∃
u
[
u
∈
x
1
∧
¬
∃
v
(
v
∈
u
)
]
∧
∃
w
(
w
∈
x
1
∧
∃
y
[
(
y
∈
w
∧
¬
∃
z
(
z
∈
y
)
]
)
ϕ
r
(
x
1
)
=
∃
x
2
[
x
2
∈
x
1
∧
¬
∃
x
3
(
x
3
∈
x
2
)
]
∧
∃
x
2
(
x
2
∈
x
1
∧
∃
x
3
[
(
x
3
∈
x
2
∧
¬
∃
x
4
(
x
4
∈
x
3
)
]
)
{\displaystyle {\begin{aligned}\phi (x_{1})\,&=\,\exists u\;\,[\,u\in x_{1}\,\land \,\neg \exists v\;\,(\;v\,\in \,u\,)]\,\land \,\,\exists w\;{\bigl (}w\in x_{1}\,\land \,\exists y\;\,[(\;y\,\in w\;\land \;\neg \exists z\;\,(\;z\,\in \,y\,)]{\bigr )}\\\phi _{r}(x_{1})\,&=\,\exists x_{2}[x_{2}\!\in \!x_{1}\,\land \,\neg \exists x_{3}(x_{3}\!\in \!x_{2})]\,\land \,\,\exists x_{2}{\bigl (}x_{2}\!\in \!x_{1}\,\land \,\exists x_{3}[(x_{3}\!\in \!x_{2}\,\land \,\neg \exists x_{4}(x_{4}\!\in \!x_{3})]{\bigr )}\end{aligned}}}
x
1
{\displaystyle x_{1}}
が唯一の自由変数であるため、
n
=
1
{\displaystyle n=1}
である。量化された変数
x
3
{\displaystyle x_{3}}
がネスト深さ 2 の
x
3
∈
x
2
{\displaystyle x_{3}\in x_{2}}
で 2 回現れる。
n
+
q
=
1
+
2
=
3
{\displaystyle n+q=1+2=3}
であるので、この下付き添字は 3 である。2 つの量化子の範囲が同じネスト深さの場合、それらは同一か互いに素である。
x
3
{\displaystyle x_{3}}
の 2 回の出現は量化子の範囲が互いに素であるためで、それゆえ互いに干渉することはない。
クラス存在定理の証明. 証明は与えられた論理式に変換規則を適用して、論理式を変換することから始める。この論理式は与えられた論理式と等価であるので、変換済みの論理式を証明すればクラス存在定理の証明が完了する。
変換後の論理式に対するクラス存在定理の証明 —
以下の補題を証明の中で用いる。
拡大の補題 ―
1
≤
i
<
j
≤
n
{\displaystyle 1\leq i<j\leq n}
と置き、
P
{\displaystyle P}
を、
R
(
x
i
,
x
j
)
.
{\displaystyle R(x_{i},x_{j}).}
を満たすすべての順序対
(
x
i
,
x
j
)
{\displaystyle (x_{i},x_{j})}
を含むクラスとする。すなわち、
P
⊇
{
(
x
i
,
x
j
)
:
R
(
x
i
,
x
j
)
}
{\displaystyle P\supseteq \{(x_{i},x_{j}):R(x_{i},x_{j})\}}
である。すると
P
{\displaystyle P}
は
R
(
x
i
,
x
j
)
{\displaystyle R(x_{i},x_{j})}
を満たす
n
{\displaystyle n}
-組の唯一のクラス
Q
{\displaystyle Q}
に拡張することができる。すなわち、
Q
=
{
(
x
1
,
…
,
x
n
)
:
R
(
x
i
,
x
j
)
}
{\displaystyle Q=\{(x_{1},\ldots ,x_{n}):R(x_{i},x_{j})\}}
である。
証明:
i
=
1
{\displaystyle i=1}
のとき、
P
1
=
P
{\displaystyle P_{1}=P}
とする。
i
>
1
{\displaystyle i>1}
のとき、
x
i
{\displaystyle x_{i}}
の前に成分が追加される:組の補題 の言明 1 を
P
{\displaystyle P}
with
z
=
(
x
1
,
…
,
x
i
−
1
)
{\displaystyle z=(x_{1},\dots ,x_{i-1})}
に適用する。この操作により、
R
(
x
i
,
x
j
)
{\displaystyle R(x_{i},x_{j})}
を満たすすべての
(
i
+
1
)
{\displaystyle (i+1)}
-組
(
(
x
1
,
…
,
x
i
−
1
)
,
x
i
,
x
j
)
=
(
x
1
,
…
,
x
i
−
1
,
x
i
,
x
j
)
{\displaystyle ((x_{1},\dots ,x_{i-1}),x_{i},x_{j})=(x_{1},\dots ,x_{i-1},x_{i},x_{j})}
を含むクラス
P
1
{\displaystyle P_{1}}
が生成される。
j
=
i
+
1
{\displaystyle j=i+1}
のとき、
P
2
=
P
1
{\displaystyle P_{2}=P_{1}}
とする。
j
>
i
+
1
{\displaystyle j>i+1}
のとき、
x
i
{\displaystyle x_{i}}
と
x
j
{\displaystyle x_{j}}
の間に成分が追加される:組の補題の言明 2 を用いて
x
i
+
1
,
…
,
x
j
−
1
{\displaystyle x_{i+1},\dots ,x_{j-1}}
を一つずつ追加する。この操作により、
R
(
x
i
,
x
j
)
.
{\displaystyle R(x_{i},x_{j}).}
を満たすすべての
j
{\displaystyle j}
-組
(
(
(
⋯
(
(
x
1
,
…
,
x
i
)
,
x
i
+
1
)
,
⋯
)
,
x
j
−
1
)
,
x
j
)
=
(
x
1
,
…
,
x
j
)
{\displaystyle (((\cdots ((x_{1},\dots ,x_{i}),x_{i+1}),\cdots ),x_{j-1}),x_{j})=(x_{1},\dots ,x_{j})}
を含むクラス
P
2
{\displaystyle P_{2}}
が生成される。
j
=
n
{\displaystyle j=n}
のとき、
P
3
=
P
2
{\displaystyle P_{3}=P_{2}}
とする。
j
<
n
{\displaystyle j<n}
のとき、
x
j
{\displaystyle x_{j}}
のあとに成分が追加される:組の補題の言明 3 を用いて
x
j
+
1
,
…
,
x
n
{\displaystyle x_{j+1},\dots ,x_{n}}
を一つずつ追加する。この操作により、
R
(
x
i
,
x
j
)
.
{\displaystyle R(x_{i},x_{j}).}
を満たすすべての
n
{\displaystyle n}
-組
(
(
⋯
(
(
x
1
,
…
,
x
j
)
,
x
j
+
1
)
,
⋯
)
,
x
n
)
=
(
x
1
,
…
,
x
n
)
{\displaystyle ((\cdots ((x_{1},\dots ,x_{j}),x_{j+1}),\cdots ),x_{n})=(x_{1},\dots ,x_{n})}
を含むクラス
P
3
{\displaystyle P_{3}}
が生成される。
Q
=
P
3
∩
V
n
{\displaystyle Q=P_{3}\cap V^{n}}
とする。外延性の公理から、
Q
{\displaystyle Q}
が
R
(
x
i
,
x
j
)
.
{\displaystyle R(x_{i},x_{j}).}
を満たす
n
{\displaystyle n}
-組の唯一のクラスであることが導かれる。
変換後の論理式に対するクラス存在定理 ―
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
{\displaystyle \phi (x_{1},\ldots ,x_{n},Y_{1},\ldots ,Y_{m})}
を、以下を満たす論理式とする:
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
{\displaystyle x_{1},\ldots ,x_{n},Y_{1},\ldots ,Y_{m}}
以外に自由変数を持たない。
∈
{\displaystyle \in }
、
¬
{\displaystyle \neg }
、
∧
{\displaystyle \land }
、
∃
{\displaystyle \exists }
、 集合変数、クラス変数
Y
k
{\displaystyle Y_{k}}
のみからなる。ここで
Y
k
{\displaystyle Y_{k}}
は
∈
{\displaystyle \in }
より前には現れない。
集合変数
x
n
+
q
{\displaystyle x_{n+q}}
のみを量化する。ここで
q
{\displaystyle q}
は変数の、量化子ネスト深さを表す。
すると、すべての
Y
1
,
…
,
Y
m
{\displaystyle Y_{1},\dots ,Y_{m}}
に対して、以下を満たす
n
{\displaystyle n}
-組のクラス
A
{\displaystyle A}
がただ一つ存在する:
∀
x
1
⋯
∀
x
n
[
(
x
1
,
…
,
x
n
)
∈
A
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
]
.
{\displaystyle \forall x_{1}\cdots \,\forall x_{n}[(x_{1},\ldots ,x_{n})\in A\iff \phi (x_{1},\ldots ,x_{n},Y_{1},\ldots ,Y_{m})].}
証明:基礎ステップ:
ϕ
{\displaystyle \phi }
は論理記号を含まない。定理の仮説は
ϕ
{\displaystyle \phi }
が
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
または
x
i
∈
Y
k
{\displaystyle x_{i}\in Y_{k}}
の形の原子論理式であることを含意する。
Case 1:
ϕ
{\displaystyle \phi }
が
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
のとき、
x
i
∈
x
j
.
{\displaystyle x_{i}\in x_{j}.}
を満たす
n
{\displaystyle n}
-組の唯一のクラス
E
i
,
j
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
x
j
}
{\displaystyle E_{i,j,n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in x_{j}\}}
を構成する。
Case a:
ϕ
{\displaystyle \phi }
が
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
(
i
<
j
{\displaystyle i<j}
)のとき、帰属の公理より、
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
を満たすすべての順序対
(
x
i
,
x
j
)
{\displaystyle (x_{i},x_{j})}
を含むクラス
P
{\displaystyle P}
を生成する。拡張の補題を
P
{\displaystyle P}
に適用することで、
E
i
,
j
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
x
j
}
{\displaystyle E_{i,j,n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in x_{j}\}}
を得る。
Case b:
ϕ
{\displaystyle \phi }
が
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
(
i
>
j
{\displaystyle i>j}
)のとき、帰属の公理より、
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
を満たすすべての順序対
(
x
i
,
x
j
)
{\displaystyle (x_{i},x_{j})}
を含むクラス
P
{\displaystyle P}
を生成する。組の補題の言明 4 を
P
{\displaystyle P}
に適用することで、
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
を満たすすべての順序対
(
x
j
,
x
i
)
{\displaystyle (x_{j},x_{i})}
を含むクラス
P
′
{\displaystyle P'}
を生成する。拡大の公理を
P
′
{\displaystyle P'}
に適用することで、
E
i
,
j
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
x
j
}
{\displaystyle E_{i,j,n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in x_{j}\}}
を得る。
Case c:
ϕ
{\displaystyle \phi }
が
x
i
∈
x
j
{\displaystyle x_{i}\in x_{j}}
(
i
=
j
{\displaystyle i=j}
)のとき、正則性の公理 よりこの論理式は偽であるため、これを満たす
n
{\displaystyle n}
-組は存在せず、ゆえに
E
i
,
j
,
n
=
∅
{\displaystyle E_{i,j,n}=\emptyset }
である。
Case 2:
ϕ
{\displaystyle \phi }
が
x
i
∈
Y
k
{\displaystyle x_{i}\in Y_{k}}
のとき、
x
i
∈
Y
k
.
{\displaystyle x_{i}\in Y_{k}.}
を満たす
n
{\displaystyle n}
-組の唯一のクラス
E
i
,
Y
k
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
Y
k
}
{\displaystyle E_{i,Y_{k},n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in Y_{k}\}}
を構成する。
Case a:
ϕ
{\displaystyle \phi }
が
x
i
∈
Y
k
{\displaystyle x_{i}\in Y_{k}}
(
i
<
n
{\displaystyle i<n}
)のとき、
V
{\displaystyle V}
の直積公理を
Y
k
{\displaystyle Y_{k}}
に適用してクラス
P
=
Y
k
×
V
=
{
(
x
i
,
x
i
+
1
)
:
x
i
∈
Y
k
}
{\displaystyle P=Y_{k}\times V=\{(x_{i},x_{i+1}):x_{i}\in Y_{k}\}}
を得る。拡大の補題を
P
{\displaystyle P}
に適用して
E
i
,
Y
k
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
Y
k
}
{\displaystyle E_{i,Y_{k},n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in Y_{k}\}}
を得る。
Case b:
ϕ
{\displaystyle \phi }
が
x
i
∈
Y
k
{\displaystyle x_{i}\in Y_{k}}
(
i
=
n
>
1
{\displaystyle i=n>1}
)のとき、
V
{\displaystyle V}
の直積公理を
Y
k
{\displaystyle Y_{k}}
に適用してクラス
P
=
Y
k
×
V
=
{
(
x
i
,
x
i
−
1
)
:
x
i
∈
Y
k
}
{\displaystyle P=Y_{k}\times V=\{(x_{i},x_{i-1}):x_{i}\in Y_{k}\}}
を得る。組の補題の言明 4 を
P
{\displaystyle P}
に適用して
P
′
=
V
×
Y
k
=
{
(
x
i
−
1
,
x
i
)
:
x
i
∈
Y
k
}
{\displaystyle P'=V\times Y_{k}=\{(x_{i-1},x_{i}):x_{i}\in Y_{k}\}}
を得る。拡大の補題を
P
′
{\displaystyle P'}
に適用して
E
i
,
Y
k
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
Y
k
}
{\displaystyle E_{i,Y_{k},n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in Y_{k}\}}
を得る。
Case c:
ϕ
{\displaystyle \phi }
が
x
i
∈
Y
k
{\displaystyle x_{i}\in Y_{k}}
(
i
=
n
=
1
{\displaystyle i=n=1}
)のとき、
E
i
,
Y
k
,
n
=
Y
k
{\displaystyle E_{i,Y_{k},n}=Y_{k}}
である。
帰納ステップ:
ϕ
{\displaystyle \phi }
は
k
(
>
0
)
{\displaystyle k(>0)}
個の論理記号を含む。「
k
{\displaystyle k}
未満の個数の論理記号を含むすべての
ψ
{\displaystyle \psi }
に対して、定理が真である」という、帰納の仮説を仮定する。この条件下で、
k
{\displaystyle k}
個の論理記号を含む
ϕ
{\displaystyle \phi }
に対して、定理が真であることを証明する。この証明において、クラス変数
Y
1
,
…
,
Y
m
{\displaystyle Y_{1},\dots ,Y_{m}}
を
Y
→
{\displaystyle {\vec {Y}}}
で略記する。すると例えば論理式
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
{\displaystyle \phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})}
は
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
{\displaystyle \phi (x_{1},\dots ,x_{n},{\vec {Y}})}
のように書ける。
Case 1:
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
=
¬
ψ
(
x
1
,
…
,
x
n
,
Y
→
)
{\displaystyle \phi (x_{1},\ldots ,x_{n},{\vec {Y}})=\neg \psi (x_{1},\ldots ,x_{n},{\vec {Y}})}
のとき、
ψ
{\displaystyle \psi }
は
k
−
1
{\displaystyle k-1}
個の論理記号を含むため、帰納仮説は以下を満たす
n
{\displaystyle n}
-組のクラス
A
{\displaystyle A}
がただ一つ存在することを含意する:
(
x
1
,
…
,
x
n
)
∈
A
⟺
ψ
(
x
1
,
…
,
x
n
,
Y
→
)
.
{\displaystyle \quad (x_{1},\ldots ,x_{n})\in A\iff \psi (x_{1},\ldots ,x_{n},{\vec {Y}}).}
補修号の公理より、
∀
u
[
u
∈
∁
A
⟺
¬
(
u
∈
A
)
]
{\displaystyle \forall u\,[u\in \complement A\iff \neg (u\in A)]}
となるクラス
∁
A
{\displaystyle \complement A}
が存在する。しかし、
∁
A
{\displaystyle \complement A}
は
n
>
1
{\displaystyle n>1}
のとき
n
{\displaystyle n}
-組以外の元を含む。
∁
V
n
A
=
{\displaystyle \complement _{V^{n}}A=\,}
∁
A
∩
V
n
=
{\displaystyle \complement A\cap V^{n}=\,}
V
n
∖
A
{\displaystyle V^{n}\setminus A}
を用いて、この元を消去する。これはすべての
n
{\displaystyle n}
-組のクラス
V
n
{\displaystyle V^{n}}
の相対補集合である[注釈 5] 。すると、外延性の公理から
∁
V
n
A
{\displaystyle \complement _{V^{n}}A}
は以下を満たす
n
{\displaystyle n}
-組の唯一のクラスである:
(
x
1
,
…
,
x
n
)
∈
∁
V
n
A
⟺
¬
[
(
x
1
,
…
,
x
n
)
∈
A
]
⟺
¬
ψ
(
x
1
,
…
,
x
n
,
Y
→
)
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
.
{\displaystyle {\begin{alignedat}{2}\quad &(x_{1},\ldots ,x_{n})\in \complement _{V^{n}}A&&\iff \neg [(x_{1},\ldots ,x_{n})\in A]\\&&&\iff \neg \psi (x_{1},\ldots ,x_{n},{\vec {Y}})\\&&&\iff \phi (x_{1},\ldots ,x_{n},{\vec {Y}}).\end{alignedat}}}
Case 2:
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
=
ψ
1
(
x
1
,
…
,
x
n
,
Y
→
)
∧
ψ
2
(
x
1
,
…
,
x
n
,
Y
→
)
{\displaystyle \phi (x_{1},\ldots ,x_{n},{\vec {Y}})=\psi _{1}(x_{1},\ldots ,x_{n},{\vec {Y}})\land \psi _{2}(x_{1},\ldots ,x_{n},{\vec {Y}})}
のとき、
ψ
1
{\displaystyle \psi _{1}}
と
ψ
2
{\displaystyle \psi _{2}}
はいずれも
k
{\displaystyle k}
未満の個数の論理記号を含むため、帰納仮説は以下を満たす
n
{\displaystyle n}
-組のクラス
A
{\displaystyle A}
がただ一つ存在することを含意する:
(
x
1
,
…
,
x
n
)
∈
A
1
⟺
ψ
1
(
x
1
,
…
,
x
n
,
Y
→
)
.
(
x
1
,
…
,
x
n
)
∈
A
2
⟺
ψ
2
(
x
1
,
…
,
x
n
,
Y
→
)
.
{\displaystyle {\begin{aligned}\quad &(x_{1},\ldots ,x_{n})\in A_{1}\iff \psi _{1}(x_{1},\ldots ,x_{n},{\vec {Y}}).\\&(x_{1},\ldots ,x_{n})\in A_{2}\iff \psi _{2}(x_{1},\ldots ,x_{n},{\vec {Y}}).\end{aligned}}}
共通部分および外延性の公理から、
A
1
∩
A
2
{\displaystyle A_{1}\cap A_{2}}
は以下を満たす
n
{\displaystyle n}
-組の唯一のクラスである:
(
x
1
,
…
,
x
n
)
∈
A
1
∩
A
2
⟺
(
x
1
,
…
,
x
n
)
∈
A
1
∧
(
x
1
,
…
,
x
n
)
∈
A
2
⟺
ψ
1
(
x
1
,
…
,
x
n
,
Y
→
)
∧
ψ
2
(
x
1
,
…
,
x
n
,
Y
→
)
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
.
{\displaystyle {\begin{alignedat}{2}\quad &(x_{1},\ldots ,x_{n})\in A_{1}\cap A_{2}&&\iff (x_{1},\ldots ,x_{n})\in A_{1}\land (x_{1},\ldots ,x_{n})\in A_{2}\\&&&\iff \psi _{1}(x_{1},\ldots ,x_{n},{\vec {Y}})\land \psi _{2}(x_{1},\ldots ,x_{n},{\vec {Y}})\\&&&\iff \phi (x_{1},\ldots ,x_{n},{\vec {Y}}).\end{alignedat}}}
Case 3:
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
=
∃
x
n
+
1
ψ
(
x
1
,
…
,
x
n
,
x
n
+
1
,
Y
→
)
{\displaystyle \phi (x_{1},\ldots ,x_{n},{\vec {Y}})=\exists x_{n+1}\psi (x_{1},\ldots ,x_{n},x_{n+1},{\vec {Y}})}
のとき、
ψ
{\displaystyle \psi }
は
ϕ
{\displaystyle \phi }
と比べると、量化子ネスト深さが 1 大きく、自由変数
x
n
+
1
{\displaystyle x_{n+1}}
が多い。
ψ
{\displaystyle \psi }
は
k
−
1
{\displaystyle k-1}
個の論理記号を含むため、、帰納仮説は以下を満たす
n
{\displaystyle n}
-組のクラス
A
{\displaystyle A}
がただ一つ存在することを含意する:
(
x
1
,
…
,
x
n
,
x
n
+
1
)
∈
A
⟺
ψ
(
x
1
,
…
,
x
n
,
x
n
+
1
,
Y
→
)
.
{\displaystyle \quad (x_{1},\ldots ,x_{n},x_{n+1})\in A\iff \psi (x_{1},\ldots ,x_{n},x_{n+1},{\vec {Y}}).}
領域および外延性の公理から、
D
o
m
(
A
)
{\displaystyle Dom(A)}
は以下を満たす
n
{\displaystyle n}
-組の唯一のクラスである:[注釈 8]
(
x
1
,
…
,
x
n
)
∈
D
o
m
(
A
)
⟺
∃
x
n
+
1
[
(
(
x
1
,
…
,
x
n
)
,
x
n
+
1
)
∈
A
]
⟺
∃
x
n
+
1
[
(
x
1
,
…
,
x
n
,
x
n
+
1
)
∈
A
]
⟺
∃
x
n
+
1
ψ
(
x
1
,
…
,
x
n
,
x
n
+
1
,
Y
→
)
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
→
)
.
{\displaystyle {\begin{alignedat}{2}\quad &(x_{1},\ldots ,x_{n})\in Dom(A)&&\iff \exists x_{n+1}[((x_{1},\ldots ,x_{n}),x_{n+1})\in A]\\&&&\iff \exists x_{n+1}[(x_{1},\ldots ,x_{n},x_{n+1})\in A]\\&&&\iff \exists x_{n+1}\,\psi (x_{1},\ldots ,x_{n},x_{n+1},{\vec {Y}})\\&&&\iff \phi (x_{1},\ldots ,x_{n},{\vec {Y}}).\end{alignedat}}}
ゲーデルは、クラス存在定理は「メタ定理 (英語版 ) である。すなわち、システム(NBG)に関する定理であり、システム内の定理でではない…」と指摘した。 [30] NBG 論理式の帰納によるメタ理論 の中で証明されるため、クラス存在定理は NBG に関する定理である。また、その証明は、有限個の NBG 公理を持ち出す代わりに、与えられた論理式を満たすクラスを構築するためのNBG 公理の使い方を帰納的に表現する。すべての論理式に対して、こうした表現は NBG 内の存在の構成的証明に変えられる。したがって、このメタ理論で NBG のクラス存在定理の使い方を置き換えた NBG の証明を作ることができる。
再帰 的なコンピュータプログラム で、与えられた論理式からクラスを簡単に構成することができる。このプログラムの定義はクラス存在定理の証明によらない。しかし、プログラムによって構成されるクラスが与えられた論理式を満たし、公理から構成されたかを確認するには、定理の証明が必要である。このプログラムのPascal 形式のcase文 を用いた擬似コード を以下に示す。[注釈 9]
f
u
n
c
t
i
o
n
Class
(
ϕ
,
n
)
i
n
p
u
t
:
ϕ
is a transformed formula of the form
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
;
n
specifies that a class of
n
-tuples is returned.
o
u
t
p
u
t
:
class
A
of
n
-tuples satisfying
∀
x
1
⋯
∀
x
n
[
(
x
1
,
…
,
x
n
)
∈
A
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
]
.
b
e
g
i
n
c
a
s
e
ϕ
o
f
x
i
∈
x
j
:
r
e
t
u
r
n
E
i
,
j
,
n
;
//
E
i
,
j
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
x
j
}
x
i
∈
Y
k
:
r
e
t
u
r
n
E
i
,
Y
k
,
n
;
//
E
i
,
Y
k
,
n
=
{
(
x
1
,
…
,
x
n
)
:
x
i
∈
Y
k
}
¬
ψ
:
r
e
t
u
r
n
∁
V
n
Class
(
ψ
,
n
)
;
//
∁
V
n
Class
(
ψ
,
n
)
=
V
n
∖
Class
(
ψ
,
n
)
ψ
1
∧
ψ
2
:
r
e
t
u
r
n
Class
(
ψ
1
,
n
)
∩
Class
(
ψ
2
,
n
)
;
∃
x
n
+
1
(
ψ
)
:
r
e
t
u
r
n
D
o
m
(
Class
(
ψ
,
n
+
1
)
)
;
//
x
n
+
1
is free in
ψ
;
Class
(
ψ
,
n
+
1
)
// returns a class of
(
n
+
1
)
-tuples
e
n
d
e
n
d
{\displaystyle {\begin{array}{l}\mathbf {function} \;{\text{Class}}(\phi ,\,n)\\\quad {\begin{array}{rl}\mathbf {input} \!:\;\,&\phi {\text{ is a transformed formula of the form }}\phi (x_{1},\ldots ,x_{n},Y_{1},\ldots ,Y_{m});\\&n{\text{ specifies that a class of }}n{\text{-tuples is returned.}}\\\;\;\;\;\mathbf {output} \!:\;\,&{\text{class }}A{\text{ of }}n{\text{-tuples satisfying }}\\&\,\forall x_{1}\cdots \,\forall x_{n}[(x_{1},\ldots ,x_{n})\in A\iff \phi (x_{1},\ldots ,x_{n},Y_{1},\ldots ,Y_{m})].\end{array}}\\\mathbf {begin} \\\quad \mathbf {case} \;\phi \;\mathbf {of} \\\qquad {\begin{alignedat}{2}x_{i}\in x_{j}:\;\;&\mathbf {return} \;\,E_{i,j,n};&&{\text{// }}E_{i,j,n}\;\,=\{(x_{1},\dots ,x_{n}):x_{i}\in x_{j}\}\\x_{i}\in Y_{k}:\;\;&\mathbf {return} \;\,E_{i,Y_{k},n};&&{\text{// }}E_{i,Y_{k},n}=\{(x_{1},\dots ,x_{n}):x_{i}\in Y_{k}\}\\\neg \psi :\;\;&\mathbf {return} \;\,\complement _{V^{n}}{\text{Class}}(\psi ,\,n);&&{\text{// }}\complement _{V^{n}}{\text{Class}}(\psi ,\,n)=V^{n}\setminus {\text{Class}}(\psi ,\,n)\\\psi _{1}\land \psi _{2}:\;\;&\mathbf {return} \;\,{\text{Class}}(\psi _{1},\,n)\cap {\text{Class}}(\psi _{2},\,n);&&\\\;\;\;\;\,\exists x_{n+1}(\psi ):\;\;&\mathbf {return} \;\,Dom({\text{Class}}(\psi ,\,n+1));&&{\text{// }}x_{n+1}{\text{ is free in }}\psi ;{\text{ Class}}(\psi ,\,n+1)\\&\ &&{\text{// returns a class of }}(n+1){\text{-tuples}}\end{alignedat}}\\\quad \mathbf {end} \\\mathbf {end} \end{array}}}
ϕ
{\displaystyle \phi }
を 例 2 の論理式とする。関数呼び出し
A
=
C
l
a
s
s
(
ϕ
,
1
)
{\displaystyle A=Class(\phi ,1)}
でクラス
A
{\displaystyle A}
を作成するが、以下で
ϕ
{\displaystyle \phi }
と比較する。クラス
A
{\displaystyle A}
の構成は、それを定義する論理式
ϕ
{\displaystyle \phi }
の構成を反転することがわかる。
ϕ
=
∃
x
2
(
x
2
∈
x
1
∧
¬
∃
x
3
(
x
3
∈
x
2
)
)
∧
∃
x
2
(
x
2
∈
x
1
∧
∃
x
3
(
x
3
∈
x
2
∧
¬
∃
x
4
(
x
4
∈
x
3
)
)
)
A
=
D
o
m
(
E
2
,
1
,
2
∩
∁
V
2
D
o
m
(
E
3
,
2
,
3
)
)
∩
D
o
m
(
E
2
,
1
,
2
∩
D
o
m
(
E
3
,
2
,
3
∩
∁
V
3
D
o
m
(
E
4
,
3
,
4
)
)
)
{\displaystyle {\begin{alignedat}{2}&\phi \;&&=\;\;\exists x_{2}\,(x_{2}\!\in \!x_{1}\land \;\;\neg \;\;\;\;\exists x_{3}\;(x_{3}\!\in \!x_{2}))\,\land \;\;\,\exists x_{2}\,(x_{2}\!\in \!x_{1}\land \;\;\,\exists x_{3}\,(x_{3}\!\in \!x_{2}\,\land \;\;\neg \;\;\;\;\exists x_{4}\;(x_{4}\!\in \!x_{3})))\\&A\;&&=Dom\,(\;E_{2,1,2}\;\cap \;\complement _{V^{2}}\,Dom\,(\;E_{3,2,3}\;))\,\cap \,Dom\,(\;E_{2,1,2}\;\cap \,Dom\,(\;\,E_{3,2,3}\;\cap \;\complement _{V^{3}}\,Dom\,(\;E_{4,3,4}\;)))\end{alignedat}}}
クラス存在定理の拡張
ゲーデルはクラス存在定理を、クラスの関係 (例えば
Y
1
⊆
Y
2
{\displaystyle Y_{1}\subseteq Y_{2}}
や単項関係
M
(
Y
1
)
{\displaystyle M(Y_{1})}
)、特別なクラス(例えば
O
r
d
{\displaystyle Ord}
)、演算 (例えば
(
x
1
,
x
2
)
{\displaystyle (x_{1},x_{2})}
や
x
1
∩
Y
1
{\displaystyle x_{1}\cap Y_{1}}
)を含む論理式
ϕ
{\displaystyle \phi }
に拡張した。[32] クラス存在定理を拡張するには、関係、特別なクラス、演算を定義する論理式が集合上で量化されていなければならない。すると
ϕ
{\displaystyle \phi }
はクラス存在定理の仮説 を満たす等価な論理式に変換される。
以下の定義は論理式での関係、特別なクラス、演算の定義方法を特定する。
関係
R
{\displaystyle R}
を以下のように定義する:
R
(
Z
1
,
…
,
Z
k
)
⟺
ψ
R
(
Z
1
,
…
,
Z
k
)
.
{\displaystyle R(Z_{1},\dots ,Z_{k})\iff \psi _{R}(Z_{1},\dots ,Z_{k}).}
特別なクラス
C
{\displaystyle C}
を以下のように定義する:
u
∈
C
⟺
ψ
C
(
u
)
.
{\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
,
…
,
Γ
k
,
Γ
,
{\displaystyle \,\Gamma _{1},\dots ,\Gamma _{k},\Gamma ,}
Δ
{\displaystyle \Delta }
は項を表すものとする。
関係
R
(
Z
1
,
…
,
Z
k
)
{\displaystyle R(Z_{1},\dots ,Z_{k})}
を定義論理式
ψ
R
(
Z
1
,
…
,
Z
k
)
{\displaystyle \psi _{R}(Z_{1},\dots ,Z_{k})}
で置き換える。
ψ
C
(
u
)
{\displaystyle \psi _{C}(u)}
を特別なクラス
C
{\displaystyle C}
の定義論理式とする。
Δ
∈
C
{\displaystyle \Delta \in C}
を
ψ
C
(
Δ
)
{\displaystyle \psi _{C}(\Delta )}
で置き換える。
C
∈
Δ
{\displaystyle C\in \Delta }
を
∃
z
i
[
z
i
=
C
∧
z
i
∈
Δ
]
{\displaystyle \exists z_{i}[z_{i}=C\land z_{i}\in \Delta ]}
で置き換える
ψ
P
(
u
,
Z
1
,
…
,
Z
k
)
{\displaystyle \psi _{P}(u,Z_{1},\dots ,Z_{k})}
を演算
P
(
Z
1
,
…
,
Z
k
)
{\displaystyle P(Z_{1},\dots ,Z_{k})}
の定義論理式とする。
Δ
∈
P
(
Γ
1
,
…
,
Γ
k
)
{\displaystyle \Delta \in P(\Gamma _{1},\dots ,\Gamma _{k})}
を
ψ
P
(
Δ
,
Γ
1
,
…
,
Γ
k
)
{\displaystyle \psi _{P}(\Delta ,\Gamma _{1},\dots ,\Gamma _{k})}
で置き換える。
P
(
Γ
1
,
…
,
Γ
k
)
∈
Δ
{\displaystyle P(\Gamma _{1},\dots ,\Gamma _{k})\in \Delta }
を
∃
z
i
[
z
i
=
P
(
Γ
1
,
…
,
Γ
k
)
∧
z
i
∈
Δ
]
{\displaystyle \exists z_{i}[z_{i}=P(\Gamma _{1},\dots ,\Gamma _{k})\land z_{i}\in \Delta ]}
で置き換える。
外延性の公理を用いて、
Δ
=
Γ
{\displaystyle \Delta =\Gamma }
を
∀
z
i
(
z
i
∈
Δ
⟺
z
i
∈
Γ
)
{\displaystyle \forall z_{i}(z_{i}\in \Delta \iff z_{i}\in \Gamma )}
に変換する。
例 3:
Y
1
⊆
Y
2
{\displaystyle Y_{1}\subseteq Y_{2}}
を変換する。
Y
1
⊆
Y
2
⟺
∀
z
1
(
z
1
∈
Y
1
⟹
z
1
∈
Y
2
)
(rule 1)
{\displaystyle Y_{1}\subseteq Y_{2}\iff \forall z_{1}(z_{1}\in Y_{1}\implies z_{1}\in Y_{2})\quad {\text{(rule 1)}}}
例 4:
x
1
∩
Y
1
∈
x
2
{\displaystyle x_{1}\cap Y_{1}\in x_{2}}
を変換する。
x
1
∩
Y
1
∈
x
2
⟺
∃
z
1
[
z
1
=
x
1
∩
Y
1
∧
z
1
∈
x
2
]
(rule 3b)
⟺
∃
z
1
[
∀
z
2
(
z
2
∈
z
1
⟺
z
2
∈
x
1
∩
Y
1
)
∧
z
1
∈
x
2
]
(rule 4)
⟺
∃
z
1
[
∀
z
2
(
z
2
∈
z
1
⟺
z
2
∈
x
1
∧
z
2
∈
Y
1
)
∧
z
1
∈
x
2
]
(rule 3a)
{\displaystyle {\begin{alignedat}{2}x_{1}\cap Y_{1}\in x_{2}&\iff \exists z_{1}[z_{1}=x_{1}\cap Y_{1}\,\land \,z_{1}\in x_{2}]&&{\text{(rule 3b)}}\\&\iff \exists z_{1}[\forall z_{2}(z_{2}\in z_{1}\iff z_{2}\in x_{1}\cap Y_{1})\,\land \,z_{1}\in x_{2}]&&{\text{(rule 4)}}\\&\iff \exists z_{1}[\forall z_{2}(z_{2}\in z_{1}\iff z_{2}\in x_{1}\land z_{2}\in Y_{1})\,\land \,z_{1}\in x_{2}]\quad &&{\text{(rule 3a)}}\\\end{alignedat}}}
この例は各規則がどのように演算を消去するのか示すものである。
定理 ―
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
{\displaystyle \phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})}
を集合のみを量化する論理式とし、
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
{\displaystyle x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m}}
以外に自由変数を持たず、集合のみを量化する論理式によって定義された関係、特別なクラス、操作を含みうるものとする。すると、すべての
Y
1
,
…
,
Y
m
,
{\displaystyle Y_{1},\dots ,Y_{m},}
に対して以下を満たす
n
{\displaystyle n}
-組のクラス
A
{\displaystyle A}
がただ一つ存在する:
∀
x
1
⋯
∀
x
n
[
(
x
1
,
…
,
x
n
)
∈
A
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
]
.
{\displaystyle \forall x_{1}\cdots \,\forall x_{n}[(x_{1},\dots ,x_{n})\in A\iff \phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})].}
[注釈 10]
証明 —
変換規則を
ϕ
{\displaystyle \phi }
に適用し、関係、特別なクラス、演算を含まない等価な論理式に変換する。この論理式はクラス存在定理の仮説を満たす。したがって、すべての
Y
1
,
…
,
Y
m
,
{\displaystyle Y_{1},\dots ,Y_{m},}
に対して、以下を満たす
n
{\displaystyle n}
-組のクラスがただ一つ存在する:
∀
x
1
⋯
∀
x
n
[
(
x
1
,
…
,
x
n
)
∈
A
⟺
ϕ
(
x
1
,
…
,
x
n
,
Y
1
,
…
,
Y
m
)
]
.
{\displaystyle \forall x_{1}\cdots \,\forall x_{n}[(x_{1},\dots ,x_{n})\in A\iff \phi (x_{1},\dots ,x_{n},Y_{1},\dots ,Y_{m})].}
集合公理
クラス存在定理に必要だった対の公理と正則性公理は、上記の通り与えられている。NBG はほかに 4 つの集合公理を含む。このうち 3 つは集合に適用されるクラス演算として扱われる。
定義. 以下が成り立てば
F
{\displaystyle F}
は関数 である
F
⊆
V
2
∧
∀
x
∀
y
∀
z
[
(
x
,
y
)
∈
F
∧
(
x
,
z
)
∈
F
⟹
y
=
z
]
.
{\displaystyle F\subseteq V^{2}\land \forall x\,\forall y\,\forall z\,[(x,y)\in F\,\land \,(x,z)\in F\implies y=z].}
集合論において、関数を定義する際に始域と終域を特定する必要はない(関数(集合論) を参照)。NBG の関数の定義では、 ZFC の定義のうち、順序類の集合を順序対のクラスに一般化したものになる。
ZFC における像 、和集合 、冪集合 といった集合演算の定義もクラス演算に一般化される。
F
{\displaystyle F}
によるクラス
A
{\displaystyle A}
の像は
F
[
A
]
=
{
y
:
∃
x
(
x
∈
A
∧
(
x
,
y
)
∈
F
)
}
{\displaystyle F[A]=\{y:\exists x(x\in A\,\land \,(x,y)\in F)\}}
である。 この定義は
A
⊆
D
o
m
(
F
)
{\displaystyle A\subseteq Dom(F)}
を必要としない。クラス
A
{\displaystyle A}
の和は
∪
A
=
{
x
:
∃
y
(
x
∈
y
∧
y
∈
A
)
}
{\displaystyle \cup A=\{x:\exists y(x\in y\,\,\land \,y\in A)\}}
となる。クラス
A
{\displaystyle A}
の冪集合は
P
(
A
)
=
{
x
:
x
⊆
A
}
{\displaystyle {\mathcal {P}}(A)=\{x:x\subseteq A\}}
となる。クラス存在定理の拡張版はこれらのクラスの存在を含意する。置換、和集合 、冪集合 の各公理は、これらの操作が集合に適用したときに集合となることを含意する。[34]
置換公理.
F
{\displaystyle F}
が関数で
a
{\displaystyle a}
が集合であるならば、
F
{\displaystyle F}
による
a
{\displaystyle a}
の像
F
[
a
]
{\displaystyle F[a]}
は集合である。
∀
F
∀
a
[
F
is a function
⟹
∃
b
∀
y
(
y
∈
b
⟺
∃
x
(
x
∈
a
∧
(
x
,
y
)
∈
F
)
)
]
.
{\displaystyle \forall F\,\forall a\,[F{\text{ is a function}}\implies \exists b\,\forall y\,(y\in b\iff \exists x(x\in a\,\land \,(x,y)\in F))].}
F
[
A
]
{\displaystyle F[A]}
の定義に必要条件
A
⊆
D
o
m
(
F
)
{\displaystyle A\subseteq Dom(F)}
がなければ、以下の証明に用いる強い形の置換公理となる。
和集合の公理.
a
{\displaystyle a}
が集合であるならば、
∪
a
{\displaystyle \cup a}
を含む集合が存在する。
∀
a
∃
b
∀
x
[
∃
y
(
x
∈
y
∧
y
∈
a
)
⟹
x
∈
b
]
.
{\displaystyle \forall a\,\exists b\,\forall x\,[\,\exists y(x\in y\,\,\land \,y\in a)\implies x\in b\,].}
冪集合公理.
a
{\displaystyle a}
が集合であるならば、
P
(
a
)
{\displaystyle {\mathcal {P}}(a)}
を含む集合が存在する。
∀
a
∃
b
∀
x
(
x
⊆
a
⟹
x
∈
b
)
.
{\displaystyle \forall a\,\exists b\,\forall x\,(x\subseteq a\implies x\in b).}
[注釈 11]
無限公理.
a
{\displaystyle a}
のすべての元
x
{\displaystyle x}
に対して、
x
{\displaystyle x}
が
y
{\displaystyle y}
の真部分集合である
a
{\displaystyle a}
の元
y
{\displaystyle y}
が存在するような、空でない集合
a
{\displaystyle a}
が存在する。
無限公理と置換公理から空集合 の存在が導かれる。クラス存在公理に関する議論 において、空クラス
∅
{\displaystyle \emptyset }
の存在は示されている。ここで
∅
{\displaystyle \emptyset }
が集合であることを示そう。関数
F
=
∅
{\displaystyle F=\emptyset }
と、無限公理で与えられる集合
a
{\displaystyle a}
を仮定する。置換公理より、
F
{\displaystyle F}
による
a
{\displaystyle a}
の像は、
∅
{\displaystyle \emptyset }
と等しい集合である。
NBG の無限公理は ZFC の無限公理 から含意される:
∃
a
[
∅
∈
a
∧
∀
x
(
x
∈
a
⟹
x
∪
{
x
}
∈
a
)
]
{\displaystyle \,\exists a\,[\emptyset \in a\,\land \,\forall x(x\in a\implies x\cup \{x\}\in a)]}
。
x
⊂
x
∪
{
x
}
{\displaystyle x\subset x\cup \{x\}}
であるため、 ZFC 公理の論理積 の第1項、つまり
∅
∈
a
{\displaystyle \emptyset \in a}
が NBG 公理の論理積の第1項を含意する。ZFC 公理の論理積の第2項、すなわち
∀
x
(
x
∈
a
⟹
x
∪
{
x
}
∈
a
)
{\displaystyle \forall x(x\in a\implies x\cup \{x\}\in a)}
が NBG 公理の論理積の第2項を含意する。 NBG の無限公理から ZFC の無限公理を証明するには、ほかの NBG 公理が必要である(弱い選択公理 を参照)。[注釈 12]
NBG 集合論を導いた手法の変遷
フォン・ノイマンの1925年の公理系
フォン・ノイマンは自身の公理系に関する入門的な論文を1925年に発行した。1928年、彼は公理系の詳細な説明を与えた。[39] フォン・ノイマンの公理系は、関数と引数という原始概念 (英語版 ) の 2 領域に基づく。これらの領域は重複する—両方の領域に属するものは引数関数と呼ばれる。関数が NBG におけるクラスに対応し、引数関数が集合に対応する。フォン・ノイマンの原始的演算は、a (x ) ではなく [a , x ] で表される関数適用である。ここで a は関数、 x は引数を表す。この演算から引数が生成される。フォン・ノイマンはクラスと集合を、A と B の2値の引数関数を使って定義した。また、 [a , x ] ≠ A ならば x ∈ a であると定義した。[1]
集合論におけるフォン・ノイマンの仕事はゲオルグ・カントール の論文やエルンスト・ツェルメロ の1908年の集合論公理 、アドルフ・フレンケル とトアルフ・スコーレム によって独立に発表された1922年のツェルメロ集合論 への批評によって広められた。 フレンケルとスコーレムはいずれも、ツェルメロの公理は集合 {Z 0 , Z 1 , Z 2 , ...} の存在を証明できないと指摘していた。ここで、 Z 0 は自然数 の集合であり、 Z n +1 は Z n の冪集合 である。そして彼らはそのような集合の存在を保証する置換公理を導入した。[40] [注釈 14] しかし、彼らはこの公理を適用しようとは思わなかった:フレンケルは「置換公理は『一般集合論』には強すぎる」とする一方、「スコーレムだけは置換公理を『導入できうる』と書いていた」と述べている。[42]
フォン・ノイマンはツェルメロ集合論の問題点に対処し、解決策を与えた:
順序数の理論
問題点:ツェルメロ集合論に置換公理が不足しているため、カントールの順序数 の理論をツェルメロ集合論内で展開できない。[注釈 15]
解決策: フォン・ノイマンは ∈-で整列可能な集合 を用いて順序数を定義することで、カントールの理論を復活させ、[注釈 16] そしてキーとなる定理、すなわちすべての順序付け可能な集合が順序数について順序同型 (英語版 ) であるような順序数に関する定理を、置換公理を用いて証明した。[注釈 15] フレンケルとスコーレムとは対照的に、フォン・ノイマンは集合論における置換公理の重要性を強調していた:「実際、この公理なしに順序数の理論は不可能だと思う」[45]
集合としては大きすぎるクラスを特定する基準
問題点:ツェルメロはそのような基準を示していなかった。ツェルメロ集合論では、パラドックス を引き起こす大きなクラスが排除されていたが、フレンケルとスコーレムが指摘したような、多くの集合が除外されていた。[注釈 17]
解決策:フォン・ノイマンは基準を導入した:クラスが集合として大きすぎるのは、クラスからすべての集合のクラス V への全射 が存在するときで、かつそのときに限る。フォン・ノイマンはこのような大きなクラスを元に持つ任意のクラスを許可しないことで、集合論的パラドックスを回避できることを知っていた。この制限と彼の基準を組み合わせることで、サイズ制限公理を得た: クラス C はどのクラスの元でもないのは、 C から V への全射が存在するとき、またそのときに限る。[48] [注釈 18]
有限公理化
問題点:ツェルメロは彼の分出公理において、「定値命題関数 」の不正確な概念を用いていた。
解決策:スコーレムはのちに ZFC で用いられる分出公理図式を導入し、フレンケルは等価な解決策を用いた。[50] しかし、ツェルメロは「彼自身の観点では、集合論の土台となる自然数の概念をも暗に巻き込む部分があるため」いずれの方法も拒否した。[注釈 19] フォン・ノイマンは「定値命題関数」の概念を有限個の公理から構築できる関数で定式化することにより、公理図式 を除外した。これによって、フォン・ノイマンの理論は有限公理化できるようになった。[51] 1961年、リチャード・モンタギュー は ZFC が有限公理化できないことを証明した。[52]
正則性公理
問題点:ツェルメロ集合論は空集合と無限集合から議論を始め、対の公理の反復、和集合、冪集合、分出公理、選択公理によって新たな集合を得る。しかし、この集合論では集合をこれらの形に制限していない。例えば、集合 x が x ∈ x を満たすような、整礎 でない集合の存在が許容される。[注釈 20]
解決策:フレンケルはこうした集合を除外するために公理を導入した。フォン・ノイマンはフレンケルの公理を分析し、「厳密な定式化」がなされていないと大雑把に指摘した:「集合に加えて ... その存在は公理に対して絶対必要になる、これ以上に集合はなく。」[54] フォン・ノイマンは正則性公理を整楚でない集合を除外する方法として提案したが、ツェルメロ公理系には取り入れられなかった。1930年になって初めて、ツェルメロは正則性公理を取り入れた公理系を発表した。[注釈 21]
フォン・ノイマンの1929年の公理系
ジョン・フォン・ノイマン
1929年、フォン・ノイマンは NBG につながる公理を含む論文を発表した。 この論文はサイズ制限公理の無矛盾性に対する懸念がきっかけだった。この公理をフォン・ノイマンは「たくさん、実際には多すぎる」と述べている。また、分出公理と置換公理は整列可能定理を含意するほか、濃度 が V より小さいどのクラスも集合であることをも含意する。フォン・ノイマンは後者について、カントール集合論を越えたと考え、以下のように結論づけた:「ゆえに(公理の)無矛盾性は、それが問題にならないかだけではなく、必須となるカントールのフレームワークを越えない集合論の公理化となるかを議論しなければならない。」[57]
フォン・ノイマンは無矛盾性の調査を1929年の公理系を導入することで始めた。この公理系はサイズ制限公理以外は1925年の公理系すべてを含む。彼は、サイズ制限公理は、そこから得られる 2 つの結果である、置換公理と選択公理に置き換えた。フォン・ノイマンの選択公理は以下の通り:「どの関係 R も、 R と同じ定義域の写像を部分クラスとしてもつ。」[58]
S をフォン・ノイマンの1929年の公理系とする。フォン・ノイマンは公理系 S + Regularity (S と正則性公理からなる)を導入し、自身の1925年の公理系が S と相対的に無矛盾 であることを示した。また、以下を証明した:
S が無矛盾であれば、 S + Regularity は無矛盾である。
S + Regularity はサイズ制限公理を含意する。Since これは1925年の公理系のうち S + Regularity にない唯一のものであるため、 S + Regularity は自身の1925年の公理系の公理すべてを含意する。
これらの結果は以下の内容を含意する: S が無矛盾であれば、フォン・ノイマンの1925年の公理系は無矛盾である。証明: S が無矛盾であれば、 S + Regularity は無矛盾である(結果 1)。背理法 を用いて、1925年の公理系が矛盾である、つまり1925年の公理系が矛盾を含意すると仮定する。 S + Regularity は1925年の公理系を含意する(結果 2)ので、 S + Regularity も矛盾を含意する。しかし、これは S + Regularity の無矛盾性に反する。したがって、 S が無矛盾であれば、フォン・ノイマンの1925年の公理系も無矛盾である。
S は彼の1929年の公理系であるので、フォン・ノイマンの1925年の公理系は(カントール集合論に近い)1929年のものと相対的に無矛盾である。カントール集合論と1929年の公理系の大きな違いは、クラスとフォン・ノイマンの選択公理である。公理系 S + Regularity はベルナイスとゲーデルによって修正され、NBG と等価な公理系となっていった。
ベルナイスの公理系
パウル・ベルナイス
1929年、パウル・ベルナイス はフォン・ノイマンの新しい公理系を、クラスと集合を原始概念とすることで修正し始めた。ベルナイスは自身の仕事を 1937年から1954年にかけて、一連の論文として発表した。[59] ベルナイスは以下のように述べている:
フォン・ノイマンの公理系を修正する目的は、元のツェルメロ公理系の構造に近いまま維持するほか、論理学者に馴染みのある
シュレーダー論理 (英語版 ) と
プリンキピア・マテマティカ の集合論的概念を同時に活用するためである。見ての通り、この仕事によって、注目すべき簡略化ができた。
[60]
ベルナイスは集合とクラスを2-ソート論理 で扱い、2 つの原始的帰属概念を導入した:一つは集合の関係で、もう一つはクラスの関係である。これらの原始概念によって、ベルナイスはフォン・ノイマンの1929年の公理系を簡略化した。ベルナイスはまた、その公理系に正則性公理を導入した。[61]
ゲーデルの公理系 (NBG)
クルト・ゲーデル、1926年頃
1931年、ベルナイスは自身の集合論に関してクルト・ゲーデル に手紙を送った。ゲーデルはベルナイスの理論を、集合をすべてクラスで置き換え、1ソートで1つの原始概念(帰属関係)からなる理論に簡略化した。ゲーデルはまた、ベルナイスの公理のいくつかを弱め、フォン・ノイマンの選択公理を大域選択公理と等価なものに置き換えた。[62] [注釈 22] ゲーデルは、1940年の大域選択と一般連続体仮説の相対的無矛盾性に関するモノグラフの中で、自身の公理系を使った。[63]
ゲーデルが自身のモノグラフの中で NBG を用いた理由はいくつか考えられる:[注釈 23]
ゲーデルは数学的理由を与えた—NBGの大域選択公理から、より強い無矛盾な定理が導かれる:「この強い形式の(選択)公理は、他の公理に対して無矛盾であれば、当然弱い形式についての無矛盾性を含意する。」[5]
ロバート・ソロヴェイ (英語版 ) は以下のように予想した:「私が思うに、彼(ゲーデル)は公理的集合論内でモデル理論 の基本を発展させることに関連する、細部の議論を避けたかった。」[67] [注釈 24]
ケネス・キューネン はゲーデルが議論を避けた理由を以下のように考えている:「L (構成可能集合 )に関する組み合わせ論的アプローチもたくさんある、例えば ... (1940年のモノローグの中でゲーデルは)論理学者以外に説明することを試みていた。 ... このアプローチは L を扱う際に、論理の痕跡を残さないというメリットがある。」[68]
チャールズ・パーソンズ (Charles Prsons) はゲーデルの選択に哲学的理由を考えた:「この(「集合の特徴」が集合論の原始概念であるという)見方は、ゲーデルの(モノグラフのように)クラス変数をフレームワークとする理論の選択に反映されているかもしれない。」[69]
ゲーデルの成果と詳細な説明により、その後20年間にわたって NBG が発展した。[70] 1963年、ゲーデルの作り上げたNBGの無矛盾性証明を援用して、ポール・コーエン はZFの独立性を証明した。[71] その後、 ZFC が NBG よりも一般的になった。これにはいくつかの要因があり、その一つは NBG において強制法 を扱うには追加の仕事が必要だったためである。[72] これに関するコーエンの1966年の強制法の発表では、ZFが用いられた。[73] [注釈 25] 他の要因としては、NBG が ZFC の保存拡大であることが証明されたからである。[注釈 26]
NBG は論理的に ZFC と等価ではない。なぜなら、NBG の言葉は表現的であるからである。NBG ではクラスに関して表現できる一方、ZFC ではできない。しかし集合に関しては、 NBG も ZFC で同じ内容の表現を含意する。したがって、NBG は ZFC の保存拡大 である。 NBG は ZFC が含意しない定理を含意するが、 NBG は保存拡大であるため、これらの定理は真のクラスに関するものでなければならない。例えば、大域選択公理は 真のクラス V は整列可能であり、どの真のクラスも V と一対一対応することを含意するが、これは NBG の定理である。[注釈 27]
保存拡大の帰結の一つは、 ZFC と NBG が無矛盾性同値であることである。 この証明には爆発原理(矛盾 からは、何でも証明可能である)を用いる。 ZFC か NBG のいずれかが無矛盾でないと仮定する。すると無矛盾でない理論は集合に関する、矛盾 する表現 ∅ = ∅ かつ ∅ ≠ ∅ を含意する。保存拡大の特性から、もう一方の理論もこれらの表現を含意する。したがって、こちらも無矛盾ではない。ゆえに、 NBG はより表現的であるものの、 ZFC と無矛盾性同値なのである。この結果とフォン・ノイマンの1929年の相対的無矛盾性の証明を合わせると、彼の1925年の公理系にサイズ制限公理を加えたものが ZFC と無矛盾性同値であることが含意される。ZFCはカントール集合論のフレームワークに含まれるため、この事実は完全にこの強力な公理の相対的無矛盾性に関するフォン・ノイマンの懸念 を払拭するものである。
NBG は ZFC の保存拡大であるものの、定理は NBG のほうが ZFC より短くエレガントに証明可能である(逆もしかり)。この側面について知られている結果の調査結果は Pudlák 1998 を参照。
モース=ケリー集合論 は、量化子の範囲がクラスである論理式を含むクラス内包公理図式を有する。MK は NBG の無矛盾性を証明できるため、 NBG より強力な理論である一方、[76] ゲーデルの第二不完全定理 から NBG は NBG自身の無矛盾性を証明できない。
NBG に関する存在論 的な議論や哲学的な問題、特に ZFC と MK との比較については、Potter 2004 の Appendix C を参照。
モデル
ZFC、NBG、MKは累積的階層 Vα および 構成可能階層 Lα の言葉で表現可能なモデル を持つ。 V は到達不能基数 κ を含み、 X が X ⊆ Vκ であると仮定して、 Def(X ) は X のパラメータによる1次の定義可能部分集合 のクラスを表すとする。記号として "
(
X
,
∈
)
{\displaystyle (X,\in )}
" は領域
X
{\displaystyle X}
と関係
∈
{\displaystyle \in }
のモデルを表し、 "
⊨
{\displaystyle \models }
" は満足関係(en:Structure_(mathematical_logic)#Satisfaction_relation )を表すものとする:
Def
(
X
)
:=
{
{
x
∣
x
∈
X
and
(
X
,
∈
)
⊨
ϕ
(
x
,
y
1
,
…
,
y
n
)
}
:
ϕ
is a first-order formula and
y
1
,
…
,
y
n
∈
X
}
.
{\displaystyle \operatorname {Def} (X):={\Bigl \{}\{x\mid x\in X{\text{ and }}(X,\in )\models \phi (x,y_{1},\ldots ,y_{n})\}:\phi {\text{ is a first-order formula and }}y_{1},\ldots ,y_{n}\in X{\Bigr \}}.}
このとき:
(V κ , ∈) と (L κ , ∈) は ZFC のモデルである。[77]
(V κ , V κ+1 , ∈) は MK のモデルであり、ここで V κ はモデルの集合からなり、 V κ+1 はモデルのクラスからなる。[78] MK のモデルは NBG のモデルであるため、このモデルも NBG のモデルである。
(V κ , Def(V κ ), ∈) は、NBG の大域選択公理を ZFC の選択公理に置き換えた、メンデルソン版の NBG のモデルである。[79] (V κ , ∈) は ZFC のモデルであるため、ZFC 公理はこのモデル内で真である。特に、ZFC の選択公理が成り立つが、 NBG の大域選択公理は成り立たないかもしれない。[注釈 28] 存在を主張するクラスは1次の定義で定義できることから、NBG のクラス存在公理はこのモデル内で真である。例えば、
E
{\displaystyle E}
が以下のように定義されるため、帰属公理が成り立つ:
E
=
{
x
∈
V
κ
:
(
V
κ
,
∈
)
⊨
∃
u
∃
v
[
x
=
(
u
,
v
)
∧
u
∈
v
]
}
.
{\displaystyle E=\{x\in V_{\kappa }:(V_{\kappa },\in )\models \exists u\ \exists v[x=(u,v)\land u\in v]\}.}
(L κ , L κ+ , ∈) (κ+ は κ の後続基数)は NBG のモデルである。[注釈 29] NBG のクラス存在公理は (L κ , L κ+ , ∈) の中で真である。例えば、
E
{\displaystyle E}
が以下のように定義されるため、帰属公理が成り立つ:
E
=
{
x
∈
L
κ
:
(
L
κ
,
∈
)
⊨
∃
u
∃
v
[
x
=
(
u
,
v
)
∧
u
∈
v
]
}
.
{\displaystyle E=\{x\in L_{\kappa }:(L_{\kappa },\in )\models \exists u\ \exists v[x=(u,v)\land u\in v]\}.}
ゆえに、 E ∈ 𝒫(L κ ) である。一般連続体仮説 が L の中で真というゲーデルの証明において、ゲーデルは 𝒫(L κ ) ⊆ L κ+ であることを証明した。[81] したがって、 E ∈ L κ+ であり、ゆえに (L κ , L κ+ , ∈) の中で帰属公理は真である。同様に、ほかのクラス存在公理も真である。(順序数のクラスを構成可能集合に移す)ゲーデルの関数を κ 未満の順序数に制限 することによって L κ が整列可能であるため、大域選択公理は真である。したがって、 (L κ , L κ+ , ∈) は NBG のモデルである。