一些集合论内容的笔记

Abstract. 因为本学期的离散数学课程讲了一些集合论但是留了很多悬念，所以将暑假时候学习的一些集合论笔记整理之后发出。本篇笔记参考 李文威，代数学方法（第一卷）基础架构，高等教育出版社（2019） 的第一章，刨去了 1.5 Grothendieck 宇宙 一节，因为我也没有看懂。

本文中的观点相比真正的公理化集合论尚属表层，有很多问题在这一层次难以解决，但仅作诸如离散数学、代数与分析之类科目的前置已经足够，仅供参考。

• ZFC 公理
• 序结构
• 超穷递归
• 基数

ZFC 公理

在公理化的集合论中，一切的物件都是集合，集合之间定义了一个二元谓词 $\in$ 用以一个集合是否是另一个集合中的元素。用下面的公理系统定义出集合之后，可以在上层定义常见的谓词或者二元运算诸如 $\subset, \cap, \cup, \setminus$ 等等。不交集合的并写作 $\sqcup$，可能不是很常见，特此声明。这些东西的定义即使充分地形式化也相当符合日常习惯，因此省略不写。

本节中我们所有的公理用尽可能清晰的自然语言叙述，因为形式化的工作是琐碎且降低直观性的。

A1（外延公理）. 两集合相等当且仅当其有相同的元素。

A2（配对公理）. 对于任意的 $x, y$，存在一个集合 $\{x, y\}$，其元素恰好为 $x$ 和 $y$。这里需要一些形式化：

$$
\forall x. \forall y. \exists \{x, y\}. \forall a. a\in \{x, y\}\rightarrow a = x\vee a = y
$$

A3（分离公理模式）. 给定谓词 $P$，则对于任意集合 $X$ 都存在 $Y = \{u\in X : P(u)\}$。

A4（并集公理）. 对于任意集合 $X$，存在相应的并集

$$
\cup_{v\in X}v := \{u : \exists v\in X, u\in v\}
$$

A5（幂集公理）. 对于任意集合 $X$，存在其幂集

$$
P(x) := \{x : x\subset X\}
$$

A6（无穷公理）. 存在归纳集 $X$。因为其并非显式列举的，我们被迫用一阶语言来描述这个集合 $X$ 的存在性。

$$
\exists X. (\varnothing \in X) \wedge (\forall y. y\in X \rightarrow y \cup \{y\}\in X)
$$

A7（替换公理模式）. 给定函数 $F: X\rightarrow Y$ 和集合 $X$，存在集合

$$
F(X) = \{F(X) : x\in X\}
$$

A8（正则公理）. 任意非空集存在对于关系 $\in$ 极小的元。

下一条公理是可选的。

A9（选择公理）. $X$ 的所有元素均非空，则存在选择函数。用一阶语言来描述就是

$$
\exists g. (g : X \rightarrow \cup_{x\in X} x) \wedge (x\in X, g(x)\in x)
$$

集中对于上述公理中的一些可能的问题做一些解释。

• A3 和 A7 被称为公理模式，类似于 C++ 中的模板：以 A3 为例，每提供一个谓词 $P$，产生一条分离公理。这是因为在一阶逻辑中，量词不能作用在谓词上。所以我们被迫定义无穷条公理模式。

• 分离公理中的”函数“可以由一阶语言定义，本质是是满足下述条件的二元谓词 $\varphi$：

  $$
  \forall x. \exists !y. \varphi(x, y)
  $$

  因此没有循环论证。

• A2 没有要求 $x\ne y$。如果取 $x = y$，相当于对于任意元素，可以在外面加一层大括号。

关于 A9 我们再额外做一些说明。

选择公理事实上断言了一个集合（选择函数 $F$）的存在性，但是没有进行显示构造。

但是并非所有的选择问题都要用到选择函数。例如：

