集合语言与集合证明

前面几章一直在练一件事：把一句数学话拆成命题、量词和推理规则。现在我们给这些话找一个能装下对象的容器。比如论域是本学期选课的学生，谓词 $P(x)$ 表示“学生 $x$ 完成了逻辑测验”，那么所有使 $P(x)$ 为真的学生就组成一个集合：

$$A=\{x\in U\mid P(x)\}.$$

这就是集合语言和量词语言的接缝。$x\in A$ 不只是“一个点画在一个圈里”，它等价于命题 $P(x)$ 为真；$A\subseteq B$ 也不只是“小圈在大圈里”，它其实藏着一个全称量词。

本章会反复做同一个动作：先把集合式翻译成元素条件，再在元素条件上推理。只要这个动作熟练，集合恒等式就不再靠图形猜，后面的关系、函数、计数和图论也会有统一的语言。

---

从论域和元素开始

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

“确定”不等于“能够全部列完”。它只要求：给定一个候选对象，元素条件足够明确，原则上可以判断这个对象是否属于集合。“本班身高不低于 170 厘米的学生”给出了可判断的条件；“本班比较高的学生”没有说明“比较高”的界线，暂时还不是一个清楚的数学集合。

在讨论集合之前，最好先固定论域 $U$，也就是当前允许拿来判断的全部对象。设 $U$ 是某门课的全部学生，$A$ 是完成逻辑测验的学生，$B$ 是提交集合练习的学生。一个学生可以属于 $A$，属于 $B$，同时属于两者，也可能只在论域 $U$ 中而不属于这两个集合。

论域在补集问题中尤其不能省略。若 $A$ 表示“大于 $0$ 的数”，相对于整数论域，补集是所有非正整数；相对于实数论域，补集是所有非正实数，两个答案不是同一个集合。以后看到 $A^c$，第一反应不应是“圈外涂色”，而应是“相对于哪个 $U$？”

列举法与描述法

小而有限的集合可以直接列出元素：

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

集合不记录先后次序，也不记录重复次数，所以

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

第二个写法中的 $2$ 出现两次，并不会产生两个不同的 $2$。如果确实要记录顺序或重复次数，需要使用序列或多重集，而不是普通集合。

元素太多或根本列不完时，描述法更合适：

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

竖线左边写候选元素及其论域，右边写筛选条件。于是

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

这也解释了为什么描述法和谓词如此接近：一个集合可以看成“让某个谓词为真的全部候选对象”。

集合相等只看元素

两个集合相等，意思是它们有完全相同的元素。写成量词就是

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

集合的名字、元素的书写顺序和描述方式都不重要。比如

$$\{1,4,9\}=\{n^2\mid n\in\{1,2,3\}\}.$$

左边在列举，右边在生成，但任意对象属于左边当且仅当属于右边，所以它们是同一个集合。这个“只看成员、不看包装”的原则叫外延观点，也是后面证明集合相等的根本依据。

---

属于、子集与对象层级

“属于”和“包含”看起来都在说对象之间的关系，但它们的两端类型不同：

• $a\in A$：左边是一个对象，右边是集合。
• $S\subseteq A$：左边和右边都是集合。

设

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

这里 $1\in A$，而且 $\{1,2\}\in A$，因为集合 $\{1,2\}$ 被整体当作一个元素放进了 $A$。同时 $\{1,2\}\subseteq A$ 也为真，因为 和 分别属于 。不过 为假： 列出了元素 ，却没有把集合 整体列作元素。

1

设 A={1,2,{1,2}}，下面哪一个断言为假？

A.1∈AB.{1,2}∈AC.{1,2}⊆AD.{1}∈A

子集是一个全称命题

若 $A$ 的每个元素都是 $B$ 的元素，就说 $A$ 是 $B$ 的子集：

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

请留意这里的方向。证明 $A\subseteq B$ 时，我们从“$x\in A$”出发，目标是推出“$x\in B$”。我们不需要证明 $B$ 的每个元素都在 $A$ 中，因此 $B$ 完全可以多出一些元素。

