数学对象可以用不同的结构来表示汇总.docx

数学对象可以用不同的结构来表示汇总.docx

《数学对象可以用不同的结构来表示汇总.docx》由会员分享，可在线阅读，更多相关《数学对象可以用不同的结构来表示汇总.docx（10页珍藏版）》请在冰点文库上搜索。

数学对象可以用不同的结构来表示汇总

§5.1格

数学对象可以用不同的结构来表示。

格就是一种可以用代数或关系来表示的数学对象。

我们先用代数结构来定义格。

5.1.1定义格L是非空集合，和是L上两个二元运算。

称为一个格（按习惯将（x,y）记为xy，将（x,y）记为xy，称为交，称为并），如果L满足以下条件：

（1）幂等律任给xL，都有

xx=x，xx=x。

（2）结合律任给x,y,zB，都有

（xy）z=x（yz），（xy）z=x（yz）。

（3）交换律任给x,yB，都有

xy=yx，xy=yx。

（4）吸收律任给x,yB，都有

（xy）y=y，（xy）y=y。

当,是已知或不必指出时，简称L是一个格。

由结合律，多个元素作交或并时可以省略括号。

吸收律刻画了两种运算和的关系，由吸收律还能得到以下重要关系

5.1.2定理L是格，任给x,yL，都有

xy=x当且仅当xy=y。

证如果xy=x，则y=（xy）y=（xy）（yy）=xy。

如果xy=y，则x=（xy）x=（xx）（yx）=xy。

■

以下是格的一些例子。

5.1.3例幂集P（s）的对于和封闭的子集是格，称为集格。

5.1.4例在单元集{a}上定义和如下：

aa=a，aa=a，

则<{a},,>是格，称为单元格。

单元格上的和是唯一的。

5.1.5例正逻辑系统Pm的公理是：

（1）|（）。

（2）|（（））（）（）。

（3）|。

（4）|。

（5）|（）（）（）。

（6）|。

（7）|。

（8）|（）（）（）。

推演规则是分离规则：

从和得到。

的定义是：

~=df（）（）。

令Form是Pm的所有公式的集合，因为在Pm中有：

（1）|；

（2）如果|，则|；

（3）如果|且|，则|。

所以可以在Form上定义等价关系~如下：

~=df|。

公式在等价关系~下的等价类记为[]，取L是Form在等价关系~下的商集Form/~。

因为在Pm中有：

如果|且|，则

|，|，

所以可以在L上定义和如下：

[][]=[]，[][]=[]

是格，相应的Pm逻辑等值式如下：

（1）|，|。

（2）|（）（），|（）（）。

（3）|，|。

（4）|（），|（）。

更一般地，对于Pm的任何扩充系统，都可以用同样的方法定义这样的格。

5.1.6定理L是格，定义L上二元关系如下：

xy=dfxy=x，

则是L上偏序关系。

证

（1）自返性。

任给xL，都有xx=x，因此xx。

（2）反对称性。

任给x,yL，如果xy且yx，则

xy=x且yx=y，

因此x=xy=yx=y。

（3）传递性。

任给x,y,zL，如果xy且yz，则

xy=x且yz=y，

所以

xz=（xy）z=x（yz）=xy=x，

因此xz。

■

由定理5.1.2，xy当且仅当xy=y。

5.1.7定理L是格，是如上定义的偏序关系。

（1）任给x,yL，都有xyx且xyy。

（2）任给x,y,zL，如果zx且zy，则zxy。

（3）任给x,yL，都有xxy且yxy。

（4）任给x,y,zL，如果xz且yz，则xyz。

证

（1）因为（xy）x=（yx）x=y（xx）=xy，

（xy）y=（xy）y=x（yy）=xy，。

（2）如果zx且zy，则

zx=z且zy=z，

所以

z（xy）=（zx）（zy）=zz=z，

因此zxy。

（3）（4）类似于

（1）

（2），使用xy当且仅当xy=y。

■

由定理5.1.7可知，在这个偏序关系下，xy就是{x,y}的上确界，xy就是{x,y}的下确界。

设L是偏序结构，如果L的任何两个元素都有上确界和下确界，在L上定义和如下：

xy={x,y}的下确界，xy={x,y}的上确界，

则是格。

因此，也可以用任何两个元素都有上确界和下确界的偏序结构来定义格。

详细定义如下：

是关系结构，称为一个格，如果满足以下条件：

（1）（xL）（xx）。

（2）（x,yL）（xyyxx=y）。

（3）（x,y,zL）（xyyzxz）。

（4）（x,yL）（aL）（xaya（zL）（xzyzaz））。

（5）（x,yL）（bL）（bxby（zL）（zxzyzb））。

（1）

（2）（3）是说是偏序结构，（4）是说任何两个元素都有上确界，（5）是说任何两个元素都有下确界。

可以证明：

（4）中a和（5）中b都是唯一的，所以可以在这样定义的格中引进两个二元运算：

：

L×LL（x,y）=a（由（4）确定的唯一的a），

：

L×LL（x,y）=a（由（5）确定的唯一的b），

则就是用代数定义的格。

以下讨论中仍用格的代数定义，但同时使用偏序关系。

5.1.8例全序集的任何两个元素都有上确界和下确界，所以任何非空全序集都可以形成格。

5.1.9例G是群，L={H|H是G的子群}，L在集合的包含关系下是一个偏序集，两个子群H和K的下确界是HK，上确界是HK生成的子群，所以如果在L上定义和如下：

HK=HK，HK=HK生成的子群，

则是格。

5.1.10定义子格是一个格，SL，如果

是一个格，则称S是L的子格。

SL，S是L的子格的充要条件是：

任给x,yS，都有xyS且xyS。

5.1.11例L是L的子格，不等于L的子格称为真子格。