• 你现在有一个 / 有限个集合（这里“有限”没有严格定义，我们不严格地说成可以对集合个数做归纳），现在要构造选择函数。这个选择函数的存在性证明可以由 A8 正则公理给出。
• 你现在有“无限多的”集合，即使每个集合当中的元素都是有限的，也需要选择公理才能拿到选择函数。你可以试着想象几条可能的路径，但会发现都有问题。

在上述公理体系下可以定义一些简单的结构。

定义 1.1（空集）. 给定任意集合 $S$，定义空集

$$
\varnothing := \{u \in S : u\ne u\}
$$

Remark. 上述定义给出了空集的一个代表元。在一阶逻辑层面空集的定义是

$$
\forall x, x\in\varnothing \leftrightarrow\bot
$$

其存在性证明可以直接用分离公理模式接上一些谓词演算完成。而 1.1 定义出的空集事实上和这个形式定义一致。

定理 1.2. 空集是存在的，且无关乎 $S$ 的选取。

证明. 空集的唯一性由 A1 可以推出，中途需要用到 ex falso quodlibet。

定义 1.3（二元组）. 对于元素 $x, y$，定义二元组

$$
(x, y) := \{x, \{x, y\}\}
$$

这个集合依据配对公理存在。

定义 1.4（笛卡尔积）. 对于集合 $X, Y$，定义其笛卡尔积

$$
X\times Y = \{(x, y) : x\in X, y\in Y\}
$$

定理 1.5. 笛卡尔积 $(x, y)$ 是集合。

证明. 定义一个从 $Y$ 到所有二元组二元组的映射 $F$：

$$
F : y\mapsto (x_0, y)
$$

根据替换公理模式存在第一维是 $x_0$，第二维遍历 $y$ 的有序对集合 $S_{x_0}$。根据并集公理

$$
\cup_{x\in X} S_{x}
$$

存在，这实际上就是 $X\times Y$。

对于一些对象构成的、无法用 ZFC 公理生成的总体，称为真类

Remark. 在 ZFC 中谈论真类十分吃力。这里所谓的“生成”虽直观但并不妥当。事实上 ZFC 公理是一套定义在一阶逻辑上的结构，你可以感性地理解为它是在钦定一个客观存在的论域 $\Omega$（即“全体集合”）内部的性质，而不能说它生成了什么东西。可以认为从这里开始，下面的语言都是不严谨但是一定程度上正确的。

定理 1.6（Russell’s Paradox）. 所有集合构成真类。

证明. 若所有集合构成集合 $\mathbf{Set}$，那么根据分离公理模式，下面的集合存在：

$$
S := \{x \in \mathbf{Set} : x\notin x\}
$$

此时无论 $S$ 是否属于自身都将导出矛盾。

Remark. 事实上这个定理仍然可以在一阶语言层面严谨地形式化为

$$
(\exists \mathbf{Set}, \forall y, y\in \mathbf{Set})\rightarrow \bot
$$

但是如你所见这个定理非常无聊，直接做谓词演算的证明也无需构造上述集合。但是构造一个罗素悖论状物是证明中常用的手法，这才是上述证明的价值所在。

序结构

定义 2.1（偏序集）. 一个偏序集系指一个集合 $P$ 和其上定义的一个二元关系 $\leq$，满足

1. （自反性）$\forall x\in P. x \leq x$；
2. （传递性）$\forall x, y, z\in P. x\leq y \wedge y\leq z \rightarrow x\leq z$；
3. （反对称性）$\forall x, y\in P. x\leq y \wedge y\leq x \rightarrow x = y$。

仅满足 $(1), (2)$ 的集合称为预序集。若偏序集中任两元素均可比大小，称为全序集。

今后我们通常将二元关系省略不写，直接称 $P$ 是偏序集。$\leq$ 的定义可以从上下文看出。

定义 2.2. $P\rightarrow Q$ 的函数 $f$ 称为保序的，若满足

$$
\forall x, y\in P, x\leq y \rightarrow f(x)\leq f(y)
$$

