离散7.4几种特殊的格

1、7.4 几种特殊的格 7.4.1 有 界 格 7.4.2 有 余 格 7.4.3 分 配 格 7.4.4 模 格 7.4.1 有 界 格 引理1 设(L，)是一个格。若S是L的任意一个有限非空子集，则S有一个最大下界和一个最小上界。记集合S的最大下界为inf S； 集合S的最小上界为sup S。 Note: 对于格的一个无穷子集，引理1的结论不成立。 例.在格（I+，）中，所有正偶数组成的集合记为E+，显然，E+ I+，但E+没有最小上界。 定义. 格（L，）称为有界格，如果它有一个最大元素（记为1）和一个最小元素（记为0），亦即，对任意aL，都有 0a1 0，1称为格（L，）的界。 结论：有

2、限格必是有界格 令L=a1，an , 0 = a1a2an, 1 = a1a2an 引理2. 若（L,0,1）是有界格，则对任意aL，恒有 a 0 = a， a1 = a， a 1 = 1， a0 = 0。 定义. 在有界格（L，0，1）中，一个元素bL，称为元素aL的余元素，如果 ab = 0， ab = 1。 1 1 1 a b a b a b c 0 0 0 (a,b都无余）（a有唯一余）（a有b,c两个余） 1 a b c 0引理3 在有界格（L，0，1）中，1是0的唯一一个余元素，反之亦然。证明：由引理2，01 = 0， 01 = 1，所以，0，1互为余元素。若cL，且c1，c是0的

3、余元素，0c = 0， 0c = 1。但是，由引理2知，0c = c故，c = 1，矛盾。 7.4.2 有 余 格 定义. 称有界格（L，0，1）是一个有余格，如果对L中每一个元素，都至少有一个余元素。例. n维格（Ln，n）是一个有余格，其中1n=(1，1，1), 0n=(0，0，0)是界。对任意Ln中元素（a1，an），元素（b1，bn）是其 余元素，其中例. 设S是有n个元素的集合，(S)是S的幂集合，于是，（S），）是有余格。其中， 和S是此格的界.对（S）中任意元素A，（S）中的元素S-A是其余元素。7.4.3 分 配 格 定义7.4.4 格（L，）称为分配格，如果对任意a，b，cL

4、，恒有a（bc）=（ab）（ac）a（bc）=（ab）（ac）Note: (1)分配格定义中的两个等式是等价的 (2) n维格（Ln，n），格（S），）， 格（I+，D），格（Sn，D）都是分配格。 但不是所有的格都是分配格 (3)分配格的任意子格仍是分配格。 例子 d d e e c b c b c d d bb a a c a a L1 L2 L3 L4图中L1和L2是分配格，但L3,L4不是。因为在L3中 b(cd)=b e=b和(b c) (b d)=a a=a；在L4中d(bc)=d e=d和(d b) (d c)=a c=c。L3称为钻石格， L4称为五角格。引理4 任意一个链都是

5、一个分配格。证明：设格（L，）是一个链，任取a,b,c L, 1）若ab且ac，于是abc，故 a（bc）= bc而ab = b，ac = c，所以（ab）（ac）= bc故a（bc）=（ab）（ac）。2）若ab或者ac，于是a（bc），故a（b c）= a。而（ab）（ac）= a所以a（bc）=（ab）（ac）。 De Morgan定律定理7.4.1 设（L,）是一个分配格,对任意a,bL,若a，b有余元素a,b，则（ab）= ab（ab）= ab证明： (ab)(ab)=(aba)(abb) =(1b)(a1)= 11 = 1而(ab)(ab)=(aab)(bab) =(0b)(0a)

6、= 00 = 0故由余元素定义知， （ab）= ab同理可证另一等式。定理7.4.2 设格（L，）是分配格，对任意a，b，cL，如果 ac = bc， ac = bc，则有a = b。证明：若（L，）是分配格，且ac=bc，ac=bc，则a = a（ac）= a（bc） =（ab）（ac） =（ab）（bc）= b（ac） = b（bc）= b 推论 设格（L，）是一个有余分配格，则对任意aL，a的余元素a是唯一的。证明： 因（L，）是有余格，设a和a都是a的余元素，即 aa= 0， aa= 1 aa= 0， aa= 1故aa= aa，aa= aa。由定理8.4.2知，a= a。 7.4.4

7、模 格 定义7.4.5 设（L，）是一个格，对任意a，b，cL，如果ab，都有a（bc）= b（ac）则称（L，）为模格。Note:(1)任意一个分配格都是模格， 由ab， ab=b,故 a（bc）= （ab）（ a c） = b（ac）（2）模格不一定是分配格。 例.如图所示,L=0,1,b1,b2,b3。则，格(L,)不是分配格： b1（b2b3）= b1（b1b2）（b1b3）= 0。格(L,)是模格： (1)当a=1时,若ab,则b也一定是1。故 a(bc)=1(1c) = 1 b(ac)=1(1c)= 11 = 1。(2)当a=0时,若ab,则b可能为0,b1,b2,b3,1。故 a

8、(bc)= 0(bc)=bc b(ac)=b(0c)= bc。1b3b20b1(3)当a= b1,b2,b3之一时， 若ab，则b是1或a。 若b = 1，则 a(bc)= a（1c）=ac b(ac)=1(ac)=ac 。 若b = a，则 a(bc）= a（ac） = a b(ac)= a（ac）= a。综上，对任意a，b，cL，如果ab，都有a(bc）= b(ac) 。 1b3b20b1例子与结论前面描述的格L1、L2和L3都是模格，但L4不是。因为cd,但c (bd)=c,(cb) d=d 一个格L是模格当且仅当L不含与五角格同构的子格。一个模格是分配格当且仅当L不含与钻石格同构的子格

9、模格的例群G中的所有正规子群做成一个模格。证明：设群G的所有正规子群做成的集合为S，规定S中两种运算： ， ，对任意AS，BS，A与B的交集记为AB。A与B的乘积（记为AB）为如下集合：AB = y(A)(yB)（1）往证（S,， )是格 往证， 是S上的二元代数运算。因为正规子群的交仍为正规子群，故运算 对S封闭。 对任意AS，BS，对任意gG，任取ug（AB），于是，u = gab其中aA,bB。因为A，B是正规子群，所以gab = a1gb = a1b1g其中a1A,b1B。故u=gab（AB）g，故g（AB）（AB）g同理可证：（AB）g g（AB）。故 g（AB）=（AB）g即，AB

10、是正规子群.所以，乘运算对S也是封闭的。往证， 适合交换律、结合律、吸收律结合律 ， 满足结合律是显然的。交换律 满足交换律是显然的 对于乘运算 ：任取uAB,即 u=ab(aA,bB)。由于B是正规子群，所以， u = ab = b1a（b1B）故uBA，即AB BA。同理可证：BA AB，故AB=BA。即乘运算满足交换律。吸收律 任取uA(AB),于是,u=ac,其中cAB,故u = acA，即A（AB）A。任取uA，因为A，B都是子群，故单位元素1在A中，也在B中，故1AB，故u = u1A（AB），即A A（AB）。故 A（AB）=A. 同理可证：A（AB）=A。 亦即：运算和满足吸收

11、律。因此，（S，）是一个格。由于此格中的运算就是集合的交运算，故与（S，）等价的半序格的部份序就是集合之间的包含关系。 （2）往证（S,， )是 模格对任意AS，BS，CS，如果AB，任取uA(CB),于是,u=ad,其中dCB,aA,而AAC,故u=ad（AC）B，即 A（CB）（AC）B。 任取u(AC)B,于是,uB,uAC。令 u = ad(其中aA，dC)，于是，d = a-1u。因为a-1AB，uB，故a-1uB，即dB。故dCB。因此， u = adA（CB），即（AC）BA（CB），所以有 A（CB）=（AC）B由定义知，（S，）是模格。 定理7.4.3 格(L，)是模格的充要条件是：对任意a，b，cL，如果ab，ac=bc，ac=bc则必有a=b。证明：必要性。若格（L，）是模格，则对任意a，b，cL，如果ab，ac=bc，a c=b c，则a = a （ac）= a （bc） = b（ac）= b（bc）= b充分性。任取a，b，cL，且ab。因为(a(bc) c = a (bc)c)=ac 又因为ab，所以ab（ac），故a c（b（ac）c （a c） c = ac所以，（b（a c） c = a c。因此(a(bc