第一章　逻辑、等式与类

本章为学习公理化集合论准备语言和推理工具。内容限于三部分：一阶逻辑的基本语法与演算、等式的定义及其性质、类记号及罗素类。

我们采用经典一阶逻辑，所有对象变量都取遍集合。本章不使用选择公理，也不提前引入后续的集合构造公理。

有一项约定需要先说明：许多教材把等号作为逻辑的原始符号，再通过外延公理说明集合何时相等。本章遵循给定目录，先使用不含原始等号的一阶语言，再用“具有相同元素”定义等号。因此，等号的替换性质需要证明，不能预先作为逻辑规则使用。

1. 必要的逻辑学铺垫

1.1 ZF 的语言

一种形式语言首先要规定：可以使用哪些符号，以及这些符号如何组成合法表达式。

本章采用的基本符号包括：

类别	符号	用途
对象变量	(x,y,z,a,b,c,\ldots)	表示集合
二元关系符号	(\in)	表示隶属关系
逻辑联结词	(\neg,\to)	表示否定和蕴含
量词	(\forall)	表示“对所有集合”
辅助符号	((,))	确定表达式的结构和作用范围

变量符号有无限多个；需要时可以使用带下标的变量。

这里只有一个非逻辑的原始关系符号，即 (\in)。表达式

[ x\in y ]

读作“(x) 是 (y) 的元素”，或“(x) 属于 (y)”。

(\in) 是二元关系符号，因为它连接两个对象。两边的位置不能随意交换：

[ x\in y ]

与

[ y\in x ]

通常表达不同的事情。

当前语言没有原始常量符号和函数符号，因此它的项只有变量。后面出现的等号、类记号等，都是可以展开的缩写。

常用逻辑缩写

为方便阅读，我们约定：

[ \begin{aligned} \phi\land\psi &;\coloneqq; \neg(\phi\to\neg\psi),\ \phi\lor\psi &;\coloneqq; (\neg\phi\to\psi),\ \phi\leftrightarrow\psi &;\coloneqq; (\phi\to\psi)\land(\psi\to\phi),\ \exists x,\phi &;\coloneqq; \neg\forall x,\neg\phi. \end{aligned} ]

其中，(\phi,\psi) 是我们讨论公式时使用的元语言符号，并不是取遍集合的对象变量。

这些符号分别读作“并且”“或者”“当且仅当”“存在一个集合”。

另约定：

[ x\notin y ;\coloneqq; \neg(x\in y). ]

这里的“或者”是相容或：两边都成立时，析取仍然成立。

1.2 合式公式：wff

合式公式，英文为 well-formed formula，简称 wff，是按语言的形成规则构造出的表达式。

其递归定义如下：

1. 若 (u,v) 是变量，则 (u\in v) 是公式，称为原子公式。
2. 若 (\phi) 是公式，则 (\neg\phi) 是公式。
3. 若 (\phi,\psi) 是公式，则 ((\phi\to\psi)) 是公式。
4. 若 (\phi) 是公式，(x) 是变量，则 (\forall x,\phi) 是公式。
5. 只有有限次使用上述规则得到的表达式才是公式。

使用已定义的缩写后，下面都是公式：

[ x\in y, ]

[ (x\in y)\land\neg(y\in z), ]

[ \forall x,(x\in a\to x\in b), ]

[ \exists y,\forall x,(x\in y\leftrightarrow x\in a). ]

下面则不是公式：

[ \in x, \qquad x\in, \qquad \forall(x\in y). ]

它们分别缺少关系的一个位置，或者没有在量词后指定被量化的变量。

合式与真假是两回事。 一个公式可以写得完全合法，但在某种解释下为假。例如，(x\in x) 是合式公式；它是否成立不是语法问题。

括号与作用范围

括号决定公式的结构。例如：

[ \forall x,(\phi\to\psi) ]

表示量词作用于整个蕴含式；而

[ (\forall x,\phi)\to\psi ]

表示它只作用于 (\phi)。

两者一般不能互换。

本章在可能产生歧义的地方保留括号，不依赖读者猜测运算顺序。

1.3 自由变量与约束变量

目录中的“自由遍历”应为“自由变量”或“自由变元”。

量词不仅说明“所有”或“存在”，还会约束其作用范围内相应变量的出现。

例如：

[ \forall x,(x\in y). ]

其中 (x) 的出现受 (\forall x) 约束，而 (y) 的出现是自由的。公式表达的性质依赖于 (y) 取哪个集合。

再看：

[ (x\in y)\land\forall x,(x\in z). ]

左边的 (x) 是自由出现，右边的 (x) 是约束出现。因此，严格地说，自由或约束首先是变量某次出现的性质；同一个变量符号可以在一个公式中兼有两种出现。

记 (\operatorname{FV}(\phi)) 为公式 (\phi) 的自由变量集合，则：

[ \operatorname{FV}(u\in v)={u,v}, ]

[ \operatorname{FV}(\neg\phi)=\operatorname{FV}(\phi), ]

[ \operatorname{FV}(\phi\to\psi)

\operatorname{FV}(\phi)\cup\operatorname{FV}(\psi), ]

[ \operatorname{FV}(\forall x,\phi)

\operatorname{FV}(\phi)\setminus{x}. ]

没有自由变量的公式称为句子或闭公式。例如：

[ \forall x,\neg(x\in x) ]

是句子，而

[ \neg(x\in x) ]

不是句子。

写成 (\phi(x))，通常表示我们特别关注自由变量 (x)，不一定表示它是唯一的自由变量。需要明确其他变量时，可以写成：

[ \phi(x,p_1,\ldots,p_n). ]

当我们固定 (p_1,\ldots,p_n) 的取值，讨论关于 (x) 的性质时，把这些变量称为参数。

1.4 代入与变量捕获

记

[ \phi[t/x] ]

为把 (\phi) 中 (x) 的所有自由出现替换为项 (t) 所得的公式。本章的项只有变量。

例如，若

[ \phi(x)\equiv(x\in y)\land\forall x,(x\in z), ]

则

[ \phi[a/x] \equiv (a\in y)\land\forall x,(x\in z). ]

量词约束的 (x) 不参与替换。

代入时还必须避免变量捕获。例如：

[ \phi(x)\equiv\forall y,(x\in y). ]

如果直接把 (x) 换成 (y)，得到

[ \forall y,(y\in y), ]

原本打算作为自由变量代入的 (y)，被已有的量词约束了。这不是我们需要的代入。

正确做法是先把约束变量改为新变量：

[ \phi(x)\equiv\forall z,(x\in z), ]

再代入，得到：

[ \phi[y/x]\equiv\forall z,(y\in z). ]

我们说“(t) 对 (x) 可自由代入 (\phi)”，是指直接代入不会发生这种捕获。也可以约定：每次代入前，先对必要的约束变量作改名。

后文的 (\phi(a))、(\phi(b)) 都按这种避免捕获的方式理解。

1.5 公式的解释与逻辑有效性

理解形式演算前，先区分三个层次。

• 语法层次：一个表达式是否按规则组成公式。
• 语义层次：给定论域、关系解释和自由变量的取值后，公式是否成立。
• 证明层次：一个公式能否由指定公理和推理规则推出。