若 $\phi$ 为预序集 $P, Q$ 间的双射，且其自身和其逆都保序，则称 $\phi$ 为 $P, Q$ 间的同构。预序集在同构意义下的等价类称为序型。

针对预序集可以定义极大小元、上下界、上下确界等概念，均与直观想象的一致，这里默认读者已经知道。

定义 2.3（良序集）. $P$ 是全序集，且任意 $P$ 的非空子集都有极小元，则 $P$ 称为良序集。

良序集的每一个集合都自带一个选择函数（选出极小元），因此很多从良序性质出发的定理无需依靠选择公理即可证明。

引理 2.4. $P$ 为良序集，$\phi$ 为一严格递增的函数，则有

$$
\forall x. \phi(x)\geq x
$$

这同时蕴含：

1. $P$ 没有非平凡的自同构。
2. 不存在 $P$ 到 $P_{<x} := \{y\in P : y < x\}$（称为 $P$ 的一个前段）的同构。

证明. 定义违反限制的集合

$$
S := \{x\in P, \phi(x) < x\}
$$

若 $S$ 不是空集，由于 $P$ 良序，$S$ 有极小元 $x$。此时无论 $\phi(x)$ 是否属于 $x$ 均导出矛盾，因此总断言成立。后面两条子断言的证明是习题难度，因此不写证明。

定义 2.5（传递集）. 若 $\alpha$ 为集合且 $\alpha \subset P(\alpha)$，则称 $\alpha$ 是传递集。（形象地说，就是 $\forall x. x\in \alpha \rightarrow x \subset\alpha$）

此时“传递”这个词出现了歧义（2.5 和 2.1.2）。我们在描述 2.5 中定义的传递集时，必然完整的写出“传递集”三个字。其余时候提到的传递性都是某偏序集中二元关系具有的性质。

定义 2.6（序数）. $\alpha$ 为传递集，且与 $\in$ 构成良序集，则称 $\alpha$ 为序数。

$\varnothing$ 依照定义就是序数。此外显然 $\alpha$ 是序数则 $\alpha\sqcup \{\alpha\}$ 是序数。前几个序数依次是

$$
\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}, …
$$

当然上面说的“前”和序数的枚举都不是显然的。先证明以下引理

引理 2.6.

1. $\alpha$ 是序数，$\beta\in \alpha$，那么 $\beta$ 是序数；
2. $\alpha, \beta$ 都是序数，$\alpha \subsetneq \beta$ 则 $\alpha \in \beta$；
3. $\alpha, \beta$ 都是序数，则 $\alpha\subset \beta \vee\beta\subset \alpha$。

证明.

1. $\beta$ 的良序性可以直接从 $\alpha$ 的良序性导出。难点是证明 $\beta$ 也是传递集。考虑 $x\in \beta$，要证明 $x\subset \beta$，即

   $$
   \forall y\in x. y\in \beta
   $$

   $\alpha$ 的传递性给出 $x, y, \beta\in \alpha$，而 $\alpha$ 的良序性（具体地，是 $\in$ 的传递性）给出了上述欲证明的关系。

2. 我们断言 $\alpha = \min \beta \setminus \alpha$。简便起见将 RHS 记为 $\gamma$。

   $\alpha \subset \gamma$：考虑 $x\in \alpha$，显然 $x\ne \gamma$，那么显然 $x\in \gamma$ 或者 $\gamma \in x$，因为 $\alpha$ 为良序，任意两元素都可比。我们只需要排除 $\gamma \in x$。若 $\gamma\in x$，那么 $\gamma\in \alpha$（$\in$ 的传递性），这与 $\gamma = \min \color{red}{\beta\setminus \alpha}$ 矛盾。

   $\gamma \subset \alpha$：考虑 $x\in \gamma$，由于 $\gamma$ 是极小元，有 $\gamma \notin \beta\setminus \alpha$。另外 $\gamma \in \beta$（$\beta$ 是传递集），只能是 $x\in \alpha$。

