偏序集实例

偏序集的典型例子、极值与界的性质、Hasse 图与常见误解。

标签 数学 / 偏序集 / 序理论 / Hasse 图

本页承接 偏序集 的定义,整理典型例子、极值与界的性质、Hasse 图和常见误解。

偏序与全序

“偏”不是“元素之间不能比较”,而是“不要求任意两个元素都能比较”。有些元素对可以比较,有些不可以。实数集上的通常大小关系是全序,因此也是偏序;它的任意两个元素都可比。

极值与界的性质

最小元一定是极小元,但极小元不一定是最小元。最小元若存在则唯一;极小元可以有很多个。

若 𝑆 非空且有限,则 𝑆 中极小元和极大元一定存在:从任意元素出发,若还能向下走就继续走,有限步后必然停在极小元。最小元、最大元则不一定存在。

例如在集合 {2,3,6} 上按整除关系定义 𝑎≤𝑏 当且仅当 𝑎 整除 𝑏。此时 2 和 3 是极小元,6 是最大元,但没有最小元,因为 2 和 3 不可比。

上确界和下确界若存在则唯一。它们不要求属于 𝑆:若 sup𝑆 恰好属于 𝑆,它就是 𝑆 的最大元;若 inf𝑆 恰好属于 𝑆,它就是 𝑆 的最小元。反过来,𝑆 的最大元或最小元不存在时,sup𝑆 或 inf𝑆 仍可能存在。

有上界不代表有上确界:上界集合中可能没有最小者。类似地,有下界也不代表有下确界。

Hasse 图

Hasse 图把每个元素画成一个点,只在覆盖关系 𝑥≺𝑦 处从 𝑥 向 𝑦 连边,并把 𝑦 画在 𝑥 上方。传递性产生的边不画,但那些关系仍然成立。

因此 Hasse 图只记录“直接相邻”的序关系;沿有向路径走若干步,才得到完整的 ≤。在有限偏序集中,覆盖关系构成一个 DAG,取它的传递闭包并补上自反关系,就还原出偏序。

反过来,给定 DAG,令 𝑢≤𝑣 表示从 𝑢 出发能到达 𝑣(允许 𝑢=𝑣),也得到一个偏序集。DAG 的拓扑序是这个偏序集的一个 线性扩展:它把不可比的元素也排出先后,但不违反已有的 ≤。

常见例子

  • 集合包含:(2𝑈,⊆) 是 布尔格。元素是 𝑈 的子集,𝐴≤𝐵 当且仅当 𝐴⊆𝐵。|𝑈|≥2 时它不是链;所有大小为 𝑘 的子集构成反链。
  • 整除:正整数按“𝑎≤𝑏 当且仅当 𝑎 整除 𝑏”构成偏序集。1 是最小元,一般没有最大元;若只看 𝑛 的约数,则 𝑛 是最大元。
  • 乘积序:若 𝑃 和 𝑄 各有偏序,在 𝑃×𝑄 上按分量比较,(𝑎,𝑏)≤(𝑐,𝑑) 当且仅当 𝑎≤𝑐 且 𝑏≤𝑑,得到乘积偏序。多维 DP 的状态空间常用这种序。
  • 树形偏序:在 有根树 上令 𝑢≤𝑣 表示 𝑢 是 𝑣 的后代(含 𝑢=𝑣)。根是最大元,叶子是极小元;每个节点的后代集合对“向下走”封闭,是 主理想 的例子。

常见误解

  • 认为偏序就是“任意两个元素都不能比较”:偏序只要求三条公理,允许部分元素可比;全序才要求任意两个都可比。
  • 认为极小元就是最小元:极小元只要求“下面没有更小的”,不同极小元之间可以不可比;最小元要求比所有元素都小,存在时唯一。
  • 认为上确界一定属于集合:sup𝑆 可以不属于 𝑆;只有 sup𝑆∈𝑆 时,它才是 𝑆 的最大元。
  • 认为 Hasse 图没画的边就不成立:Hasse 图只画覆盖关系,由传递性得到的关系仍然成立。
  • 认为偏序集一定有限:无限偏序集很常见;算法题通常只处理有限情形,因为有限性保证极小元、极大元和拓扑序存在。
  • 认为 ≤ 必须像数值大小一样:它可以是集合包含、整除、后代关系等任意满足公理的关系。
源码位置