形式陈述
格 公理库 格 Lattice · Lattice order 任意两元素都有最大下界与最小上界的偏序集。 L 称为分配格,若对任意 x , y , z ∈ L ,
x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) , 并且对偶地
x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) . 在任意格中这两条分配律互相蕴含,因此验证其中一条即可。
有限情形由 Birkhoff 表示定理完全刻画:设 P 为 L 中全体 join-不可约元素(非底元、且不能写成两个严格更小元素之并的元素)按格序构成的偏序 公理库 偏序 Partial order · Partially ordered set 满足自反、反对称和传递性的关系。 集,则 L 同构于 P 的全体下闭集按包含序、以集合交并为格运算所成的格。另一个刻画不依赖有限性:格是分配格,当且仅当它不含五元钻石格 M 3 、也不含五元五边形格 N 5 作为子格。
直觉
分配律断言"先合并再取公共部分"与"分别取公共部分再合并"总给出同一结果,这恰好是集合交并运算的行为,所以分配格可以理解为"表现得像一族集合的格"。Birkhoff 定理把这句口号升级为定理:有限时,每个分配格确实同构于某族对交并封闭的集合。反过来看,一般格中的"并"常会产生凭空多出的元素——两条直线的并张成整个平面——这正是子空间格违反分配律的根源;M 3 与 N 5 是这种失效的最小样板,禁用它们等价于排除一切非集合式行为。有效的心智图像是把格元素想成偏序集中的下闭区域:交与并就是区域的交与并,join-不可约元素对应由单个点生成的主下集。
例子与边界
正例很常见:任意全序 公理库 全序 Total order · Linear order 任意两个元素都可比较的偏序。 是分配格,此时 ∧ , ∨ 就是 min , max ,分情况即可验证;集合的幂集 公理库 幂集 Power set 把 A 的每一种子集选择提升为元素所得的集合,记作 P(A)。 格 ( P ( X ) , ∩ , ∪ ) 、任意拓扑空间 公理库 拓扑空间 Topological space 在集合上指定满足并与有限交公理的开集族,以编码邻近、连续和极限。 的开集格也是分配格;正整数 n 的因子按整除 公理库 整除 Divisibility 存在整数倍关系时定义的二元关系。 排序、以 gcd 与 lcm 为交并同样构成分配格。以 12 的因子格为例:gcd ( 4 , lcm ( 2 , 3 ) ) = gcd ( 4 , 6 ) = 2 ,而 lcm ( gcd ( 4 , 2 ) , gcd ( 4 , 3 ) ) = lcm ( 2 , 1 ) = 2 ,两侧一致。
典型反例来自线性代数:在 R 2 中取三条过原点的不同直线 L 1 , L 2 , L 3 ,则 L 3 ∧ ( L 1 ∨ L 2 ) = L 3 ∩ R 2 = L 3 ,而 ( L 3 ∧ L 1 ) ∨ ( L 3 ∧ L 2 ) = { 0 } 。这五个子空间 { 0 } , L 1 , L 2 , L 3 , R 2 恰好构成一个 M 3 :子空间格是模格,却不是分配格,可见分配性严格强于模性。使用禁用子格刻画时要注意,"子格"必须对原格的交与并封闭,仅仅序嵌入五个元素不算数。
还有两处常见误区。其一,布尔代数是有补的分配格,但分配格未必有补:三元链 0 < a < 1 中 a 没有补元。其二,Birkhoff 表示中 join-不可约元素不包括底元;而且该表示只对有限格成立,无限分配格不能声称同构于某个偏序集的全部下闭集,需要 Stone、Priestley 对偶等更细致的表示理论。
推论与应用
分配格是多个领域共用的骨架。逻辑方向,命题逻辑 公理库 命题逻辑 Propositional logic · Propositional calculus 研究命题如何通过逻辑联结词组合以及公式在真值赋值下何时成立。 公式在合取与析取下的等价类构成分配格,添上否定即得布尔代数。拓扑方向,开集格是分配格,这一观察是无点拓扑(frame 与 locale 理论)的出发点。组合方向,Birkhoff 定理在有限分配格与有限偏序集之间建立了完整的双向翻译,使下闭集计数、链与反链结构以及偏序集上的 Möbius 反演 公理库 偏序集 Möbius 反演 Möbius inversion on posets 在局部有限偏序集的区间和变换中用 Möbius 函数恢复原函数。 可以在两种语言之间自由切换;这一对应常称为有限分配格基本定理,是偏序组合学的基本工具。
参考资料
Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011,§3.4, distributive lattices and finite Birkhoff representation。
Garrett Birkhoff, Lattice Theory, 3rd ed., American Mathematical Society, 1967,Ch. II, distributive lattices and representation。