集合语言与集合证明

集合把“哪些对象被放在一起”说清楚。它看起来只是一些符号，但后面的关系、函数、计数、图论都会用它做底层语言。本章的目标不是背一串运算名称，而是学会把集合语句翻译成元素条件，再用这些条件写证明。

在前几章里，我们已经会用命题逻辑和量词表达数学断言。集合证明正好把这两条线接起来：$x \in A$ 是一个关于元素 $x$ 的命题，$A \subseteq B$ 则是带全称量词的断言。

---

集合先从论域说起

集合是由一些确定对象组成的整体。对象叫作元素。写 $x \in A$ 表示“$x$ 是集合 $A$ 的元素”，写 $x \notin A$ 表示“$x$ 不是集合 $A$ 的元素”。

“确定”不是说集合必须很小，也不是说元素必须能全部列出来。它的意思是：给定一个对象，原则上能判断它在不在集合里。比如“本班身高超过 170 厘米的学生”是集合，“本班比较高的学生”如果没有明确标准，就暂时不是一个数学上清楚的集合。

集合常见有两种写法。列举法直接列出元素，例如

$$A=\{2,4,6,8\}.$$

描述法说明元素满足的条件，例如

$$B=\{x\in \mathbb{Z}\mid x \text{ 是偶数且 } 0<x<10\}.$$

这两个集合其实相等。集合不关心列出的顺序，也不关心同一个元素写了几次，所以

$$\{2,4,6,8\}=\{8,6,4,2,2\}.$$

例题：设

$$A=\{1,2,\{1,2\}\}.$$

判断下面四个断言的真假。

1. $1\in A$
2. $\{1,2\}\in A$
3. $\{1,2\}\subseteq A$
4. $\{1\}\in A$

---

子集、空集与幂集

如果 $A$ 的每个元素也都是 $B$ 的元素，就说 $A$ 是 $B$ 的子集，记作 $A\subseteq B$。这句话展开成量词就是

$$A\subseteq B \quad \Longleftrightarrow \quad \forall x(x\in A\rightarrow x\in B).$$

如果 $A\subseteq B$ 且 $A\ne B$，就说 $A$ 是 $B$ 的真子集，常写作 $A\subset B$。不同教材对 的使用习惯略有差异；本章用 表示“允许相等的子集”，需要强调不相等时会写“真子集”。

空集 $\varnothing$ 是没有元素的集合。它不是“什么都没有”这种含糊说法，而是一个确定的集合对象。由于没有任何元素能违反“如果 $x\in \varnothing$，那么 $x\in A$”，所以

$$\varnothing\subseteq A$$

对任意集合 $A$ 都成立。

幂集把层级再往上推一层。集合 $S$ 的幂集记作 $\mathcal{P}(S)$，它的元素是 $S$ 的所有子集：

$$\mathcal{P}(S)=\{A\mid A\subseteq S\}.$$

如果 $S=\{a,b,c\}$，那么 $\mathcal{P}(S)$ 有 8 个元素：

$$\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}.$$

这里每一个“元素”本身都是集合。比如 $\{a,b\}\in \mathcal{P}(S)$，同时 $\{a,b\}\subseteq S$。这两个符号分别站在不同层级上。

每个元素在构造子集时都有两个选择：取，或不取。因此若 $S$ 有 $n$ 个元素，$\mathcal{P}(S)$ 有 $2^n$ 个元素。

---

并、交、补、差

集合运算最稳妥的读法，是把每个运算都翻译成关于元素的条件。设 $A$、$B$ 是论域 $U$ 中的集合。

$$x\in A\cup B \quad \Longleftrightarrow \quad x\in A \text{ 或 } x\in B.$$ $$x\in A\cap B \quad \Longleftrightarrow \quad x\in A \text{ 且 } x\in B.$$ $$x\in A-B \quad \Longleftrightarrow \quad x\in A \text{ 且 } x\notin B.$$ $$x\in A^c \quad \Longleftrightarrow \quad x\in U \text{ 且 } x\notin A.$$

并集对应“至少在一个集合里”，交集对应“同时在两个集合里”，差集对应“在前一个集合里但不在后一个集合里”，补集对应“在论域中但不在这个集合里”。