5.1.12例L是格，a,bL，ab，令

[a,b]={x|axb}，

因为任给x,y[a,b]，都有

axb且ayb，

由定理5.1.7得

axyb且axyb，

所以

xy,xy[a,b]。

因此[a,b]是L的子格，称为由a和b确定的闭子格。

[a,a]就是单元格{a}。

类似地可定义由a确定的上开子格[a）={x|ax}和由b确定的下开子格。

（b]={x|xb}，

5.1.13定理L是格，是L的子格的集合，即任给S，S都是L的子格，则：

（1）是L的子格。

（2）如果单调的，则是L的子格。

■

由定理5.1.13

（1），可定义由X所生成的子格，其中

={S|XS且S是L的子格}。

格的同态和同构就是一般代数结构的同态和同构，格的同态基本定理就是一般代数结构的同态基本定理，简单重述如下：

5.1.14定理同态基本定理、是两个格，是到的满同态。

取等价关系如下：

ab当且仅当（a）=（b），

则是正规的等价关系，因此可以构造商格（和是商集L1/上的二元运算），使得

≌。

■

成立分配律的格称为分配格。

分配律是指：

任给x,y,zL，都有

x（yz）=（xy）（xz），x（yz）=（xy）（xz）。

5.1.15例分配格的子格是分配格

5.1.16例全序集形成的格是分配格。

5.1.17定理L是分配格，x,yL。

如果存在aL，使得

ax=ay，ax=ay，

则x=y。

证x=x（ax）=x（ay）=（xa）（xy）

=（ya）（xy）=y（ax）=y（ay）=y。

■

集格都是分配格。

在同构的意义上，分配格都是集格。

5.1.18定义滤L是格，F是L的非空子集。

如果F满足：

（1）任给x,yL，如果xF且yF，则xyF；

（2）任给x,yL，如果xF且xy，则yF。

则称F是L的滤。

5.1.19定理L是格，是L的滤的集合，即任给F，F都是L的滤，则：

（1）是L的滤。

（2）如果单调的，则是L的滤。

■

如果X，则由定理5.1.19的

（1），可以定义由X所生成的滤，其中={F|F且F是L的滤}，可以证明由X所生成的滤是

{y|存在x1,…,xnX，使得x1…xny}。

aL，由{a}生成的滤就是上开子格[a）。

F是L的滤，aL，由F{a}生成的滤是

{x|存在uI，使得uax}。

5.1.20定义素滤L是格，P是L的真滤。

如果任给x,yL，都能从xyF推出xF或yF，则称F是素滤。

素滤有以下基本性质。

5.1.21定理L是格，P是L的素滤，则：

（1）任给x,yL，都有xyP当且仅当xP且yP。

（2）任给x,yL，都有xyP当且仅当xP或yP。

证

（1）如果xP且yP，则xyP。

如果xyP，则由xyx得xP，由xyy得yP。

（2）如果xyP，则xP或yP。

如果xP或yP，则由xxy和yxy得xyP。

■

5.1.22定理L是分配格，F是滤，bF，xyF。

令F1是由F{x}生成的滤，F2是由F{y}生成的滤，则bF1或bF2。

证反证法。

设bF1且bF2，则存在uF，vF，使得

uxb且vyb，

所以

uvxb且uvyb，uvF

所以

（uvx）（uvy）b，

由分配律得

（uv）（xy）b，

因此bF，矛盾。

■

5.1.23定理素滤存在定理L是一个分配格，任给a,bL，如果ba，则存在素滤P，使得aP且bP。

证令={F|F是滤，aF且bF}，由a生成的滤[a），所以非空，任给是单调的，则F=是滤，并有aF且bF，所以F。

由Zorn引理，有极大元P，证明P是素滤。

任给xyP，令F1是由P{x}生成的滤，F2是由P{y}生成的滤，则由定理5.1.22得bF1或bF2，所以F1或F2，由P是极大元得F1=P或F2=P，因此xP或yP。

■

5.1.24定理L是格，令s={P|P是L的素滤}，任给xL，令x*={P|Ps且xP}，则：

（1）任给x,yL，都有（xy）*=x*y*。

（2）任给x,yL，都有（xy）*=x*y*。

证首先由x*的定义得Px*当且仅当xP。

（1）P（xy）*当且仅当xyP

当且仅当（xP且yP）

当且仅当（Px*且Py*）

当且仅当Px*y*。

所以（xy）*=x*y*。

（2）P（xy）*当且仅当xyP

当且仅当（xP或yP）

当且仅当（Px*或Py*）

当且仅当Px*y*。

所以（xy）*=x*y*。

■

3.6.19定理分配格表示定理任何分配格都同构于集格。

证设分配格为，令s={P|P是L的素滤}，取L到P（s）的映射如下：

：

LP（s）（x）=x*，

先证明是单射，

任给x,yL，如果xy，则xyxy，由定理5.1.23得存在素滤P，使得xyP且xyP，所以

Px且Py，或Py且Px，

因此x*y*，即（x）（y）。

取集格<[L],,>，则是L到[L]的双射，再证明是L到[L]的同构。

（xy）=（xy）*=x*y*=（x）（y），

（xy）=（xy）*=x*y*=（x）（y）。

■

习题3.4

5.1.1L是格，证明：

（1）任给x,yL，都有xy当且仅当xyxy。

（2）任给x,y,zL，都有

（xy）（xz）x（yz），x（yz）（xy）（xz）。

5.1.2证明定理5.1.13。

5.1.3证明全序集形成的格是分配格。

5.1.4证明定理5.1.19。

5.1.5X，证明{y|存在x1,…,xnX，使得x1…xny}是一个滤。

5.1.6F是L的滤，aL，证明由F{a}生成的滤是

{x|存在uI，使得uax}。