格实例
格的基本例子:链、布尔格、整除格、不是格的偏序集,以及完备性、格中的理想与 Zeta 变换。标签 数学 / 偏序集 / 格 / 分配格 / 布尔格
本页承接 格 的定义,整理典型例子、完备性、格中的理想与 Zeta 变换,以及常见误解。
分配格与布尔格
若对任意 都有
则称 是分配格。格中一个分配律成立时,对偶分配律也自动成立。
有界格中,若 且 ,则称 是 的补元。补元不一定唯一;在分配格中,补元若存在则唯一。
有补的分配格称为布尔格;布尔格是格中结构最规整的一类。
取 ,偏序为集合包含:
此时
它是最典型的布尔格:最小元是 ,最大元是 ;每个 的补元是它在 中的补集;并集和交集又满足分配律。
当 是 个比特时, 就是所有 位掩码按子集关系构成的偏序集。这正是 Zeta 变换 和 SOS DP 的标准场景。
链
取 为全序集,即任意两个元素都可比。此时对任意 , 是较大者, 是较小者,所以链一定是格。
链还是分配格,因为 和 满足分配律。有限链有最小元和最大元;无限链不一定完备。例如有理数集 按通常大小关系是链,但 在 中没有上确界。
整除格
取 为正整数集,偏序定义为
任意两个数都有最小公倍数和最大公约数,因此
这个格有最小元 ,但没有最大元。把每个正整数写成素数指数向量后,整除关系就是逐分量比较;这种链的乘积结构使整除格成为分配格。
不是格的偏序集
- 只有两个不可比元素的偏序集不是格:这两个元素既没有最小上界,也没有最大下界。
- 取三个元素 ,令 、,且 与 不可比。此时 ,但 不存在,所以它不是格。这说明 join 存在并不能保证 meet 也存在。
完备性
有限格一定是完备格:任意子集的 join 和 meet 都可以由二元运算逐个合并得到。
反过来,无限有界格不一定是完备格。例如有理数区间 按通常大小关系是有界格,但 在其中有上界却没有上确界。
格中的理想与 Zeta 变换
在格中,理想通常定义为非空下集,并且对二元 join 封闭;这条额外条件在一般偏序集里没有。对偶地,格论意义下的滤子对二元 meet 封闭。主理想
自动满足这些条件,仍然是由 生成的最小理想,详见 理想。
布尔格是 SOS DP 的标准场景:集合包含关系对应位掩码的子集关系,join 对应按位或,meet 对应按位与。更一般的下集聚合见 Zeta 变换。
常见误解
- 认为格一定是全序:格只要求每对元素有 join 和 meet,不要求它们可比。集合幂集格在 时就不是链。
- 认为任意偏序集都是格:两个不可比且没有共同上界、下界的元素就会破坏格的定义。
- 认为 join 和 meet 一定是 max 和 min:max/min 只是链上的特例;集合幂集格上是并集和交集,整除格上是最小公倍数和最大公约数。