对当前不含等号的语言，一个结构包括一个非空论域，以及对二元关系符号 (\in) 的解释。在预期的集合论解释中，对象是集合，(\in) 表示实际的隶属关系。

公式

[ \forall x,\phi(x) ]

成立，意为论域中的每个对象代入 (x) 后，(\phi(x)) 都成立。公式

[ \exists x,\phi(x) ]

成立，意为至少有一个对象使它成立。

在所有结构及所有相关变量赋值下都成立的公式，称为逻辑有效式。例如：

[ \phi\to\phi. ]

集合论公理则对 (\in) 的解释施加额外要求，不是单凭逻辑就成立的公式。

1.6 一阶逻辑公理和逻辑演算

形式证明必须明确允许哪些起点和推理步骤。下面给出一种经典的一阶逻辑 Hilbert 演算。

这不是唯一的演算方式；选择它是为了使本章有清楚的形式基础。

一、命题逻辑公理模式

采用以下三个模式：

[ \phi\to(\psi\to\phi), \tag{L1} ]

[ \bigl(\phi\to(\psi\to\chi)\bigr) \to \bigl((\phi\to\psi)\to(\phi\to\chi)\bigr), \tag{L2} ]

[ (\neg\psi\to\neg\phi)\to(\phi\to\psi). \tag{L3} ]

这里每个希腊字母都可以由任意公式替换。

因此，“公理模式”不是单独一个公式，而是一整族公式的生成规则。例如，L1 的一个实例是：

[ (x\in y)\to\bigl((z\in w)\to(x\in y)\bigr). ]

二、量词公理模式

全称实例化：

[ (\forall x,\phi)\to\phi[t/x], \tag{L4} ]

其中 (t) 必须对 (x) 可自由代入 (\phi)。

全称量词与蕴含：

[ \forall x,(\phi\to\psi) \to \bigl(\phi\to\forall x,\psi\bigr), \tag{L5} ]

其中要求：

[ x\notin\operatorname{FV}(\phi). ]

这个条件不能省略。它保证前提 (\phi) 不依赖我们正在推广的变量 (x)。

三、推理规则

分离规则，又称 modus ponens：

从

[ \phi \qquad\text{和}\qquad \phi\to\psi ]

推出

[ \psi. ]

全称推广规则：

从

[ \phi ]

推出

[ \forall x,\phi. ]

若证明中使用了尚未解除的假设，则要求 (x) 不在这些假设中自由出现。

例如，从假设 (x\in a) 不能直接推出 (\forall x,(x\in a))：关于某个对象的假设，并不说明所有对象都有同一性质。

四、证明与可推导性

从假设集合 (\Gamma) 出发的一份证明，是一个有限公式序列，每一行都是：

• 逻辑公理的实例；
• 当前采用的集合论公理；
• (\Gamma) 中的假设；
• 由前面的行依推理规则得到的公式。

记

[ \Gamma\vdash\phi ]

表示从这些假设可以推导出 (\phi)。

后文不会把每份证明都拆成 Hilbert 演算的全部行，而会使用它支持的常见推理方式：分情况、反证、全称实例化和存在量词推理等。

使用“取一个满足条件的对象”时，要遵守存在量词推理的限制：给这个对象起的新名字不能带有额外假设，最终结论也不能依赖这个临时名字。

例如，从

[ \forall x,(x\in a\to x\in b) ]

和

[ c\in a ]

可以推出 (c\in b)。理由是先由 L4 得到

[ c\in a\to c\in b, ]

再使用分离规则。

2. 等式

2.1 等式的定义

对集合变量 (a,b)，定义：

[ a=b ;\coloneqq; \forall x,(x\in a\leftrightarrow x\in b). ]

其中 (x) 选为不同于 (a,b) 的新变量。

这个定义说：

两个集合相等，意味着它们具有完全相同的元素。

另定义：

[ a\ne b ;\coloneqq; \neg(a=b). ]

此时等号只是公式的缩写。证明时，我们可以随时把它展开为只含 (\in) 和逻辑符号的公式。

特别要注意：定义一个记号，并不会自动赋予它通常等号的全部性质。 我们接下来要逐一建立这些性质。

2.2 等号是等价关系

一个关系称为等价关系，是指它具有自反性、对称性和传递性。

定理 2.1　自反性

对任意集合 (a)，有：

[ a=a. ]

证明。 对任意 (x)，命题逻辑给出：

[ x\in a\leftrightarrow x\in a. ]

全称推广后得到：

[ \forall x,(x\in a\leftrightarrow x\in a). ]

这正是 (a=a) 的定义。证毕。

定理 2.2　对称性

[ a=b\to b=a. ]

证明。 假设 (a=b)。展开定义：

[ \forall x,(x\in a\leftrightarrow x\in b). ]

双条件的两边可以交换，因此：

[ \forall x,(x\in b\leftrightarrow x\in a). ]

这就是 (b=a)。证毕。

定理 2.3　传递性

[ (a=b\land b=c)\to a=c. ]

证明。 假设 (a=b) 且 (b=c)。对任意 (x)，有：

[ x\in a\leftrightarrow x\in b, ]

以及

[ x\in b\leftrightarrow x\in c. ]

由命题逻辑推出：

[ x\in a\leftrightarrow x\in c. ]

再全称推广，得到 (a=c)。证毕。

这三个结论只依赖等式定义和逻辑，尚未使用下面的集合论公理。

2.3 Axiom 1：相等集合可以在元素位置替换

公理 1。

[ \forall a,\forall b,\forall c, \bigl((a=b\land a\in c)\to b\in c\bigr). \tag{A1} ]

后面书写公理或定理时，有时省略最外层的全称量词；应理解为对所有自由变量作全称量化。

为什么需要这个公理？

由 (a=b) 的定义，我们立即得到：

[ x\in a\leftrightarrow x\in b. ]

也就是说，在 (\in) 的右侧位置，相等集合可以替换。

但定义本身尚未说明：

[ a\in c\leftrightarrow b\in c. ]

这是在 (\in) 的左侧位置进行替换。公理 1 补充了这项要求。

推论 2.4

[ a=b\to(a\in c\leftrightarrow b\in c). ]

证明。 假设 (a=b)。

由公理 1：

[ a\in c\to b\in c. ]

由对称性，(b=a)，再次使用公理 1：

[ b\in c\to a\in c. ]

合并即得结论。证毕。

因此，两个位置现在都允许替换：

[ a=b\to(c\in a\leftrightarrow c\in b), ]

[ a=b\to(a\in c\leftrightarrow b\in c). ]

与通常 ZF 写法的关系。
如果以等号为原始逻辑符号，替换性质由等号逻辑提供，而“具有相同元素的集合相等”由外延公理提供。本章按目录采用另一种组织方式：用相同元素定义等号，再用 A1 保证元素位置的替换。A1 是本章的编号，不是所有教材通用的 ZF 公理编号。

2.4 任意公式中的相等替换

下面的定理说明，这个定义出来的等号，确实可以在所有公式中按通常方式使用。

定理 2.5　相等替换定理

设 (\phi(x,\vec p)) 是任意公式，其中 (\vec p) 表示其他参数。则：

[ a=b\to \bigl(\phi(a,\vec p)\leftrightarrow\phi(b,\vec p)\bigr). ]

这里两次代入均须避免变量捕获。为陈述和证明方便，可以先把有关变量改名，使 (a,b) 是新变量。

