Skip to content

分配格

Distributive lattice

交与并彼此满足分配律的格。

条目类型
定义

形式陈述

L 称为分配格,若对任意 x,y,zL

x(yz)=(xy)(xz),

并且对偶地

x(yz)=(xy)(xz).

在任意格中这两条分配律互相蕴含,因此验证其中一条即可。

有限情形由 Birkhoff 表示定理完全刻画:设 PL 中全体 join-不可约元素(非底元、且不能写成两个严格更小元素之并的元素)按格序构成的偏序集,则 L 同构于 P 的全体下闭集按包含序、以集合交并为格运算所成的格。另一个刻画不依赖有限性:格是分配格,当且仅当它不含五元钻石格 M3、也不含五元五边形格 N5 作为子格。

直觉

分配律断言"先合并再取公共部分"与"分别取公共部分再合并"总给出同一结果,这恰好是集合交并运算的行为,所以分配格可以理解为"表现得像一族集合的格"。Birkhoff 定理把这句口号升级为定理:有限时,每个分配格确实同构于某族对交并封闭的集合。反过来看,一般格中的"并"常会产生凭空多出的元素——两条直线的并张成整个平面——这正是子空间格违反分配律的根源;M3N5 是这种失效的最小样板,禁用它们等价于排除一切非集合式行为。有效的心智图像是把格元素想成偏序集中的下闭区域:交与并就是区域的交与并,join-不可约元素对应由单个点生成的主下集。

例子与边界

正例很常见:任意全序是分配格,此时 , 就是 min,max,分情况即可验证;集合的幂集(P(X),,)、任意拓扑空间的开集格也是分配格;正整数 n 的因子按整除排序、以 gcdlcm 为交并同样构成分配格。以 12 的因子格为例:gcd(4,lcm(2,3))=gcd(4,6)=2,而 lcm(gcd(4,2),gcd(4,3))=lcm(2,1)=2,两侧一致。

典型反例来自线性代数:在 R2 中取三条过原点的不同直线 L1,L2,L3,则 L3(L1L2)=L3R2=L3,而 (L3L1)(L3L2)={0}。这五个子空间 {0},L1,L2,L3,R2 恰好构成一个 M3:子空间格是模格,却不是分配格,可见分配性严格强于模性。使用禁用子格刻画时要注意,"子格"必须对原格的交与并封闭,仅仅序嵌入五个元素不算数。

还有两处常见误区。其一,布尔代数是有补的分配格,但分配格未必有补:三元链 0<a<1a 没有补元。其二,Birkhoff 表示中 join-不可约元素不包括底元;而且该表示只对有限格成立,无限分配格不能声称同构于某个偏序集的全部下闭集,需要 Stone、Priestley 对偶等更细致的表示理论。

推论与应用

分配格是多个领域共用的骨架。逻辑方向,命题逻辑公式在合取与析取下的等价类构成分配格,添上否定即得布尔代数。拓扑方向,开集格是分配格,这一观察是无点拓扑(frame 与 locale 理论)的出发点。组合方向,Birkhoff 定理在有限分配格与有限偏序集之间建立了完整的双向翻译,使下闭集计数、链与反链结构以及偏序集上的 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。
关系图谱2 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。