2.1 集合与集合运算

集合是用来描述一批对象的基础语言。在这门课里，集合不是旁支， 而是逻辑、函数、关系，以及后续数系构造共同依赖的语言。

如果你现在觉得符号有些陌生，这是正常的。这一单元的目标就是把这套语言 变得足够精确，好让后面的章节可以直接使用。

集合、属于、相等

定义

集合

集合是一批对象所组成的整体。

如果 $x$ 是集合 $A$ 的元素，我们写 $x \in A$；如果不是，就写 $x \notin A$。

例子：

• $\{1, 2, 3\}$ 是集合。
• {香港岛、九龙、新界} 是集合。
• $\varnothing$ 是空集合，也就是没有任何元素的集合。

同一个集合可以有不同写法，但集合本身只由元素决定。

定理

外延性

两个集合相等，当且仅当它们拥有完全相同的元素。

符号上写成：

$$A = B \iff \forall x\, (x \in A \leftrightarrow x \in B).$$

所以证明集合相等的标准方法是先证两个包含关系：

1. 证明 $A \subset B$
2. 证明 $B \subset A$

常见错误

不要把集合相等和描述相等混淆

$\{1, 2, 3\}$ 和 $\{3, 2, 1\}$ 是同一个集合，因为元素完全一样。列出的顺序并不重要。

常见错误

子集符号要注意本地约定

本课程用 $A \subset B$ 表示“$A$ 的每个元素都在 $B$ 里”。有些书会用 $A \subseteq B$ 表示这个意思，而把 $A \subset B$ 留给 strict subset。 读书时要先确认约定。

集合列式和有界谓词

学过谓词逻辑之后，最常见的定义集合方式，是先指定一个已知集合，再保留其中 满足某个条件的元素：

$$\{x \in S \mid P(x)\}.$$

这个记号要仔细读。竖线前面的部分说明变量允许在哪个集合里取值；竖线后面的 谓词说明哪些元素会被留下。例如

$$\{n \in \mathbb{Z} \mid n \text{ is even}\}$$

就是所有偶整数的集合。

常见错误

不要忽略所在集合

$\{x \mid P(x)\}$ 有时是方便的简写，但严谨版本应该把变量限制在某个已知集合 里。这样做可以避免把任何文字描述都当成自动产生良好数学对象。

常见错误

集合不是 multiset

集合只记录某个对象是否出现，不记录它在列表里出现多少次。因此 $\{1,1,2,3\}$ 和 $\{1,2,3\}$ 描述同一个集合；如果讨论 multiset，二者才会不同。

建立新集合

知道了一些集合之后，我们通常会想造出更多集合。标准运算就是用来做这件事的。

补集一定要先指定全集 $E$。在这一单元里，我们通常默认所有集合都在某个 固定 $E$ 里面，所以 $A^c$ 就是 $E \setminus A$。

例题

追踪元素如何经过几个运算

设

$$A = \{1, 2, 4\}, \qquad B = \{2, 3, 4\},$$

而全集取为

$$E = \{1, 2, 3, 4, 5\}.$$

那么：

• $A \cup B = \{1, 2, 3, 4\}$
• $A \cap B = \{2, 4\}$
• $A \setminus B = \{1\}$
• $B \setminus A = \{3\}$
• $A^c = \{3, 5\}$
• $(A \cup B)^c = \{5\}$

$A^c$ 不是 $A$ 自身的绝对性质。在不同 universe 里，同一个集合的补集可以完全不同。 所以一定要先知道当前讨论的是哪个全集。

这些等式怎么证

本单元的集合恒等式不是靠死记，而是靠逐个元素追踪来证明。

定理

基本集合代数

对集合 $A$、$B$、$C$：

• $A \cup \varnothing = A$
• $A \cup B = B \cup A$
• $A \cup (B \cup C) = (A \cup B) \cup C$
• $A \cup 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)$
• $(A \cup B)^c = A^c \cap B^c$
• $(A \cap B)^c = A^c \cup B^c$
• $(A^c)^c = A$
• $A \cap A^c = \varnothing$
• $A \cup A^c = E$
• $A \subset B$ 当且仅当 $A \cup B = B$
• $A \subset B$ 当且仅当 $A \cap B = A$
• $A \subset B$ 当且仅当 $B^c \subset A^c$

