《代数系统群.ppt》由会员分享，可在线阅读，更多相关《代数系统群.ppt（43页珍藏版）》请在三一办公上搜索。
1、Algebraic Systems and Groups,Discrete Mathematical,Algebraic Operations,Function:AnB is called an n-nary operation from A to B.Binary operation:AAB(:AAA)An example:a new operation“*”defined on the set of real number,using common arithmetic operations:x*y=x+y-xyNote:2*3=-1；0.5*0.7=0.85,Closeness of O
2、perations,For any operation:AnB,if BA,then it is said that A is closed with respect to.Or,we say that is closed on A.Example:Set A=1,2,3,10,gcd is closed,but lcm is not.,Operation Table,Operation table can be used to define unary or binary operations on a finite set(usually only with several element
3、s),How many binary operations can be defined here?,Association,Operation“”defined on the set A is associative if and only if:For any x,y,z A,(xy)z=x(yz)If“”is associative,then x1x2x3 xn can be computed by any order of among the(n-1)operations,with the constraint that the order of all operands are no
4、t changed.,Commutation,Operation“”defined on the set A is associative if and only if:For any x,y A,xy=yxIf“”is commutative and associative,then x1x2x3 xn can be computed by any order of the operations,and in any permutation of all operands.,Distribution,Two different operations must be defined for a
5、n algebraic system for discussion of distribution.Operation“”is distributive over“”(both operations defined on the set A)if and only if:For any x,y,z A,x(yz)=(xy)(xz)(Exactly speaking,this is the first distributive property),Identity of an Algebraic System,For arithmetic multiplication on the set of
6、 real number,there is a specific real number 1，satisfying that for any real number x,1x=x1=xAn element e is called the identity element of an algebraic system(S,)if and only if:For any xS,ex=xe=x。Denotation:1S,or simply 1,but remember that it is not that“1”.It is not that every algebraic system has
7、its identity element.,Left Identity and Right Identity,el is called a left identity of an algebraic system S,if and only if:For any xS,elx=xRight identity er。can be defined similarly.,More about Identity,For any algebraic system S:There may or may not be left or right identity.There may be more than
8、 one left or right identities.If S has a left identity and a right identity as well,then they must be equal,and this element is also an identity of the system:el=eler=erIf existing,the identity of an algebraic system is unique:e1=e1e2=e2,Inverse,(Inverse can be discussed for those system with identi
9、ty.)For a given element x in the system S,if there is some element x in the system,satisfying that xx=1S,then x is called a left inverse of x.Similarly,if there is some x in the system,such that xx”=1S,then x is called a right inverse of x.For a given element x in the system S,if there is some eleme
10、nt x*,satisfying that:xx*=x*x=1S,then x*is called an inverse of x,denotes as x-1.,An Example about Inverse,Note:,*,a,b,c,d,a,a,b,c,d,b,b,c,d,a,c,c,a,c,a,d,d,b,c,d,Identity,More about Inverse,If a system(S,)is associate:For a given x,if x has a left inverse,and a right inverse as well,then they must
11、be equal,and it is the unique inverse of x.Assuming that the left inverse is x,and the right inverse is x:x=x1S=x(xx”)=(xx)x”=1Sx”=x”If every element of S has a left inverse,then the left inverse is also its right inverse,and the inverse is unique.For any a in S,let b is a left inverse of a,Let c is
12、 a left inverse of b,then:ab=(1Sa)b=(cb)a)b=(c(ba)b=(c1S)b=cb=1S,Zero,For the arithmetic multiplication defined on the set of real number,there is a real number 0,satisfying that:for any real number x,0 x=x0=0An element z in S is the zero element of S if and only if,for any xS,zx=xz=z.It is easy to
13、prove that,if existing,the zero of a system is unique.Denotation:0S,or simply,0,but remember that it is not that“0”.A system may not have a zero element.,An Example,Define a binary operation“”on the set of real number,using arithmetic operations as follows:for any real number x,y,xy=x+y-xyCommutatio
14、n:ObviouslyAssociation:(xy)z=x(yz)=z+y+z-xy-xz-yz+xyzIdentity:0(common 0！)Inverse of x(x1):x/(x-1)(Note:1 has no inverse！),Properties and Operation Table,Commutation:Symmetric matrixIdentity:There is a row/column identical to the title row/columnZero:There is a row/column having the same value,which
15、 is identical to the corresponding element in the titlesAssociation What a pity!,Semigroup,Axiom of semigroupAssociationAn example(1,2,*),*defined as follows:For any x,y1,2,x*y=yProof:it should be proved that for any x,y,z in 1,2,(x*y)*z=x*(y*z),Commutative(Abelian)Semigroup,If(S,)is a commutative s
16、emigroup,then(S,）is an Abelian semigroup.Examples:(Z,+)(S),)S is a fixed nonempey set,construct SS and define*as f*g=fg,how about(SS,*)?,Niels Abel(1802-1829):Genius and Poverty,阿贝尔的第一个抱负不凡的冒险，是试图解决一般的五次方程。失败给了他一个非常有益的打击；它把他推上了正确的途径，使他怀疑一个代数解是否是可能的。他证明了不可解。那时他大约十九岁。阿贝尔的关于非常广泛的一类超越函数的一般性质的论文呈交给巴黎科学院。
17、这就是勒让德后来用贺拉斯的话描述为“永恒的纪念碑”的工作，埃尔米特说：“他给数学家们留下了够他们忙上五百年的东西。”它是现代数学的一项登峰造极的成就。(摘自贝尔：数学精英)这篇论文的一个评阅人勒让德74岁，发现这篇论文很难辨认，而另一位评阅人，39岁的柯西正处于自我中心的顶峰，把论文带回家，不知放在何处，完全忘了。4年后，当柯西终于将它翻出来时，阿贝尔已经不在人世。作为赔偿，科学院让阿贝尔和雅可比一起获得1830年的数学大奖。,Monoid,Axioms of the system:Association,IdentityAn Example:Let“*”be matrix multiplic
18、ation,then both(S,*)and(T,*)are both monoids.,Subsemigroup,submonoid,(S,*)is a semigroup,T is a subset of S,if*is closed in T,then T is a subsemigroup of S(S,*,e)is a monoid,T is a subsemigroup of S and e T,then T is a submonoid of SIn above example,T is a subsemigroup of S,but it is not a submonoid
19、.,Power,In semigroup(S,),we can define the exponential function as follows:x1=x xn+1=xnx(n is positive integer)In addition,if“”has the identity,then:x0=e（e is the identity）xn+1=xnx(n is nonnegative integer)xn xm=xn+m(xn)m=xnm,Systems that look alike,“Logical or”and“Boolean sum”Note:if the signs and
20、their meaning are ignored,the two tables are same,Isomorphism,Semigroup(G1,)and(G2,*)are isomorphic(G1G2)if and only if:There exist a one-to-one correspondence f:G1G2,such that:(f is called an isomorphism)For any x,yG1,f(xy)=f(x)*f(y)G1G2 under f,then G2G1 under f-1f-1 is one to one correspondenceSe
21、t f(x)=a,f(y)=bf-1(a*b)=f-1(f(x)*f(y)=f-1(f(xy)=xy=f-1(a)f-1(b)So,we get it.,How to prove the isomorphism,Basic approach:(S,&)and(T,#)Define a function f:S-TShow that f is one to oneShow that f is onto Show that f(a&b)=f(a)#f(b)Examples“logical OR”semigroup(F,T,)and Boolean sum semigroup(0,1,+)isomo
22、rphism f:F,T0,1:f(F)=0,f(T)=1,How to prove the isomorphism,Positive real number multiplication semigroup(R+,)and real number addition semigroup(R,+)isomorphism1),f:R+R:f(x)=ln x2),if f(a)=f(b)then ln a=ln b,a=b.so,f is one to one3),for any x in R,there exists ex in R+,f(ex)=x.so f is onto4),need to
23、prove:f(xy)=f(x)+f(y).f(xy)=ln(xy)=lnx+lny=f(x)+f(y).So,we get it.Note:f(x)=lg x is another isomorphism,How to Negate isomorphism,To prove groups(G1,)and(G2,*)are not isomorphic to each other,you must prove that any functions from(G1,)to(G2,*)cannot be an isomorphism between them.Example:nonzero rat
24、ional number multiplication group(Q-0,)and rational number addition group(Q,+)are not isomorphic to each other If there exists an isomorphism f:Q-0Q,then f(1)=0(otherwise,f(1x)f(1)+f(x)However,f(-1)+f(-1)=f(-1)(-1)=f(1)=0 So,f(-1)=f(1)，f is not one-to-one,contradiction.,Sometimes,another way:,(S,*)a
25、nd(T,*)are monoids with identity e and e.If f:S-T is an isomorphism,then f(e)=eShow that f(e)is identity of TSet b be any element of T:b=f(a)=f(a*e)=f(a)*f(e)=b*f(e)f(e)is right identity of bb=f(a)=f(e*a)=f(e)*f(a)=f(e)*bf(e)is left identity of bf(e)=e,Homomorphism,semigroup(G1,)and(G2,*)are homomor
26、phic,denoted as(G1 G2)if and only if:There exists a function f:G1G2 such that:for any x,yG1,f(xy)=f(x)*f(y)Example:integer addition group(Z,+)and mod-3 addition group(Z3,+3)homomorphism:f:ZZ3,f(3k+r)=rf(a+b)=f(3k1+r1)+(3k2+r2)=f(3(k1+k2)+(r1+r2)=f(3(k1+k2)+3k3+r3)=r3f(a)+3f(b)=(3k1+r1)+3(3k2+r2)=r3I
27、f f is also onto,then G2 is a homomorphic image of G1.Note:isomorphism is a special case of homomorphism,Isomorphism and Homomorphism:Generalized,The discussion about isomorphism and homomorphism can be generalized to general algebraic systemsAlgebraic systems(G1,)and(G2,*)are isomorphic if and only
28、 if:there exists a one-to-one correspondence f:G1G2,such that:for any x,yG1,f(xy)=f(x)*f(y)Algebraic systems(G1,)and(G2,*)homomorphic if and only if:there exists a function f:G1G2,such that:for any x,yG1,f(xy)=f(x)*f(y)And if f is onto,then G2 is a homomorphic image of G1.,Homomorphic Image and Syst
29、em Properties,AssociationAssuming that f:G1G2 is a homomorphism,and G2 is a homomorphic image of G1,then,if G1 is associative,so is G2,i.e.for any x,y,zG2,(xy)z=x(yz)Proof:for any x,y,zG2,since f is onto,there must be x,y,zG1,such that f(x)=x,f(y)=y,f(z)=z.So,(x*y)*z=(f(x)*f(y)*f(z)=f(xy)*f(z)=f(xy)
30、z)=f(x(y z)=f(x)*(f(y)*f(z)=x*(y*z)Same discussion applies for commutation.,Homomorphic Image and System Properties,AssociationAssuming that f:G1G2 is a homomorphism,and G2 is a homomorphic image of G1,then,if G1 has an identity e,so does G2,and it is f(e).Proof:for any xG2,since f is onto,there mus
31、t be xG1,such that f(x)=x.(x*f(e)=(f(x)*f(e)=f(xe)=f(x)=x.(f(e)*x)=x can be proved similarly.So,f(e)is the identity of G2.,Products and quotients of semigroup,If(S,*)and(T,*)are semigroup,then(ST,*)is semigroup where:(s1,t1)*(s2,t2)=(s1*s2,t1*t2)*is closed in ST Association property needs to be prov
32、ed.,Congruence relation,Equivalence relation R on semigroup(S,*)is called a congruence relation if a R a and b R b imply(a*b)R(a*b)(Z,+),a R b iff ab(mod2):aRb and cRd imply(a+c)R(b+d)?a-b=2k,c-d=2ma+c=2k+b+2m+d=2(k+m)+(b+d)We get it.,Congruence relation,(Z,+),f(x)=x2-x-2.define R:a R b iff f(a)=f(b
33、)how about this R?R is equivalence relation:reflex,symmetric,transitiveBut:(-1,2)R,(-2,3)R(-1)+(-2)R(2+3)?So,R is not congruence relation,Quotient semigroup,R be a congruence relation on semigroup(S,*)Construct S/R:a,b,Define binary operation:S/R S/R-S/R(a,b)=a*b(S/R,)is a semigroupVerify associatio
34、n propertyWe call(S/R,)the quotient semigroup of(S,*),Quotient semigroup,R be a congruence relation on monoid(S,*).Quotient semigroup(S/R,#)is also a monoidLet e be identity of(S,*),e is the identity of(S/R,#)For any a of S/R,e#a=e*a=a=a*e=a#e,Quotient semigroup,Zn:quotient semigroup of Z,under:(Z,+
35、)Relation:R:ab(mod n)Let Zn as Z/R,define new operation:+na+nb=a+b,such as 3+4 2=1(Zn,+n)(0,1,2,3,+4)(0,1,n-1,+n),Semigroup and quotient semigroup,Semigroup(S,*)Congruence relation RQuotient semigroup:(S/R,)(S,*)and(S/R,)are onto homomorphicfR:S-S/R fR(a)=afR(a*b)=a*b=ab=fR(a)fR(b)fR is the natural
36、homomorphism,Fundamental homomorphism theorem,Semigroup(S,*)and(T,*),f:S-T is a onto homomorphismDefine R on S:aRb iff f(a)=f(b)Prove:R is a congruence relation(T,*)and(S/R,)are isomorphic,R:congruence relation,Show that R is equivalence relation:Reflexive:(a,a)R;symmetric:(a,b)R imply(b,a)R;transit
37、ive:f(a)=f(b)and f(b)=f(c)imply f(a)=f(c)Show that aRb,cRd imply a*c R b*df(a*c)=f(a)*f(c)/f is homomorphismf(a)*f(c)=f(b)*f(d)/aRb,cRdf(b)*f(d)=f(b*d)/f is homomorphisma*c R b*d,(T,*)and(S/R,):isomorphic,Define g:S/R-T:g(a)=f(a)Show that g is functionSuppose a=b,then aRb,then f(a)=f(b)Show that g i
38、s one to oneSuppose g(a)=g(b),then f(a)=f(b),then aRb,then a=bShow that g is ontofor any bT,there exists a S,b=f(a)=g(a).,(T,*)and(S/R,):isomorphic,Show that g keeps:g(ab)=g(a)*g(b)g(ab)=g(a*b)/R is congruence relation/(S/R,)is quotientg(a*b)=f(a*b)/definition of gf(a*b)=f(a)*f(b)/S,T are homomorphism/under ff(a)*f(b)=g(a)*g(b)/definition of gSo,we get it,
