04 集合论：一切数学结构的容器

集合是数学中最朴素、最基本的概念之一。它如此基础，以至于几乎不可能用更简单的概念来定义它。康托尔说：“集合就是我们可以明确感知其为一整体的多个对象的总和。” 在这篇博客中，我们将从空集出发，一路探索到无穷集合的奇妙世界。

---

一、什么是集合？

集合（Set）是由确定的不同对象构成的整体。这些对象称为集合的元素（Element）。

朴素定义

集合是由满足某种特定性质的对象所组成的整体。

• a ∈ A：a 是集合 A 的元素（属于）
• a ∉ A：a 不是集合 A 的元素（不属于）

集合的表示方法

1. 列举法：直接列出所有元素

   • A = {1, 2, 3, 4, 5}
   • B = {a, e, i, o, u}（元音字母集合）

2. 描述法：用性质描述元素

   • A = {x | x 是正整数且 x ≤ 5}
   • B = {x | x 是偶数}
   • C = {x ∈ ℕ | x² < 20}

3. Venn 图：用图形直观表示

   • 画一个矩形表示全集
   • 画圆表示集合
   • 圆的位置和重叠表示集合关系

---

二、集合的基本关系

1. 子集（Subset）

A ⊆ B 当且仅当 ∀x (x ∈ A → x ∈ B)

即：A 的每个元素都是 B 的元素。

例子：

• {1, 2} ⊆ {1, 2, 3}
• ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ

2. 真子集（Proper Subset）

A ⊂ B 当且仅当 A ⊆ B 且 A ≠ B

即：A 是 B 的子集，但 B 至少有一个元素不在 A 中。

3. 集合相等

A = B 当且仅当 A ⊆ B 且 B ⊆ A

即：两个集合相等，当且仅当它们有完全相同的元素。证明集合相等的基本方法：证明互相包含。

---

三、集合的基本运算

1. 并集（Union）：∪

A ∪ B = {x | x ∈ A ∨ x ∈ B}

“A 或 B 中的元素”。

例子：{1, 2, 3} ∪ {2, 3, 4} = {1, 2, 3, 4}

Venn 图：两个圆覆盖的全部区域。

2. 交集（Intersection）：∩

A ∩ B = {x | x ∈ A ∧ x ∈ B}

“同时属于 A 和 B 的元素”。

例子：{1, 2, 3} ∩ {2, 3, 4} = {2, 3}

Venn 图：两个圆重叠的区域。

3. 差集（Difference）：− 或 \

A − B = {x | x ∈ A ∧ x ∉ B}

“在 A 中但不在 B 中的元素”。

例子：{1, 2, 3} − {2, 3, 4} = {1}

Venn 图：A 圆中不与 B 重叠的部分。

4. 补集（Complement）：Aᶜ 或 Ā

Aᶜ = {x | x ∈ U ∧ x ∉ A} = U − A

其中 U 是全集（Universal Set），即当前讨论中所有可能元素的集合。

例子：若 U = {1, 2, 3, 4, 5}，A = {1, 2}，则 Aᶜ = {3, 4, 5}

Venn 图：矩形中 A 圆以外的区域。

5. 对称差（Symmetric Difference）：⊕ 或 Δ

A ⊕ B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B)

“只属于 A 或只属于 B 的元素”（即异或）。

例子：{1, 2, 3} ⊕ {2, 3, 4} = {1, 4}

---

四、集合运算的代数性质

集合运算满足许多漂亮的代数律，和实数的运算律非常相似：

基本运算律

名称	公式
幂等律	A ∪ A = A；A ∩ A = A
交换律	A ∪ B = B ∪ A；A ∩ B = B ∩ A
结合律	(A ∪ B) ∪ C = A ∪ (B ∪ C)；同理 ∩
分配律	A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)；A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

德摩根律（De Morgan’s Laws）⭐