这个定理说：

固定其他参数后，相等的集合满足完全相同的公式性质。

证明。 对公式的构造作结构归纳。

第一步：原子公式。

原子公式形如 (u\in v)。

如果指定变量 (x) 只出现在左侧，所需结论由推论 2.4 给出；只出现在右侧，则由等式定义给出；两侧都不出现 (x)，两次代入得到同一个公式。

若两侧都是 (x)，需要证明：

[ a=b\to(a\in a\leftrightarrow b\in b). ]

在假设 (a=b) 下，先替换左侧，再替换右侧：

[ a\in a \leftrightarrow b\in a \leftrightarrow b\in b. ]

故结论仍成立。

第二步：逻辑联结词。

假设归纳结论对 (\psi) 成立，则由命题逻辑，它也对 (\neg\psi) 成立：

[ \psi(a)\leftrightarrow\psi(b) \quad\Longrightarrow\quad \neg\psi(a)\leftrightarrow\neg\psi(b). ]

若归纳结论对 (\psi,\theta) 都成立，则它也对 (\psi\to\theta) 成立：

[ \bigl(\psi(a)\to\theta(a)\bigr) \leftrightarrow \bigl(\psi(b)\to\theta(b)\bigr). ]

其他联结词是缩写，因此也包括在内。

第三步：量词。

考虑：

[ \phi(x)\equiv\forall y,\psi(x,y). ]

先把约束变量改名，保证 (y) 不同于 (x,a,b)。由归纳假设，在 (a=b) 下，对任意 (y) 都有：

[ \psi(a,y)\leftrightarrow\psi(b,y). ]

于是：

[ \forall y,\psi(a,y) \leftrightarrow \forall y,\psi(b,y). ]

若量词本身约束的是 (x)，它的作用范围内没有需要替换的自由 (x)，该部分保持原样。

至此，所有公式形成规则都已覆盖，定理成立。证毕。

这里的“对任意公式”属于元语言中的陈述。它给出一个定理模式，并不表示 ZF 的对象变量能够取遍公式。

3. 类（class）

3.1 为什么引入类记号

数学中经常需要谈论“所有满足某个条件的集合”。若条件由公式 (\phi(x)) 表达，我们希望把它简写为：

[ {x\mid\phi(x)}. ]

这称为由 (\phi) 定义的类。

目录中的“类型”在这里统一称为“类”，以免与类型论中的“类型”混淆。

本章中的类都是可定义类，允许带集合参数。ZF 的对象变量仍然只取遍集合；我们没有增加一种取遍任意类的新变量。

因此：

类记号是一种表达公式的便利方式，写出一个类并不意味着已经证明存在一个以其全部成员为元素的集合。

3.2 类抽象与自由变量

设：

[ A\coloneqq{x\mid\phi(x,\vec p)}. ]

类抽象记号约束指定变量 (x)。作为扩充记号，它的自由变量为：

[ \operatorname{FV}\bigl({x\mid\phi}\bigr)

\operatorname{FV}(\phi)\setminus{x}. ]

所以，“自由变量少一个 (x)”的准确含义是：从自由变量中去掉 (x)；若 (x) 原本不自由出现，就不会减少自由变量的数目。

例如：

[ {x\mid x\in a} ]

仍依赖参数 (a)，但不再把 (x) 作为自由变量。

类抽象中的变量可以一致改名：

[ {x\mid\phi(x,\vec p)}

{z\mid\phi(z,\vec p)}, ]

其中改名必须避免捕获。

3.3 集合属于类

定义：

[ a\in{x\mid\phi(x,\vec p)} ;\coloneqq; \phi(a,\vec p). ]

例如：

[ a\in{x\mid x\notin x} ]

就是：

[ a\notin a. ]

这是一条展开记号的规则，不是宣告某个新集合存在的公理。

3.4 一个类何时是集合

设：

[ A={x\mid\phi(x,\vec p)}. ]

如果存在集合 (s)，使得：

[ \forall z, \bigl(z\in s\leftrightarrow\phi(z,\vec p)\bigr), ]

就说这个类由集合 (s) 表示，通常直接说“(A) 是集合”。

因此，“(A) 是集合”可以展开为：

[ \exists s,\forall z, \bigl(z\in s\leftrightarrow\phi(z,\vec p)\bigr). ]

表示它的集合在本章的等号意义下是唯一的：若 (s,t) 都满足这个条件，则

[ \forall z,(z\in s\leftrightarrow z\in t), ]

从而 (s=t)。

若不存在这样的集合，就称 (A) 为真类。即：

[ \neg\exists s,\forall z, \bigl(z\in s\leftrightarrow\phi(z,\vec p)\bigr). ]

真类不能成为集合的元素，因为集合的元素仍然是集合。

3.5 类属于集合

若左边是类记号，不能把它未经解释就塞进原始关系符号 (\in) 的位置。因此定义：

[ {x\mid\phi(x,\vec p)}\in a ;\coloneqq; \exists s, \left[ s\in a \land \forall z, \bigl(z\in s\leftrightarrow\phi(z,\vec p)\bigr) \right]. ]

其中 (s,z) 是适当选取的新变量。

这个定义同时要求：

1. 该类由某个集合 (s) 表示；
2. 这个集合 (s) 属于 (a)。

因而：

[ A\in a\to A\text{ 是集合}. ]

注意两种方向的差异：

[ a\in A ]

只断言集合 (a) 满足类的定义条件；而

[ A\in a ]

还断言类 (A) 本身能够由集合表示。

3.6 类属于类

设：

[ A={x\mid\phi(x,\vec p)}, \qquad B={y\mid\psi(y,\vec q)}. ]

定义：

[ A\in B ;\coloneqq; \exists s, \left[ \psi(s,\vec q) \land \forall z, \bigl(z\in s\leftrightarrow\phi(z,\vec p)\bigr) \right]. ]

也就是说，存在一个表示 (A) 的集合 (s)，并且 (s) 满足定义 (B) 的条件。

这里也修正了原目录中的变量笔误：右侧类应写为 ({y\mid\psi(y)})，展开后才是 (\psi(s))。若写为 ({y\mid\psi(x)})，其中的 (x) 仍然自由，含义就变了。

由定义立即得到：

[ A\in B\to A\text{ 是集合}. ]

右边的 (B) 可以是真类；左边的 (A) 若是真类，则这个隶属断言不成立。

3.7 类相等

定义：

[ A=B ;\coloneqq; \forall x,(x\in A\leftrightarrow x\in B). ]

若

[ A={x\mid\phi(x)}, \qquad B={x\mid\psi(x)}, ]

那么展开就是：

[ A=B \quad\Longleftrightarrow\quad \forall x,(\phi(x)\leftrightarrow\psi(x)). ]

证明两个类相等，通常采用以下方法：取任意集合 (x)，证明它属于第一个类当且仅当属于第二个类。

与集合等式一样，类相等具有自反性、对称性和传递性，证明都来自双条件的逻辑性质。

类相等不要求两边都是集合。两个表达式可以定义同一个真类。

对集合 (a)，有：

[ a={x\mid x\in a}. ]

这是因为对任意集合 (z)：

[ z\in{x\mid x\in a} \leftrightarrow z\in a. ]

