集合

本章主线：集合与元素 → 集合运算 → 幂集 → 笛卡尔积 → 算法中的集合表示。

1 集合与元素

集合是由若干确定对象组成的整体，其中的对象称为集合的元素。

若元素 $x$ 属于集合 $A$，记作 $x\in A$；若 $x$ 不属于集合 $A$，记作 $x\notin A$。

例如，设 $A=\{1,2,3\}$，则 $1\in A$，而 $4\notin A$。

集合中的元素具有三个基本特点：

• 元素是否属于集合必须是确定的；
• 元素没有先后顺序；
• 同一元素重复书写不会重复计数。

因此，$\{1,2,3\}=\{3,2,1\}$，且 $\{1,1,2,3\}=\{1,2,3\}$。

集合与序列不同。序列通常关心元素顺序，而集合只关心包含哪些元素。

---

2 集合的表示方法

2.1 列举法

直接列出集合中的全部元素。

例如，$A=\{1,3,5,7,9\}$。

列举法适合元素数量较少的有限集合。

2.2 描述法

通过元素满足的条件表示集合。

例如，所有偶整数可以写成 $A=\{x\in\mathbb Z\mid 2\mid x\}$。

描述法的一般形式为

$$\{\text{讨论范围中的元素}\mid\text{元素满足的条件}\}.$$

例如，$B=\{x\in\mathbb Z\mid 1\le x\le 10\}$ 表示从 $1$ 到 $10$ 的全部整数。

描述法中应同时注意：

• 元素来自什么范围；
• 元素需要满足什么条件。

---

3 常见数集

常见数集包括：

• $\mathbb N$：自然数集；
• $\mathbb Z$：整数集；
• $\mathbb Q$：有理数集；
• $\mathbb R$：实数集。

它们满足 $\mathbb N\subseteq\mathbb Z\subseteq\mathbb Q\subseteq\mathbb R$。

不同教材对 $0\in\mathbb N$ 可能有不同约定，使用时应先确认定义。

---

4 集合相等

集合 $A$ 与集合 $B$ 相等，当且仅当它们包含完全相同的元素。

形式化地，

$$A=B\Longleftrightarrow \forall x,\ x\in A\Longleftrightarrow x\in B.$$

证明两个集合相等时，通常分别证明：

1. 任取 $x\in A$，能够推出 $x\in B$；
2. 任取 $x\in B$，能够推出 $x\in A$。

这种方法也称为双向包含法。

---

5 子集

若集合 $A$ 中的每个元素都属于集合 $B$，则称 $A$ 是 $B$ 的子集，记作 $A\subseteq B$。

其定义为

$$A\subseteq B\Longleftrightarrow \forall x,\ x\in A\Longrightarrow x\in B.$$

例如，若 $A=\{1,2\}$，$B=\{1,2,3\}$，则 $A\subseteq B$。

每个集合都是自身的子集，因此 $A\subseteq A$。

若 $A\subseteq B$ 且 $A\ne B$，则称 $A$ 是 $B$ 的真子集，记作 $A\subsetneq B$。

---

6 区分属于与包含

$x\in A$ 表示元素 $x$ 属于集合 $A$。

$A\subseteq B$ 表示集合 $A$ 是集合 $B$ 的子集。

例如，设 $A=\{1,2,3\}$，则 $1\in A$，而 $\{1,2\}\subseteq A$。

再设 $B=\{1,\{1,2\},3\}$，则 $\{1,2\}\in B$，因为集合 $\{1,2\}$ 本身是 $B$ 的一个元素。

但 $\{1,2\}\nsubseteq B$，因为虽然 $1\in B$，却有 $2\notin B$。

因此，$\in$ 描述元素与集合之间的关系，$\subseteq$ 描述集合与集合之间的关系。

---

7 空集

不含任何元素的集合称为空集，记作 $\varnothing$ 或 $\{\}$。

空集的元素数量为 $|\varnothing|=0$。

集合 $\{\varnothing\}$ 含有一个元素，这个元素恰好是空集，因此 $|\{\varnothing\}|=1$。

空集是任意集合的子集，即 $\varnothing\subseteq A$。

这是因为不存在元素 $x$ 满足 $x\in\varnothing$ 且 $x\notin A$。

---

8 全集

在一个具体问题中，所有允许讨论的对象组成的集合称为全集，常记作 $U$。

例如，若 $U=\{1,2,3,4,5,6\}$，则之后讨论的集合都默认是 $U$ 的子集。

在算法中，全集可以是：

• 所有顶点；
• 所有边；
• 所有下标；
• 所有合法状态；
• 所有可能取值。

全集取决于当前问题的讨论范围。

---

9 集合运算

9.1 并集

集合 $A$ 与集合 $B$ 的并集由至少属于其中一个集合的元素组成，记作 $A\cup B$。

定义为 $x\in A\cup B\Longleftrightarrow x\in A\lor x\in B$。

例如，若 $A=\{1,2,3\}$，$B=\{3,4,5\}$，则 $A\cup B=\{1,2,3,4,5\}$。

这里的“或”是包含性的“或”，允许元素同时属于 $A$ 和 $B$。

---

9.2 交集

集合 $A$ 与集合 $B$ 的交集由同时属于两个集合的元素组成，记作 $A\cap B$。

定义为 $x\in A\cap B\Longleftrightarrow x\in A\land x\in B$。

例如，若 $A=\{1,2,3\}$，$B=\{3,4,5\}$，则 $A\cap B=\{3\}$。

若 $A\cap B=\varnothing$，则称 $A$ 与 $B$ 不相交。

---

9.3 差集

集合 $A$ 与集合 $B$ 的差集由属于 $A$ 但不属于 $B$ 的元素组成，记作 $A\setminus B$。