每个集合都是自己的子集，因为

$$\forall x\,(x\in A\rightarrow x\in A)$$

永远成立。如果 $A\subseteq B$ 且 $A\ne B$，那么 $A$ 是 $B$ 的真子集。本章用 $A\subsetneq B$ 表示真子集，避免把“允许相等的子集”和“严格更小的子集”混用。

还有一个非常实用的判据：

$$A\subseteq B \quad\Longleftrightarrow\quad A-B=\varnothing.$$

如果 $A$ 中不存在一个落在 $B$ 外面的元素，那么 $A$ 的所有元素就都在 $B$ 中。

为什么空集是任何集合的子集

空集 $\varnothing$ 是没有任何元素的集合。第一次看到

$$\varnothing\subseteq A$$

很多人会觉得奇怪：空集“什么都没有”，凭什么包含在 $A$ 中？问题出在把子集想成了把一个实体塞进另一个实体。我们回到定义：要让 $\varnothing\subseteq A$ 失败，必须找到一个对象 $x$，满足

$$x\in\varnothing \quad\text{且}\quad x\notin A.$$

可第一项根本不可能发生。空集中没有元素，所以找不到违反子集条件的反例。换成量词语言，断言是

$$\forall x\,(x\in\varnothing\rightarrow x\in A).$$

对每个 $x$，前件 $x\in\varnothing$ 都是假。条件命题在前件为假时为真，因此整个全称命题成立。这正是前面学过的“空真”，现在它有了一个非常具体的用途。

也可以用反证法看同一件事。假设 $\varnothing\nsubseteq A$，按“不包含”的含义，就应当存在某个 $x\in\varnothing$ 且 $x\notin A$。但 $x\in\varnothing$ 与空集定义矛盾，所以假设不成立。

---

幂集：把所有子集收成一个集合

集合 $S$ 的幂集记作 $\mathcal{P}(S)$，它的元素是 $S$ 的所有子集：

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

于是下面两句话完全等价：

$$T\in\mathcal{P}(S) \quad\Longleftrightarrow\quad T\subseteq S.$$

这条等价式非常适合检查层级。$T$ 在左边是幂集的一个元素，在右边是原集合 $S$ 的一个子集。

若 $S=\{a,b,c\}$，那么

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

别漏掉两个边界成员：$\varnothing$ 是 $S$ 的子集，所以 $\varnothing\in\mathcal{P}(S)$；$S$ 也是自己的子集，所以 $S\in\mathcal{P}(S)$。

为什么 $n$ 个元素会有 $2^n$ 个子集

设

$$S=\{s_1,s_2,\ldots,s_n\}.$$

任取一个子集 $T\subseteq S$，依次检查 $s_1,s_2,\ldots,s_n$：若 ，就在第 位写 ；若 ，就在第 位写 。这样每个子集对应唯一一个长度为 的 - 串。

反过来，给定一个 $n$ 位 $0$-$1$ 串，把写着 $1$ 的位置对应的元素取进来，就恢复了唯一的子集。两个方向互相还原，所以“$S$ 的子集”和“长度为 $n$ 的二进制串”一一对应。

每一位有两种选择，共有 $n$ 位，因此

$$|\mathcal{P}(S)|=2^n.$$

这里出现了本章第一个有限基数公式。有限集合 $A$ 的基数 $|A|$ 就是它的元素个数。特别地，$|\varnothing|=0$，而 $|\{\varnothing\}|=1$。

试着先选择三个元素，再把其中一个取消。你看到的不只是答案从 $8$ 变成 $4$，而是每删除一个可独立选择的元素，二进制串就少一位，选择总数也随之减半。

---

集合运算就是元素条件

设 $A,B\subseteq U$。与其死记图中哪块区域要涂色，不如直接记住四个元素条件。

并集：至少属于一个

$$x\in A\cup B \quad\Longleftrightarrow\quad x\in A\text{ 或 }x\in B.$$

