集合论

集合论是数学的基础！在《逻辑与集合》章节中，我们已经介绍了集合的基础知识。这里我们将深入探讨集合论的更多内容。

回顾：集合基础

在《逻辑与集合》章节中，我们已经学习了：

• 集合的定义和表示方法
• 集合的运算（并、交、补、差）
• 子集、真子集、幂集
• 集合的基数（元素个数）

关系

什么是关系？

关系（Relation）是两个集合之间的对应关系。

定义

集合 $A$ 和 $B$ 之间的二元关系 $R$ 是 $A \times B$ 的子集：

$R \subseteq A \times B$

如果 $(a, b) \in R$，则称 $a$ 与 $b$ 有关系 $R$，记作 $aRb$。

例子

例子：$A = \{1, 2, 3\}$，$B = \{2, 4, 6\}$

关系 $R = \{(1, 2), (2, 4), (3, 6)\}$ 表示"$a$ 的一半等于 $b$"。

关系的性质

自反性

如果对于所有 $a \in A$，都有 $(a, a) \in R$，则关系 $R$ 是自反的（Reflexive）。

对称性

如果对于所有 $(a, b) \in R$，都有 $(b, a) \in R$，则关系 $R$ 是对称的（Symmetric）。

传递性

如果对于所有 $(a, b) \in R$ 和 $(b, c) \in R$，都有 $(a, c) \in R$，则关系 $R$ 是传递的（Transitive）。

反对称性

如果对于所有 $(a, b) \in R$ 和 $(b, a) \in R$，都有 $a = b$，则关系 $R$ 是反对称的（Antisymmetric）。

等价关系

如果关系 $R$ 是自反、对称、传递的，则称 $R$ 是等价关系（Equivalence Relation）。

例子：整数集合上的"模 $n$ 同余"关系是等价关系。

偏序关系

如果关系 $R$ 是自反、反对称、传递的，则称 $R$ 是偏序关系（Partial Order）。

例子：集合上的"子集"关系是偏序关系。

函数

什么是函数？

函数（Function）是一种特殊的关系，每个输入对应唯一的输出。

定义

从集合 $A$ 到集合 $B$ 的函数 $f$ 是一个关系，满足：

1. 对于每个 $a \in A$，存在 $b \in B$，使得 $(a, b) \in f$
2. 如果 $(a, b_1) \in f$ 且 $(a, b_2) \in f$，则 $b_1 = b_2$

记作 $f: A \to B$。

函数的性质

单射（一对一）

如果对于所有 $a_1, a_2 \in A$，$f(a_1) = f(a_2)$ 蕴含 $a_1 = a_2$，则函数 $f$ 是单射（Injective）。

满射（映上）

如果对于每个 $b \in B$，存在 $a \in A$，使得 $f(a) = b$，则函数 $f$ 是满射（Surjective）。

双射（一一对应）

如果函数 $f$ 既是单射又是满射，则称 $f$ 是双射（Bijective）。

复合函数

如果 $f: A \to B$ 和 $g: B \to C$，则复合函数 $g \circ f: A \to C$ 定义为：

$(g \circ f)(a) = g(f(a))$

逆函数

如果 $f: A \to B$ 是双射，则存在逆函数 $f^{-1}: B \to A$，满足：

$f^{-1}(f(a)) = a \quad \text{且} \quad f(f^{-1}(b)) = b$

基数

有限集合的基数

有限集合 $A$ 的基数（Cardinality）是 $A$ 中元素的个数，记作 $|A|$。

无限集合的基数

可数无限

如果集合 $A$ 与自然数集合 $\mathbb{N}$ 之间存在双射，则称 $A$ 是可数无限（Countably Infinite），记作 $|A| = \aleph_0$。

例子：整数集合 $\mathbb{Z}$、有理数集合 $\mathbb{Q}$ 都是可数无限的。

不可数无限

如果集合 $A$ 是无限的但不是可数的，则称 $A$ 是不可数无限（Uncountably Infinite）。

例子：实数集合 $\mathbb{R}$ 是不可数无限的，$|\mathbb{R}| = \mathfrak{c}$。

基数比较

等势

如果两个集合之间存在双射，则称它们等势（Equipotent），记作 $|A| = |B|$。

基数大小

如果存在从 $A$ 到 $B$ 的单射，则 $|A| \le |B|$。

如果 $|A| \le |B|$ 且 $|A| \neq |B|$，则 $|A| < |B|$。

康托尔定理

对于任何集合 $A$，都有 $|A| < |\mathcal{P}(A)|$，其中 $\mathcal{P}(A)$ 是 $A$ 的幂集。

选择公理

选择公理

选择公理（Axiom of Choice）是集合论中的一个重要公理：

对于任何非空集合的集合，存在一个函数，从每个集合中选择一个元素。

应用

选择公理在数学中有广泛应用，例如：

• 证明某些存在性定理
• 构造某些数学对象
• 证明某些等价性

集合论的应用

计算机科学

• 💻 数据结构：集合、映射、关系
• 🔢 数据库：关系数据库理论
• 🔐 形式化方法：形式化验证

数学

• 📐 数学基础：数学的基础理论
• 🔢 抽象代数：群、环、域
• 📊 拓扑学：拓扑空间

常见错误

错误 1：关系和函数混淆

• 关系：一个输入可以对应多个输出
• 函数：一个输入只能对应一个输出

错误 2：基数比较错误

要正确比较无限集合的基数。

错误 3：选择公理使用错误

要正确理解和使用选择公理。

小练习

1. 判断关系 $R = \{(a, b) | a, b \in \mathbb{Z}, a < b\}$ 是否具有自反性、对称性、传递性
2. 判断函数 $f(x) = x^2$ 是否是单射、满射、双射
3. 证明整数集合是可数无限的
4. 应用题：在数据库中，如何用关系表示表之间的关联？

---

💡 小贴士：集合论是数学的基础。记住：函数是特殊的关系（每个输入对应唯一输出），等价关系是自反、对称、传递的关系。掌握集合论，你就能理解数学的各个分支！