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

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

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

一、什么是集合？

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

朴素定义

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

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

集合的表示方法

二、集合的基本关系

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}

四、集合运算的代数性质

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

基本运算律

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

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

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

定义

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(ℕ)|
• 依此类推，无穷集合有无穷多个层次

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

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

用位运算表示子集

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

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

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

这就是为什么幂集有 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 公理系统），对集合的构造加以限制。

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

十、本章小结

思考与练习

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

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