这里的“或”允许两边同时成立。因此同时属于 $A$ 和 $B$ 的元素也在并集中。

交集：同时属于两者

$$x\in A\cap B \quad\Longleftrightarrow\quad x\in A\text{ 且 }x\in B.$$

若 $A\cap B=\varnothing$，就说 $A$ 和 $B$ 不相交。请不要把“不相交”误写成“两个集合没有任何关系”；它只说明没有共同元素。

差集：在前者中而不在后者中

$$x\in A-B \quad\Longleftrightarrow\quad x\in A\text{ 且 }x\notin B.$$

差集有方向。一般来说 $A-B\ne B-A$。例如 $A=\{1,2\}$、$B=\{2,3\}$ 时，，而 。

补集：相对于论域排除

$$x\in A^c \quad\Longleftrightarrow\quad x\in U\text{ 且 }x\notin A.$$

如果已经明确所有对象都在 $U$ 中，常把 $x\in U$ 省略，只写 $x\notin A$。但论域本身不能从概念上消失。

把差集和补集放在一起，会得到常用改写：

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

还有一种常见运算叫对称差，保留“恰好属于一个集合”的元素：

$$A\triangle B=(A-B)\cup(B-A).$$

等价地，

$$x\in A\triangle B \quad\Longleftrightarrow\quad (x\in A)\text{ 与 }(x\in B)\text{ 恰有一个为真}.$$

从实际语句翻译集合式

某课程平台中，$A$ 表示完成逻辑测验的学生，$B$ 表示提交集合练习的学生。我们逐句翻译：

在交互实验中，先固定一个元素，再改变它是否属于 $A$、是否属于 $B$。你会发现集合运算的结果完全由这两个真假值决定，这正是集合恒等式能够转化为命题逻辑的原因。

---

有限集合的大小怎样随运算变化

集合相等关心的是“元素完全相同”，基数相等只关心“元素个数相同”。例如 $\{1,2,3\}$ 与 $\{a,b,c\}$ 不是同一个集合，但它们的基数都是 $3$。

对有限集合，并集的大小不能简单相加，因为交集中的元素会被数两次。正确公式是

$$|A\cup B|=|A|+|B|-|A\cap B|.$$

思路并不神秘：$|A|+|B|$ 先把两边全部计入，共同元素因此出现两次；减去一次 $|A\cap B|$，每个共同元素就只剩一次。

差集的大小也能从同一个拆分得到：

$$|A-B|=|A|-|A\cap B|.$$

若 $A\subseteq B$ 且二者有限，那么 $|A|\le |B|$。如果进一步知道 $|A|=|B|$，那么 $B$ 不可能还有 之外的元素，于是 。

幂集公式 $|\mathcal{P}(S)|=2^{|S|}$ 也可以理解成基数比较：每个子集都与一个唯一的 $0$-$1$ 选择串配对。这里真正有力量的不是“数起来刚好一样”，而是找到了两个集合之间的一一对应。等到学习函数时，我们会给这种对应一个正式名字。

---

笛卡尔积：从集合走向有序对

并、交、差都在判断一个对象是否属于某个集合。若我们想表达“学生选了哪门课”“城市之间有哪条航线”，单个元素就不够了，需要把两个角色按顺序配成一对。

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

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

$(a,b)$ 是有序对。两个有序对相等的条件是对应坐标分别相等：

$$(a,b)=(c,d) \quad\Longleftrightarrow\quad a=c\text{ 且 }b=d.$$

一般来说 $(a,b)\ne(b,a)$，因为第一坐标和第二坐标承担不同角色。若 $A$ 是学生集合，$B$ 是课程集合，$(\text{小林},\text{离散数学})$ 可以表示一次选课记录；把顺序倒过来就变成“课程是学生、学生是课程”，类型已经不对。

若 $A=\{\text{红},\text{蓝}\}$、$B=\{1,2,3\}$，那么

$$A\times B= \{(\text{红},1),(\text{红},2),(\text{红},3), (\text{蓝},1),(\text{蓝},2),(\text{蓝},3)\}.$$

