2.1 集合与集合运算

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

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

集合、属于、相等

例子：

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

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

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

1. 证明 $A \subset B$
2. 证明 $B \subset A$

建立新集合

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

| 运算 | 符号 | 定义 | | --- | --- | --- | | 并集 | $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$。

这些等式怎么证

本单元的集合恒等式不是靠死记，而是靠逐个元素追踪来证明。

核心证明法是 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 \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$”。

怎样仔细证明集合恒等式

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

标准证明方法通常是：

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

这种逐元素追踪的方法，后面还会再次出现在德摩根律、关系，以及数系构造中。

有限集合怎样计数

集合语言不只用来分类，也直接控制计数。

如果 $A$、$B$ 都是有限集合，那么：

• $|A \times B| = |A|\,|B|$；
• $|P(A)| = 2^{|A|}$；
• $|A \cup B| = |A| + |B| - |A \cap B|$。

并集公式之所以要减交集，是因为交集中的元素如果直接相加，会被算两次。

子集证明检查表

子集证明会反复出现，所以最好让它变成固定套路。

如果要证明 $A \subseteq B$，就从任取 $x \in A$ 开始，再用 $A$ 的定义推出 足够信息，最后证明同一个 x 其实也在 $B$ 里面。由于 x 是任取，结论 就对 $A$ 的每个元素成立。

这种 direct proof 模式，后面在关系、偏序，以及等价类中都会再次出现。

常见错误

小检查

为什么这一单元重要

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

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