核心证明法是 element chasing。比如：

$$x \in A \cap (B \cup C) \iff x \in A \text{ 且 } (x \in B \text{ 或 } x \in C)$$

等价于

$$(x \in A \text{ 且 } x \in B) \text{ 或 } (x \in A \text{ 且 } x \in C),$$

所以又等价于

$$x \in (A \cap B) \cup (A \cap C).$$

证明：为什么 $A \subset B$ 会推出 $A \cup B = B$

假设 $A \subset B$。

要证 $A \cup B = B$，只需证两个包含。

先证 $A \cup B \subset B$：如果 $x \in A \cup B$，那么 $x \in A$ 或 $x \in B$。 若 $x \in A$，由 $A \subset B$ 得 $x \in B$。所以无论哪种情况，都有 $x \in B$。

再证 $B \subset A \cup B$：如果 $x \in B$，那当然 $x \in A \cup B$。

因此 $A \cup B = B$。

证明：一个有条件的分配恒等式

命题

$$(A \cap B) \cup C = A \cap (B \cup C)$$

成立，当且仅当 $C \subset A$。

先证充分性。假设 $C \subset A$。若 $x$ 属于左边，那么或者 $x \in A \cap B$，或者 $x \in C$。后一种情况下，由 $C \subset A$ 可得 $x \in A$，所以两种情况下都有 $x \in A$ 且 $x \in B \cup C$。因此左边包含于右边。反过来，若 $x \in A \cap (B \cup C)$，则 $x \in A$，并且或者 $x \in B$，或者 $x \in C$。前一种情况下 $x \in A \cap B$，后一种情况下 $x \in C$， 所以 $x$ 属于左边。这证明了两个集合相等。

再证必要性。假设等式成立，任取 $c \in C$。因为 $c \in (A \cap B) \cup C$，由等式可知 $c \in A \cap (B \cup C)$， 特别地 $c \in A$。因此 $C$ 的每个元素都在 $A$ 中，即 $C \subset A$。 等价地，若存在 $c \in C \setminus A$，它会属于左边而不属于右边， 从而直接反驳该等式。

证明：对称差满足结合律

定义

$$A \mathbin{\triangle} B=(A\setminus B)\cup(B\setminus A)$$

对每个元素 $x$，

$$x\in A\mathbin{\triangle}B \iff (x\in A\text{ 且 }x\notin B)\text{ 或 }(x\notin A\text{ 且 }x\in B)$$

所以 $x$ 属于对称差，当且仅当 $A$、$B$ 中恰有一个包含 $x$。 再次应用这个规则可知，$x$ 属于 $(A\mathbin{\triangle}B)\mathbin{\triangle}C$ 当且仅当 $x\in A$、$x\in B$、$x\in C$ 这三个命题中恰有奇数个为真： 第一次对称差记录前两个命题的奇偶性，第二次在 $x\in C$ 时翻转它。 改变括号得到的 $A\mathbin{\triangle}(B\mathbin{\triangle}C)$ 也正好由同一个 奇偶条件刻画。因此

$$(A\mathbin{\triangle}B)\mathbin{\triangle}C =A\mathbin{\triangle}(B\mathbin{\triangle}C)$$

这是逐元素证明，不依赖某一幅特定的 Venn 图。

证明：补集反转包含方向

设 $A,B\subseteq E$ 且 $A\subseteq B$。对 $x\in E\setminus B$，若 $x\in A$，包含关系会推出 $x\in B$，矛盾。所以 $x\in E\setminus A$，即 $B^c\subseteq A^c$。共同全集 $E$ 保证两个补集比较的是同一范围内的元素。

反例模式

并集不能直接消去

$A\subseteq B\Rightarrow A\cup C\subseteq B\cup C$ 成立，但逆命题失败。取 $A=\{1\}$、$B=\varnothing$、$C=\{1\}$，两个并集都等于 $\{1\}$，却有 $A\nsubseteq B$。加入 $C$ 遮住了见证 1。一种正确修补是再假设 $A\cap C=\varnothing$：任意 $x\in A$ 属于 $B\cup C$ 却不属于 $C$，因此属于 $B$。

