泛代数与格论

哈塞图

哈塞图是绘制有限偏序集、以便一眼看清其结构的标准方式。诀窍在于只画最少的边:仅当一个元素紧挨在另一个之上、其间别无他物时才连线,余者交由传递性隐式补全。向上读即“更大”,于是这幅图把全部序信息压缩成一张干净的分层图。

严格地说,在偏序集 (P, ≤) 中,称 b 覆盖 a,记作 a ⋖ b,若 a < b 且不存在 c 使 a < c < b。哈塞图是这样一张图:顶点为 P 的元素,边恰为覆盖对,并使得每当 a ⋖ b 时 b 画得高于 a。于是把整个序 ≤ 作为自反传递闭包恢复出来:a ≤ b 当且仅当存在从 a 到 b 的向上路径。自反环以及一切由传递性蕴含的边都被有意省略。

哈塞图对可视化格与小偏序集不可或缺——meet 与 join 化为“下方最近公共祖先”与“上方最近公共后代”,特殊的格也获得可辨认的轮廓。菱形 M_3 与五边形 N_5 正是因其哈塞图形状而得名,而分配格、模格的禁用子格判别通常也以图示来陈述与检验。注意:该图需要覆盖关系说得通,故主要对有限(或至少良基、局部有限)偏序集才有意义。

6 的因子在整除下的哈塞图:1 在底、6 在顶、2 与 3 并列居中;边为 1–2、1–3、2–6、3–6(无直接的 1–6 边,因 1 < 2 < 6)。

只画覆盖边;1–6 边被省略,因 2(或 3)介于其间。