3. 令 $\gamma = \alpha\cap \beta$。只需要证明 $\gamma = \alpha \vee\gamma = \beta$。

   使用反证法，假设 $\gamma \ne \alpha \wedge \gamma \ne \beta$。此时有 $\gamma \subsetneq \alpha \wedge \gamma \subsetneq \alpha$，根据本引理第二条断言，$\gamma \in \alpha \cap \beta = \gamma$，导出矛盾。

序数类简记为 $\mathbf{On}$，稍后再证明 $\mathbf{On}$ 是真类。由于 $\in$ 已经成为序数类上非常自然的二元关系，接下来将 $\in$ 都记作 $<$。

引理自然导出

定理 2.7.

1. $<$ 定义了 $\mathbf{On}$ 上的全序。序数 $\alpha$ 无非是 $\{\beta : \beta < \alpha\}$。
2. $C$ 为序数构成的非空类，则 $\inf C := \cap C$ 是序数，必有 $\inf C\in C$。另有 $\alpha\cup \{\alpha\} = \inf \{\beta : \beta > \alpha\}$。
3. $S$ 为序数构成的非空集，则 $\sup C := \cup S$ 是序数。

根据 2.7.2 定义序数 $\alpha$ 的后继为 $\alpha + 1 := \alpha \cup \{\alpha\}$。对于 $\alpha$，若不存在 $\beta$ 使得 $\alpha = \beta + 1$，则称 $\alpha$ 为极限序数。$0$ 依照定义成为极限序数。最小的非零极限序数记为 $\omega$（形象地理解，$\omega = \mathbb{N}$），$<\omega$ 的序数成为有限序数。

命题 2.8. $\mathbf{On}$ 是真类。

证明. 若其为集合，则根据 2.7.3 有 $\sup \mathbf{On} + 1$ 是序数，且有

$$
\sup \mathbf{On} + 1 > \sup \mathbf{On} \geq \sup \mathbf{On} + 1
$$

从而导出矛盾。

超穷递归

很多问题在允许使用归纳法的情况下会变得容易，然而常见的整数归纳法直接施加于序数，容易引发可数性相关的问题。因此需要为序数类定制专门的归纳法。

定理 3.1（超穷归纳法）. 假设 $C$ 为序数构成的类，满足

1. $0\in C$；
2. $\alpha \in C \rightarrow \alpha + 1 \in C$；
3. $\alpha$ 为极限序数，$(\forall \beta < \alpha. \beta \in C) \rightarrow \alpha \in C$。

那么 $C = \mathbf{On}$。

证明. 定理 2.7.2 实际上保证了 $<$ 成为 $\mathbf{On}$ 上的良序（任意非空子集 $S$ 的极小元为 $\inf S$）。于是我们可以取 $\alpha$ 为 $\mathbf{On}\setminus C$ 的极小元，无论 $\alpha$ 是 $0$，非零极限序数或是后继均导出矛盾。

归纳时也可以给上述条件均添加 $<\theta$。上述定理同时保证了归纳定义形式的序列的存在唯一性。据此可以证明一系列重要结论。

定理 3.2. 任意良序集 $P$ 都同构于唯一的序数 $\alpha$。

证明. 递归地定义一列 $a$，其中 $a_0 := \min(P)$，而

$$
a_\alpha := \begin{cases}
\min(P \setminus \{a_\beta : \beta < \alpha\}) & \{a_\beta : \beta < \alpha\} \subsetneq P \\
P & \text{otherwise}
\end{cases}
$$

这里其他情况取 $P$ 的用意是 $P$ 一定不是自身的元素，此时可以成功区分前半段和后半段。

则类 $C = \{\theta : a_\theta = P\}$ 必然非空。否则 $\alpha \mapsto a_\alpha$ 给出了 $\mathbf{On}$ 到 $P$ 的单射。$a(\mathbf{On}) = \{x \in P : \exists y \in \mathbf{On}. a_y = x\}$ 是集合（根据 A3），$\mathbf{On} = a^{-1}(a(\mathbf{On}))$ 是集合（根据 A7），导出矛盾。