定义为 $x\in A\setminus B\Longleftrightarrow x\in A\land x\notin B$。

例如，若 $A=\{1,2,3,4,5\}$，$B=\{2,4,6\}$，则 $A\setminus B=\{1,3,5\}$。

差集通常不满足交换律，即一般有 $A\setminus B\ne B\setminus A$。

---

9.4 补集

设全集为 $U$，且 $A\subseteq U$。

集合 $A$ 的补集由全集中不属于 $A$ 的元素组成，记作 $A^{\complement}$ 或 $\overline A$。

其定义为 $A^{\complement}=U\setminus A$。

例如，若 $U=\{1,2,3,4,5,6\}$，$A=\{2,4,6\}$，则 $A^{\complement}=\{1,3,5\}$。

补集依赖于全集。

---

10 用元素法证明集合恒等式

证明两个集合相等时，可以任取元素 $x$，把集合关系逐步转化为逻辑条件。

例如证明

$$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 A$ 且“$x\in B$ 或 $x\in C$”。

这又等价于“$x\in A$ 且 $x\in B$”，或“$x\in A$ 且 $x\in C$”。

因此，$x\in(A\cap B)\cup(A\cap C)$。

反方向同理，所以两个集合相等。

---

11 基本运算律

11.1 交换律

$A\cup B=B\cup A$。

$A\cap B=B\cap A$。

11.2 结合律

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

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

11.3 分配律

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

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

11.4 幂等律

$A\cup A=A$。

$A\cap A=A$。

11.5 吸收律

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

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

11.6 与空集、全集的运算

$A\cup\varnothing=A$。

$A\cap\varnothing=\varnothing$。

$A\cup U=U$。

$A\cap U=A$。

---

12 德摩根律

集合补集满足

$$(A\cup B)^{\complement}=A^{\complement}\cap B^{\complement},$$

$$(A\cap B)^{\complement}=A^{\complement}\cup B^{\complement}.$$

例如，$x\in(A\cup B)^{\complement}$ 表示 $x\notin A\cup B$。

这等价于 $x\notin A$ 且 $x\notin B$，也就是 $x\in A^{\complement}\cap B^{\complement}$。

---

13 集合的大小

有限集合 $A$ 的元素数量记作 $|A|$。

例如，若 $A=\{1,2,3\}$，则 $|A|=3$。

若 $A,B$ 为有限集合，则

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

原因是 $A\cap B$ 中的元素在 $|A|+|B|$ 中被重复计算了一次。

例如，若 $A=\{1,2,3\}$，$B=\{3,4,5\}$，则 $|A\cup B|=3+3-1=5$。

---

14 幂集

集合 $A$ 的所有子集组成的集合称为 $A$ 的幂集，记作 $\mathcal P(A)$。

例如，若 $A=\{1,2\}$，则

$$\mathcal P(A)=\{\varnothing,\{1\},\{2\},\{1,2\}\}.$$

若 $|A|=n$，则每个元素都有“选”或“不选”两种状态，因此 $|\mathcal P(A)|=2^n$。

幂集对应算法中的子集枚举与状态压缩。

---

15 笛卡尔积

设有两个集合 $A,B$。

从 $A$ 中选一个元素作为第一项，从 $B$ 中选一个元素作为第二项，得到有序对 $(a,b)$。

所有这样的有序对组成 $A$ 与 $B$ 的笛卡尔积：

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

例如，若 $A=\{1,2\}$，$B=\{a,b\}$，则

$$A\times B=\{(1,a),(1,b),(2,a),(2,b)\}.$$

若 $A,B$ 为有限集合，则 $|A\times B|=|A|\cdot|B|$。

通常有 $A\times B\ne B\times A$，因为有序对的顺序有意义。

笛卡尔积是后续定义关系与映射的基础。

---

16 集合与算法

16.1 访问状态

搜索过程中，可以定义已访问顶点集合：

$$V_{\mathrm{vis}}=\{v\in V\mid v\text{ 已访问}\}.$$

16.2 连通分量

一个连通分量本质上是顶点集合 $C\subseteq V$。

并查集维护的是顶点集合 $V$ 的动态划分。

16.3 子集枚举

若全集含有 $n$ 个元素，则共有 $2^n$ 个子集。

状态压缩常用一个 $n$ 位二进制数表示一个子集。

16.4 集合运算与位运算

在状态压缩中：

• 并集对应按位或；
• 交集对应按位与；
• 对称差对应按位异或；
• 补集对应按位取反后限制在全集范围内。

---

18 与后续内容的联系

• 笛卡尔积是定义 关系 的基础；
• 关系满足额外的存在性与唯一性条件后，就得到 映射；
• 集合运算与逻辑运算之间的对应，会在 命题逻辑与证明方法 中继续出现；
• 幂集与子集枚举连接状态压缩，但具体算法实现仍应放在算法知识库中。

---

19 本章思考题

1. 说明为什么 $\{1,2,3\}=\{3,2,1,1\}$。

2. 设 $A=\{1,\{1\}\}$，判断下列命题：

   • $1\in A$；
   • $\{1\}\in A$；
   • $\{1\}\subseteq A$；
   • $\varnothing\subseteq A$。

3. 设 $A=\{1,2,3,4\}$，$B=\{3,4,5,6\}$，求 $A\cup B$、$A\cap B$、$A\setminus B$ 与 $B\setminus A$。

4. 用元素法证明 $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$。

5. 写出集合 $A=\{1,2,3\}$ 的幂集。

6. 若 $|A|=4$，求 $|\mathcal P(A)|$。

7. 设 $A=\{1,2\}$，$B=\{a,b,c\}$，写出 $A\times B$，并计算其元素数量。

8. 思考并查集为什么维护的不是一个集合，而是一个集合划分。