因此，可以把每个集合看作由其元素确定的类；反过来，却不能把每个类都看作集合。

3.8 类记号只是缩写

前面的定义确保，含类记号的表达式都可以还原成原来的一阶公式。例如：

[ a\in A ]

还原成定义 (A) 的公式在 (a) 处的实例；

[ A\in B ]

还原成关于某个集合是否表示 (A)、并满足 (B) 的定义条件的存在公式；

[ A=B ]

还原成两个定义条件对所有集合是否等价的全称公式。

所以，这里没有引入“量词取遍所有类”的能力。字母 (A,B) 是我们在元语言中使用的类记号占位符，并不是 ZF 新增的对象变量。

3.9 全域类 (V)

定义：

[ V\coloneqq{x\mid x=x}. ]

由于已经证明每个集合都满足 (x=x)，对任意集合 (a)，有：

[ a\in V. ]

因此，(V) 称为全域类，即所有集合组成的类。

这并没有断言存在一个包含所有集合的集合。类记号的引入不提供这样的存在性结论。

对任意可定义类 (A)，按照类属于类的定义：

[ A\in V \quad\Longleftrightarrow\quad A\text{ 是集合}. ]

因为左边展开为“存在一个表示 (A) 的集合 (s)，并且 (s=s)”，而后一条件自动成立。

3.10 罗素类

定义：

[ \operatorname{Rus} \coloneqq {x\mid x\notin x}. ]

它叫作罗素类。在证明之前就把它叫作“罗素集”容易造成误解，因为下面正要证明它不是集合。

根据定义，对任意集合 (a)：

[ a\in\operatorname{Rus} \quad\Longleftrightarrow\quad a\notin a. ]

定理 3.1　罗素类是真类

即：

[ \neg\exists r,\forall z, \bigl(z\in r\leftrightarrow z\notin z\bigr). ]

证明。 反设存在集合 (r)，使：

[ \forall z, \bigl(z\in r\leftrightarrow z\notin z\bigr). ]

由于 (r) 是集合，可以在全称量词中代入 (z=r)，得到：

[ r\in r\leftrightarrow r\notin r. ]

记命题 (r\in r) 为 (P)，则上式是：

[ P\leftrightarrow\neg P. ]

由其中的 (P\to\neg P)，假设 (P) 会导致矛盾，故 (\neg P)。再由 (\neg P\to P) 得到 (P)，再次矛盾。

所以这样的集合 (r) 不存在，罗素类是真类。证毕。

这给出了本章第一个被证明是真类的例子。证明不依赖选择公理，也不依赖“任何集合都不属于自身”这一额外断言。

3.11 为什么没有发生体系内部的矛盾

我们已经定义罗素类，却又证明它不能是集合。这并不矛盾。

定义

[ \operatorname{Rus}={x\mid x\notin x} ]

只是引入一个缩写，用来谈论满足条件的集合。若进一步断言存在集合 (r)，恰好收集所有这些对象，才会引出矛盾。

因此，不能对每个公式 (\phi(x)) 都无条件断言：

[ \exists a,\forall x, \bigl(x\in a\leftrightarrow\phi(x)\bigr). ]

取 (\phi(x)\equiv x\notin x)，这个断言便失败。

还有一个常见误区：既然

[ a\in\operatorname{Rus}\leftrightarrow a\notin a, ]

能否直接把 (a) 换成 (\operatorname{Rus})？

不能。该陈述中的 (a) 是取遍集合的对象变量，而罗素类不是集合项。

若按照本章对类隶属的定义解释

[ \operatorname{Rus}\in\operatorname{Rus}, ]

它要求首先存在表示罗素类的集合。我们已经证明这样的集合不存在，所以这个表达式为假，并不会重新产生矛盾。

本章练习

练习 1：自由变量

求下列公式的自由变量集合：

[ \forall x,\bigl(x\in y\to\exists y,(y\in z)\bigr). ]

练习 2：避免变量捕获

设：

[ \phi(x)\equiv\exists y,(x\in y\land y\in z). ]

求避免捕获的 (\phi[y/x])。

练习 3：两个位置的替换

证明：

[ (a=b\land c=d) \to (a\in c\leftrightarrow b\in d). ]

说明哪一步使用公理 1，哪一步使用等式定义。

练习 4：展开类记号

设：

[ A={x\mid\phi(x)}, \qquad B={y\mid\psi(y)}. ]

把以下表达式展开成不含类记号的公式：

[ a\in A, \qquad A\in b, \qquad A=B. ]

练习 5：真类不能作为元素

证明：若 (A) 是真类，则对任意可定义类 (B)，有：

[ A\notin B. ]

练习 6：判断错误所在

指出下面“证明”的错误：

对所有集合 (x)，有 (x\in V)。罗素类也是一个类，因此 (\operatorname{Rus}\in V)。

练习参考解答

1. 自由变量

自由变量集合是：

[ {y,z}. ]

(x\in y) 中的 (y) 是自由出现，内层 (\exists y) 只约束自己的作用范围，并不约束前面的 (y)。

2. 避免变量捕获

先把约束变量 (y) 改成新变量 (u)：

[ \phi(x)\equiv\exists u,(x\in u\land u\in z). ]

然后代入：

[ \phi[y/x] \equiv \exists u,(y\in u\land u\in z). ]

3. 两个位置的替换

假设 (a=b) 且 (c=d)。由公理 1 及相等的对称性：

[ a\in c\leftrightarrow b\in c. ]

由 (c=d) 的定义：

[ b\in c\leftrightarrow b\in d. ]

连接两个双条件，即得结论。

4. 展开类记号

分别为：

[ \phi(a), ]

[ \exists s, \left[ s\in b \land \forall z,(z\in s\leftrightarrow\phi(z)) \right], ]

[ \forall z,(\phi(z)\leftrightarrow\psi(z)). ]

所有代入均须避免捕获。

5. 真类不能作为元素

假设 (A\in B)。展开定义，存在一个集合表示 (A)，所以 (A) 是集合，与它是真类矛盾。故 (A\notin B)。

6. 错误所在

“所有集合都属于 (V)”中的量词只取遍集合，不能把真类作为对象变量的取值。

事实上，按照类隶属的定义：

[ \operatorname{Rus}\in V \quad\Longleftrightarrow\quad \operatorname{Rus}\text{ 是集合}. ]

罗素类是真类，因此：

[ \operatorname{Rus}\notin V. ]

第二章　类的基础性质

本章接着第一章，介绍无序对、有序对、并、交、幂集等基本构造，并依次引入配对公理、并集公理、幂集公理、替代公理模式和正则公理。

本章分为两节：第 4 节讨论类的基本构造与运算；第 5 节讨论限制量词、替代与分离、空集以及正则性。

我们继续使用以下约定：

• 小写字母 (a,b,x,y,\ldots) 表示集合。
• 大写字母 (A,B,\ldots) 表示可定义类，允许带集合参数。
• 类记号只是公式的缩写，不额外引入取遍所有类的对象变量。
• (A\in V) 表示类 (A) 能够由一个集合表示，即“(A) 是集合”。
• 等号沿用第一章的外延定义；公式中的相等替换已经得到证明。

本章所有结论都不需要选择公理。正则公理的类形式将按目录先陈述、暂缓证明；最后一个命题会明确指出对它的依赖。

