在NBG 下,“属于关系”以一个双元断言符号
P
(
x
,
y
)
{\displaystyle P(x,\,y)}
来表示,
P
(
x
,
y
)
{\displaystyle P(x,\,y)}
通常简记为
x
∈
y
{\displaystyle x\in y}
,并被直观理解成“x属于y”;类似地,
P
(
x
,
y
)
{\displaystyle P(x,\,y)}
的否定
¬
P
(
x
,
y
)
{\displaystyle \neg P(x,\,y)}
通称被简记为
x
∉
y
{\displaystyle x\notin y}
,并被直观理解为“x不属于y”。
以下都把
⊢
N
B
G
{\displaystyle \vdash _{NBG}}
简写为普通的
⊢
{\displaystyle \vdash }
。
本条目定理的证明会频繁引用一阶逻辑的定理,定理的代号可以参见一阶逻辑#常用的推理性质 一节。
类与集合
“类”这个名词在公理化集合论 出现之前,通常被理解为“以集合 为元素 的集合。”或是集合(如等价类 )。
但NBG 所谈及的一切对象(变数和项 )都是类 。而所谓的集合,是属于某个类的类 ,也就是说以下的合式公式 (
M
{\displaystyle {\mathcal {M}}}
来自德语 的"集合"“Menge ”)式
M
(
x
)
:=
∃
y
(
x
∈
y
)
{\displaystyle {\mathcal {M}}(x):=\exists y(x\in y)}
可直观理解为“x是集合”,特别注意到,为了避免跟其他合式公式的变数产生混淆,
y
{\displaystyle y}
必须是展开
M
(
x
)
{\displaystyle {\mathcal {M}}(x)}
时首次出现的变数。反之合式公式
P
r
(
x
)
:=
¬
M
(
x
)
{\displaystyle {\mathcal {Pr}}(x):=\neg {\mathcal {M}}(x)}
可称为“
x
{\displaystyle x}
是真类 (proper class )”。
子类
直观上“x包含于y”意为“所有x的元素a都会属于y”,以此为动机,NBG 有以下的符号简写
x
⊆
y
:=
∀
a
[
(
a
∈
x
)
⇒
(
a
∈
y
)
]
{\displaystyle x\subseteq y:=\forall a[\,(a\in x)\Rightarrow (a\in y)\,]}
以上可称为“x包含于y”或“x是y的子类 (subclass )”;在
M
(
x
)
{\displaystyle {\mathcal {M}}(x)}
和
M
(
y
)
{\displaystyle {\mathcal {M}}(y)}
成立的前提下(也就是“x和y都是集合”),可称为“x是y的子集 (subset )”。
与集合相关的量词简写
仿造量词的简写 ,对于任意变数
x
{\displaystyle x}
与合式公式
A
{\displaystyle {\mathcal {A}}}
,可作如下的符号定义
(
∀
M
x
)
A
:=
∀
x
[
M
(
x
)
⇒
A
]
{\displaystyle ({\forall }^{M}x){\mathcal {A}}:=\forall x[\,{\mathcal {M}}(x)\Rightarrow {\mathcal {A}}\,]}
(对所有
x
{\displaystyle x}
,
x
{\displaystyle x}
是集合则
A
{\displaystyle {\mathcal {A}}}
)
(
∃
M
x
)
A
:=
∃
x
[
M
(
x
)
∧
A
]
{\displaystyle ({\exists }^{M}x){\mathcal {A}}:=\exists x[\,{\mathcal {M}}(x)\wedge {\mathcal {A}}\,]}
(存在
x
{\displaystyle x}
不但是集合且
A
{\displaystyle {\mathcal {A}}}
)
也有书籍以小写字母来表示被量化的集合变数[ 3] ,但考虑到一般的非逻辑数学书籍都将大小写的差异挪作他用,为避免混淆本条目采用以上的上标表示法。
看待等号的不同方式
直观上,两个集合相等意为“x的元素就是y的元素”,也就是朴素集合论 的外延公理 ,换句话说,可用以下的严谨合式公式重写为
∀
a
[
(
a
∈
x
)
⇔
(
a
∈
y
)
]
{\displaystyle \forall a[\,(a\in x)\Leftrightarrow (a\in y)\,]}
但一阶逻辑的等号可以视为单独的断言符号 ,也可以视为一条复合的合式公式。具体来说,视为一个新的断言符号
Q
(
x
,
y
)
{\displaystyle Q(x,\,y)}
并简记为
x
=
y
{\displaystyle x=y}
的话,需在NBG 内额外添加以下的公理
(
T
′
)
{\displaystyle (T^{\prime })}
—
(
x
=
y
)
⇔
∀
a
[
(
a
∈
x
)
⇔
(
a
∈
y
)
]
{\displaystyle (x=y)\Leftrightarrow \forall a[\,(a\in x)\Leftrightarrow (a\in y)\,]}
直观上可理解为“类x的元素就是类y的元素,等价于类x等于类y”。
但视为一条合式公式,则仅需做以下的符号定义
(
x
=
y
)
:=
∀
a
[
(
a
∈
x
)
⇔
(
a
∈
y
)
]
{\displaystyle (x=y):=\forall a[\,(a\in x)\Leftrightarrow (a\in y)\,]}
不管是何种看待方法,习惯上都会把
¬
(
x
=
y
)
{\displaystyle \neg (x=y)}
简记成
(
x
≠
y
)
{\displaystyle (x\neq y)}
(直观上的“不相等”)。
等号的良置
为了确保
(
x
=
y
)
{\displaystyle (x=y)}
的确符合直观上对等号的要求,还需添加以下的公理
(
T
)
{\displaystyle (T)}
—
(
x
=
y
)
⇒
∀
z
[
(
x
∈
z
)
⇔
(
y
∈
z
)
]
{\displaystyle (x=y)\Rightarrow \forall z[\,(x\in z)\Leftrightarrow (y\in z)\,]}
直观上,这个公理确保“x等于y,则x属于z等同于y属于z”。
这样,以下的元定理 就确保了如此定义的等号是“成功的”。
元定理 — NBG 是带相等符号
(
x
=
y
)
{\displaystyle (x=y)}
的一阶逻辑 理论
证明
以下的证明会逐条检验等式定理一节 所条列的定义
(E1):
(
x
=
x
)
{\displaystyle (x=x)}
展开来是(或等价于)
∀
a
[
(
a
∈
x
)
⇔
(
a
∈
x
)
]
{\displaystyle \forall a[\,(a\in x)\Leftrightarrow (a\in x)\,]}
那考虑到恒等关系 和(AND) 有
⊢
(
a
∈
x
)
⇔
(
a
∈
x
)
{\displaystyle \vdash (a\in x)\Leftrightarrow (a\in x)}
那再套用(GEN) ,就会有
⊢
∀
a
[
(
a
∈
x
)
⇔
(
a
∈
x
)
]
{\displaystyle \vdash \forall a[\,(a\in x)\Leftrightarrow (a\in x)\,]}
所以(E1)得证。
(E2):
因为目前的NBG 理论内没有任何函数符号 ,所以对变数
x
{\displaystyle x}
来说,NBG 的原子公式 只有
(
x
∈
z
)
{\displaystyle (x\in z)}
和
(
z
∈
x
)
{\displaystyle (z\in x)}
两种可能,这样的话,(E2)等同于要求以下两式是NBG 的定理
(1)
(
x
=
y
)
⇒
[
(
x
∈
z
)
⇒
(
y
∈
z
)
]
{\displaystyle (x=y)\Rightarrow [\,(x\in z)\Rightarrow (y\in z)\,]}
(2)
(
x
=
y
)
⇒
[
(
z
∈
x
)
⇒
(
z
∈
y
)
]
{\displaystyle (x=y)\Rightarrow [\,(z\in x)\Rightarrow (z\in y)\,]}
但依据量词公理 (A4),(1)可从本节一开始添加的公理(T)所推出;类似地,把
(
x
=
y
)
{\displaystyle (x=y)}
视为断言符号时,(2)都可以从(T')配合(A4)推出;若把
(
x
=
y
)
{\displaystyle (x=y)}
视为合式公式的简写,(2)也可以用
(
x
=
y
)
{\displaystyle (x=y)}
的定义配上(A4)推出。
(E3):
本条定义要求以下的合式公式为NBG 的定理
(
x
=
y
)
⇒
(
y
=
x
)
{\displaystyle (x=y)\Rightarrow (y=x)}
从且的交换性 有
⊢
(
∀
z
)
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
⇒
(
∀
z
)
[
(
z
∈
y
)
⇔
(
z
∈
x
)
]
{\displaystyle \vdash (\forall z)[(z\in x)\Leftrightarrow (z\in y)]\Rightarrow (\forall z)[(z\in y)\Leftrightarrow (z\in x)]}
对上式使用(AND) 和(D1) 就有
(
x
=
y
)
⊢
(
∀
z
)
[
(
z
∈
y
)
⇔
(
z
∈
x
)
]
{\displaystyle (x=y)\vdash (\forall z)[(z\in y)\Leftrightarrow (z\in x)]}
再对上面式使用(AND) 和(D1) 又有
(
x
=
y
)
⊢
(
y
=
x
)
{\displaystyle (x=y)\vdash (y=x)}
所以(E3)的确是NBG 的定理。
综上所述,定理得证。
◻
{\displaystyle \Box }
真子类
在定义“相等”以后,可以把“相等的类”排除出子类的定义中,换句话说,NBG 有以下的符号定义
x
⊂
y
:=
(
x
⊆
y
)
∧
(
x
≠
y
)
{\displaystyle x\subset y:=(x\subseteq y)\wedge (x\neq y)}
可直观理解为“x是y的真子类 (proper subclass ),定义为x包含于y且x不等于y”;在
M
(
x
)
{\displaystyle {\mathcal {M}}(x)}
和
M
(
y
)
{\displaystyle {\mathcal {M}}(y)}
成立的前提下(也就是“x和y都是集合”),可称为“x是y的真子集 (proper subset )”。
外延定理
为以下的定理可直观理解为“x等于y等价于,对所有集合z,z属于x等价于z属于y”,也就是说,等于的定义可以“限缩”成元素为集合的状况。
外延定理 —
⊢
(
x
=
y
)
⇔
(
∀
M
z
)
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
{\displaystyle \vdash (x=y)\Leftrightarrow (\forall ^{M}z)[\,(z\in x)\Leftrightarrow (z\in y)\,]}
证明
以下取一个不曾出现的变数
t
{\displaystyle t}
来展开
M
(
z
)
{\displaystyle {\mathcal {M}}(z)}
(
⇒
{\displaystyle \Rightarrow }
)
∀
z
(
z
∈
x
⇔
z
∈
y
)
⊢
∀
z
{
∃
t
(
z
∈
t
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
}
{\displaystyle \forall z(z\in x\Leftrightarrow z\in y)\vdash \forall z\{\exists t(z\in t)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]\}}
(1)
∀
z
(
z
∈
x
⇔
z
∈
y
)
{\displaystyle \forall z(z\in x\Leftrightarrow z\in y)}
(Hyp)
(2)
z
∈
x
⇔
z
∈
y
{\displaystyle z\in x\Leftrightarrow z\in y}
(MP with 1, A4)
(3)
∃
t
(
z
∈
t
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
{\displaystyle \exists t(z\in t)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]}
(MP with 2, A1)
(4)
∀
z
{
∃
t
(
z
∈
t
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
}
{\displaystyle \forall z\{\exists t(z\in t)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]\}}
(GEN with 3)
(
⇐
{\displaystyle \Leftarrow }
)
∀
z
{
M
(
z
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
}
⊢
∀
z
(
z
∈
x
⇔
z
∈
y
)
{\displaystyle \forall z\{{\mathcal {M}}(z)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]\}\vdash \forall z(z\in x\Leftrightarrow z\in y)}
A
:=
(
z
∈
x
)
⇔
(
z
∈
y
)
{\displaystyle {\mathcal {A}}:=(z\in x)\Leftrightarrow (z\in y)}
(1)
∀
z
[
∃
t
(
z
∈
t
)
⇒
A
]
{\displaystyle \forall z[\exists t(z\in t)\Rightarrow {\mathcal {A}}]}
(Hyp)
(2)
∃
t
(
z
∈
t
)
⇒
A
{\displaystyle \exists t(z\in t)\Rightarrow {\mathcal {A}}}
(MP with A4, 1)
(3)
¬
A
⇒
∀
t
[
¬
(
z
∈
t
)
]
{\displaystyle \neg {\mathcal {A}}\Rightarrow \forall t[\neg (z\in t)]}
(MP with T, 2)
(4)
¬
A
⇒
[
¬
(
z
∈
t
)
]
{\displaystyle \neg {\mathcal {A}}\Rightarrow [\neg (z\in t)]}
(D1, with A4, 3)
(5)
(
z
∈
t
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
{\displaystyle (z\in t)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]}
(MP with T, 4)
(6)
∀
t
{
(
z
∈
t
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
}
{\displaystyle \forall t\{(z\in t)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]\}}
(GEN with 5)
(7)
(
z
∈
x
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
{\displaystyle (z\in x)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]}
(MP with A4, 6)
(8)
(
z
∈
y
)
⇒
[
(
z
∈
x
)
⇔
(
z
∈
y
)
]
{\displaystyle (z\in y)\Rightarrow [(z\in x)\Leftrightarrow (z\in y)]}
(MP with A4, 6)
(9)
(
z
∈
x
)
⇒
[
(
z
∈
x
)
⇒
(
z
∈
y
)
]
{\displaystyle (z\in x)\Rightarrow [(z\in x)\Rightarrow (z\in y)]}
(D1 with AND, 7)
(10)
(
z
∈
y
)
⇒
[
(
z
∈
y
)
⇒
(
z
∈
x
)
]
{\displaystyle (z\in y)\Rightarrow [(z\in y)\Rightarrow (z\in x)]}
(D1 with AND, 8)
(11)
(
z
∈
x
)
⇒
(
z
∈
y
)
{\displaystyle (z\in x)\Rightarrow (z\in y)}
(MP twice with A2, I, 9)
(12)
(
z
∈
y
)
⇒
(
z
∈
x
)
{\displaystyle (z\in y)\Rightarrow (z\in x)}
(MP twice with A2, I, 10)
(13)
(
z
∈
x
)
⇔
(
z
∈
y
)
{\displaystyle (z\in x)\Leftrightarrow (z\in y)}
(AND with 11, 12)
(14)
∀
z
(
z
∈
x
⇔
z
∈
y
)
{\displaystyle \forall z(z\in x\Leftrightarrow z\in y)}
(GEN with 13)
引入新的函数符号前,常需要唯一存在性 的证明,而外延定理大大简化了证明的难度。
特定条件下的存在性
以下关于一阶逻辑 的一般性定理,也大大简化了 NBG 引入新公理的过程所需的证明
(DC, Definition under certain condition) —
x
{\displaystyle x}
于合式公式
A
{\displaystyle {\mathcal {A}}}
完全不自由且
c
{\displaystyle c}
是常数符号 。若
A
⊢
(
∃
x
)
B
{\displaystyle {\mathcal {A}}\vdash (\exists x){\mathcal {B}}}
则有
⊢
(
∃
x
)
{
[
¬
A
∧
(
x
=
c
)
]
∨
(
A
∧
B
)
}
{\displaystyle \vdash (\exists x)\{\,[\,\neg {\mathcal {A}}\wedge (x=c)\,]\vee ({\mathcal {A}}\wedge {\mathcal {B}})\,\}}
证明
(1)
A
⇒
(
∃
x
)
B
{\displaystyle {\mathcal {A}}\Rightarrow (\exists x){\mathcal {B}}}
(Hyp)
(2)
(
∀
x
)
{
¬
{
[
¬
A
∧
(
x
=
c
)
]
∨
(
A
∧
B
)
}
}
{\displaystyle (\forall x)\{\neg \{[\neg {\mathcal {A}}\wedge (x=c)]\vee ({\mathcal {A}}\wedge {\mathcal {B}})\}\}}
(Hyp)
(3)
¬
{
[
¬
A
∧
(
x
=
c
)
]
∨
(
A
∧
B
)
}
{\displaystyle \neg \{[\neg {\mathcal {A}}\wedge (x=c)]\vee ({\mathcal {A}}\wedge {\mathcal {B}})\}}
(MP with A4, 2)
(4)
¬
[
¬
A
∧
(
x
=
c
)
]
∧
¬
(
A
∧
B
)
{\displaystyle \neg [\neg {\mathcal {A}}\wedge (x=c)]\wedge \neg ({\mathcal {A}}\wedge {\mathcal {B}})}
(MP with 3, DIS)
(5)
¬
[
¬
A
∧
(
x
=
c
)
]
{\displaystyle \neg [\neg {\mathcal {A}}\wedge (x=c)]}
(MP with AND,4)
(6)
¬
(
A
∧
B
)
{\displaystyle \neg ({\mathcal {A}}\wedge {\mathcal {B}})}
(MP with AND, 4)
(7)
¬
A
⇒
¬
(
x
=
c
)
{\displaystyle \neg {\mathcal {A}}\Rightarrow \neg (x=c)}
(MP with DIS, DN 5)
(8)
A
⇒
¬
B
{\displaystyle {\mathcal {A}}\Rightarrow \neg {\mathcal {B}}}
(MP with DIS, DN, 5)
(9)
B
⇒
¬
A
{\displaystyle {\mathcal {B}}\Rightarrow \neg {\mathcal {A}}}
(MP with T, 8)
(10)
(
∃
x
)
B
⇒
¬
A
{\displaystyle (\exists x){\mathcal {B}}\Rightarrow \neg {\mathcal {A}}}
(GENe with 9)
(11)
A
⇒
¬
(
∃
x
)
B
{\displaystyle {\mathcal {A}}\Rightarrow \neg (\exists x){\mathcal {B}}}
(MP with T, 11)
(12)
¬
A
{\displaystyle \neg {\mathcal {A}}}
(A3' with 1, 11)
(13)
¬
(
x
=
c
)
{\displaystyle \neg (x=c)}
(MP with 7, 12)
(14)
(
∀
x
)
[
¬
(
x
=
c
)
]
{\displaystyle (\forall x)[\neg (x=c)]}
(GEN with 13)
再套用一次(DN)也就是
A
⇒
(
∃
x
)
B
⊢
(
∀
x
)
{
¬
{
[
¬
A
∧
(
x
=
c
)
]
∨
(
A
∧
B
)
}
}
⇒
¬
(
∃
x
)
(
x
=
c
)
{\displaystyle {\mathcal {A}}\Rightarrow (\exists x){\mathcal {B}}\,\vdash (\forall x)\{\neg \{[\neg {\mathcal {A}}\wedge (x=c)]\vee ({\mathcal {A}}\wedge {\mathcal {B}})\}\}\Rightarrow \neg (\exists x)(x=c)}
但由一阶逻辑的等式性质 有
⊢
c
=
c
{\displaystyle \vdash c=c}
对上式以变数
x
{\displaystyle x}
套用一次(GENe)有
⊢
(
∃
x
)
(
x
=
c
)
{\displaystyle \vdash (\exists x)(x=c)}
所以由(C2)本定理就会得证。
◻
{\displaystyle \Box }
(
P
)
{\displaystyle (P)}
—
(
∀
M
x
)
(
∀
M
y
)
(
∃
M
p
)
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle ({\forall }^{M}x)({\forall }^{M}y)({\exists }^{M}p)({\forall }^{M}z)\{(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\}}
这个公理的直观意思是“对所有集合x和集合y,存在一个仅以x跟y为元素的集合p”。
这个公理还确保了以下的唯一性:
定理(P-1) —
M
(
x
)
∧
M
(
y
)
⊢
(
∃
!
p
)
{
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
{\displaystyle {\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\vdash (\exists !p){\big \{}\,{\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}}
证明
根据量词的简写 ,配对公理(P)等价于
(
∀
x
)
(
∀
y
)
{
M
(
x
)
∧
M
(
y
)
⇒
(
∃
p
)
{
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
}
{\displaystyle (\forall x)(\forall y){\bigg \{}\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\Rightarrow (\exists p){\big \{}\,{\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}\,{\bigg \}}}
这样对上式套用两次量词公理 的(A4)有
M
(
x
)
∧
M
(
y
)
⇒
(
∃
p
)
{
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
{\displaystyle {\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\Rightarrow (\exists p){\big \{}\,{\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}}
这样在有
M
(
x
)
∧
M
(
y
)
{\displaystyle {\mathcal {M}}(x)\wedge {\mathcal {M}}(y)}
的前提就有
(
∃
p
)
{
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
{\displaystyle (\exists p){\big \{}\,{\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}}
所以
M
(
x
)
∧
M
(
y
)
⊢
(
∃
p
)
{
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
{\displaystyle {\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\vdash (\exists p){\big \{}\,{\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}}
另一方面,若假设
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle {\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
M
(
π
)
∧
(
∀
M
z
)
{
(
z
∈
π
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle {\mathcal {M}}(\pi )\wedge ({\forall }^{M}z)\{\,(z\in \pi )\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
这样根据逻辑与的直观性质 有
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
(
∀
M
z
)
{
(
z
∈
π
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle ({\forall }^{M}z)\{\,(z\in \pi )\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
再根据(A4)有
M
(
z
)
⇒
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle {\mathcal {M}}(z)\Rightarrow \{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
M
(
z
)
⇒
{
(
z
∈
π
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle {\mathcal {M}}(z)\Rightarrow \{\,(z\in \pi )\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
如果再假设
M
(
z
)
{\displaystyle {\mathcal {M}}(z)}
,根据MP律 有
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
{\displaystyle (z\in p)\Leftrightarrow [(z=x)\vee (z=y)]}
(
z
∈
π
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
{\displaystyle (z\in \pi )\Leftrightarrow [(z=x)\vee (z=y)]}
这样根据演绎定理 的推论(D1)和逻辑与的直观性质 有
(
z
∈
p
)
⇔
(
z
∈
π
)
{\displaystyle (z\in p)\Leftrightarrow (z\in \pi )}
也就是说
B
(
p
)
∧
B
(
π
)
,
M
(
z
)
⊢
(
z
∈
p
)
⇔
(
z
∈
π
)
{\displaystyle {\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi ),\,{\mathcal {M}}(z)\,\vdash \,(z\in p)\Leftrightarrow (z\in \pi )}
其中
B
(
p
)
:=
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle {\mathcal {B}}(p):={\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
因为变数
z
{\displaystyle z}
在
B
(
p
)
{\displaystyle {\mathcal {B}}(p)}
和
B
(
π
)
{\displaystyle {\mathcal {B}}(\pi )}
内完全不自由,对上式套用演绎定理 (D)将
M
(
z
)
{\displaystyle {\mathcal {M}}(z)}
移到右方后,再对
z
{\displaystyle z}
套用普遍化 会有
B
(
p
)
∧
B
(
π
)
⊢
(
∀
M
z
)
[
(
z
∈
p
)
⇔
(
z
∈
π
)
]
{\displaystyle {\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )\,\vdash \,(\forall ^{M}z)[\,(z\in p)\Leftrightarrow (z\in \pi )\,]}
这样根据本条目的外延定理 有
B
(
p
)
∧
B
(
π
)
⊢
(
p
=
π
)
{\displaystyle {\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )\,\vdash \,(p=\pi )}
那以演绎定理 (D)将
B
(
p
)
∧
B
(
π
)
{\displaystyle {\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )}
移到右方,然后接连对
p
{\displaystyle p}
和
π
{\displaystyle \pi }
使用普遍化 有
⊢
(
∀
p
)
(
∀
π
)
[
B
(
p
)
∧
B
(
π
)
⇒
(
p
=
π
)
]
{\displaystyle \vdash (\forall p)(\forall \pi )[\,{\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )\Rightarrow (p=\pi )\,]}
故本定理得证。
◻
{\displaystyle \Box }
这样的话会有
定理 —
⊢
(
∃
!
p
)
{
{
¬
[
M
(
x
)
∧
M
(
y
)
]
∧
(
p
=
∅
)
}
∨
{
M
(
x
)
∧
M
(
y
)
∧
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
}
{\displaystyle \vdash (\exists !p){\bigg \{}\,\{\,\neg [\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\,]\wedge (p=\varnothing )\,\}\vee {\big \{}\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\wedge {\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}\,{\bigg \}}}
证明
根据(P-1)和本条目的特定条件下的存在性 (DC)会有
(P-2)
⊢
(
∃
p
)
{
{
¬
[
M
(
x
)
∧
M
(
y
)
]
∧
(
p
=
∅
)
}
∨
{
M
(
x
)
∧
M
(
y
)
∧
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
}
{\displaystyle \vdash (\exists p){\bigg \{}\,\{\,\neg [\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\,]\wedge (p=\varnothing )\,\}\vee {\big \{}\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\wedge {\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}\,{\big \}}\,{\bigg \}}}
设
A
(
p
)
:=
¬
[
M
(
x
)
∧
M
(
y
)
]
∧
(
p
=
∅
)
{\displaystyle {\mathcal {A}}(p):=\neg [\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\,]\wedge (p=\varnothing )}
B
(
p
)
:=
M
(
x
)
∧
M
(
y
)
∧
M
(
p
)
∧
(
∀
M
z
)
{
(
z
∈
p
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
{\displaystyle {\mathcal {B}}(p):={\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\wedge {\mathcal {M}}(p)\wedge ({\forall }^{M}z)\{\,(z\in p)\Leftrightarrow [(z=x)\vee (z=y)]\,\}}
C
:=
M
(
x
)
∧
M
(
y
)
{\displaystyle {\mathcal {C}}:={\mathcal {M}}(x)\wedge {\mathcal {M}}(y)}
那连续套用逻辑与合逻辑或的分配律 与逻辑与的交换性 会有
⊢
{
[
A
(
p
)
∨
B
(
p
)
]
∧
[
A
(
π
)
∨
B
(
π
)
]
}
⇔
{
{
[
A
(
p
)
∧
A
(
π
)
]
∨
[
B
(
p
)
∧
A
(
π
)
]
}
∨
{
[
A
(
p
)
∧
B
(
π
)
]
∨
[
B
(
p
)
∧
B
(
π
)
]
}
}
{\displaystyle \vdash \{\,[\,{\mathcal {A}}(p)\vee {\mathcal {B}}(p)\,]\wedge [\,{\mathcal {A}}(\pi )\vee {\mathcal {B}}(\pi )\,]\,\}\Leftrightarrow {\big \{}\,\{\,[\,{\mathcal {A}}(p)\wedge {\mathcal {A}}(\pi )\,]\vee [\,{\mathcal {B}}(p)\wedge {\mathcal {A}}(\pi )\,]\,\}\vee \{\,[\,{\mathcal {A}}(p)\wedge {\mathcal {B}}(\pi )\,]\vee [\,{\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )\,]\,\}\,{\big \}}}
但考虑到逻辑与的直观性质 和逻辑与的定义 有
⊢
[
B
(
p
)
∧
A
(
π
)
]
⇒
(
¬
C
∧
C
)
{\displaystyle \vdash [\,{\mathcal {B}}(p)\wedge {\mathcal {A}}(\pi )\,]\Rightarrow (\neg {\mathcal {C}}\wedge {\mathcal {C}})}
⊢
[
A
(
p
)
∧
B
(
π
)
]
⇒
(
¬
C
∧
C
)
{\displaystyle \vdash [\,{\mathcal {A}}(p)\wedge {\mathcal {B}}(\pi )\,]\Rightarrow (\neg {\mathcal {C}}\wedge {\mathcal {C}})}
⊢
(
¬
C
∧
C
)
⇔
¬
(
C
⇒
C
)
{\displaystyle \vdash (\neg {\mathcal {C}}\wedge {\mathcal {C}})\Leftrightarrow \neg ({\mathcal {C}}\Rightarrow {\mathcal {C}})}
那根据恒等关系
(
I
)
{\displaystyle (I)}
和常用的推理性质 (T)有
⊢
¬
[
B
(
p
)
∧
A
(
π
)
]
{\displaystyle \vdash \neg [\,{\mathcal {B}}(p)\wedge {\mathcal {A}}(\pi )\,]}
⊢
¬
[
A
(
p
)
∧
B
(
π
)
]
{\displaystyle \vdash \neg [\,{\mathcal {A}}(p)\wedge {\mathcal {B}}(\pi )\,]}
所以根据逻辑或的定义 来重复使用演绎定理 的推论(D1)会有
⊢
{
[
A
(
p
)
∨
B
(
p
)
]
∧
[
A
(
π
)
∨
B
(
π
)
]
}
⇔
{
[
A
(
p
)
∧
A
(
π
)
]
∨
[
B
(
p
)
∧
B
(
π
)
]
}
{\displaystyle \vdash \{\,[\,{\mathcal {A}}(p)\vee {\mathcal {B}}(p)\,]\wedge [\,{\mathcal {A}}(\pi )\vee {\mathcal {B}}(\pi )\,]\,\}\Leftrightarrow \{\,[\,{\mathcal {A}}(p)\wedge {\mathcal {A}}(\pi )\,]\vee [\,{\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )\,]\,\}}
然后从NBG 的等式定理 会有
⊢
[
A
(
p
)
∧
A
(
π
)
]
⇒
(
p
=
π
)
{\displaystyle \vdash [\,{\mathcal {A}}(p)\wedge {\mathcal {A}}(\pi )\,]\Rightarrow (p=\pi )}
另一方面,根据(P-1)有
⊢
[
B
(
p
)
∧
B
(
π
)
]
⇒
(
p
=
π
)
{\displaystyle \vdash [\,{\mathcal {B}}(p)\wedge {\mathcal {B}}(\pi )\,]\Rightarrow (p=\pi )}
这样结合逻辑与 的(DisJ)有
⊢
{
[
A
(
p
)
∨
B
(
p
)
]
∧
[
A
(
π
)
∨
B
(
π
)
]
}
⇒
(
p
=
π
)
{\displaystyle \vdash \{\,[\,{\mathcal {A}}(p)\vee {\mathcal {B}}(p)\,]\wedge [\,{\mathcal {A}}(\pi )\vee {\mathcal {B}}(\pi )\,]\,\}\Rightarrow (p=\pi )}
再对
p
{\displaystyle p}
和
π
{\displaystyle \pi }
套用普遍化 有
⊢
(
∀
p
)
(
∀
π
)
{
{
[
A
(
p
)
∨
B
(
p
)
]
∧
[
A
(
π
)
∨
B
(
π
)
]
}
⇒
(
p
=
π
)
}
{\displaystyle \vdash (\forall p)(\forall \pi ){\bigg \{}\,\{\,[\,{\mathcal {A}}(p)\vee {\mathcal {B}}(p)\,]\wedge [\,{\mathcal {A}}(\pi )\vee {\mathcal {B}}(\pi )\,]\,\}\Rightarrow (p=\pi )\,{\bigg \}}}
这样结合刚刚的(P-2)与逻辑与的直观性质 ,本定理就得证了。
◻
{\displaystyle \Box }
所以根据函数符号与唯一性 一节,可以在NBG 加入新的双元函数符号
f
p
2
(
x
,
y
)
{\displaystyle f_{p}^{2}(x,\,y)}
(简记为
{
x
,
y
}
{\displaystyle \{x,\,y\}}
)和以下的新公理
(
P
′
)
{\displaystyle (P^{\prime })}
—
{
¬
[
M
(
x
)
∧
M
(
y
)
]
∧
(
{
x
,
y
}
=
∅
)
}
∨
{\displaystyle {\bigg \{}\neg [\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\,]\wedge (\{x,\,y\}=\varnothing ){\bigg \}}\vee }
{
M
(
x
)
∧
M
(
y
)
∧
M
(
{
x
,
y
}
)
∧
(
∀
M
z
)
{
(
z
∈
{
x
,
y
}
)
⇔
[
(
z
=
x
)
∨
(
z
=
y
)
]
}
}
{\displaystyle {\bigg \{}{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\wedge {\mathcal {M}}\left(\{x,\,y\}\right)\wedge ({\forall }^{M}z)\{\,(z\in \{x,\,y\})\Leftrightarrow [(z=x)\vee (z=y)]\,\}{\bigg \}}}
这个新公理的直观意思是“若x和y为集合,则
{
x
,
y
}
{\displaystyle \{x,\,y\}}
就是那个只以x和y为元素的集合;但反之,若x和y不全为集合,则
{
x
,
y
}
{\displaystyle \{x,\,y\}}
为空集 ”。
有序对
{
x
}
:=
{
x
,
x
}
{\displaystyle \{x\}:=\{x,\,x\}}
⟨
x
⟩
:=
x
{\displaystyle \langle x\rangle :=x}
⟨
x
,
y
⟩
:=
{
{
x
}
,
{
x
,
y
}
}
{\displaystyle \langle x,\,y\rangle :=\{\{x\},\,\{x,\,y\}\}}
⟨
x
1
,
…
,
x
n
,
x
n
+
1
⟩
:=
⟨
⟨
x
1
,
…
,
x
n
⟩
,
x
n
+
1
⟩
{\displaystyle \langle x_{1},\,\dots ,\,\,x_{n},\,x_{n+1}\rangle :=\langle \langle x_{1},\,\dots ,\,\,x_{n}\rangle ,\,x_{n+1}\rangle }
在不跟括弧产生混淆的情况下,也可以把
⟨
x
1
,
…
,
x
n
,
x
n
+
1
⟩
{\displaystyle \langle x_{1},\,\dots ,\,\,x_{n},\,x_{n+1}\rangle }
记为
(
x
1
,
…
,
x
n
,
x
n
+
1
)
{\displaystyle (x_{1},\,\dots ,\,\,x_{n},\,x_{n+1})}
。
关系
R
e
l
(
f
)
:=
(
∀
M
a
)
{
(
a
∈
f
)
⇒
(
∃
x
)
(
∃
y
)
{
M
(
x
)
∧
M
(
y
)
∧
[
a
=
(
x
,
y
)
]
}
}
{\displaystyle Rel(f):=(\forall ^{M}a){\big \{}\,(a\in f)\Rightarrow (\exists x)(\exists y)\{\,{\mathcal {M}}(x)\wedge {\mathcal {M}}(y)\wedge [\,a=(x,\,y)\,]\,\}\,{\big \}}}
类函数
F
n
c
(
f
)
:=
R
e
l
(
f
)
∧
(
∀
M
x
)
(
∀
M
y
)
(
∀
M
υ
)
{
[
(
x
,
y
)
∈
f
∧
(
x
,
υ
)
∈
f
]
⇒
(
y
=
υ
)
}
{\displaystyle Fnc(f):=Rel(f)\wedge (\forall ^{M}x)(\forall ^{M}y)(\forall ^{M}\upsilon )\{\,[\,(x,\,y)\in f\wedge (x,\,\upsilon )\in f\,]\Rightarrow (y=\upsilon )\,\}}
类函数跟普通函数 的差别在于普通函数是个集合 。
属于类公理
(
K
∈
)
{\displaystyle (K_{\in })}
—
(
∃
e
)
(
∀
M
a
)
(
∀
M
b
)
{
[
(
a
,
b
)
∈
e
]
⇔
(
a
∈
b
)
}
{\displaystyle (\exists e)(\forall ^{M}a)(\forall ^{M}b)\{[(a,\,b)\in e]\Leftrightarrow (a\in b)\}}
交类公理
(
K
i
)
{\displaystyle (K_{i})}
—
(
∀
x
)
(
∀
y
)
(
∃
i
)
(
∀
M
a
)
{
(
a
∈
i
)
⇔
[
(
a
∈
x
)
∧
(
a
∈
y
)
]
}
{\displaystyle (\forall x)(\forall y)(\exists i)({\forall }^{M}a)\{(a\in i)\Leftrightarrow [(a\in x)\wedge (a\in y)]\}}
补类公理
(
K
c
)
{\displaystyle (K_{c})}
—
(
∀
x
)
(
∃
c
)
(
∀
M
a
)
[
(
a
∈
c
)
⇔
(
a
∉
x
)
]
{\displaystyle (\forall x)(\exists c)({\forall }^{M}a)[(a\in c)\Leftrightarrow (a\not \in x)]}
定义域公理
(
K
D
)
{\displaystyle (K_{D})}
—
(
∀
x
)
(
∃
d
)
(
∀
M
a
)
{
(
a
∈
d
)
⇔
(
∃
M
b
)
[
(
a
,
b
)
∈
x
]
}
{\displaystyle (\forall x)(\exists d)(\forall ^{M}a)\{(a\in d)\Leftrightarrow (\exists ^{M}b)[(a,\,b)\in x]\}}
积类公理
(
K
p
)
{\displaystyle (K_{p})}
—
(
∀
x
)
(
∃
p
)
(
∀
M
a
)
(
∀
M
b
)
{
[
(
a
,
b
)
∈
p
]
⇔
(
a
∈
x
)
}
{\displaystyle (\forall x)(\exists p)(\forall ^{M}a)(\forall ^{M}b)\{[\,(a,\,b)\in p\,]\Leftrightarrow (a\in x)\}}
置换类公理
(
K
σ
1
)
{\displaystyle (K_{\sigma 1})}
—
(
∀
x
)
(
∃
σ
)
(
∀
M
a
)
(
∀
M
b
)
(
∀
M
c
)
{
[
(
a
,
b
,
c
)
∈
x
]
⇔
[
(
b
,
c
,
a
)
∈
σ
]
}
{\displaystyle (\forall x)(\exists \sigma )(\forall ^{M}a)(\forall ^{M}b)(\forall ^{M}c)\{[(a,\,b,\,c)\in x]\Leftrightarrow [(b,\,c,\,a)\in \sigma ]\}}
(
K
σ
2
)
{\displaystyle (K_{\sigma 2})}
—
(
∀
x
)
(
∃
σ
)
(
∀
M
a
)
(
∀
M
b
)
(
∀
M
c
)
{
[
(
a
,
b
,
c
)
∈
x
]
⇔
[
(
a
,
c
,
b
)
∈
σ
]
}
{\displaystyle (\forall x)(\exists \sigma )(\forall ^{M}a)(\forall ^{M}b)(\forall ^{M}c)\{[(a,\,b,\,c)\in x]\Leftrightarrow [(a,\,c,\,b)\in \sigma ]\}}
类的存在元定理
这个元定理对应到ZFC尔集合论的分类公理 。
首先需要递归地定义 “可叙述公式 ”(predicative well-formed formula):
对任意变数
x
{\displaystyle x}
和
y
{\displaystyle y}
,
x
∈
y
{\displaystyle x\in y}
为可叙述公式。
若
P
{\displaystyle {\mathcal {P}}}
与
Q
{\displaystyle {\mathcal {Q}}}
为可叙述公式,
x
{\displaystyle x}
为任意变数,则
(
¬
P
)
{\displaystyle (\neg {\mathcal {P}})}
、
(
P
⇒
Q
)
{\displaystyle ({\mathcal {P}}\Rightarrow {\mathcal {Q}})}
与
(
∀
M
x
)
P
{\displaystyle (\forall ^{M}x){\mathcal {P}}}
都是可叙述公式。
这样依据上列诸类存在公理,就有以下元定理:
类的存在元定理 —
P
{\displaystyle {\mathcal {P}}}
为一条只内含变数
x
1
,
…
,
x
n
,
y
1
,
…
,
y
m
{\displaystyle x_{1},\,\dots ,\,x_{n},\,y_{1},\,\dots ,\,y_{m}}
的可叙述公式,则有
⊢
(
∃
s
)
(
∀
M
x
1
)
…
(
∀
M
x
n
)
[
(
⟨
x
1
,
…
,
x
n
⟩
∈
s
)
⇔
P
]
{\displaystyle \vdash (\exists s)(\forall ^{M}x_{1})\ldots (\forall ^{M}x_{n})[(\langle x_{1},\,\dots ,\,x_{n}\rangle \in s)\Leftrightarrow {\mathcal {P}}]}