泛代數與格論

哈塞圖

哈塞圖是繪製有限偏序集、以便一眼看清其結構的標準方式。訣竅在於只畫最少的邊:僅當一個元素緊挨在另一個之上、其間別無他物時才連線,餘者交由傳遞性隱式補全。向上讀即「更大」,於是這幅圖把全部序資訊壓縮成一張乾淨的分層圖。

嚴格地說,在偏序集 (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)介於其間。