理解格

术语格(lattice)来源于描述这种次序的哈斯图的形状。


序理论定义
考虑偏序集合(L,≤)。L 是一个格,如果

对于 L 的所有元素 x 和 y,集合 {x, y} 有在 L 中的最小上界(并或上确界)和在 L 中的最大下界(交或下确界)二者。
x 与 y 的并和交分别被指示为∨和∧。因为假定并和交存在于格中,∨和∧是二元运算。所以这个定义等价于要求 L 是并半格和交半格二者。

有界格有一个最大元素和一个最小元素,按惯例分别指示为 1 和 0(也叫做顶和底)。任何格都可以通过增加一个最大元素和最小元素而转换成有界格。

使用容易的归纳论证,你可以演绎出任何格的所有非空有限子集的上确界(并)和下确界(交)的存在。一个很重要的格的种类是完全格。一个格是完全的,如果它的所有子集都有一个交和一个并,这对比于上述格的定义,这里只要求所有非空有限子集的交和并的存在。

抽象代数定义
另一种定义格的方式是将格定义为一种代数结构。一个格是一个代数结构(L,∨) ,其中∨ 和∧  是定义在集合 L 上的二元运算,且对于所有的a,b,c,d满足:

  

从上述三个公理恒等式可以得出重要的:

这些公理断言了 (L,∨) 和 (L,∧) 都是半格。吸收律是唯一交和并都出现了的公理,把格同一对半格区别开来并确保这两个半格正确的交互。特别是,每个半格都是另一个半格的对偶。“有界格”要求交和并都有一个零(neutral)元素,分别习惯叫做 1 和 0。参见半格条目。

格与广群家族有一些联系。因为交和并都符合交换律和结合律。格可以看作由有相同的承载者的两个交换半群组成的。如果格是有界的,这些半群也是交换幺半群。吸收律是特定于格理论的唯一定义恒等式。

L 闭包于交和并之下,通过归纳,蕴涵了 L 的任何有限子集的交和并的存在性,有着一个例外:空集的交和并分别是最大元素和最小元素。所以格只在它是有界的条件下包含所有有限(包含空)交和并。为此有些作者定义格的时候要求 0 和 1 是 L 的成员。而以这种方式定义格不损失一般性,因为任何格都可以被嵌入一个有界格中,这里不接受这种定义。

格的代数解释在泛代数中扮演根本性角色。

例子
对于任何集合 A,A 的所有子集的搜集(叫做 A 的幂集)可以通过子集包含的次序获得一个以 A 自身和空集为上下界的格。集合的交集和并集分别解释为交(meet)和并(join)。
对于任何集合 A,A 的所有有限子集的搜集,通过包含次序也是格,并且将是有界的当且仅当 A 是有限的。
自然数(包括 0)在“极小值”(min)和“极大值”(max)运算下,按照通常次序形成格。0 是底,没有顶。
自然数的笛卡尔平方,按有随后定义的 ≤ 排序是格,(a,b) ≤ (c,d) ↔ (a ≤ c) & (b ≤ d)。(0,0) 是底;没有顶。
正整数在采用最大公约数和最小公倍数运算之下,用整除作为次序关系也形成一个格: a ≤ b 如果 a 整除 b。底是 1;没有顶。
任何完全格都是(非常特殊的)有界格。这个类别引出了大量实际例子。

原文地址:https://www.cnblogs.com/emanlee/p/1948481.html