有限情况下，每个 $A$ 中元素都能与每个 $B$ 中元素配对，因此

$$|A\times B|=|A|\,|B|.$$

笛卡尔积通常不满足交换律。$A\times B$ 与 $B\times A$ 可能大小相同，却包含不同类型的有序对。它还满足两个有用的边界性质：

$$A\times\varnothing=\varnothing, \qquad \varnothing\times B=\varnothing.$$

因为要组成一对，就必须从两边各取一个元素；任一边无元素，都无法产生有序对。

它对并集和交集也能分配。例如

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

下一章会把 $A\times B$ 的某些子集叫作从 $A$ 到 $B$ 的关系；再加上“每个输入恰好对应一个输出”的条件，就得到函数。也就是说，笛卡尔积不是孤立的新运算，它是在给关系和函数准备容器。

---

集合恒等式不是图形记忆题

集合恒等式是对所有允许的集合都成立的等式。之所以有些恒等式和命题逻辑长得很像，是因为成员条件会把 $\cup$、$\cap$、补集分别翻译成“或”“且”“非”。

下面这张表可以当作检查清单，但不要只靠式子的形状背诵。

例如吸收律

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

可以这样读：如果元素已经在 $A$ 中，那么再补上一批“既在 $A$ 又在 $B$ 中”的元素，不会带来任何新成员。

德摩根律中的符号变化也有清楚的语言来源。“不属于 $A\cup B$”意思是既不属于 $A$，也不属于 $B$，所以

$$(A\cup B)^c=A^c\cap B^c.$$

---

元素追踪：把集合式拆回逻辑式

证明集合命题时，最可靠的主角不是整张维恩图，而是一个任取的元素 $x$。我们不知道 $x$ 是谁，也不挑选一个特别方便的 $x$；正因为它是任意的，最后得到的结论才覆盖全部元素。

证明包含

要证明 $A\subseteq B$，标准骨架是：

如果要证明 $A\nsubseteq B$，任务正好相反：只需找出一个见证元素 $x$，使得 $x\in A$ 且 $x\notin B$。

证明相等

由集合相等的定义，常用两种写法：

$$A=B \quad\Longleftrightarrow\quad \forall x\,(x\in A\leftrightarrow x\in B),$$

或者证明双向包含：

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

连续的“当且仅当”适合成员条件能够直接等价改写的恒等式；双向包含适合两个方向使用不同构造或不同论证的场景。两种方法背后都是外延相等。

完整示范：证明分配律

证明

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

先别急着写“显然”。我们先说思路：左边要求 $x$ 在 $A$ 中，并且在 $B$ 或 $C$ 中。逻辑分配律会把它拆成“在 $A$ 和 $B$ 中，或者在 $A$ 和 $C$ 中”，这正是右边。

任取元素 $x$，有

$$\begin{aligned} x\in A\cap(B\cup C) &\Longleftrightarrow x\in A\text{ 且 }x\in B\cup C\\ &\Longleftrightarrow x\in A\text{ 且 }(x\in B\text{ 或 }x\in C)\\ &\Longleftrightarrow (x\in A\text{ 且 }x\in B) \text{ 或 }(x\in A\text{ 且 }x\in C)\\ &\Longleftrightarrow x\in A\cap B\text{ 或 }x\in A\cap C\\ &\Longleftrightarrow x\in(A\cap B)\cup(A\cap C). \end{aligned}$$

任意 $x$ 属于左边当且仅当属于右边，所以两个集合相等。

这段证明里每一步都有明确依据：交集定义、并集定义、命题逻辑的分配律、再合回交集和并集。所谓“把思考过程暴露出来”，在集合证明里就是别让这些依据藏在“显然”二字后面。

完整示范：证明德摩根律

证明

$$(A\cup B)^c=A^c\cap B^c.$$

任取 $x\in U$，则