其他常见构造

这门课后面还会反复用到下面几种集合构造。

笛卡儿积

$A \times B$ 是所有有序对 $(a, b)$ 的集合，其中 $a \in A$ 而 $b \in B$。 顺序是有意义的：$(a, b)$ 和 $(b, a)$ 通常不同。

如果 $|A| = 5$ 且 $|B| = 3$，那么 $|A \times B| = 15$。

$R \times R = R^2$ 就是平面。

有限次积

$A^n$ 表示 $A$ 和自己做 $n$ 次笛卡儿积，也就是所有 $n$-tuple。

幂集

$P(A)$ 是 $A$ 的所有子集所组成的集合。

如果 $A$ 有 $n$ 个元素，那么 $P(A)$ 有 $2^n$ 个元素。另一个很有用的理解方式 是 indicator function：每个子集都可以对应到一个 $A \to {0,1}$ 的函数。

例如

$$P(\{a, b\}) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}.$$

不交并

有时两个集合在原始写法上可能有重叠，但我们又想保留每个元素的来源。 不交并就是通过标签记住每个元素最初属于哪个集合。

直观上，$A \sqcup B$ 就是“加了标签 1 的 $A$”和“加了标签 2 的 $B$”。

反例：乘积分配不一定成立

在任意集合上，不一定存在

$$A \cup (B \times C) \quad\text{与}\quad (A \cup B) \times (A \cup C)$$

之间的双射。取 $A = \{0,1\}$ 且 $B=C=\varnothing$。左边就是 $A$， 有两个元素；右边是 $A \times A$，有四个有序对。基数不同，所以这个例子 中不存在双射。

怎样仔细证明集合恒等式

到了这里，集合恒等式应该被理解成“属元条件相同”的命题，而不是只靠图形 去记。

标准证明方法通常是：

1. 任取一个元素 $x$；
2. 把 $x \in$ 两边集合翻译成逻辑条件；
3. 逐步化简，直到两边变成同一句话。

例题

证明 $A \cap (B \setminus C) = (A \cap B) \setminus C$

从

$$x \in A \cap (B \setminus C)$$

出发，就表示：

• $x \in A$，
• $x \in B$，
• $x \notin C$。

而这三个条件合起来，正是

$$x \in (A \cap B) \setminus C$$

的意思。

由于推理可以反向读回去，所以两边集合相等。

这种逐元素追踪的方法，后面还会再次出现在德摩根律、关系，以及数系构造中。

怎样正确阅读 Venn 图

Venn 图适合用来整理情况，但证明仍然要回到成员条件。图形可以提示某个区域 为空、包含在另一个区域里，或被切成几部分；正式文字则要说明这对应哪个 包含关系、不交条件或计数等式。

对三个集合来说，$A \subset (B \cup C)$ 表示 $A$ 的每个元素都至少落在 $B$ 或 $C$ 之一。它不表示 $A \subset B$，也不表示 $A \subset C$。能否分清这些 可能性，是检查自己是否真正用逻辑方式阅读图形的好方法。

例题

把四种 Venn 图条件翻译成区域语言

假设 $A$、$B$、$C$ 都是非空集合。以下常见练习条件，最好先读成区域指令， 而不是只凭图形印象处理。

条件	图中必须呈现的意思
$A \subset B$、$C \subset B$，且 $A \cap C = \varnothing$	$A$ 和 $C$ 都在 $B$ 里面，但二者互不相交。$B$ 仍然可以有不属于 $A$ 或 $C$ 的元素。
$A \cap B \ne \varnothing$、$A \cap C \ne \varnothing$、$B \cap C \ne \varnothing$，且 $A \cap B \cap C = \varnothing$	每两个集合都有交集，但三者共同交集为空。因此三个 pairwise overlap 必须是分开的区域。
$A \subset (B \cap C)$，且 $B \subset C$	因为 $B \subset C$，所以 $B \cap C$ 其实就是 $B$。于是 $A$ 在 $B$ 里面，而 $B$ 又在 $C$ 里面。
$A \subset (B \cup C)$、并非 $A \subset B$、并非 $A \subset C$	$A$ 没有元素落在 $B \cup C$ 外面，但 $A$ 必须至少有一个元素在 $C \setminus B$，也至少有一个元素在 $B \setminus C$。

