《离散数学课件(英文版)----Semigroup》由会员分享，可在线阅读，更多相关《离散数学课件(英文版)----Semigroup（44页珍藏版）》请在金锄头文库上搜索。
1、Algebraic Systems and Groups Lecture 13 Discrete Mathematical StructuresAlgebraic 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-xy Note
2、: 2*3 = -1； 0.5*0.7 = 0.85Closeness of Operations 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
3、on a finite set (usually only with several elements) 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) opera
4、tions, with the constraint that the order of all operands are not changed. Commutation Operation “” defined on the set A is associative if and only if: For any x, y A, xy = yx If “” is commutative and associative, then x1x2x3 xn can be computed by any order of the operations, and in any permutation
5、of all operands. Distribution Two 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 distribut
6、ive property)Identity of an Algebraic System For arithmetic multiplication on the set of real number, there is a specific real number 1， satisfying that for any real number x, 1x=x1=x An element e is called the identity element of an algebraic system (S,) if and only if :For any xS, ex=xe=x。 Denotat
7、ion: 1S, or simply 1, but remember that it is not that “1”. It is not that every algebraic system has 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=x Right identity er 。can be defined similarly.More about
8、 Identity For any algebraic system S: There may or may not be left or right identity. There may be more than 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= er If existing, th
9、e identity of an algebraic system is unique: e1= e1e2= e2Inverse(Inverse can be discussed for those system with identity.) 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 th
10、e 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 element x*, satisfying that: xx*=x*x=1S, then x* is called an inverse of x, denotes as x-1.An Example about InverseNote: (1) b has different left and right inverses c(2) has 2 r
11、ight inverses, but no left inverse (3) d has left inverse, but no right inverse * a b c d a a b c d b b c d a c c a c a d d b c d Identityleft inverseRight inverseMore 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 e
12、qual, 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, Le
13、t 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 defined on the set of real number, there is a real number 0, satisfying that: for any real number x, 0x=x0=0 An element z in S is the zero element of S if and only if, for any x
14、S, 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 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
15、any real number x, y, xy=x+y-xy Commutation: Obviously Association: (xy)z = x(yz) = z+y+z-xy-xz- yz+xyz Identity: 0 (common 0！) Inverse of x (x1): x/(x-1) (Note: 1 has no inverse！)Properties and Operation Table Commutation: Symmetric matrix Identity:There is a row/column identical to the title row/column Zero:There is a row/column having the same value, which is identical to the corresponding element in the titles AssociationWhat a pity!Semigroup Axiom of semigroup Association An example (1,2,*), * defined as follows: For
