格实例

格的基本例子:链、布尔格、整除格、不是格的偏序集,以及完备性、格中的理想与 Zeta 变换。

标签 数学 / 偏序集 / 格 / 分配格 / 布尔格

本页承接 格 的定义,整理典型例子、完备性、格中的理想与 Zeta 变换,以及常见误解。

分配格与布尔格

若对任意 𝑎,𝑏,𝑐∈𝑃 都有

𝑎∧(𝑏∨𝑐)=(𝑎∧𝑏)∨(𝑎∧𝑐)

则称 𝑃 是分配格。格中一个分配律成立时,对偶分配律也自动成立。

有界格中,若 𝑎∨𝑏=⊤ 且 𝑎∧𝑏=⊥,则称 𝑏 是 𝑎 的补元。补元不一定唯一;在分配格中,补元若存在则唯一。

有补的分配格称为布尔格;布尔格是格中结构最规整的一类。

取 𝑃=2𝑈,偏序为集合包含:

𝐴≤𝐵≝𝐴⊆𝐵

此时

𝐴∨𝐵=𝐴∪𝐵,𝐴∧𝐵=𝐴∩𝐵

它是最典型的布尔格:最小元是 ∅,最大元是 𝑈;每个 𝐴⊆𝑈 的补元是它在 𝑈 中的补集;并集和交集又满足分配律。

当 𝑈 是 𝐵 个比特时,2𝑈 就是所有 𝐵 位掩码按子集关系构成的偏序集。这正是 Zeta 变换 和 SOS DP 的标准场景。

链

取 𝑃 为全序集,即任意两个元素都可比。此时对任意 𝑎,𝑏∈𝑃,𝑎∨𝑏 是较大者,𝑎∧𝑏 是较小者,所以链一定是格。

链还是分配格,因为 max 和 min 满足分配律。有限链有最小元和最大元;无限链不一定完备。例如有理数集 ℚ 按通常大小关系是链,但 {𝑥∈ℚ:𝑥2<2} 在 ℚ 中没有上确界。

整除格

取 𝑃 为正整数集,偏序定义为

𝑎≤𝑏≝𝑎整除𝑏

任意两个数都有最小公倍数和最大公约数,因此

𝑎∨𝑏=lcm(𝑎,𝑏),𝑎∧𝑏=gcd(𝑎,𝑏)

这个格有最小元 1,但没有最大元。把每个正整数写成素数指数向量后,整除关系就是逐分量比较;这种链的乘积结构使整除格成为分配格。

不是格的偏序集

  • 只有两个不可比元素的偏序集不是格:这两个元素既没有最小上界,也没有最大下界。
  • 取三个元素 𝑎,𝑏,𝑐,令 𝑎<𝑐、𝑏<𝑐,且 𝑎 与 𝑏 不可比。此时 𝑎∨𝑏=𝑐,但 𝑎∧𝑏 不存在,所以它不是格。这说明 join 存在并不能保证 meet 也存在。

完备性

有限格一定是完备格:任意子集的 join 和 meet 都可以由二元运算逐个合并得到。

反过来,无限有界格不一定是完备格。例如有理数区间 [0,2]∩ℚ 按通常大小关系是有界格,但 {𝑥∈[0,2]∩ℚ:𝑥2<2} 在其中有上界却没有上确界。

格中的理想与 Zeta 变换

在格中,理想通常定义为非空下集,并且对二元 join 封闭;这条额外条件在一般偏序集里没有。对偶地,格论意义下的滤子对二元 meet 封闭。主理想

𝐼(𝑥)={𝑦∈𝑃:𝑦≤𝑥}

自动满足这些条件,仍然是由 𝑥 生成的最小理想,详见 理想。

布尔格是 SOS DP 的标准场景:集合包含关系对应位掩码的子集关系,join 对应按位或,meet 对应按位与。更一般的下集聚合见 Zeta 变换。

常见误解

  • 认为格一定是全序:格只要求每对元素有 join 和 meet,不要求它们可比。集合幂集格在 |𝑈|≥2 时就不是链。
  • 认为任意偏序集都是格:两个不可比且没有共同上界、下界的元素就会破坏格的定义。
  • 认为 join 和 meet 一定是 max 和 min:max/min 只是链上的特例;集合幂集格上是并集和交集,整除格上是最小公倍数和最大公约数。
源码位置