第四行最容易被误读。它不只是说 $A$ 同时碰到 $B$ 和 $C$；它还说 $A$ 完全 被 $B$ 和 $C$ 覆盖，但又不能只由其中一个集合单独覆盖。

有限集合怎样计数

集合语言不只用来分类，也直接控制计数。

如果 $A$、$B$ 都是有限集合，那么：

• $|A \times B| = |A|\,|B|$；
• $|P(A)| = 2^\{|A|\}$；
• $|A \cup B| = |A| + |B| - |A \cap B|$。

并集公式之所以要减交集，是因为交集中的元素如果直接相加，会被算两次。

例题

计算一个并集和幂集

假设 $|A| = 6$、$|B| = 5$、$|A \cap B| = 2$。

那么

$$|A \cup B| = 6 + 5 - 2 = 9$$

再设 $S = \{a,b,c\}$。每个元素都只有两种选择：放进某个子集，或者不放进。 所以总共有

$$2 \cdot 2 \cdot 2 = 2^3 = 8$$

个子集。因此 $|P(S)| = 8$。

例题

不用画图也能完成的 Venn 图计数

十位学生去远足。七位使用防晒，六位戴帽，两位没有任何防晒保护。

设 $S$ 是使用防晒的集合，$H$ 是戴帽的集合。由于两位学生不在这两个集合里，

$$|S \cup H| = 10 - 2 = 8.$$

由 inclusion-exclusion，

$$|S \cap H| = |S| + |H| - |S \cup H| = 7 + 6 - 8 = 5.$$

所以五位学生同时使用防晒并戴帽。

子集证明检查表

子集证明会反复出现，所以最好让它变成固定套路。

如果要证明 $A \subseteq B$，就从任取 $x \in A$ 开始，再用 $A$ 的定义推出 足够信息，最后证明同一个 $x$ 其实也在 $B$ 里面。由于 $x$ 是任取，结论 就对 $A$ 的每个元素成立。

这种 direct proof 模式，后面在关系、偏序，以及等价类中都会再次出现。

常见错误

常见错误

补集是相对于全集的差集

当 $A\subseteq E$ 时，补集 $A^c=E\setminus A$ 是“在指定全集 $E$ 内、但不属于 $A$ 的部分”。 而 $A\setminus B$ 是“属于 $A$、但不属于 $B$ 的部分”。因此，补集是以全集为左操作数的差集， 不是全集以外的部分。

常见错误

没有全集就不能写补集

如果你写补集，一定要知道你是在什么 universe 里做运算。否则 $^c$ 是含糊的。

常见错误

积集顺序有意义

$A \times B$ 和 $B \times A$ 一般包含不同的有序对。这就是为什么函数和关系要用积集语言。

小检查

思考检查

为什么在未指定全集之前，$A^c$ 不够清楚？

想一想补集是“在哪个范围内”取外面。

解答 · 答案

因为同一个集合在不同 universe 里的补集可以完全不同。

思考检查

如果 $A \subset B$，那么 $A \cup B$ 和 $A \cap B$ 会简化成什么？

用上面的 absorption laws。

解答 · 答案

$A \cup B = B$，而 $A \cap B = A$。

思考检查

假设 $A \subset (B \cup C)$，但 $A$ 不是 $B$ 的子集，也不是 $C$ 的子集。$A$ 的哪两个部分必须非空？

把每一个“不是子集”的叙述翻译成存在某个元素。

解答 · 答案

必须至少有一个 $A$ 的元素在 $C \setminus B$，并且至少有一个 $A$ 的元素在 $B \setminus C$。条件 $A \subset (B \cup C)$ 则排除了 $A$ 有元素同时不在 $B$ 和 $C$ 的可能。

为什么这一单元重要

这一单元是后面数系构造的语言基础。

• $N^2$ 会用来构造整数。
• 等价类会用来构造有理数。
• 一个集合上的关系会变成偏序和等价关系的语言。
• 幂集和笛卡儿积会在后面讲 family、tuple，以及各种构造时再次出现。