取 $\theta$ 为 $C$ 的极小元，$a_\alpha \mapsto \alpha$ 就是同构映射。唯一性由任意集合没有到其前段的非平凡同构给出（两个序数之间存在前段关系）。

定理 3.3（Zermelo 良序定理）. 任意集合 $S$ 可以被赋予良序（即同构于某个序数 $P$）。

证明. 选择公理给出了 $P(S)$ 的选择函数 $F$。接下来递归定义

$$
a_\alpha := \begin{cases}
F(S\setminus \{a\beta : \beta < \alpha\}) & \{a_\beta : \beta < \alpha\} \subsetneq S \\
S & \text{otherwise}
\end{cases}
$$

这个序列类似于上一条定理给出了 $S$ 到某序数 $\theta$ 的同构。

这个定理也可以推导选择公理，因为良序可以给出选择函数。

定理 3.4（Zorn 引理）. $P$ 为非空偏序集，若 $P$ 每个链都有上界，则 $P$ 有极大元。

证明. 假设 $P$ 没有极大元，就相当于对于任意元素 $x$，$\{y\in P : x < y\}$ 都是非空集合。考虑 $2^P$ 上的选择函数 $F$，递归定义

$$
a_\alpha := \begin{cases}
F(\{y\in P : \alpha < y\}) & \alpha = \alpha’ + 1 \\
\mathrm{UpperBound}(\{a_\beta : \beta < \alpha\}) & \text{otherwise}
\end{cases}
$$

对于第二行额外做一些说明：该上界一定不在原集合中，否则与 $a_\alpha < a_{\alpha + 1}$ 矛盾。这给出了 $\mathbf{On}$ 到 $P$ 的双射，用类似于定理 3.2 的手法可以说明这导出了矛盾。

基数

定义 4.1. 若存在 $X \xrightarrow\sim Y$ 则记 $|X| = |Y|$。若存在 $X\hookrightarrow Y$ 则记 $|X| \leq |Y|$。若 $|X|\leq |Y|\wedge \neg |X| = |Y|$ 记 $|X| < |Y|$。

注意我们现在只定义了一种“基数比较”，也就是两个二元谓词 $|\cdot| = |\cdot|$ 和 $|\cdot|\leq |\cdot|$。$|\cdot|$ 的定义将在若干个定理之后给出。

定理 4.2. $|X|\leq |Y|\wedge |Y|\leq |X|\rightarrow |X| = |Y|$。

证明. 假设 $f : X \hookrightarrow Y, g : Y \hookrightarrow X$，首先用 $g$ 将 $Y$ 嵌入 $X$ 中，然后不失一般性地假设 $Y \subset X, g = \mathrm{Id}_y$。构造子集链

$$
X_0 = X, Y_0 = Y, X_{n + 1} = f(X_n), Y_{n + 1} = f(Y_n)
$$

显然有

$$
X_0 \supset Y_0 \supset X_1 \supset Y_2 \supset \cdots
$$

定义

$$
\Phi(x) = \begin{cases}
f(x) & \exists n, x \in X_n\setminus Y_n \\
x & \text{otherwise}
\end{cases}
$$

可以验证 $\Phi$ 确实是双射。

上述构造可能显得匪夷所思，因此我们简单做一些点评。需要注意下方的语言都是不严谨不形式化的，但或许有助于理解上述证明的思路。我们假定读者理解图论中的基本概念。

从整体角度来看，一个集合到自己的单射可以感性地变成一些环和链（若 $f(x) = y$，则加一条单向边 $x\rightarrow y$。函数的定义保证了每个点出度恰好为 $1$，单射的定义保证了每个点入度至多为 $1$）。此时对于每一个整体的环或者链，统一的定义双射中这些元素应当如何被映射（是被映射到 $x$ 还是 $f(x)$）。

