05 关系与函数：元素之间的秘密纽带

05 关系与函数元素之间的秘密纽带如果集合是盛物的容器那么关系就是容器里物品之间的故事线。两个元素之间是朋友、“大于”、“属于同一个班级”——这些联系抽象化后就形成了数学中的关系。而函数则是关系中最规则、最可控的一种特殊形态。一、什么是二元关系1. 从直觉到定义先看几个生活中的关系“3 大于 2”“张三和李四是朋友”“北京到上海的火车票价是 553 元”“5 整除 10”这些关系都有共同结构涉及两个对象或更多以及它们之间的某种联系。2. 笛卡尔积关系的舞台在定义关系之前我们需要一个舞台来放置所有可能的对象对笛卡尔积Cartesian ProductA × B {(a, b) | a ∈ A, b ∈ B}即A 和 B 的元素两两配对形成所有有序对。例子A {1, 2}, B {a, b}A × B {(1, a), (1, b), (2, a), (2, b)}|A × B| |A| × |B| 2 × 2 43. 二元关系的定义二元关系Binary RelationR 从 A 到 B 是笛卡尔积 A × B 的一个子集R ⊆ A × B即关系就是一组有序对的集合。若 (a, b) ∈ R记作 aRb读作a 与 b 有 R 关系。例子设 A {1, 2, 3}, B {2, 3, 4}大于关系R {(3, 2), (2, 2)? 不对2 不大于 2。R {(3, 2), (3, 2)? 让我重新想…}实际上大于关系R₁ {(3, 2), (3, 2)? 不让我重新列3 2: (3, 2) ✓3 3? 不3 4? 不2 2? 不2 3? 不2 4? 不1 2? 不…等等让我重新想如果 A {1,2,3}, B {2,3,4}3 2 → (3, 2) ∈ R好像只有这一个。让我换一个例子设 A {1, 2, 3, 4}整除关系R {(a, b) | a 整除 b}(1, 1), (1, 2), (1, 3), (1, 4) — 1 整除所有数(2, 2), (2, 4) — 2 整除 2 和 4(3, 3) — 3 整除 3(4, 4) — 4 整除 4R {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}二、关系的表示方法1. 集合表示法直接列出所有有序对R {(a, b), (c, d), …}2. 关系矩阵Relation Matrix对于有限集合上的关系可以用矩阵表示M_R 是一个 |A| × |B| 的矩阵其中M_R[i][j] 1 如果 (aᵢ, bⱼ) ∈ R否则为 0例子A {1, 2, 3}, 整除关系从 A 到 A1231111201030013. 关系图有向图用有向图Directed Graph表示每个元素是一个节点若 (a, b) ∈ R则从 a 到 b 画一条有向边这是图论与关系的交汇点三、关系的运算1. 定义域与值域定义域Domaindom® {a | ∃b, (a, b) ∈ R}值域Rangeran® {b | ∃a, (a, b) ∈ R}2. 逆关系R⁻¹ {(b, a) | (a, b) ∈ R}即把关系中的所有有序对反过来。例子若 R “大于”则 R⁻¹ “小于”。3. 关系的复合R ∘ S {(a, c) | ∃b, (a, b) ∈ R ∧ (b, c) ∈ S}即先走 R 关系再走 S 关系能到达的终点。例子R “…的父亲”即 (a, b) 表示 a 是 b 的父亲S “…的母亲”R ∘ R “…的祖父”父亲的父亲R ∘ S “父亲的母亲” 奶奶S ∘ R “母亲的父亲” 外公注意关系复合一般不满足交换律即 R ∘ S ≠ S ∘ R。四、关系的性质五种基本类型当 A 上的关系 R ⊆ A × A即关系定义在同一个集合上时我们可以讨论以下五种基本性质1. 自反性Reflexive∀a ∈ A, (a, a) ∈ R即每个元素都和自己有关系。例子✅ “等于”每个数都等于自己✅ “整除”每个数都整除自己✅ “同班同学”每个人都是自己的同班同学❌ “大于”3 不大于 3❌ “父子”没有人是自己的父亲关系矩阵特征对角线全为 1。2. 反自反性Irreflexive∀a ∈ A, (a, a) ∉ R即没有任何元素和自己有关系。例子✅ “大于”没有任何数大于自己✅ “父子”没有人是自己的父亲❌ “等于”每个数都等于自己⚠️ 注意一个关系可以既不是自反的也不是反自反的例如A {1, 2, 3}R {(1,1), (1,2)} —— 1 和自己有关系但 2、3 没有。关系矩阵特征对角线全为 0。3. 对称性Symmetric∀a, b ∈ A, (a, b) ∈ R → (b, a) ∈ R即如果 a 和 b 有关系那么 b 和 a 也有关系。例子✅ “等于”如果 a b那么 b a✅ “朋友”如果 a 是 b 的朋友b 也是 a 的朋友假设朋友关系是对称的❌ “大于”如果 3 2不能推出 2 3❌ “整除”2 整除 4但 4 不整除 2关系矩阵特征对称矩阵M_R M_Rᵀ。4. 反对称性Antisymmetric∀a, b ∈ A, (a, b) ∈ R ∧ (b, a) ∈ R → a b即如果 a 和 b 互相有关系那么它们必须是同一个元素。另一种理解不允许两个不同元素互相有关系但可以一个有关系另一个没有。例子✅ “小于等于”如果 a ≤ b 且 b ≤ a那么 a b✅ “整除”在正整数上如果 a|b 且 b|a那么 a b❌ “朋友”对称关系通常不是反对称的⚠️ 注意一个关系可以既是对称的又是反对称的例如R {(1,1), (2,2)}恒等关系—— 它是对称的因为逆关系就是本身也是反对称的因为不存在两个不同元素互相有关系。实际上恒等关系是唯一既对称又反对称的关系。关系矩阵特征如果 M_R[i][j] 1 且 i ≠ j那么 M_R[j][i] 0。5. 传递性Transitive∀a, b, c ∈ A, (a, b) ∈ R ∧ (b, c) ∈ R → (a, c) ∈ R即如果 a 和 b 有关系b 和 c 有关系那么 a 和 c 也有关系。例子✅ “小于”如果 a b 且 b c那么 a c✅ “整除”如果 a|b 且 b|c那么 a|c✅ “祖先”如果 a 是 b 的祖先b 是 c 的祖先那么 a 是 c 的祖先❌ “父子”如果 a 是 b 的父亲b 是 c 的父亲那么 a 是 c 的祖父不是父亲所以 “父子” 关系不传递关系矩阵特征如果 M_R²矩阵的布尔积中某位置为 1则 M_R 的对应位置也必须为 1。五、两种最重要的关系等价关系与偏序关系1. 等价关系Equivalence Relation满足以下三条性质的关系自反性对称性传递性等价关系的作用分类等价关系把集合分成互不相交的等价类Equivalence Class[a]_R {b ∈ A | (a, b) ∈ R}即所有与 a 等价的元素构成的集合。例子“等于”每个等价类只有一个元素即 {a}“同余模 3”把整数分成三类——被 3 整除余 0 的、余 1 的、余 2 的[0] {…, -3, 0, 3, 6, …}[1] {…, -2, 1, 4, 7, …}[2] {…, -1, 2, 5, 8, …}“同班同学”每个班级就是一个等价类等价类的性质每个元素属于且仅属于一个等价类不同等价类互不相交所有等价类的并集就是全集这就是集合的划分Partition定理集合上的等价关系与集合的划分一一对应。2. 偏序关系Partial Order满足以下三条性质的关系自反性反对称性传递性偏序关系通常记作 ≤注意这里的 “≤” 不一定指数值上的小于等于而是抽象的偏序符号。例子数上的小于等于(ℝ, ≤)集合上的包含(P(A), ⊆)整除关系(ℤ⁺, |)正整数上的整除字符串上的前缀关系“abc” ≤ “abcd”偏序中的特殊元素设 (A, ≤) 是一个偏序集概念定义例子P({a,b,c}), ⊆最大元∀x ∈ A, x ≤ M{a, b, c}唯一最小元∀x ∈ A, m ≤ x∅唯一极大元不存在 y 使得 x y{a,b,c}唯一极小元不存在 y 使得 y x∅唯一上界对子集 Bu 满足 ∀b ∈ B, b ≤ u对 {{a}, {b}}上界有 {a,b}, {a,b,c}下界对子集 Bl 满足 ∀b ∈ B, l ≤ b对 {{a}, {b}}下界有 ∅上确界最小上界上界中最小的对 {{a}, {b}}上确界是 {a,b}下确界最大下界下界中最大的对 {{a}, {b}}下确界是 ∅⚠️ 最大元/最小元不一定存在但上确界/下确界如果存在则唯一。全序与偏序全序Total Order/Linear Order任意两个元素都可比较即 ∀a, b ∈ A, a ≤ b 或 b ≤ a例子(ℝ, ≤)、字典序偏序Partial Order不是所有元素对都可比较例子(P({a,b}), ⊆){a} 和 {b} 之间没有包含关系偏序关系可以用哈斯图Hasse Diagram直观表示省略自反的环自环省略可由传递性推出的边用位置高低表示偏序关系下方 ≤ 上方六、函数特殊的关系1. 函数的定义函数Functionf: A → B 是一种特殊的关系∀a ∈ A, ∃! b ∈ B, 使得 (a, b) ∈ f即A 的每个元素都恰好对应 B 中的一个元素。A 称为定义域DomainB 称为陪域/上域Codomain{f(a) | a ∈ A} 称为值域Range/Image2. 函数与关系的区别关系函数每个 a 对应几个 b0 个、1 个或多个恰好 1 个表示R ⊆ A × Bf: A → B例子“大于”3 大于多个数“平方”每个数只有一个平方3. 函数的性质性质定义说明单射Injective/One-to-Onef(a₁) f(a₂) → a₁ a₂不同的输入对应不同的输出满射Surjective/Onto∀b ∈ B, ∃a ∈ A, f(a) bB 的每个元素都被打到双射Bijective既是单射又是满射一一对应存在逆函数例子设 f: ℤ → ℤf(x) 2x单射不满射奇数没 preimagef(x) x²不单射f(2)f(-2)4不满射负数没 preimagef(x) x 1双射4. 函数的复合(g ∘ f)(x) g(f(x))先应用 f再应用 g。性质单射的复合仍是单射满射的复合仍是满射双射的复合仍是双射复合满足结合律(h ∘ g) ∘ f h ∘ (g ∘ f)复合一般不满足交换律g ∘ f ≠ f ∘ g5. 逆函数f⁻¹ 存在当且仅当 f 是双射。f⁻¹(f(x)) xf(f⁻¹(y)) y七、关系与函数在计算机中的应用概念计算机应用关系数据库表关系数据库、图结构等价关系分类、聚类、哈希表同余类偏序关系任务调度、依赖管理、版本控制Git 的 commit DAG函数程序中的函数/方法、映射、哈希函数双射编码/解码、加密、数据转换复合函数函数式编程中的管道/链式调用数据库与关系关系数据库中的关系Relation一词正是来源于数学中的关系概念。一个数据库表本质上就是一个 n 元关系表中的一行是一个 n 元组。Git 与偏序Git 的 commit 历史形成一个有向无环图DAG这是一个偏序结构——commit 之间有先于关系祖先关系这是偏序的。分支合并就是 DAG 的交汇。八、本章小结概念要点笛卡尔积A × B {(a,b) | a∈A, b∈B}二元关系A × B 的子集关系矩阵0/1 矩阵表示关系关系图有向图表示关系自反性∀a, (a,a)∈R对称性(a,b)∈R → (b,a)∈R反对称性(a,b)∈R ∧ (b,a)∈R → ab传递性(a,b)∈R ∧ (b,c)∈R → (a,c)∈R等价关系自反对称传递划分等价类偏序关系自反反对称传递可用哈斯图表示函数每个输入对应恰好一个输出单射不同输入对应不同输出满射每个输出都有输入双射一一对应存在逆函数思考与练习设 A {1, 2, 3}列出 A × A 的所有元素。A × A 有多少个元素判断下列关系的性质自反、反自反、对称、反对称、传递A ℝR “”小于A ℝR “≤”小于等于A 所有人R “认识”假设互相认识A 所有人R “父子”A P({a,b}), R “⊆”证明一个关系如果既是对称的又是反对称的那么它一定是某个子集上的恒等关系。设 A {1, 2, 3, 4, 5, 6}在 A 上定义关系 RaRb 当且仅当 a ≡ b (mod 3)。证明 R 是等价关系并列出所有等价类。画出偏序集 (P({a,b,c}), ⊆) 的哈斯图并指出最大元、最小元、极大元、极小元。判断下列函数的性质单射、满射、双射f: ℤ → ℤ, f(x) x²f: ℝ → ℝ, f(x) 2x 1f: {1,2,3} → {a,b}, f(1)a, f(2)a, f(3)b编程实践写一个函数输入一个关系矩阵判断该关系是否具有自反性、对称性、传递性。下一篇预告关系与函数让我们知道了如何联系但如果在集合上定义运算呢加法、乘法、旋转、置换——这些运算有什么共同的结构代数系统群、环、域将告诉我们答案。它们是现代密码学、编码理论、编译器优化的数学基础。关系是集合的灵魂而函数是关系中最优雅的舞者。