完备格

任意子集的界 ​

格公理库格Lattice · Lattice order任意两元素都有最大下界与最小上界的偏序集。 $(L,\le )$ 称为完备格，若对每个子集 $X\subseteq L$，上确界与下确界公理库上确界与下确界Supremum and infimum在偏序中分别作为集合最小上界与最大下界的最紧边界元素。都存在于 $L$ 中，记作

$$\bigvee X=supX,\bigwedge X=infX.$$

“每个子集”包含无限子集与空集。空集的上确界是全格最小元

$$\mathrm{\perp }=\bigvee \varnothing ,$$

空集的下确界是全格最大元

$$\mathrm{\top }=\bigwedge \varnothing .$$

因此完备格必有顶元和底元。反过来，一个格仅有 $\mathrm{\top },\mathrm{\perp }$ 仍不够完备；它可能只保证有限 join/meet，而某个无限族没有格内的最小上界。

要求任意上确界存在已经足够：给定 $X\subseteq L$，其下界集合

$$\mathrm{LB}(X)=\{a\in L:\mathrm{\forall }x\in X,a\le x\}$$

若有上确界，则 $\bigvee \mathrm{LB}(X)$ 正是 $infX$。对偶地，任意下确界存在也能推出任意上确界存在。

幂集格与函数格 ​

最标准的例子是幂集 $(\mathcal{P}(S),\subseteq )$。任意集合族 $\mathcal{A}\subseteq \mathcal{P}(S)$ 满足

$$\bigvee \mathcal{A}=\bigcup _{A\in \mathcal{A}}A,\bigwedge \mathcal{A}=\bigcap _{A\in \mathcal{A}}A,$$

并约定空并为 $\varnothing$、空交为 $S$。这里 join 表示把各分支允许的元素合并，meet 表示保留所有分支共同拥有的元素。

若 $L$ 是完备格，对任意索引集 $I$，函数集合 $L^I$ 按点态次序也是完备格。对函数族 $\mathcal{F}\subseteq L^I$，逐点计算

$$(\bigvee \mathcal{F})(i)=\underset{f\in \mathcal{F}}{\bigvee }f(i),(\bigwedge \mathcal{F})(i)=\underset{f\in \mathcal{F}}{\bigwedge }f(i).$$

这不是抽象形式游戏：程序分析常把每个程序点映射为一个抽象状态，整个分析状态正是有限或无限索引集上的函数。

任意一族完备格的直积也按坐标逐点成为完备格。它允许把符号、奇偶性、区间等不同性质并排保存；但直积的精度与计算成本会同时增长，完备性不保证组合后的表示经济。

有限格与无限失败例 ​

每个有限格都是完备格。对非空有限子集可反复使用二元 join/meet；空集由有限格的顶元和底元处理。这里“有限”很关键，因为一般格只承诺每一对元素有界，不能把无限次二元运算当作已经存在的极限。

整数 $(\mathbb{Z},\le )$ 是全序，任意两个整数都有最小值和最大值，所以它是格；但它没有顶元和底元，因而不是完备格。闭区间 $[0,1]$ 配通常次序则是完备格：任意子集的实数上确界和下确界仍落在区间中，包括空集对应的 $0$ 与 $1$。

有理区间 $[0,1]\cap \mathbb{Q}$ 不是完备格。集合

$$X=\{q\in \mathbb{Q}\cap [0,1]:q^2<1/2\}$$

在该偏序中有上界，却没有有理数最小上界。这个反例说明“每个有限计算都在格内完成”不能替代任意子集的完备性。

完备性的几种不同含义 ​

序完备与度量完备不是同一个概念。完备格讨论任意集合的最小上界、最大下界；完备度量空间公理库完备度量空间Complete metric space每个 Cauchy 序列都在空间内部收敛的度量空间。讨论 Cauchy 序列是否收敛。一个结构可能同时具有两种完备性，但两套定义、证明机制和应用不能混用。

完备格也强于 DCPO。有向完备偏序公理库DCPO 与 Scott 连续Directed-complete partial order · DCPO · Scott-continuous function以有向近似的上确界及保持这种极限的映射描述逐步增长的信息。只要求每个有向子集有上确界，适合把相容的有限信息逼近成极限；完备格要求连彼此冲突、不可比的任意集合也有 join 和 meet。指称语义中的递归常使用 DCPO 与 Scott 连续性，抽象解释和时序不动点则常使用完备格与单调性。

一个完备格的子格未必完备。即使子集对有限 join/meet 封闭，无限族在母格中的上确界也可能落到子集外。声称某个抽象性质集合完备时，必须给出任意 join/meet，或证明它同某个已知完备格同构。

不动点与信息合流 ​

完备格让任意一族候选近似都能合流，这正是单调算子公理库偏序集上的单调映射Monotone map on posets · Order-preserving map · Isotone map在偏序之间保持次序的映射，以及它作为单调算子参与不动点迭代时的基本结构。不动点理论所需的全局边界。Knaster–Tarski 定理进一步说明，完备格上的单调自映射不仅有最小和最大不动点，全部不动点自身也形成完备格。

在数据流或抽象语义中，通常把 $a\le b$ 解释为 $a$ 比 $b$ 更精确、代表的具体状态更少。此时 join 是多条控制流汇合时覆盖所有可能性的最小可靠上界。若采用相反的信息序，运算方向也会反转；完备格只提供结构，语义方向必须由页面明确声明。

参考资料

• B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, 2nd ed., Cambridge University Press, 2002, Chs. 2–3。
• Garrett Birkhoff, Lattice Theory, 3rd ed., American Mathematical Society, 1967, Chs. I–V。
• Alfred Tarski, “A Lattice-Theoretical Fixpoint Theorem and Its Applications,” Pacific Journal of Mathematics 5(2), 1955, pp. 285–309。