半格

形式陈述 ​

半格有两种等价表达。

代数上，半格是交换的幂等半群公理库幂等半群Idempotent semigroup · Band每个元素都满足平方等于自身的半群，又称 band。 $(S,\wedge )$：

$$x\wedge y=y\wedge x,(x\wedge y)\wedge z=x\wedge (y\wedge z),x\wedge x=x.$$

序理论上，可定义

$$x\le y⟺x\wedge y=x.$$

这给出偏序公理库偏序Partial order · Partially ordered set满足自反、反对称和传递性的关系。，且 $x\wedge y$ 正是 $x,y$ 的最大下界，因而称 meet-semilattice。对偶地，以 $\vee$ 作为任意两元素的最小上界得到 join-semilattice。

半格只保证一种二元 meet 或 join。格公理库格Lattice · Lattice order任意两元素都有最大下界与最小上界的偏序集。同时拥有相容的两种运算，并满足吸收律；不能只因某个结构有 meet 就自动称为格。

直觉 ​

半格描述“合并两个对象后，只保留共同信息”或“汇总两个对象的最小共同上界”。交换性让输入次序无关，结合性让多项合并无须括号，幂等性让重复证据不产生额外效果。

一个半格运算会反过来决定“谁的信息更少”这套偏序。因此代数与序不是两份独立数据：选定 meet 后，次序由 $x\wedge y=x$ 恢复；选定 join 后则由 $x\vee y=y$ 恢复。

例子与边界 ​

幂集在交运算下是 meet-semilattice，在并运算下是 join-semilattice。自然数在 $gcd$ 下按整除关系构成 meet-semilattice，在 $\mathrm{lcm}$ 下构成 join-semilattice。全序集合上的 $min$ 与 $max$ 分别给出两种半格。

一个 meet-semilattice 未必有任意两元素的最小上界。取某个只对交封闭、却不对并封闭的集合族，就可能只有 meet 而没有 join。即使有顶元或底元，也不能补出缺失的另一运算。

非交换幂等半群不是半格。左零运算 $x\ast y=x$ 虽满足结合与幂等，却无法由上式给出反对称的自然偏序；交换条件不可省略。

推论与应用 ​

每个格的 meet 运算与 join 运算分别形成半格，但“格是半格的特例”需要先选择其中哪一种运算，故本库不把两者直接设为 special_case_of。加入单位元可得到有界半格；加入任意族 join/meet 的存在性则走向完备半格或完备格。

数据流分析中的 join、集合并、权限交集和单调汇总常具有半格结构。Sparse Table公理库稀疏表Sparse table预计算长度为二次幂的静态区间答案，以 $O(1)$ 或 $O(\log n)$ 回答区间查询。 的常数时间重叠查询只需要更弱的幂等半群条件；常见的 min/max/gcd 恰好都是半格运算，因此实践中二者经常被混称。

参考资料

• B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd ed., Cambridge University Press, 2002, Chapters 1–2.
• Garrett Birkhoff, Lattice Theory, 3rd ed., American Mathematical Society, 1967, Chapter I.
• George Grätzer, Lattice Theory: Foundation, Birkhäuser, 2011, Chapters 1–2.