第十课：关系性质、等价、划分¶
Page 2-4 — 关系的五种基本性质 ⭐¶
| 性质 | 定义 | 关系图特征 | 关系矩阵特征 |
|---|---|---|---|
| 自反 | ∀x(x∈A→xRx) | 每个节点都有环 | 对角线全1 |
| 反自反 | ∀x(x∈A→¬xRx) | 每个节点都没环 | 对角线全0 |
| 对称 | xRy ⇒ yRx | 有边就有反向边 | 对称矩阵 |
| 反对称 | xRy∧yRx ⇒ x=y | 两节点间最多一条单向边 | cᵢⱼ=1(i≠j)时cⱼᵢ=0 |
| 传递 | xRy∧yRz ⇒ xRz | 有通路就有直达边 | R²⊆R |
Page 5-6 — 例子¶
- A={1,2,3}上的关系：
- R={<1,1>,<1,3>,<2,2>,<3,3>} → 自反
- R={<1,3>,<3,1>} → 反自反（不是自反）
- R={<1,1>} → 既不是自反也不是反自反
- A上的空关系∅ → 反自反（不是自反）
- 若A=∅，空关系既自反又反自反（前件始终假）
- R={<1,3>,<3,1>,<1,2>,<1,1>} → 既不对称也不反对称
- R={<1,2>,<2,1>} → 对称
- R={<1,2>,<3,1>} → 反对称
- 相等关系Eₐ → 既对称又反对称
- R={<1,2>,<2,3>,<1,3>,<3,3>} → 传递
Page 7-8 — 关系性质的等价判定 ⭐¶
- R自反 ⟺ Eₐ ⊆ R
- R反自反 ⟺ Eₐ ∩ R = ∅
- R对称 ⟺ R ⊆ R⁻¹
- R反对称 ⟺ R ∩ R⁻¹ ⊆ Eₐ
- R传递 ⟺ R² ⊆ R ⭐常考
💡 人话：这些等价条件方便你从数学上判断关系的性质，而不是只看图。特别是R传递 ⟺ R²⊆R是个重要定理。
Page 9-10 — 运算封闭性¶
| 运算 性质 | 自反 | 反自反 | 对称 | 反对称 | 传递 |
|---|---|---|---|---|---|
| 交∩ | ✅ | ✅ | ✅ | ✅ | ✅ |
| 并∪ | ✅ | ✅ | ✅ | ❌ | ❌ |
| 差− | ❌ | ✅ | ✅ | ✅ | ❌ |
| 补 | ❌ | ❌ | ✅ | ❌ | ❌ |
| 逆⁻¹ | ✅ | ✅ | ✅ | ✅ | ✅ |
| 合成∘ | ✅ | ❌ | ❌ | ❌ | ❌ |
- 所有5种性质对交运算封闭
- 只有自反对合成运算封闭
💡 人话：做运算后性质是否保持？交运算最"稳定"（所有性质都保持），合成最"挑剔"（只有自反能保持）。
Page 11-12 — 等价关系 ⭐¶
- 等价关系 = 自反 + 对称 + 传递
- 例子：
- 三角形的相似/全等
- 舍友关系、亲戚关系
- 模k相等：x≡y(mod k) ⟺ k|(x−y)
- 等价类[a]ʀ = {x | x∈A ∧ aRx}
- a称作该等价类的代表元
- 性质：
- a∈[a]ʀ（自反保证）
- 若aRb则[a]ʀ=[b]ʀ
- 若a不Rb则[a]ʀ∩[b]ʀ=∅
Page 13-17 — 划分 ⭐¶
- 划分π = 集合A的一种分类方式
- 每个块非空
- 块之间两两不交
- 所有块的并 = A
- 等价关系 ⟺ 划分（一一对应）
- 每个等价关系确定一个划分
- 每个划分确定一个等价关系
- 划分的运算：
- 积π₁·π₂：取π₁和π₂中所有块的交
- 和π₁+π₂：取π₁和π₂中所有块的并，传递闭包
💡 人话：等价关系就是把集合中的元素分成了若干"类"，同一类里的元素互相等价。这个分类结果就是划分。
Page 31 — 商集¶
- 商集A/R = {[a]ʀ | a∈A}（所有等价类构成的集合）
- 每个划分π都是A上的一个商集
- A/(R₁∩R₂) = A/R₁ · A/R₂（对应的划分积）
- A/t(R₁∪R₂) = A/R₁ + A/R₂（对应的划分和）
Page 32 — 序关系 ⭐¶
- 序关系 = 自反 + 反对称 + 传递
- 有序集 ⟨A,≤⟩
- 例子：
- ⟨N,≤⟩（自然数上的小于等于）
- ⟨𝜌(A),⊆⟩（幂集上的包含关系）
- ⟨Z⁺,|⟩（正整数上的整除关系）
Page 33-34 — 哈斯图¶
- 对序关系关系图的简化画法： 1. 省去环（自反） 2. 省去箭头方向（默认向上） 3. 省去传递推出的边
💡 人话：哈斯图就是把偏序关系画成"谁在上谁在下"的图，只画直接相邻的关系，间接推出的不画。
Page 35-37 — 最大/最小元、极大/极小元 ⭐¶
| 概念 | 定义 | 要点 |
|---|---|---|
| 最小元 | b∈B且∀x∈B(b≤x) | 比所有元素都小，存在则唯一 |
| 最大元 | b∈B且∀x∈B(x≤b) | 比所有元素都大，存在则唯一 |
| 极小元 | b∈B且¬∃x∈B(x≠b∧x≤b) | 没人比它小，有限集恒存在 |
| 极大元 | b∈B且¬∃x∈B(x≠b∧b≤x) | 没人比它大，有限集恒存在 |
- 极大和最大的区别：极大元只要求"没人比我大"（可以比不可比较的元素），最大元要求"比所有人大"
💡 人话：最大/最小是要和所有元素比大小（全序要求），极大/极小是"没人比我大/小"就行（不要求比所有）。
Page 38-40 — 上界/下界、上确界/下确界¶
- 上界a∈A：∀x∈B(x≤a)（在A中"压住"B）
- 下界a∈A：∀x∈B(a≤x)（在A中"托住"B）
- 上确界：所有上界的最小元
- 下确界：所有下界的最大元
- 上界未必存在，存在也未必唯一
- 若无最大元但所有元素可比，则仍可能有上确界
Page 41-42 — 链与反链¶
- 链：子集中任意两个元素都可比较
- 反链：子集中任意两个不同元素都不可比较
- 定理：若最长链长度为n，则可将A划分成n个反链
Page 43 — 半序关系¶
- 半序关系 = 反自反 + 反对称 + 传递（严格序）
- 例：实数上的"大于"、公司里的"下属"关系