$$\begin{aligned} x\in(A\cup B)^c &\Longleftrightarrow x\notin A\cup B\\ &\Longleftrightarrow \text{并非}(x\in A\text{ 或 }x\in B)\\ &\Longleftrightarrow x\notin A\text{ 且 }x\notin B\\ &\Longleftrightarrow x\in A^c\text{ 且 }x\in B^c\\ &\Longleftrightarrow x\in A^c\cap B^c. \end{aligned}$$

第三行到第四行就是命题逻辑中的德摩根律。我们不是凭图形把并集改成交集，而是在否定一个“或”命题。

---

反例：找出两边分歧的那个元素

一个集合恒等式声称“对所有允许的集合都成立”。要推翻它，不需要分析所有集合，只要找出一组集合让左右两边不同。

最有信息量的反例会同时给出一个见证元素：它属于等式的一边，却不属于另一边。比如错误等式

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

右边的整个 $C$ 没有受到 $A$ 的限制。于是我们故意挑一个 $x\in C$ 且 $x\notin A$。这个 $x$ 一定属于右边，因为右边直接并上了 $$；它却不属于左边，因为左边要求元素先在 中。

若要写成最小的具体反例，可以取

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

那么

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

而

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

左右不相等，见证元素就是 $2$。

怎样有目的地构造反例

遇到可疑等式时，可以按下面的顺序找：

练习：判断下面等式是否总成立。

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

查看分析与反例

它不总成立。左边的 $A$ 没有受到 $C$ 的限制，右边却要求所有元素最终都在 $C$ 中。令 $A=\{1\}$，$B=\varnothing$，$C=\varnothing$。左边是 ，右边是 ，见证元素 只属于左边。

---

维恩图能做什么，不能做什么

两三个集合的维恩图非常适合做草稿。它能帮我们看到候选区域，猜一个恒等式，或发现某个元素应该放在哪里才能制造反例。可一旦进入证明，图就有几条绕不过去的边界。

第一，图形表达的是一种布局，不自动保证实际集合占满每个区域。两个相交的圆画出了公共区域，只表示“这里可以放同时属于两个集合的元素”，不代表交集一定非空。

第二，补集依赖论域。没有画出论域边框时，“圆外”究竟到哪里结束并不清楚。图纸边缘不是数学上的论域边界。

第三，边界上的点容易造成歧义。数学里元素是否属于集合必须确定，不能靠一个点看起来更接近哪条曲线来判断。

第四，普通三圆图对三个集合还能勉强列出八种成员状态；集合继续增加时，区域迅速增多，图会拥挤甚至无法清楚表现所有组合。元素条件和逻辑式不会遇到这个问题。

第五，一张图至多展示某种一般构型的直觉，却没有自动处理空集、集合相等、集合包含等退化情形。正式证明必须覆盖这些情况。

---

把本章的方法带到关系与函数

走到这里，集合语言已经形成了一条完整的推理链：论域给出候选对象，描述法用谓词筛选元素，子集把筛选条件变成全称蕴含，集合相等把问题变成双向等价，集合运算再把成员条件翻译成“且、或、非”。

以后遇到集合证明，可以按这个顺序检查：

1. 论域是什么，补集相对于谁？
2. 当前符号两边是元素还是集合，$\in$ 与 $\subseteq$ 有没有用错？
3. 能否把并、交、差、补逐个展开成成员条件？
4. 目标是证明包含、证明相等，还是用反例推翻全称断言？
5. 若证明相等，是连续写“当且仅当”更自然，还是分别证明两个包含更清楚？

下一步，我们会研究 $A\times B$ 的子集。一个关系会挑出某些有序对，例如“学生选修课程”会挑出若干 $(\text{学生},\text{课程})$；一个函数还会要求每个输入恰好配到一个输出。到那时，量词不会消失，集合也不会退场：关系的条件、函数的定义域和值域，仍然是在回答“哪些对象属于哪个集合”。

2

下面哪些断言对任意集合 A、B 都成立？

A.∅⊆AB.A−B=B−AC.A∩B⊆AD.A∈P(A)E.A×∅=∅

提交