元数据卡
- 前置知识：第2章 集合论，第4章 递归
- 预计时间：50 分钟
- 核心难度：进阶
- 完成标志：掌握关系的性质，区分函数的不同类型，理解等价关系与偏序关系
你的进度
第五层。馆长递给你一张对照表——左侧是"用户 ID"，右侧是"用户姓名"。他又递来一张——左侧是"学生"，右侧是"选课列表"。这两张表有什么共同结构？又有什么不同？
你的任务
你每天都在操作"关系"——数据库表是关系，变量赋值是关系，API 调用是映射。但在数学上，关系是集合的笛卡尔积的子集，函数是一类特殊的关系。这一章让你理清"关系"和"函数"这两个概念的精确数学定义。
本章分层
- 必读：关系的定义与性质，等价关系，函数的单射/满射/双射
- 选读：偏序与格，闭包
破局 · 溯源
你在设计数据库模式。一个用户可以关注另一个用户——这是follows关系。一个学生属于一个班级——这是belongs_to关系。你直觉上知道区分"1 对 1"、"1 对多"、"多对多"，但数学上它们的区别是什么？
关系是两个集合元素的配对。A 和 B 的笛卡尔积 A×B 是所有有序对 (a,b) 的集合，其中 a∈A, b∈B。A 到 B 的关系 R 是 A×B 的子集。
A = {1, 2, 3}, B = {a, b}
A×B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}
关系 R = {(1,a), (2,a), (3,b)} // 描述了一个配对规则关系的性质是判断它属于什么类型的依据：
| 性质 | 定义 | 示例 |
|---|---|---|
| 自反 | 每个元素都与自己相关 | "等于"是自反的 |
| 对称 | aRb 则 bRa | "是兄弟"是对称的 |
| 反对称 | aRb 且 bRa 则 a=b | "小于等于"是反对称的 |
| 传递 | aRb 且 bRc 则 aRc | "大于"是传递的 |
等价关系满足自反、对称、传递。等价关系将集合划分为互不相交的等价类。"模 3 同余"是一个典型等价关系——所有整数被分为 [0], [1], [2] 三个等价类。你在做 hashCode() 时就是在定义等价关系：a.equals(b) → a 和 b 必须在同一个等价类中。
偏序关系满足自反、反对称、传递。典型例子：集合的包含关系 ⊆。文件系统的目录结构、类型系统的子类型关系、任务的依赖关系——这些都是偏序。
函数是一种特殊的关系：每个输入恰好对应一个输出。
f: A → B 读作"从 A 到 B 的函数"。A 是定义域，B 是值域。
函数有三种核心性质：
- 单射（一对一）：不同的输入映射到不同的输出。f(a₁) = f(a₂) → a₁ = a₂。
- 满射（到上）：值域中的每个元素都有至少一个输入映射到它。
- 双射（一一对应）：是单射和满射——每个输入对应唯一输出，每个输出有唯一输入。
数据库中的唯一索引就是单射约束。双射在密码学中至关重要：加密函数（双射）确保你能解密回来。
函数的类型在编程中同样重要：
- 偏函数：不是所有输入都有定义。比如"1/x"在 x=0 时无定义。对应到编程就是返回 Optional 或抛出异常的函数。
- 全函数：所有输入都有定义。编程中大部分函数是全函数——至少从语法角度看。
- 递归函数：用自身定义，有终止条件。前面一章已经深入讨论过。
常见陷阱
- 混淆关系和函数。所有函数都是关系，但不是所有关系都是函数。关系可以一个输入对应多个输出，函数不行。
- 把"关系数据库"中的"关系"误解为数学关系。关系数据库中的"关系"指的是表（即笛卡尔积的子集），两者在概念上有渊源，但不完全等同。
- 混淆函数签名和函数定义。
f: int → int只告诉你输入输出类型，不告诉你计算规则。f(x) = x²才是完整的定义。
通关挑战
- 判断关系 R = {(a,b) | a 和 b 同年出生} 是否自反、对称、传递。
- 给定函数 f: Z → Z, f(x) = 2x，判断它是单射还是满射（Z 是整数集）。
- 用 Python 实现一个简单的等价关系检查——给定关系矩阵，判断它是否满足自反、对称、传递性。
旅人笔记
关系是配对，函数是映射。加限制条件后，关系变成等价关系（分类）、偏序（排序）、函数（确定性映射）。这是离散数学的核心视角之一。
→ 下一站预告：离散的数学到这里告一段落。下一段你将进入组合数学的世界——"如果有 5 件衣服、3 条裤子，有多少种穿法？"从逻辑转向计数。