• 对于环，无论如何选择都无妨，只需保证一个环上的选择是统一的。
• 有下面三种链
  • 没有起点的链（可能出现于集合不可数的情况），只需保证选择是统一的。
  • 起点在 $X\setminus Y$ 中的链。只能定义为 $f(x)$，否则起点对应的值不在 $Y$ 中。
  • 起点在 $Y$ 中的链，只能定义为 $x$，否则起点没有原像。

考虑如何区分后两种链。我们发现如果 $x \in X \setminus Y$，那么一定有 $f(x) \in f(X)\setminus f(Y)$。这表明一整条链中的元素是否在这种补集当中的属性都是相同的。而且这里无需担心可数性的问题，因为链一定是可数的。

定理 4.3（Cantor）. 对于任意集合 $X$ 有 $|X| < |P(X)|$。

证明. $X \hookrightarrow P(X)$ 是显然的。而对任意的映射 $\varphi : X \rightarrow P(X)$ 均可以找到

$$
\{x \in X : x\notin \varphi(X)\} \notin \varphi(X)
$$

因此 $\varphi$ 一定不是满射。

定义 4.4. 序数 $\kappa$ 被称为基数若 $\forall \lambda < \kappa, |\lambda| < |\kappa|$。

可以看到有限序数都是基数，极限序数 $\omega$ 也是基数，而 $\omega + 1$ 并非基数（希尔伯特旅馆）。

定理 4.5. 对于任意集合 $X$，存在最小的序数 $\alpha(X)$ 使得 $|X| = |\alpha(X)|$。

证明. Zermelo 良序定理给出了这个双射。因此这个序数是存在的。取类 $C_X$ 为 $|X| = |\alpha|$ 的所有序数 $\alpha$ 构成的类，此类一定非空。那么 $\alpha(X) = \inf C_X$。

立即推出任意集合 $|X|, |Y|$ 必然满足 $|X|\leq |Y| \vee |Y|\leq |X|$。现在可以定义单独的势符号 $|\cdot|$ 为 $|X| := \alpha(X)$，此符号与上面的几个谓词是相容的。

引理 4.6. 对于任意序数 $\alpha$ 总是存在基数 $\kappa > \alpha$；$S$ 是由基数构成的集合，则 $\sup S$ 是基数。

证明. 令 $\kappa = \alpha(P(\alpha))$，则容易证明 $\kappa > \alpha$。

若 $\sup S$ 不是基数，可以考虑 $\beta < \sup S$，$|\beta| = |\sup S|$。由于 $\sup S$ 是上确界，必然存在 $x\in S, \beta < x$。则 $|\beta|\leq |x| \leq |\sup S| = \beta$，中间必须全部取等。于是 $|\beta| = |x|$，与 $x$ 是基数矛盾。

定义 4.7. 递归定义

$$
\aleph_\alpha := \begin{cases}
\omega & \alpha = 0 \\
\text{大于 $\aleph_{\alpha’}$ 的最小基数} & \alpha = \alpha’ + 1 \\
\sup_{\beta < \alpha} & \text{otherwise}
\end{cases}
$$

容易证明 $|\mathbb{N}| = |\mathbb{Q}| = \aleph_0$。$|\mathbb{R}|$ 是否是 $\aleph_1$ 是所谓的连续统猜想，在 ZFC 下不能证明也不能证伪。

定理 4.8. $|\mathbb{R}| = |2^{\aleph_0}|$。

证明.

• $|\mathbb{R}| \leq 2^{\aleph_0}$：每个实数对应一个戴德金分割，戴德金分割正是 $P(\mathbb{Q})$ 中的元素。
• $|2^{\aleph_0}|\leq |\mathbb{R}|$：任意一个函数 $f: \mathbb{N}\rightarrow 2$ 对应了一个 $[0, 1)$ 之间的三进制小数
  $$
  \sum_{i=0}^{\infty} f(i)3^{-i-1}
  $$

关于基数还有一些有意思的关系式，因为属于课程内容，所以我们暂时憋着不发。