公式	对应逻辑
(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ	¬(p ∨ q) ≡ ¬p ∧ ¬q
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ	¬(p ∧ q) ≡ ¬p ∨ ¬q

这就是集合与逻辑之间的深刻对应：集合运算和逻辑运算本质上是同构的！

---

五、幂集：集合的"集合"

定义

A 的幂集（Power Set），记作 P(A) 或 2ᴬ，是 A 的所有子集所组成的集合。

P(A) = {B | B ⊆ A}

例子：A = {1, 2}

P(A) = {∅, {1}, {2}, {1, 2}}

幂集的大小

若 |A| = n（A 有 n 个元素），则 |P(A)| = 2ⁿ

为什么？

A 的每个元素在子集中都有"出现"或"不出现"两种选择。n 个元素就有 2 × 2 × … × 2 = 2ⁿ 种组合，每种组合对应一个子集。

这就是幂集记作 2ᴬ 的原因！

---

六、特殊的集合

1. 空集（Empty Set）：∅

不含任何元素的集合。它有一些有趣的性质：

• ∅ ⊆ A 对任何集合 A 都成立（ vacuously true，因为不存在 x ∈ ∅ 使得 x ∉ A）
• |∅| = 0
• P(∅) = {∅}（注意：不是 ∅ 本身！空集的幂集包含一个元素——空集本身）
• |P(∅)| = 2⁰ = 1

2. 单元素集合（Singleton）

只含一个元素的集合，如 {a}、{∅}。

⚠️ 注意区分：a 和 {a} 不一样！

• a 是元素
• {a} 是集合，它的唯一元素是 a
• 所以 a ∈ {a} 为真，但 a ⊆ {a} 不一定为真（除非 a 本身也是集合）

3. 全集（Universal Set）

当前讨论范围内所有元素的集合。全集不是绝对的，取决于上下文。

---

七、集合的基数与无穷

1. 有限集与无限集

• 有限集：元素个数是一个自然数
• 无限集：元素个数不是任何自然数

2. 基数的初步概念

对于有限集，基数就是元素的个数。但无限集呢？

康托尔（Georg Cantor）的伟大发现：不同的无限集合可以有"大小"之分！

3. 可数无穷（ℵ₀）

如果一个无限集合的元素可以按某种顺序"一个一个数出来"（与自然数集建立一一对应），就称它是可数无穷（Countably Infinite）。

经典例子：

• 自然数集 ℕ = {0, 1, 2, 3, …}：显然可数
• 整数集 ℤ = {…, -2, -1, 0, 1, 2, …}：可数！可以按 0, 1, -1, 2, -2, … 的顺序排列
• 有理数集 ℚ：可数！虽然有理数"密密麻麻"，但仍然可以一个一个排出来（通过对角线枚举法）

这些集合的基数都是 ℵ₀（阿列夫零）。

4. 不可数无穷（𝔠）

但康托尔用对角线论证法证明了：

实数集 ℝ 是不可数无穷！

无论你怎么尝试把实数排成一列，总有一个实数被漏掉。这意味着实数集"比"自然数集"大"——即使它们都是无限集合。

实数集的基数记为 𝔠（连续统的基数），且 𝔠 > ℵ₀。

5. 幂集与更大的无穷

康托尔还证明了：

对任何集合 A，|P(A)| > |A|

所以：

• |P(ℕ)| > ℵ₀
• |P(P(ℕ))| > |P(ℕ)|
• 依此类推，无穷集合有无穷多个层次

这就是集合论中最令人惊叹的发现之一：无穷也有大小之分！

---

八、集合论与计算机科学的关联

集合概念	计算机对应
集合	数据结构中的集合（Set/HashSet）
并集 ∪	set1.union(set2)
交集 ∩	set1.intersection(set2)
差集 −	set1.difference(set2)
对称差 ⊕	set1.symmetric_difference(set2)
子集 ⊆	set1.issubset(set2)
幂集	子集枚举/位运算生成
空集 ∅	空集合 set()
全集	当前论域/类型系统

用位运算表示子集

对于有限集合，子集可以用二进制数编码：

A = {a, b, c}，用 3 位二进制表示：

• 第 1 位表示 a 是否在子集中
• 第 2 位表示 b 是否在子集中
• 第 3 位表示 c 是否在子集中

子集	二进制	十进制
∅	000	0
{a}	001	1
{b}	010	2
{a, b}	011	3
{c}	100	4
{a, c}	101	5
{b, c}	110	6
{a, b, c}	111	7

这就是为什么幂集有 2ⁿ 个元素！每个子集对应一个 n 位二进制数，范围是 0 到 2ⁿ−1。

Python 代码生成幂集：

def power_set(elements):
    n = len(elements)
    result = []
    for mask in range(1 << n):  # 0 到 2^n - 1
        subset = [elements[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result

print(power_set(['a', 'b', 'c']))
# 输出: [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]

---

九、集合论悖论与公理化

罗素悖论（Russell’s Paradox）

集合论的朴素定义导致了著名的悖论：

设 R = {x | x ∉ x}（所有不包含自身的集合所构成的集合）

问：R ∈ R 吗？

• 如果 R ∈ R，那么根据定义 R ∉ R（因为 R 只包含那些不包含自身的集合）
• 如果 R ∉ R，那么根据定义 R ∈ R（因为 R 不包含自身）

这就是悖论！

这个悖论说明不能随意构造集合。为了避免这样的悖论，数学家建立了公理化集合论（ZFC 公理系统），对集合的构造加以限制。

在计算机科学中，我们主要处理有限集合，所以通常不会遇到这些悖论。但了解它们有助于理解集合论的深层结构。

---

十、本章小结

概念	要点
集合	确定对象的总体
子集 ⊆	一个集合的所有元素属于另一个集合
并集 ∪	属于 A 或 B
交集 ∩	同时属于 A 和 B
差集 −	在 A 中但不在 B 中
补集 ᶜ	全集中不在 A 中的元素
对称差 ⊕	只属于 A 或只属于 B
幂集 P(A)	所有子集构成的集合，大小为 2^
德摩根律	(A∪B)ᶜ = Aᶜ∩Bᶜ，(A∩B)ᶜ = Aᶜ∪Bᶜ
可数无穷	能与自然数建立一一对应，如 ℚ
不可数无穷	不能与 ℕ 建立一一对应，如 ℝ
康托尔定理

---

思考与练习

1. 设 A = {1, 2, 3}，B = {2, 3, 4}，计算：

   • A ∪ B, A ∩ B, A − B, B − A, A ⊕ B

2. 用 Venn 图验证分配律：A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

3. 证明：A ⊆ B 当且仅当 A ∩ B = A 当且仅当 A ∪ B = B

4. 写出 P({a, b, c}) 的所有元素，并用二进制编码验证。

5. 用对角线论证法证明：对于任意集合 A，|P(A)| > |A|。（提示：假设存在从 A 到 P(A) 的满射，构造一个"不在列表中"的子集）

6. 编程实践：实现一个函数，输入一个有限集合，输出它的幂集（用位运算法）。

---

📌 下一篇预告：集合定义好了，但元素之间如何关联？两个元素可以是"朋友"、“父子”、"大于"等关系。把这些关系抽象化，我们就得到了二元关系——这是数据库、图论、类型系统等众多领域的核心概念。我们将学习关系的表示、运算、性质，以及最重要的：等价关系和偏序关系。

---

集合是数学的容器，而容器里的东西如何组织，才是故事的开始。 📦