代数系统群课件

1、Algebraic Systems and Groups Discrete MathematicalAlgebraic OperationsFunction :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.

2、85Closeness of OperationsFor 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 TableOperation table can be used to define unary or binary operations on a finite set (usually o

3、nly with several elements) How many binary operations can be defined here?CommutationOperation “” 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

4、all operands. DistributionTwo different operations must be defined for an 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

5、 property)Left Identity and Right Identityel 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 IdentityFor any algebraic system S: There may or may not be left or right identity. There may be more than one left

6、 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= e2Inverse(Inverse can be discussed for those system with identit

7、y.)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 so

8、me element x*, satisfying that: xx*=x*x=1S, then x* is called an inverse of x, denotes as x-1.An Example about Inverse Note: (1) b has different left and right inverses c(2) has 2 right inverses, but no left inverse (3) d has left inverse, but noright inverse * a b c d a a b c d b b c d a c c a c a

9、d d b c d Identityleft inverseRightinverseMore about InverseIf a system (S,) is associate: For a given x, if x has a left inverse, and a right inverse as well, then they must 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”)=(x

10、x)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 a left inverse of b, then:ab = (1Sa)b = (cb)a)b = (c(ba)b = (c1S)b = cb = 1SZero For the arithmetic multiplication de

11、fined 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 prove that, if existing, the zero of a system is unique. Denotation: 0S, or simply, 0, but remember

12、 that it is not that “0”. A system may not have a zero element. Properties and Operation TableCommutation: Symmetric matrixIdentity: There is a row/column identical to the title row/columnZero: There is a row/column having the same value, which is identical to the corresponding element in the titles

13、Association What a pity!SemigroupAxiom 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)Niels Abel(1802-1829): Genius and Poverty阿贝尔的第一个抱负不凡的冒险，是试图解决一般的五次方程。失败给了他一个非常有益的打击；它把他推上了正确的途径，使他怀疑一个代

14、数解是否是可能的。他证明了不可解。那时他大约十九岁。阿贝尔的关于非常广泛的一类超越函数的一般性质的论文呈交给巴黎科学院。这就是勒让德后来用贺拉斯的话描述为“永恒的纪念碑”的工作，埃尔米特说：“他给数学家们留下了够他们忙上五百年的东西。”它是现代数学的一项登峰造极的成就。 (摘自贝尔：数学精英)这篇论文的一个评阅人勒让德74岁，发现这篇论文很难辨认，而另一位评阅人，39岁的柯西正处于自我中心的顶峰，把论文带回家，不知放在何处，完全忘了。4年后，当柯西终于将它翻出来时，阿贝尔已经不在人世。作为赔偿，科学院让阿贝尔和雅可比一起获得1830年的数学大奖。MonoidAxioms of the syst

15、em: Association, IdentityAn Example: Let “*” be matrix multiplication, 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 su

16、bmonoid of SIn above example, T is a subsemigroup of S, but it is not a submonoid. PowerIn 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 i

17、nteger)xn xm= xn+m(xn)m= xnmSystems that look alike“Logical or” and “Boolean sum”Note: if the signs and their meaning are ignored, the two tables are sameIsomorphismSemigroup (G1,) and (G2,*) are isomorphic (G1G2) if and only if: There exist a one-to-one correspondence f: G1G2, such that: (f is call

18、ed 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 correspondenceSet 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 isomorphismPositive real number multiplication semigroup (R+,) and r

19、eal 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 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

20、 x is another isomorphismHow to Negate isomorphismTo 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 rational number multiplication group (Q-0,) and rational number addition

21、 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. Homomorphismsemigroup (G1,) and (G2,*) are homomorphic, denoted as (G1 G2) if and o

22、nly 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 )

23、= r3If f is also onto, then G2 is a homomorphic image of G1.Note: isomorphism is a special case of homomorphismIsomorphism and Homomorphism: GeneralizedThe discussion about isomorphism and homomorphism can be generalized to general algebraic systemsAlgebraic systems (G1,) and (G2,*) are isomorphic i

24、f and only 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 homomorphi

25、c image of G1.Homomorphic Image and System PropertiesAssociationAssuming 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

26、, f(z)=z. So, (x*y)*z = (f(x)* f(y)* f(z) = f(xy) * f(z) = f(xy)z) = f(x(y z) = f(x)* (f(y)* f(z) = x*(y*z) Same discussion applies for commutation. Homomorphic Image and System PropertiesAssociationAssuming that f: G1G2 is a homomorphism, and G2 is a homomorphic image of G1, then, if G1 has an iden

27、tity e, so does G2, and it is f(e).Proof: for any xG2, since f is onto, there must 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 semigroupIf (S,*) and (T,*) are semigroup, then (ST, *)

28、is semigroup where:(s1, t1)*(s2,t2) = (s1*s2, t1*t2)* is closed in ST Association property needs to be proved.Congruence relationEquivalence 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-

29、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)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 relationQuotient semigroupR be a co

30、ngruence 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 association propertyWe call (S/R, ) the quotient semigroup of (S,*)Quotient semigroupR be a congruence relation on monoid (S,*). Quotient semigroup (S/R, #) is als

31、o 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#eQuotient semigroupZn: quotient semigroup of Z, under:(Z,+)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 semigroupSemigroup (S,*)Congruence relation RQuotient semigroup: (S/R, )(S,*) and (S/R, ) are onto homomorphicfR: S-S/R fR(a) = afR (a*b) = a*