离散之格的性质.ppt

1,8.3格的性质,8.3.1格的性质8.3.2格的同态与同构,2,8.3.1格的性质,定理8.3.1设(L,)是一个格，a,b是L中任意元素，于是abab=aab=b证明：若ab，因为aa，所以a是a,b的下界，故aab。而ab是a,b的最大下界，所以aba。故ab=a。若ab=a，由吸收律知ab=(ab)b=b。若ab=b，由ab的定义知，b是a,b的最小上界，当然有ab。,3,设(L,)是一个格，a,b,c是L中任意元素，如果bc，则有：abac，abac证明：因为bc，所以由定理8.3.1知bc=b又因为(ab)(ac)=(aa)(bc)=a(bc)=ab再由定理8.3.1知：abac。同理可证得第二个不等式。,定理8.3.2,4,设(L，)是一个格，a,b,c是L中任意元素。于是有a(bc)(ab)(ac)a(bc)(ab)(ac)其中关系“”是关系“”的对偶关系。证明：因为aab，aac，所以，由的定义知：a(ab)(ac)(1)又因为bcbab，bccac所以，再由的定义知bc(ab)(ac)(2)由的定义及(1)，(2)式知a(bc)(ab)(ac)对偶地可证得另一不等式。,定理8.3.3,5,注意：在一般格中，分配律不是总成立的，但上述分配不等式总是成立的。因为a2(a1a3)=a2(a2a1)(a2a3)=a3,6,设(L,)是一个格，a,b,c是L中任意元素，于是，aba(bc)b(ac)证明：若ab，则由定理8.3.1知：ab=b。由定理8.3.3知：a(bc)(ab)(ac)=b(ac)若a(bc)b(ac)，则由的定义知a(bc)a，由的定义知b(ac)b。故ab。,定理8.3.4,7,8.3.2格的同态与同构,定义8.3.5设(L,)和(S,)是两个格，L到S内的映射g称为(L,)到(S,)的格同态映射，如果对任意a，bL，都有g(ab)=g(a)g(b)g(ab)=g(a)g(b)定义：格L到L内的同态映射称为格的自同态映射。定义：若g是L到S上的同态映射，且是一对一的，则称g是格同构映射，并称格L与格S是同构的。此时，对任意xL，任意yS，有g-1(g(x)=x，g(g-1(y)=y。,8,同态映射例,例：设S=a,b，(S)=,a,b,a,b，则(S),)是一个格。设L=0,1，规定01，,分别是集合L中两个元素在下的最大下界，最小上界运算，则(L,)是一个格。规定映射g为：g(a)=1，g(a,b)=1，g(b)=0，g()=0。则显然g是(S)到L上的映射。,9,往证g是同态映射。首先证对任意A,B(s)，g(AB)=g(A)g(B)。若aAB，则aA，aB，故g(AB)=1，g(A)g(B)=11=1。若aAB，则g(AB)=0，g(A)g(B)=综上，g(AB)=g(A)g(B)。,10,再证对任意A,B(s)，g(AB)=g(A)g(B)若aAB，则g(AB)=1，g(A)g(B)=若aAB，则aA，aB，故g(AB)=0，g(A)g(B)=00=0。综上，g(AB)=g(A)g(B)。因此，g是(s)到L上的同态映射。,11,自同态映射例,例：设S=a,b，(S)=,a,b,a,b，则(S),)是一个格。规定映射g为：g()=g(a)=，g(b)=g(a,b)=b。显然，g为(S)到(S)内的映射。往证g是同态映射。不难验证对任意A,B(S)，有：若bAB，则g(AB)=g(A)g(B)=b；若bAB，则g(AB)=g(A)g(B)=。若bAB，则g(AB)=g(A)g(B)=b；若bAB，则g(AB)=g(A)g(B)=。故g(AB)=g(A)g(B)，g(AB)=g(A)g(B)。g为格(S),)的自同态映射。,12,同构映射例,例：设S=a,b,c，(S)=,a,b,c,a,b,b,c,a,b,c，则(S),)是一个格。(S30,)是一个格，、分别是求两个正整数的最高公因、最小公倍。规定映射g为：1，a2，b3，c5，a,b6，a,c10，b,c15，a,b,c30。则显然g为(S)到S30上的1-1映射。不难验证对任意A,B(S)，有：g(AB)=g(A)g(B)，g(AB)=g(A)g(B)。因此，g为(S)到S30上的同构映射.,13,格的同态映射一定是保序映射,定理8.3.5设(L,)和(S,)是两个格集合L上对应于运算,的部分序为L，集合S上对应于运算,的部分序为s。如果g是L到S内的同态映射，则g是保序映射，亦即，对任意a，bL，若aLb，则g(a)sg(b)。证明：由ab，知ab=a，故g(ab)=g(a)，而g(ab)=g(a)g(b)=g(a)，故g(a)sg(b),14,例：,同态具有保序性，但其逆命题不一定成立，即保序映射不一定是同态的。下面给出3个格L1,L2,L3。定义映射1,2和3：1：L1L2,1(a)=1(b)=1(c)=a1,1(d)=d1。2：L1L2,2(b)=2(c)=2(d)=d1,2(a)=a1。3：L1L3,3(a)=a2，3(b)=b2，3(c)=c2，3(d)=d2。dd1d2bcaa1a2L1L2L3,c2,b2,15,例：,可以看出这3个映射都是保序的，但都不是同态的。因为1(bc)=1(d)=d1，1(b)1(c)=a1a1=a1，2(bc)=2(a)=a1，2(b)2(c)=d1d1=d1，3(bc)=3(d)=d2，3(b)3(c)=b2c2=c2。,16,设(L,)是一个格，g是此格的自同态映射，于是g(L)是(L,)的代数子格。证明：任取a,bg(L)，则必有a,bL，使a=g(a)，b=g(b)。因为g是格(L,)的自同态映射，所以ab=g(a)g(b)=g(ab)g(L)，ab=g(a)g(b)=g(ab)g(L)。即在运算,下，g(L)是封闭的。故(g(L),)是(L,)的代数子格。,定理8.3.6,17,设(L,),(S,)是两个格，若g是L到S上的同构映射，则g的逆映射g-1是S到L上的同构映射。证明：显然g-1是S到L上的一对一映射。下面证明g-1是S到L上的同态映射。任取a,bS，令g-1(a)=a，g-1(b)=b。于是g(a)=a，g(b)=b。g-1(ab)=g-1(g(a)g(b)=g-1(g(ab)=ab=g-1(a)g-1(b)。g-1(ab)=g-1(g(a)g(b)=g-1(g(ab)=ab=g-1(a)g-1(b)。故g-1是S到L上的同构映射。,定理8.3.7,18,若格(L,)和格(S,)同构，g是其同构映射，则对L中任意两个元素a，b，有aLbg(a)sg(b)其中L,S分别是集合L，S上对应于运算，的部分序关系。,推论：,19,n维格,设L=0,1，规定01。于是，(L,)是格。令(L,)是与之等价的代数格。令Ln=(a1,an)aiL，i=1,n规定：(a1,an)n(b1,bn)aibi(i=1,n)不难证明：(Ln,n)是一个格，通常称为n维格。令与(Ln,n)等价的代数格为(Ln,)，对Ln中任意两个元素(a1,an)，(b1,bn)，显然有：(a1,an)(b1,bn)=(a1b1,anbn)(a1,an)(b1,bn)=(a1b1,anbn)。,20,设S是含n个元素的集合，(s)是S的幂集合，则格(s),)与格(Ln,n)同构。证明：令S=s1,sn。令g是(s)到Ln上的映射如下：任取A(s)，g(A)=(a1,an)其中ai=1siA，i=1,n。显然，g是(s)到Ln上的一对一映射。,例：,21,任取A,B(s)，令g(A)=(a1,an)，g(B)=(b1,bn)，g(AB)=(c1,cn)，于是