格
格的定义
设\(<L,≤>\)是一个偏序集，若集合\(L\)中的任意两个元素都有最小上界和最大下界，那么称\(<L,≤>\)为格。
偏序关系的定义
设\(A≠∅\)，\(R=A×A\)，若关系R是自反的、反对称的、传递的，那么关系R是A上的偏序关系
- 自反： 每个元素 自己 和 自己 都有关系 , $x R x $;
- 反对称：若存在\(xRy\)，\(yRx\)，则\(x=y\)
- 传递：若存在\(xRy\)，\(yRz\)，则有\(xRz\)
上界与下界
偏序关系通常使用哈斯图进行表示，若a≤b，则b在a上方，如图
- 元素对\(b、c\)的上界是\(a\)，最大上界是\(a\)，下界是\(d、e、f\)，但是由于\(d、e\)不可比，所以不存在最大下界
- 同样的元素对\(d、e\)不存在最大上界
哈斯图判断格
判断以下哈斯图代表的偏序关系是否是格
- 不是格，<a,b>无最小上界
- 不是格，<a,c>既不存在最小上界也不存在最小下界
- 不是格,前面已经分析过
- 其余都是格
使用定义证明格
例一
设\(I^+\)是正整数集合,定义\(I^+\)上的二元关系\('|'\),任取\(a,b∈I^+,a|b\)当且仅当\(a\)能够整除\(b\).试证明:\(<I^+,|>\)是一个格 证明: ①任取\(a∈I^+\),显然\(a|a\),及该关系是自反的 ②取\(a,b∈I^+\),若有\(a|b\)且\(b|a\),显然\(a=b\) ③取\(a,b,c∈I^+\),满足 \(a|b,b|c\),必有\(a|c\) 综合①②③,\(<I^+,|>\)是偏序集合 ④任取\(a,b∈I^+\),其最小上界,是其最小公倍数\(lub\{a,b\}∈I^+\) ⑤任取\(a,b∈I^+\),其最大下界,是其最大公因子\(glb\{a,b\}∈I^+\) 综上所诉,显然\(<I^+,|>\)是格
例二
设\(S\)是任意集合,\(ρ(S)\)是\(S\)的幂集,偏序集合\(<ρ(S),⊆>\)是否是格(幂集是集合子集的集合)
任取\(A,B∈ρ(S)\),其最大下界是\(A∩B\),最小上界是\(A∪B\),两者都是\(ρ(S)\)中的元素,同时\(<ρ(S),⊆>\)是偏序集合,得证.
运算
通过上面两个例题,引出了以下运算
保交运算:\(a∧b=glb\{a,b\}\),求\(a,b\)的最大下界
保联运算:\(a∨b=lub\{a,b\}\),求\(a,b\)的最小上界
格的对偶定理
若\(<L,≤>\)是一个格,那么\(<L,≥>\)也是一个格(通过命题的对偶来证明)
代数格
代数格定义
代数格是通过偏序关系诱导出最大下界与最下下界两中关系的具体运算,最用与关系集合上,构成一个新的代数系统,从而将之前学过的代数系统引入,进而进一步研究
设\(<L,≤>\)是一个格,\(a,b \in L\).在\(L\)上可以定义两个运算\(*\) 与\(⊕\):
- \(a*b = glb\{a,b\}\),也写作 \(a∧b=glb\{a,b\}\)
- \(a⊕b = lub\{a,b\}\),也写作 \(a∨b=lub\{a,b\}\)
称\(<L,*,⊕>\)或者\(<L,∧,∨>\)为格\(<L,≤>\)所诱导的代数系统,简称代数格.
代数格相关定理
1.定理一
在一个格\(<A,≤>\)中，对任意的\(a,b∈A\)，都有
- \(a≤a∨b,b≤a∨b\)
- \(a∧b≤a,a∧b≤b\)
证明:
\(a∨b\)是\(a\)的一个上界，同时也是\(b\)的一个上界，\(a≤a∨b,b≤a∨b\)，根据对偶性原理，得到\(a∧b≤a,a∧b≤b\)
2.定理二
在一个\(<A,≤>\)中，对于\(a,b,c,d∈A\)，若\(a≤b\)，\(c≤d\)，则有：
- \(a∨c≤b∨d\)
- \(a∧c≤b∧d\)
证明：
对于\(a,c\)而言，其最小上界为\(a∨c\)，而\(a≤b,c≤d\)，于是有\(a≤b≤b∨d\)，\(c≤d≤b∨d\)，于是 \(b∨d\)也是\(a,c\)的一个上界，于是\(a∨c≤b∨d\)。
同理，对于\(b,d\)而言，其最大下界是\(b∧d\)，而\(a∧c\)也是其下界，从而得证
代数格基本性质
由格诱导出来的代数系统即代数格满足以下性质：
- 自反性：\(a≤a\)
- 反对称性：\(a≤b且b≤a⇒a=b\)
- 传递性：\(a≤b且b≤c⇒a≤c\)
- \(a∧b≤a,a∧b≤b\)与\(a≤a∨b,b≤a∨b\)
- \(c≤a且c≤b⇒c≤a∧b\)与\(b≤c且a≤c⇒a∨b≤c\)
- 交换律：\(a∨b=b∨a\)，\(a∧b=b∧a\)
- 结合律：
- \(a∧b∧c=(a∧b)∧c=a∧(b∧c)\)
- \(a∨b∨c=(a∨b)∨c=a∨(b∨c)\)
- 等幂律：
- \(a∧a=a\)
- \(a∨a=a\)
- 吸收律：
- \(a∧(a∨b)=a\)
- \(a∨(a∧b)=a\)
- \(a≤b⇔a∧b=a⇔a∨b=b\)
- 保号性：
- \(a≤b且c≤d⇒a∧c≤b∧d\)
- \(a≤b且c≤d⇒a∨c≤b∨d\)
- 保序性：
- \(b≤c⇒b∧a≤c∧a\)
- \(b≤c⇒b∨a≤c∨a\)
- 分配不等式：
- \(a∨(b∧c)≤(a∨b)∧(a∨c)\)
- \(a∧(b∨c)≤(a∧b)∨(a∧c)\)
- 模不等式：\(a≤c⇔a∨(b∧c)≤(a∨b)∧c\)
证明：
前三条性质是基于偏序关系的定义得到的，无需证明，后面同一性质的对偶形式只证明一次。
- 证明4：由代数格的定义可知，\(a,b\)的最大下界是\(a∧b\)，最小上界是\(a∨b\)，得证
- 证明5：有代数格定义可知，\(a,b\)的最大下界是\(a∧b\)，最小上界是\(a∨b\)，同时有前提得到，\(c\)是\(a,b\)的一个下界，于是\(c≤a∧b\)，得证
- 证明6：利用最大下界唯一和最小上界唯一进行证明
- 证明7：利用哈斯图证明，都是求哈斯图的端点
- 证明8：哈斯图证明
- 证明9：显然\(a∧(a∨b)≤a\)，\(a≤a\)，\(a≤a∨b\)，根据性质5，得到\(a≤a∧(a∨b)\)，对偶形式同理可证
- 证明10：哈斯图可证，显然\(a∧b≤a\)，\(a≤b\)，\(a≤a\)，根据性质5，\(a≤a∧b\)，有反对称性的\(a∧b=a\)
- 证明11：\(a∧c≤a≤b\)，\(a∧c≤c≤d\)，所以\(a∧c\)是\(b,d\)的一个下界，同时\(b∧d\)是\(b,d\)的最大下界，于是得证
- 证明12：\(b≤c\)，\(a≤a\)，根据性质11，得到\(b∧a≤c∧a\)，证毕
- 证明13：\(b∧c≤b\)，\(b∧c≤c\)⇒\(a∨(b∧c)≤a∨b\)，\(a∨(b∧c)≤a∨c\)⇒\(a∨(b∧c)≤(a∨b)∧(a∨c)\)
- 证明14：由性质13得到，\(a∨(b∧c)≤(a∨b)∧(a∨c)\)，又\(a≤c\)，得到\((a∨c)=c\)，得证
其他定理
1.定理一
设\(<A,∧,∨>\)是一个代数系统，其中运算\(∧\)与\(∨\)都满足吸收率，则运算\(∧\)与\(∨\)都满足等幂律
证明：
任取\(a,b∈A\)，有： \[ a∧(a∨b)=a①\\ a∨(a∧b)=a② \] 将①中\(b\)使用\(a∧b\)替换，将②中\(b\)使用\(a∨b\)替换 \[ a∧(a∨(a∧b))=a∧a=a①\\ a∨(a∧(a∨b))=a∨a=a② \] 证毕
2.定理二
设\(<A,∧,∨>\)是一个代数系统，其中\(∧\)和\(∨\)都是二元运算且满足交换律、结合律、吸收律，则\(A\)上存在偏序关系\(≤\),使得 \(<A,≤>\)是一个格。
证明：