4. 类的基本构造与运算

4.1 无序对与单元素类

对集合 (a,b)，定义：

[ {a,b} \coloneqq {x\mid x=a\lor x=b}. ]

这称为 (a,b) 的无序对。根据类的成员定义：

[ x\in{a,b} \leftrightarrow (x=a\lor x=b). ]

定义：

[ {a}\coloneqq{a,a}. ]

于是：

[ x\in{a} \leftrightarrow x=a. ]

({a}) 称为以 (a) 为唯一元素的单元素类；证明它是集合后，也称单元素集。

注意：

[ a\in{a}. ]

这里的 (a) 与 ({a}) 扮演不同角色：前者是元素，后者是以它为唯一元素的对象。不能因为记号相似就把它们混为一谈。

无序对的基本性质

由定义和命题逻辑：

[ {a,b}={b,a}. ]

因此，它不记录 (a,b) 的排列顺序。

重复列出元素不会改变类：

[ {a,a}={a}. ]

单元素类还能识别其唯一元素：

[ {a}={b} \leftrightarrow a=b. ]

证明。 若两类相等，由 (a\in{a}) 得 (a\in{b})，故 (a=b)。反方向由相等替换得到。证毕。

4.2 Axiom 2：配对公理

公理 2。

[ \forall a,\forall b,\bigl({a,b}\in V\bigr). \tag{A2} ]

即：

对任意两个集合，都存在一个集合，恰好以它们为元素。

展开类记号，就是：

[ \forall a,\forall b,\exists p,\forall x, \bigl(x\in p\leftrightarrow(x=a\lor x=b)\bigr). ]

这里要区分两个步骤：

1. 定义 ({a,b})，只是给一个条件起了名字。
2. 配对公理断言，满足这个条件的全部对象确实组成一个集合。

取 (b=a)，立即得到：

[ {a}\in V. ]

所以，从现在开始，无序对和单元素类都是已经得到存在性保证的集合。

配对公理的输入是集合。不能把真类代入 (a,b)，再据此断言“真类组成的无序对也是集合”。

4.3 Kuratowski 有序对

无序对不能区分先后顺序。为了编码“第一个对象是 (a)，第二个对象是 (b)”，定义：

[ \langle a,b\rangle \coloneqq \bigl{{a},{a,b}\bigr}. ]

这称为 Kuratowski 有序对。

由于 ({a}) 和 ({a,b}) 都是集合，再使用配对公理可得：

[ \langle a,b\rangle\in V. ]

这一定义是否合适，关键要看它能否唯一确定两个坐标。

定理 4.1　有序对的识别性质

[ \langle a,b\rangle=\langle c,d\rangle \leftrightarrow (a=c\land b=d). ]

证明。

若 (a=c) 且 (b=d)，由相等替换立即得到有序对相等。下面证明反方向。

假设：

[ \bigl{{a},{a,b}\bigr}

\bigl{{c},{c,d}\bigr}. ]

因为 ({a}) 属于左边，所以也属于右边。因此：

[ {a}={c} \quad\lor\quad {a}={c,d}. ]

第一种情形给出 (a=c)。第二种情形中，由 (c\in{c,d}={a})，也得到 (c=a)。

故必有：

[ a=c. ]

代入原等式：

[ \bigl{{a},{a,b}\bigr}

\bigl{{a},{a,d}\bigr}. ]

接着分两种情形。

情形一：(b=a)。

左边只有元素 ({a})。由于 ({a,d}) 属于右边，它必须等于 ({a})。于是 (d=a=b)。

情形二：(b\ne a)。

此时 ({a,b}\ne{a})。而 ({a,b}) 属于右边，因此只能有：

[ {a,b}={a,d}. ]

由 (b\in{a,d})，得到 (b=a\lor b=d)。排除 (b=a)，得 (b=d)。

所以两种情形下都有 (a=c) 且 (b=d)。证毕。

当两个坐标相同时，定义仍然有效：

[ \langle a,a\rangle

\bigl{{a}\bigr}. ]

上面的证明已经包括这种情况。

4.4 有限列举与有限有序组

对固定的正整数 (n)，定义：

[ {a_1,\ldots,a_n} \coloneqq {x\mid x=a_1\lor\cdots\lor x=a_n}. ]

这里的 (n) 暂时是我们在元语言中使用的普通有限计数，并不预设已经在集合论内部构造了自然数。

有限列举不记录顺序，也不记录重复次数。例如：

[ {a,b,a}={a,b}, ]

[ {a,b,c}={c,a,b}. ]

配对公理已经保证一个或两个元素的列举是集合。任意固定有限长度的情形，将在第 4.7 小节证明。

有限有序组

二元有序组使用刚才的有序对。对 (n\ge 3)，递归定义：

[ \langle a_1,\ldots,a_n\rangle \coloneqq \bigl\langle \langle a_1,\ldots,a_{n-1}\rangle, a_n \bigr\rangle. ]

例如：

[ \langle a,b,c\rangle

\langle\langle a,b\rangle,c\rangle. ]

若需要一元记号，可约定：

[ \langle a\rangle\coloneqq a. ]

这样，递归式也适用于 (n=2)。

对每个固定的正整数 (n)，反复使用定理 4.1，得到：

[ \langle a_1,\ldots,a_n\rangle

\langle b_1,\ldots,b_n\rangle \leftrightarrow \bigwedge_{i=1}^{n}a_i=b_i. ]

这里比较的是相同长度的有序组。当前编码没有另加“长度标签”，不能据此断言不同长度的有序组永远不相等。

4.5 一个类的并

对任意可定义类 (A)，定义：

[ \cup(A) \coloneqq {x\mid\exists y,(x\in y\land y\in A)}. ]

读作“(A) 的并”。

它收集的是：属于 (A) 的某个元素的所有元素。即：

[ x\in\cup(A) \leftrightarrow \exists y,(y\in A\land x\in y). ]

这里有两层隶属：

[ x\in y, \qquad y\in A. ]

不能仅凭这两层关系就推出 (x\in A)。隶属关系本身不具有一般的传递性。

例如：

[ \cup({a})=a. ]

证明。 对任意集合 (x)：

[ \begin{aligned} x\in\cup({a}) &\leftrightarrow \exists y,(x\in y\land y=a)\ &\leftrightarrow x\in a. \end{aligned} ]

由外延相等得到结论。证毕。

4.6 Axiom 3：并集公理

公理 3。

[ \forall a,\bigl(\cup(a)\in V\bigr). \tag{A3} ]

即：

一个集合的所有元素所具有的元素，可以收集成一个集合。

展开为：

[ \forall a,\exists u,\forall x, \left[ x\in u \leftrightarrow \exists y,(x\in y\land y\in a) \right]. ]

公理的输入必须是集合。对任意类 (A)，(\cup(A)) 都可以作为类记号使用，但 A3 不保证它一定是集合。

4.7 两个类的并与交

定义：

[ A\cup B \coloneqq {x\mid x\in A\lor x\in B}, ]

[ A\cap B \coloneqq {x\mid x\in A\land x\in B}. ]

所以：

[ x\in A\cup B \leftrightarrow (x\in A\lor x\in B), ]

[ x\in A\cap B \leftrightarrow (x\in A\land x\in B). ]

注意两个并记号的区别：

