等价关系 vs 偏序关系

概述

等价关系（Equivalence Relation）和偏序关系（Partial Ordering）是二元关系中两种最重要的特殊类型，都要求自反性和传递性，但第三个性质截然不同：等价关系要求对称性，偏序关系要求反对称性。等价关系将元素”分类”（产生等价类和划分），偏序关系将元素”排列”（建立层次结构）。

定义

等价关系

集合 $A$ 上的关系 $R$ 同时满足自反性、对称性和传递性，则称为等价关系。等价关系将 $A$ 划分为若干不相交的等价类 $[a{]}_R=\{s\in A\mid (a,s)\in R\}$，等价类的集合构成 $A$ 的一个划分。等价关系与划分之间存在一一对应。

偏序关系

集合 $A$ 上的关系 $R$ 同时满足自反性、反对称性和传递性，则称为偏序关系。偏序关系建立元素间的”大小”或”先后”层次结构，但并非所有元素对都可比（因此称为”偏”序）。偏序集可用 Hasse 图可视化。

对比维度

维度	等价关系	偏序关系
自反性	要求	要求
对称性	要求	不要求
反对称性	不要求	要求
传递性	要求	要求
核心功能	将元素”分类”	将元素”排列”
产生结构	等价类 → 划分	极大/极小元 → Hasse 图
可比性	等价类内所有元素等价	元素间可能不可比
典型实例	同余 $a\equiv b(\mathrm{mod}m)$、相等	整除 $\mid$、$\le$、子集 $\subseteq$
可视化	划分图	Hasse 图
衍生概念	商集 $A/R$、代表元	全序、良序、格、拓扑排序
唯一性	等价类相等或不相交	极大元不唯一，最大元唯一

关键区别

• 等价关系要求对称性（$aRb\Rightarrow bRa$），偏序关系要求反对称性（$aRb\wedge bRa\Rightarrow a=b$）——这是二者最核心的区别
• 等价关系将元素分成”类”，同一类中的元素被视为等价的；偏序关系建立元素间的层次，不同元素可能有先后之分
• 一个关系不可能同时是等价关系和偏序关系（除非是相等关系 $=$，它同时满足对称性和反对称性）
• 等价关系与划分一一对应，偏序关系与 Hasse 图一一对应
• 等价类中的代表元可以任意选取，偏序集中的极小元可能有多个但最大元若存在则唯一

联系

• 二者都是二元关系的特殊类型，都建立在自反性和传递性之上
• 二者共享自反性和传递性，仅在第三个性质上分道扬镳（对称 vs 反对称）
• 同余关系 $a\equiv b(\mathrm{mod}m)$ 是等价关系的经典实例，整除关系 $({\mathbb{Z}}^{+},\mid )$ 是偏序关系的经典实例
• 在偏序集 $({\mathbb{Z}}^{+},\mid )$ 中，$\mathrm{lub}=\mathrm{lcm}$，$\mathrm{glb}=\gcd$
• 二者都是第9章关系的核心内容，分别在 9.5 节和 9.6 节讨论

参见

• 二元关系 — 等价关系和偏序关系的共同基础
• 偏序关系 — 偏序关系的完整概念卡片