2.1 集合与集合运算

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

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

集合、属于、相等

定义

集合

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

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

例子：

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

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

定理

外延性

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

符号上写成：

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

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

证明 $A \subset B$
证明 $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，二者才会不同。

建立新集合

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

运算	符号	定义
并集	$A \cup B$	属于 $A$ 或 $B$ 的元素
交集	$A \cap B$	同时属于 $A$ 和 $B$ 的元素
差集	$A \setminus B$	属于 $A$ 但不属于 $B$ 的元素
补集	$A^c$	在所选全集内，不属于 $A$ 的元素

补集一定要先指定全集 $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$ 、 $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 \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$ ”。

怎样仔细证明集合恒等式

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

标准证明方法通常是：

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

例题

证明 $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^c$ 是“在全集外面的部分”。 $A \setminus B$ 是“A 里面但不在 B 里面的部分”。两者有关，但不一样。

常见错误

没有全集就不能写补集

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

常见错误

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

解答

答案

为什么这一单元重要

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

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

边读边试

比较一对集合

互动探索器让你把元素加入或移出 A 与 B，并即时看见运算结果改变。

集合 A

集合 B

并集

{1, 2, 3, 4}

交集

{2, 4}

差集 A \ B

{1}

2.1 集合与集合运算

MATH1090：集合论

集合、属于、相等

集合

外延性

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

子集符号要注意本地约定

集合列式和有界谓词

不要忽略所在集合

集合不是 multiset

建立新集合

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

为什么补集一定要有全集

这些等式怎么证

基本集合代数

示范：为什么 A⊂BA \subset BA⊂B 会推出 A∪B=BA \cup B = BA∪B=B

其他常见构造

笛卡儿积

有限次积

幂集

不交并

怎样仔细证明集合恒等式

证明 A∩(B∖C)=(A∩B)∖CA \cap (B \setminus C) = (A \cap B) \setminus CA∩(B∖C)=(A∩B)∖C

怎样正确阅读 Venn 图

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

有限集合怎样计数

计算一个并集和幂集

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

子集证明检查表

常见错误

补集不等于差集

没有全集就不能写补集

积集顺序有意义

小检查

如果 A=a,b,cA = {a, b, c}A=a,b,c 而 B=b,c,dB = {b, c, d}B=b,c,d，A∩BA \cap BA∩B 是什么？

答案

为什么在未指定全集之前，AcA^cAc 不够清楚？

答案

十位学生去远足。七位使用防晒，六位戴帽，两位两者都没有。多少位两者都有？

答案

如果 A⊂BA \subset BA⊂B，那么 A∪BA \cup BA∪B 和 A∩BA \cap BA∩B 会简化成什么？

答案

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

答案

为什么这一单元重要

比较一对集合

本节掌握 checkpoint

先备知识

本单元重点词汇

Premium learning add-ons

本系列更多笔记

示范：为什么 $A \subset B$ 会推出 $A \cup B = B$

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

如果 $A = {a, b, c}$ 而 $B = {b, c, d}$ ， $A \cap B$ 是什么？

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

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

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