• (\cup(A)) 对一个类作运算，收集其成员的元素。
• (A\cup B) 收集属于两个类中至少一个类的对象。

对集合 (a,b)，二者有如下联系：

[ a\cup b=\cup({a,b}). ]

因此，由配对公理和并集公理：

[ a\cup b\in V. ]

交的集合存在性将在第 5.3 小节的分离公理模式处得到证明。

有限列举是集合

现在可以补上：

[ {a_1,\ldots,a_n}\in V ]

对每个固定正整数 (n) 都成立。

单元素情形已知。若前 (n) 个对象的列举是集合，则：

[ {a_1,\ldots,a_n,a_{n+1}}

{a_1,\ldots,a_n}\cup{a_{n+1}} ]

也是集合。

这是元语言中对有限构造长度的归纳，不需要本章预先构造自然数集。

并与交的基本运算律

对任意可定义类 (A,B,C)，有交换律：

[ A\cup B=B\cup A, \qquad A\cap B=B\cap A; ]

结合律：

[ (A\cup B)\cup C=A\cup(B\cup C), ]

[ (A\cap B)\cap C=A\cap(B\cap C); ]

幂等律：

[ A\cup A=A, \qquad A\cap A=A; ]

分配律：

[ A\cap(B\cup C)

(A\cap B)\cup(A\cap C), ]

[ A\cup(B\cap C)

(A\cup B)\cap(A\cup C). ]

这些都由对应的命题逻辑等价式得到。例如：

[ \begin{aligned} x\in A\cap(B\cup C) &\leftrightarrow x\in A\land(x\in B\lor x\in C)\ &\leftrightarrow (x\in A\land x\in B) \lor (x\in A\land x\in C)\ &\leftrightarrow x\in(A\cap B)\cup(A\cap C). \end{aligned} ]

这也是证明类等式的常用方法：把成员条件展开，再用逻辑等价式整理。

4.8 包含与真包含

定义：

[ A\subseteq B ;\coloneqq; \forall x,(x\in A\to x\in B). ]

读作“(A) 包含于 (B)”或“(A) 是 (B) 的子类”。当两者都是集合时，称 (A) 为 (B) 的子集。

定义真包含：

[ A\subset B ;\coloneqq; (A\subseteq B\land A\ne B). ]

本章使用 (\subset) 专门表示真包含。

包含的基本性质

[ A\subseteq A, ]

[ (A\subseteq B\land B\subseteq C)\to A\subseteq C, ]

[ A=B \leftrightarrow (A\subseteq B\land B\subseteq A). ]

最后一个等价式说明：证明两个类相等，也可以分别证明两个包含方向。

并与交满足：

[ A\cap B\subseteq A, \qquad A\cap B\subseteq B, ]

[ A\subseteq A\cup B, \qquad B\subseteq A\cup B. ]

此外：

[ A\subseteq B \leftrightarrow A\cap B=A \leftrightarrow A\cup B=B. ]

必须区别：

[ a\in b ]

与

[ a\subseteq b. ]

前者说 (a) 是 (b) 的一个元素；后者说 (a) 的每个元素都属于 (b)。

4.9 幂集

对集合 (a)，定义：

[ \mathcal P(a) \coloneqq {x\mid x\subseteq a}. ]

这称为 (a) 的幂集类。

因此：

[ x\in\mathcal P(a) \leftrightarrow x\subseteq a. ]

这里 (x) 是集合变量，所以该类收集的是 (a) 的所有集合子集。

4.10 Axiom 4：幂集公理

公理 4。

[ \forall a,\bigl(\mathcal P(a)\in V\bigr). \tag{A4} ]

展开为：

[ \forall a,\exists p,\forall x, \left[ x\in p \leftrightarrow \forall z,(z\in x\to z\in a) \right]. ]

即：

一个集合的所有集合子集组成一个集合。

由自包含性：

[ a\in\mathcal P(a). ]

若 (a\subseteq b)，则：

[ \mathcal P(a)\subseteq\mathcal P(b). ]

证明。 若 (x\in\mathcal P(a))，则 (x\subseteq a)。由 (a\subseteq b) 得 (x\subseteq b)，故 (x\in\mathcal P(b))。证毕。

还可得到：

[ \cup(\mathcal P(a))=a. ]

证明。

若 (x\in\cup(\mathcal P(a)))，则存在 (y\subseteq a)，使 (x\in y)，从而 (x\in a)。

反之，若 (x\in a)，则单元素集 ({x}\subseteq a)，所以：

[ {x}\in\mathcal P(a). ]

由 (x\in{x})，得到 (x\in\cup(\mathcal P(a)))。证毕。

第 4 节练习

练习 4.1：无序对的相等

证明：

[ {a,b}={c,d} \leftrightarrow \bigl((a=c\land b=d)\lor(a=d\land b=c)\bigr). ]

证明须包括元素发生重复的情形。

练习 4.2：有序对的集合编码

证明：

[ \cup(\langle a,b\rangle)={a,b}, ]

并进一步证明：

[ \cup\bigl(\cup(\langle a,b\rangle)\bigr)=a\cup b. ]

练习 4.3：幂集与包含

对集合 (a,b)，证明：

[ a\subseteq b \leftrightarrow \mathcal P(a)\subseteq\mathcal P(b). ]

第 4 节练习参考解答

练习 4.1 解答

反方向由定义立即成立。

正方向假设 ({a,b}={c,d})。由 (a\in{c,d})，分两种情形。

若 (a=c)，则：

[ {a,b}={a,d}. ]

若 (b=a)，左边为单元素集，故 (d=a=b)。若 (b\ne a)，由 (b\in{a,d}) 得 (b=d)。所以第一种情形给出 (a=c\land b=d)。

若 (a=d)，同理得到 (b=c)，给出第二个合取式。

练习 4.2 解答

由定义：

[ \begin{aligned} x\in\cup(\langle a,b\rangle) &\leftrightarrow x\in{a}\lor x\in{a,b}\ &\leftrightarrow x=a\lor x=b. \end{aligned} ]

所以：

[ \cup(\langle a,b\rangle)={a,b}. ]

再取一次并：

[ \cup\bigl(\cup(\langle a,b\rangle)\bigr)

\cup({a,b})

a\cup b. ]

练习 4.3 解答

正方向已在第 4.10 小节证明。

反方向，若 (\mathcal P(a)\subseteq\mathcal P(b))，由：

[ a\in\mathcal P(a) ]

得到：

[ a\in\mathcal P(b), ]

即 (a\subseteq b)。

5. 替代、分离与正则性

5.1 限制量词

为了简化书写，定义：

[ \forall x\in A,\phi(x) ;\coloneqq; \forall x,(x\in A\to\phi(x)), ]

[ \exists x\in A,\phi(x) ;\coloneqq; \exists x,(x\in A\land\phi(x)). ]

这里默认类记号 (A) 不以被量化的 (x) 为自由参数；有冲突时先改名。

全称限制量词使用蕴含，存在限制量词使用合取。这两者不能混写。

例如：

[ A\subseteq B \leftrightarrow \forall x\in A,(x\in B), ]

[ x\in\cup(A) \leftrightarrow \exists y\in A,(x\in y). ]

其否定规律是：

