集合语言与集合证明

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

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

本章默认所有集合都放在某个固定论域 $U$ 里讨论。只要出现补集 $A^c$ ，就必须先知道补的是谁：是相对于整数、实数、全体学生，还是某个具体数据表。

论域 U 中包含集合 A、集合 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\in A$
$\{1,2\}\in A$
$\{1,2\}\subseteq A$
$\{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$ 。不同教材对 $\subset$ 的使用习惯略有差异；本章用 $\subseteq$ 表示“允许相等的子集”，需要强调不相等时会写“真子集”。

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

\varnothing\subseteq A

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

子集、真子集、空集以及元素与单元素集合关系的集合示意图 — 子集与属于的区别：元素属于集合，单元素集合可以作为子集；空集是任何集合的子集。

最常见的错误是把 $\in$ 和 $\subseteq$ 混用。 $a\in A$ 说的是“对象 $a$ 是 $A$ 的元素”； $\{a\}\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={a,b,c} 为例，通过取与不取的选择树展示幂集 P(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$ 表示提交了集合练习的学生。用集合语言表达下面三类学生。

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

“至少完成一项任务”表示学生在 $A$ 中，或者在 $B$ 中，所以集合是 $A\cup B$ 。

“两项任务都完成”表示学生同时在 $A$ 和 $B$ 中，所以集合是 $A\cap B$ 。

“完成逻辑测验但没有提交集合练习”表示学生在 $A$ 中且不在 $B$ 中，所以集合是 $A-B$ 。

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

笛卡尔积与有序对

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

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

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

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

笛卡尔积 A×B 的 2×3 网格示意图，展示集合 A={红,蓝} 与 B={1,2,3} 组成的有序对。 — 笛卡尔积把第一坐标和第二坐标按顺序配成有序对，顺序不同结果可能不同。

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

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

集合恒等式

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

一些常用恒等式如下：

名称	恒等式
交换律	$A\cup B=B\cup A$ ， $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\cap(B\cup C)=(A\cap B)\cup(A\cap C)$
德摩根律	$(A\cup B)^c=A^c\cap B^c$ ， $(A\cap B)^c=A^c\cup B^c$
差集改写	$A-B=A\cap B^c$

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

证明集合恒等式时，最可靠的做法是把左右两边都翻译成关于任意元素 $x$ 的条件。如果两个条件逻辑等价，两个集合就相等。

元素追踪法

要证明 $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).

先证明从左到右的包含。任取 $x\in A\cap(B\cup C)$ 。根据交集定义， $x\in A$ 且 $x\in B\cup C$ 。

展开并集条件，得到 $x\in B$ 或 $x\in C$ 。如果 $x\in B$ ，那么 $x\in A\cap B$ ；如果 $x\in C$ ，那么 $x\in A\cap C$ 。

两种情况都说明 $x\in (A\cap B)\cup(A\cap C)$ 。所以 $A\cap(B\cup C)\subseteq (A\cap B)\cup(A\cap C)$ 。

再证明从右到左的包含。任取 $x\in (A\cap B)\cup(A\cap C)$ 。那么 $x\in A\cap B$ 或 $x\in A\cap C$ 。

若 $x\in A\cap B$ ，则 $x\in A$ 且 $x\in B$ ，因此 $x\in B\cup C$ ，从而 $x\in A\cap(B\cup C)$ 。若 $x\in A\cap C$ ，同理也得到 $x\in A\cap(B\cup C)$ 。

两个方向的包含都成立，所以两个集合相等。

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

A-B=A\cap B^c.

写集合证明时，不要从“显然图上一样”直接跳到结论。维恩图可以帮你猜到等式，但证明要说明任意元素在左右两边的归属条件相同。

用反例处理错误等式

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

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

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

用反例元素 x 推翻错误集合等式的并列教学图 — 反例元素在集合 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.

维恩图的边界

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

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

三集合维恩图连接到边界情况表格，说明图像帮助观察，证明检查所有情况。 — 维恩图能提示集合关系的直觉，但边界元素仍要通过元素条件逐项证明。

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

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

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

学完本章后，你已经可以把集合语句拆成逻辑语句。下一章进入关系与函数时，很多定义都会写成集合、笛卡尔积和有序对的语言；本章的元素追踪法会继续派上用场。