例题：某课程平台上，$A$ 表示完成了逻辑测验的学生，$B$ 表示提交了集合练习的学生。用集合语言表达下面三类学生。

1. 至少完成一项任务的学生。
2. 两项任务都完成的学生。
3. 完成逻辑测验但没有提交集合练习的学生。

这种语言也出现在数据库里。查询两个结果表的并、交、差时，实际处理的就是“记录是否在某个结果集合中”。在真实数据里，论域通常是某个数据库、某张表或某次查询的候选记录；一旦论域换了，补集的意思也会跟着换。

---

笛卡尔积与有序对

并、交、差处理的是“同一类对象是否在集合里”。笛卡尔积处理的是“从两个集合各取一个对象，并按顺序配成一对”。

集合 $A$ 与 $B$ 的笛卡尔积定义为

$$A\times B=\{(a,b)\mid a\in A \text{ 且 } b\in B\}.$$

这里 $(a,b)$ 是有序对。一般来说，$(a,b)$ 与 $(b,a)$ 不同，除非两个坐标刚好相同。顺序之所以重要，是因为第一坐标和第二坐标承担不同角色。

如果 $A=\{\text{红},\text{蓝}\}$，$B=\{1,2,3\}$，那么 $A\times B$ 有 6 个有序对。若 $A$ 有 个元素， 有 个元素，则 有 个元素。

笛卡尔积是后面学习关系和函数的入口。一个“学生选择课程”的关系，可以看作“学生集合 $\times$ 课程集合”的某个子集；函数也可以看作满足额外条件的有序对集合。

---

集合恒等式

集合恒等式是对所有相关集合都成立的等式。它们和命题逻辑的等价式很像，因为集合运算本质上会变成元素条件中的“且、或、非”。

一些常用恒等式如下：

这些式子不应该只靠形状记忆。比如分配律里 $A\cap(B\cup C)$ 先要求元素在 $A$ 中，再要求元素在 $B$ 或 $C$ 中；这等价于“元素在 $A$ 和 $B$ 中，或者在 和 中”。

---

元素追踪法

要证明 $A\subseteq B$，就证明任意一个属于 $A$ 的元素也属于 $B$。要证明 $A=B$，通常证明两个包含：

$$A\subseteq B \quad \text{且} \quad B\subseteq A.$$

这个方法常叫元素追踪法，也可以叫元素法。它的基本动作很固定：任取一个元素，从“属于左边”开始，逐步展开定义，最后得到“属于右边”。

例题：证明

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

再看一个更短的例题：证明差集改写

$$A-B=A\cap B^c.$$

---

用反例处理错误等式

不是所有看起来像分配律的式子都成立。比如下面这个式子是错的：

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

右边的 $C$ 没有被 $A$ 限制住。如果某个元素在 $C$ 中但不在 $A$ 中，它会落入右边，却不会落入左边。

给出一个具体反例。令

$$A=\{1\},\quad B=\varnothing,\quad C=\{2\}.$$

左边是

$$A\cap(B\cup C)=\{1\}\cap\{2\}=\varnothing.$$

右边是

$$(A\cap B)\cup C=\varnothing\cup\{2\}=\{2\}.$$

左右不相等，所以原等式不成立。

练习：判断下面等式是否总成立。如果不成立，给出一个反例。

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

---

维恩图的边界

维恩图适合观察两三个集合的关系。它能帮助你看到哪些区域被包含、哪些区域被排除，也能帮助你设计反例。但维恩图有边界。

第一，维恩图默认每个区域都“可能有元素”，但实际集合中某些区域可能为空。第二，补集必须依赖论域；图外面的区域如果没有论域边框，就无法判断它是不是补集的一部分。第三，集合变多时，图形会越来越难读，甚至会遮住真正需要检查的逻辑条件。

所以，维恩图适合放在证明之前，用来猜结论、找反例、检查思路。正式证明时，还是要回到元素条件。

可以用下面的检查表收尾：

1. 先写清论域 $U$，尤其在出现补集时。
2. 区分 $\in$ 和 $\subseteq$，不要混淆元素与集合。
3. 把每个集合运算翻译成“且、或、非”的元素条件。
4. 证明包含时从任意元素出发；证明相等时做两个方向。
5. 反驳集合等式时给出具体集合，并指出某个元素只在一边。