[ \neg\forall x\in A,\phi(x) \leftrightarrow \exists x\in A,\neg\phi(x), ]

[ \neg\exists x\in A,\phi(x) \leftrightarrow \forall x\in A,\neg\phi(x). ]

限制量词没有改变对象变量的取值范围；它仍然只是原有一阶公式的缩写。

5.2 Axiom Schema 5：替代公理模式

设 (\phi(x,y,\vec p)) 是公式，(\vec p) 表示允许出现的集合参数。

公理模式 5。

[ \left[ \forall x,\forall y,\forall z, \bigl( (\phi(x,y,\vec p)\land\phi(x,z,\vec p)) \to y=z \bigr) \right] \to \left[ {y\mid\exists x\in a,\phi(x,y,\vec p)}\in V \right]. \tag{A5} ]

其中 (a) 和所有参数都作全称量化；用于代入和量化的变量均须避免捕获。

前提的含义是：

每个输入 (x) 至多对应一个输出 (y)。

结论的含义是：

当输入限制在集合 (a) 内时，所有实际得到的输出组成一个集合。

这里要求的是“至多一个”，没有要求每个输入都必须有输出。因此，本章采用的是允许部分对应的替代模式。

有些教材把替代写成“对定义域中的每个输入恰有一个输出”的版本；这里严格按目录使用上述形式。

为什么称为公理模式

(\phi) 可以取不同公式，每个公式都给出一个公理实例。ZF 的对象变量不取遍公式，因此这不是用一个对象量词“对所有公式”写成的单一公理。

一个简单例子

取：

[ \phi(x,y)\equiv y={x}. ]

每个 (x) 都唯一确定单元素集 ({x})，所以 A5 给出：

[ {y\mid\exists x\in a,(y={x})}\in V. ]

也就是说，把集合 (a) 的每个元素换成它的单元素集，所得输出仍然组成集合。

这里的 (y={x}) 可以展开为：

[ \forall z,(z\in y\leftrightarrow z=x), ]

所以这确实是原语言公式的缩写。

5.3 从替代推出分离

定理 5.1　Zermelo 分离公理模式

对任意集合 (a) 和任意可定义类 (A)，有：

[ a\cap A\in V. ]

设：

[ A={x\mid\psi(x,\vec p)}. ]

这个结论展开为：

[ \exists b,\forall y, \bigl( y\in b \leftrightarrow (y\in a\land\psi(y,\vec p)) \bigr). ]

它说：

可以从一个已有集合中，筛选出满足某个公式条件的元素，所得仍然是集合。

证明。 在 A5 中取：

[ \phi(x,y,\vec p) \equiv (x=y\land\psi(x,\vec p)). ]

若 (\phi(x,y,\vec p)) 与 (\phi(x,z,\vec p)) 同时成立，则 (y=x=z)，所以唯一性前提成立。

于是：

[ b\coloneqq {y\mid \exists x\in a, (x=y\land\psi(x,\vec p)) } ]

是集合。

对任意 (y)，由相等替换：

[ \begin{aligned} y\in b &\leftrightarrow \exists x\in a, (x=y\land\psi(x,\vec p))\ &\leftrightarrow y\in a\land\psi(y,\vec p)\ &\leftrightarrow y\in a\cap A. \end{aligned} ]

故 (b=a\cap A)，所以 (a\cap A\in V)。证毕。

这一证明使用了 A5 允许某些输入没有输出的特点：不满足 (\psi) 的输入不产生输出。

推论：集合的可定义子类仍是集合

若：

[ A\subseteq a, ]

其中 (a) 是集合，则：

[ A=a\cap A, ]

因此：

[ A\in V. ]

特别地，对集合 (a,b)：

[ a\cap b\in V. ]

分离并不允许直接断言：

[ {x\mid\psi(x)}\in V. ]

它要求先有一个集合 (a)，再从 (a) 内进行筛选。这个限制正是它与无约束概括之间的区别。

5.4 差类

定义：

[ A\setminus B \coloneqq {x\mid x\in A\land x\notin B}. ]

它收集属于 (A)、但不属于 (B) 的对象。

立即得到：

[ A\setminus B\subseteq A. ]

若左边的 (A) 是集合 (a)，则由分离：

[ a\setminus B\in V. ]

这里右边的 (B) 可以是真类。

由成员条件还可验证：

[ A\setminus(B\cup C)

(A\setminus B)\cap(A\setminus C), ]

[ A\setminus(B\cap C)

(A\setminus B)\cup(A\setminus C), ]

[ A=(A\cap B)\cup(A\setminus B). ]

5.5 空类与空集

定义：

[ 0\coloneqq{x\mid x\ne x}. ]

因为每个集合都满足 (x=x)，所以：

[ \forall x,(x\notin 0). ]

因此，(0) 是没有元素的类，称为空类。

此处的 (0) 是空对象的记号；本章不进一步讨论它作为自然数的角色。

定理 5.2　空类是集合

[ 0\in V. ]

证明。 第一章的一阶逻辑采用非空论域，因此可以取一个集合 (a)。由分离：

[ {x\in a\mid x\ne x} ]

是集合。

没有对象满足 (x\ne x)，所以这个集合恰好等于 (0)。故 (0\in V)。证毕。

从现在开始，可以称 (0) 为空集。

空集是唯一的：若集合 (b) 没有元素，则对任意 (x)：

[ x\in b\leftrightarrow x\in 0, ]

故 (b=0)。

空集的基本性质

对任意类 (A)：

[ 0\subseteq A, ]

[ A\cup0=A, \qquad A\cap0=0, ]

[ A\setminus0=A, \qquad A\setminus A=0. ]

其中 (0\subseteq A) 来自：

[ \forall x,(x\in0\to x\in A). ]

由于前件永远不成立，这个全称蕴含成立。

还可得到：

[ A=0 \leftrightarrow \neg\exists x,(x\in A), ]

以及在经典逻辑下：

[ A\ne0 \leftrightarrow \exists x,(x\in A). ]

特别注意：

[ 0\ne{0}. ]

因为 (0) 没有元素，而 (0\in{0})。

此外：

[ \mathcal P(0)={0}. ]

理由是 (x\subseteq0) 当且仅当 (x) 没有元素，也就是 (x=0)。

5.6 Axiom 6：正则公理

公理 6。

[ \forall a, \left[ a\ne0 \to \exists x\in a,(x\cap a=0) \right]. \tag{A6} ]

也称基础公理。

它说：

每个非空集合 (a) 都有一个元素 (x)，使 (x) 与 (a) 没有共同元素。

将限制量词展开：

[ a\ne0 \to \exists x, \bigl(x\in a\land x\cap a=0\bigr). ]

而：

[ x\cap a=0 ]

等价于：

[ \neg\exists y,(y\in x\land y\in a). ]

因此，这个 (x) 在 (a) 内部没有更低一层的成员。我们称它为 (a) 的一个 (\in)-极小元素。

“极小”不意味着唯一，也不意味着 (x=0)。它只要求 (x) 的元素都不在 (a) 里面。

5.7 正则公理的类形式

完整 ZF 中还可证明下面的加强形式：

[ A\ne0 \to \exists x\in A,(x\cap A=0). ]

其中 (A) 是任意可定义类，可以是真类。

它说：

每个非空可定义类，都有一个 (\in)-极小元素。

