离散数学 1 第 8 章：偏序关系——哈斯图与上下确界

这一章有两个互不相同的主题被放在一起：前半是等价关系与划分（把集合切成块），后半是偏序关系与哈斯图（把元素排成层次）。二者的共同点是都靠第 6 章的性质组合来定义，区别在于"对称"换成了"反对称"，于是一个产生"块"，一个产生"序"。考试失分最集中的地方不是画图，而是极大元与最大元混用、上界与上确界混用——这两组词只差一个字，含义差一整层。

一、等价关系、等价类与划分

等价关系是同时满足自反、对称、传递的关系。典型例子：数的相等、模 n 同余、"同姓"、"住同一间宿舍"。

设 R 是 A 上的等价关系，x 的等价类为

[x]_R = {y∈A | ∈R}

四条性质构成整个划分理论的骨架：

1. [x] 非空：至少含 x（自反性保证）。
2. xRy 当且仅当 [x] = [y]：等价的元素同类，且类完全相同。
3. 若 [x] ≠ [y]，则 [x]∩[y] = ∅：不同类绝不相交（若交出一个 z，由对称与传递可推出 [x]=[y]，矛盾）。
4. 所有等价类的并等于 A：每个元素都在自己的类里。

商集 A/R = {[x] | x∈A}，即以等价类为元素的集合。划分是 A 的一族非空子集，两两不交、并为 A。

核心结论：A 上的等价关系与 A 的划分一一对应——每个等价关系给出一个划分（等价类就是划分块），每个划分也唯一确定一个等价关系（"同属一块"）。这条对应是本章前半的全部价值：判断一个关系是不是等价关系，等价于判断它能不能把集合切成干净的块。

例：A = {1,2,3,4,5,6}，R 为"模 3 同余"，则等价类为 {1,4}、{2,5}、{3,6}，商集有三个元素。

二、偏序关系与偏序集

偏序关系是同时满足自反、反对称、传递的关系，记 ≼，称 为偏序集。注意 ≼ 只是一个符号，具体含义由关系决定，不必是"小于等于"。

三个典型偏序：

• (ℝ, ≤)：实数的大小。
• (P(A), ⊆)：幂集上的包含关系。
• (ℤ⁺, |)：正整数上的整除关系。1 整除一切，所以 1 在最底层。

"偏"字的含义是允许不可比：整除关系下 2 与 3 谁都不整除谁，二者不可比。这一点是偏序与全序的分水岭。

三、哈斯图的绘制

哈斯图是偏序集的"精简版关系图"，画法四步：

1. 去掉所有自环——自反性人人都有，画出来是噪声。
2. 只保留覆盖关系：若 x≺y 且不存在 z 使 x≺z≺y（即 y 是 x 的直接后继），才连一条线。被传递性推出来的边全部删掉。
3. 去掉箭头，约定小的在下方、大的在上方，位置本身表示方向。
4. 同一层的元素左右错开画，避免线段交叉。

例：A = {1,2,3,4,6,12}，关系为整除。覆盖关系是 1≺2、1≺3、2≺4、2≺6、3≺6、4≺12、6≺12。注意 1≺4、2≺12 都在 R 里但不是覆盖（中间有 2、有 4/6），所以哈斯图上不画。

层次从下往上：第 1 层是 1；第 2 层是 2、3；第 3 层是 4、6；顶层是 12。

四、极大元、极小元、最大元、最小元

这四个概念的定义只差一个量词位置，必须对着看。设 B⊆A：

概念	定义	存在性	唯一性	哈斯图上的样子
极大元	不存在 y∈B 使 x≺y	有限偏序集必有	可多个	B 中"上层"的点，头顶没有 B 内的点
极小元	不存在 y∈B 使 y≺x	有限偏序集必有	可多个	B 中"下层"的点
最大元	对所有 y∈B，y≼x	未必存在	存在则唯一	唯一的最高点，且与 B 中所有点可比
最小元	对所有 y∈B，x≼y	未必存在	存在则唯一	唯一的最低点，且与 B 中所有点可比

两句话概括差别：极大元只管"没有比我大的"，最大元要求"比所有人都大"。所以在 B = {2,3,4}（上例）中，极大元是 3 和 4，但没有最大元——3 与 4 不可比；极小元只有 2，同样没有最小元——2 不能整除 3。这个例子正好说明：极大元、极小元一定存在（有限集），最大元、最小元却可能缺席，而这四者都只在 B 内部比较，与 B 外的元素无关。

五、上界、下界、上确界、下确界

这四个概念把"比较"扩展到整个偏序集 A，而不只限于 B 内部：

• 上界：a∈A，且对每个 b∈B 都有 b≼a。
• 下界：a∈A，且对每个 b∈B 都有 a≼b。
• 上确界 sup B：上界集合的最小元，也叫最小上界。
• 下确界 inf B：下界集合的最大元，也叫最大下界。

要点有三：上界、下界可以不在 B 内，甚至可以不唯一；上确界若存在必唯一；上确界一定属于上界集合，但未必属于 B。

仍用上例，取 B = {2,3}：上界是 {6,12}，其中最小的是 6，所以 sup B = 6；下界是 {1}，所以 inf B = 1。取 B = {4,6}：上界 {12}，sup B = 12；下界 {1,2}，最大的是 2，所以 inf B = 2。

对照记：B 中最大元 = B 的上界中落在 B 里的那个；若最大元存在，它必然等于 sup B。反之 sup B 存在时，B 未必有最大元——B = {4,6} 就没有最大元，但有上确界 12。

六、全序与良序

• 全序（线序）：偏序集中任意两个元素都可比。哈斯图退化成一条竖链，没有分叉。
• 良序：全序集，且每个非空子集都有最小元。

三条对比：(ℕ, ≤) 是良序；(ℤ, ≤) 是全序但不是良序，因为整数集本身没有最小元；(ℝ, ≤) 连良序都不是，开区间 (0,1) 没有最小元。

一条实用结论：有限的全序集一定是良序集——有限个元素里总能挑出最小的。良序的价值在于支撑"最小元归纳法"：证明关于自然数的命题时，可以先假设反例集合非空，取它的最小元导出矛盾。

易错点

1. 极大元 ≠ 最大元。极大元可以多个（不可比），最大元必须与所有元素可比且唯一。
2. 上界不一定在 B 里，甚至不一定在哈斯图的"上方"视觉位置——它只由关系决定。
3. 上确界是"上界里的最小者"，不是"B 里最大的"。B = {4,6} 有上确界 12 却无最大元。
4. 画哈斯图时把非覆盖的边也画上，是最常见的图面错误；判据是看中间还有没有元素。
5. 整除关系的哈斯图别按数值大小排层，2 与 3 同层、4 与 6 同层，靠"能不能整除"定上下。

这一章在整门课里的位置

本章是第 6 章五条性质的两种"打包"：自反+对称+传递得等价关系，自反+反对称+传递得偏序关系；哈斯图则是第 5 章关系图的精简版，删边规则正好是第 7 章传递闭包的逆操作。第 9 章讲函数的单射、满射时，判定"|A| = |B|"用到的仍是本章等价类的思想——把集合按基数分成等价类。

本文是《离散数学 1：数理逻辑与集合论》第 8 章的知识点摘要。完整板书与例题见 课程页；上一章 关系的运算，下一章 函数。