这仍应理解为关于定义 (A) 的公式的定理模式，不是对所有类作对象量化。

本章暂不证明这个加强形式。 它不能通过把 A6 中的集合变量 (a) 直接换成真类 (A) 得到；标准证明需要本章尚未建立的辅助构造。

下面关于自隶属和有限隶属环的结论，只使用集合形式 A6。第 5.11 小节的定理 5.6 则会使用这里陈述的类形式，其证明依赖也据此保留。

5.8 集合不属于自身

定理 5.3

对任意集合 (a)：

[ a\notin a. ]

证明。 反设：

[ a\in a. ]

由配对公理，({a}) 是集合；又因为 (a\in{a})，它非空。

对 ({a}) 使用正则公理，存在：

[ x\in{a} ]

使得：

[ x\cap{a}=0. ]

由 (x\in{a}) 得 (x=a)，所以：

[ a\cap{a}=0. ]

但假设给出 (a\in a)，而 (a\in{a})，故：

[ a\in a\cap{a}, ]

与该交为空矛盾。证毕。

与第一章罗素类的联系

第一章定义：

[ \operatorname{Rus}

{x\mid x\notin x}. ]

现在每个集合都满足 (x\notin x)，所以：

[ \operatorname{Rus}=V. ]

第一章证明罗素类是真类，并不需要正则公理；现在正则公理进一步说明，全域类中的每个集合都满足罗素类的定义条件。

5.9 不存在有限隶属环

定理 5.4

对任意固定正整数 (n)：

[ \neg \bigl( a_1\in a_2 \land a_2\in a_3 \land\cdots\land a_n\in a_1 \bigr). ]

当 (n=1) 时，这就是 (a_1\notin a_1)。

证明。 反设存在这样的环。令：

[ s={a_1,\ldots,a_n}. ]

有限列举的集合存在性已在第 4.7 小节证明，且 (s\ne0)。

由正则公理，存在 (x\in s)，使：

[ x\cap s=0. ]

因为 (x\in s)，存在某个 (i)，使 (x=a_i)。

若 (i>1)，环上的前一个对象满足：

[ a_{i-1}\in a_i=x, \qquad a_{i-1}\in s. ]

故：

[ a_{i-1}\in x\cap s, ]

矛盾。

若 (i=1)，则由：

[ a_n\in a_1=x, \qquad a_n\in s ]

同样得到矛盾。证毕。

证明不要求这些 (a_i) 两两不同。即使列表中有重复，也一样成立。

特别地：

[ \neg(a\in b\land b\in a). ]

这个定理讨论固定有限长度的环，不在这里扩展到无限序列的讨论。

5.10 全域类不属于自身

定理 5.5

[ V\notin V. ]

证明。 先证明 (V) 不可能是集合。

反设存在集合 (v) 表示 (V)。由于 (V) 包含每个集合，尤其包含 (v)，所以：

[ v\in V. ]

由 (v=V) 的成员等价性，得到：

[ v\in v, ]

与定理 5.3 矛盾。因此 (V) 是真类。

第一章已经说明：

[ A\in V \leftrightarrow A\text{ 是集合}. ]

取 (A=V)，便得到：

[ V\notin V. ]

证毕。

不能直接在“对所有集合 (a)，(a\notin a)”中代入真类 (V)。上面的论证先假设它由集合表示，再对那个集合应用定理，因而没有越过变量的取值范围。

5.11 包含其所有集合子集的类必为 (V)

最后考虑一个类 (A)，满足：

[ \forall x,(x\subseteq A\to x\in A). ]

这里 (x) 是集合变量。条件的意思是：

凡是元素全部属于 (A) 的集合，它自己也属于 (A)。

定理 5.6

[ \left[ \forall x,(x\subseteq A\to x\in A) \right] \to A=V. ]

以下证明使用第 5.7 小节陈述、暂未证明的正则公理类形式。

证明。 假设：

[ \forall x,(x\subseteq A\to x\in A). ]

反设 (A\ne V)。因为 (A) 的成员都是集合，(A\subseteq V)，所以：

[ B\coloneqq V\setminus A ]

非空。

对非空类 (B) 使用正则公理的类形式，得到集合 (b)，满足：

[ b\in B, \qquad b\cap B=0. ]

我们证明：

[ b\subseteq A. ]

取任意 (y\in b)。由于 (y) 是集合，(y\in V)。若 (y\notin A)，则：

[ y\in V\setminus A=B. ]

于是 (y\in b\cap B)，与交为空矛盾。因此 (y\in A)。

因为 (y\in b) 是任取的，所以 (b\subseteq A)。再由题设条件：

[ b\in A. ]

但 (b\in B=V\setminus A) 又说明 (b\notin A)，矛盾。

故 (A=V)。证毕。

这一证明的关键是：如果存在不属于 (A) 的集合，就取其中一个 (\in)-极小者。它的每个元素都已属于 (A)，题设便迫使它自己也属于 (A)。

第 5 节练习

练习 5.1：包含关系

证明：

[ A\subseteq B \leftrightarrow A\setminus B=0. ]

练习 5.2：分离与罗素论证

对任意集合 (a)，令：

[ r={x\in a\mid x\notin x}. ]

不用正则公理，证明 (r\notin a)。

再说明，引入正则公理后，为什么 (r=a)。

练习 5.3：区分空集与单元素集

求：

[ \cup(0), \qquad \cup({0}), \qquad \mathcal P(0), \qquad \mathcal P({0}). ]

练习 5.4：正则公理的应用

证明：

[ a\in b\to b\not\subseteq a. ]

练习 5.5：定理 5.6 中的空集

若类 (A) 满足：

[ \forall x,(x\subseteq A\to x\in A), ]

不使用正则公理，先证明：

[ 0\in A. ]

第 5 节练习参考解答

练习 5.1 解答

[ \begin{aligned} A\setminus B=0 &\leftrightarrow \neg\exists x,(x\in A\land x\notin B)\ &\leftrightarrow \forall x,(x\in A\to x\in B)\ &\leftrightarrow A\subseteq B. \end{aligned} ]

练习 5.2 解答

由分离，(r) 是集合，并满足：

[ x\in r \leftrightarrow (x\in a\land x\notin x). ]

反设 (r\in a)。代入 (x=r)，得到：

[ r\in r\leftrightarrow r\notin r, ]

矛盾。因此 (r\notin a)。

引入正则公理后，由定理 5.3，每个集合 (x) 都满足 (x\notin x)，所以：

[ x\in r\leftrightarrow x\in a, ]

即 (r=a)。

练习 5.3 解答

[ \cup(0)=0, ]

[ \cup({0})=0, ]

[ \mathcal P(0)={0}, ]

[ \mathcal P({0})={0,{0}}. ]

最后一个等式成立，是因为 ({0}) 的子集或者不含 (0)，从而为空集；或者含 (0)，从而就是 ({0})。

练习 5.4 解答

假设 (a\in b) 且 (b\subseteq a)。由包含关系，把 (a\in b) 代入可得：

[ a\in a, ]

与定理 5.3 矛盾。因此：

[ a\in b\to b\not\subseteq a. ]

练习 5.5 解答

对任意类 (A)，都有：

[ 0\subseteq A. ]

将集合 (0) 代入题设条件，立即得到：

[ 0\in A. ]