离散数学--第3讲-同余关系和商代数ppt课件.ppt

《离散数学--第3讲-同余关系和商代数ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学--第3讲-同余关系和商代数ppt课件.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学（二）离散数学（二）同余关系和商代数同余关系和商代数同余关系同余关系11商代数商代数2主要内容主要内容: :同余关系同余关系重点重点: : 商代数和同态象的关系商代数和同态象的关系难点难点: :重点和难点重点和难点: :商代数和同态象的关系商代数和同态象的关系3一、同余关系一、同余关系关于运算的同余关系：关于运算的同余关系：设是代数A=的载体S上的等价关系,任取a,b,cS，(1) 当ab时, 若有acbc和cacb, 那么我们说等价关系在运算*下具有置换性质，或者说等价关系在运算*下仍能保持，称是关于运算关于运算* *的同余关系的同余关系；(2) 当ab时, 若有ab, 那么我们说

2、等价关系在运算下具有置换性质, 或者说等价关系在运算下仍能保持，称是关关于运算的同余关系于运算的同余关系。一、同余关系一、同余关系同余关系定义同余关系定义: : 设R为代数A=的载体S上的等价关系, 如果在代数运算*下仍能保持, 则称R是关于运算关于运算*的同余关系的同余关系。 一、同余关系一、同余关系例例1：给定代数A=，I：整数集合，运算为普通乘法运算，R为I上的模k相等(kI+)关系, 即xRy当且仅当xy(mod k)，现在证明R是关于运算的同余关系。 证明证明： (a)容易看出R是I上的等价关系； (b)下面只需证明对任意a,b,cI，若aRb,则(ac)R(bc)和(ca)R(cb

3、)。 设aRb, 即存在nI使得a-b=kn。于是(ac)-(bc)=tn, 因此(ac)R(bc)。又乘法是可交换, 有(ca)R(cb) 。所以, R是关于的同余关系。一、同余关系一、同余关系 例例2：给定代数A=，I：整数集合，I上的一元运算定义为：zI, (z) = z2(mod m)(m0)，I上的模m相等关系R为: z1Rz2 当且仅当z1z2(mod m)，问：R是关于运算的同余关系吗？ 证明证明： (a)容易看出R是I上的等价关系, (b)因此只需证明对任意z1, z2I，若z1Rz2, 则(z1)R(z2)。 若z1Rz2, 即z1z2(mod m),设z1=ma1+r, z

4、2=ma2+r(0 r m-1, a1,a2I), (z1) = (z1)2(mod m)= (ma1+r)2(mod m) = (a1)2m2+2ma1+r2) (mod m) = r2 (mod m) (z2) = (z2)2(mod m)=(ma2+r)2(mod m) = (a2)2m2+2ma2+r2) (mod m) = r2 (mod m) 所以，(z1)(z2)(mod m), 即(z1)R(z2)。一、同余关系一、同余关系代数代数A A上的同余关系定义上的同余关系定义: : 设是代数A=的载体S上的等价关系，对一切元素a、b、cS，若 (1) 若ab, 则acbc 和 cac

5、b , (2) 若ab, 则ab ,都满足, 则称为代数代数A上的同余关系上的同余关系。的等价类叫做关系的 同余类。 注意：注意：S上的等价关系是代数A的同余关系当且仅当关于A的每一运算是同余的。一、同余关系一、同余关系 例例3：A=a,b,c,d, 运算表(a)为在A上定义的*运算，表(b)为A上的等价关系R，判断R是不是关于运算*的同余关系。 从上述表中可以看出从上述表中可以看出cRd, b*c=d, b*d = a, 但是但是d与与a不等价，即不等价，即b*c与与b*d不等价，所以不等价，所以R不是关于运算不是关于运算*的同余关系。的同余关系。一、同余关系一、同余关系 定理定理1：等价关

6、系关于二元运算*是一个同余关系当且仅当对任意a、b、c、dS, ab和cd 时有acbd。 证明证明： 必要性：必要性： 设是关于运算*的同余关系,并对任意a、b、c、dS,假设ab和cd。ab蕴含着acbc,而cd蕴含着bcbd。根据的传递性, 得出acbd。 充分性：充分性： 是一等价关系, 假设对任意a、b、c、dS,当ab和cd时,acbd。因为cc,故如果ab,那么acbc。类似地,cacb。 所以关于运算*是一同余关系。一、同余关系一、同余关系自然等价关系自然等价关系: : h是 A到A的任一个同态, h：SS可诱导出一个S上的自然等价关系, 这一关系定义如下: a、bS, ab当

7、且仅当h(a) = h(b)。定理定理2: 设h是从A=到A=的一个同态。如果在 A上定义二元关系R: aRbh(a)=h(b)(a、bS),则R是代数A上的同余关系。 证明证明：先证R是等价关系。对任意a、bS， h(a)=h(a), aRa， R自反； 若aRb, 则h(a)=h(b),有h(b)=h(a), bRa，R对称； 若aRb, bRc, 则有h(a)=h(b),h(b)=h(c), h(a)=h(c), aRc,R传递。 综上所述，R是等价关系。 再证该等价关系R是A上的同余关系。证明见下页 由和知R是A上的同余关系。一、同余关系一、同余关系 定理定理2：设h是从A=到A=的一

8、个同态。如果在A上定义二元关系R: aRbh(a)=h(b)(a、bS),则R是代数A上的同余关系。 证明证明：再证该等价关系R是A上的同余关系。 对任意a、b、c、dS， i）如果aRb，则h(a)=h(b), h(a)= h(b), h为同态 h(a)=h(a)，h(b)=h(b) h(a)= h(b), aRb，即R是关于运算的同余关系； ii）如果aRb，cRd，则h(a)=h(b),h(c)=h(d), h(a)*h(c)= h(b)*h(d)， h为同态 h(a*c)=h(a)*h(c)，h(b*d) = h(b)*h(d) h(a*c)= h(b*d)， (a*c)R(b*d)，

9、即R是关于运算*的同余关系。 由定理由定理2 2可以看出，一可以看出，一个同态可以诱导出一个同态可以诱导出一个同余关系；个同余关系； 反过来，反过来，可以证明一个同余关可以证明一个同余关系也可以导出一个同系也可以导出一个同态。态。二、商代数二、商代数 回忆回忆：设R是非空集合S上的等价关系,称划分aRaS为S关于R的商集，记为S/R。即S/R=aRaS。 商代数的定义商代数的定义 设是代数A=上的同余关系, A的关于的商代数定义为商代数定义为A/=,其中运算*和的定义如下:对所有a、bS/, a*b=a*b, a=a。S/表示等价关系下S的商集，即等价关系的等价类的集合。 为证明A/是一个代数

10、必须证明*和都是良定的, 即运算*和的结果不依赖于参加运算的等价类中的表示元素。 (1) 证明S/关于运算*和是封闭的。 (2) 证明是良定的, 即证明如果a=b, 那么a=b。 (3) 证明*是良定的,即证明如果a=b和c=d, 那么a*c=b*d。 二、商代数二、商代数 证明证明： (1) 证明S/关于运算*和是封闭的。显然。显然。 (2) 证明是良定的, 即证明如果a=b, 那么a=b。 如果如果a=b, 那么那么ab。因为。因为是同余关系是同余关系, ab, 所以所以a=b。由。由的定义的定义知知a=a和和b=b, 这得出这得出a=b。这样。这样, 运算运算是良定的。是良定的。 (3)

11、 证明*是良定的,即证明如果a=b和c=d, 那么a*c=b*d。 如果如果a=b和和c=d, 那么那么ab和和cd, 因为因为是一同余关系是一同余关系, a*cb*d。所以。所以, a*c=b*d。由。由*的定义知因为的定义知因为a*c=a*c和和b*d=b*d, 得得a*c=b*d。所以。所以, *是良定的。是良定的。 综上所述综上所述, 和和*都是都是S/上良定的运算上良定的运算, 因此因此A/是具有与是具有与A相同构成成分的代相同构成成分的代数。数。 证毕。证毕。 二、商代数二、商代数 商代数的运算和常数保留了许多原代数的性质: (1) 代数A中如果运算*是可交换的, 那么A/中 *也

12、是可交换的； (2) 如果*是可结合的, *也是可结合的； (3) A中如果k是关于*的么元,那么 A/中k是关于*的么元； (4) 如果k是关于*的零元, 那么k是关于*的零元。 定理定理1：如果是代数A=上的同余关系, 那么规范映射h: SS/，h(a)=a(aS),是从代数A到商代数A/=的同态,称为与相关的自然同态。 证明证明: (1) 代数A与A/是具有与A相同构成成分; (2)设h是从S到S/的规范映射, 根据商代数的定义有a*b=a*b和a=a, 因而h(a*b)=a*b=a*b=h(a)*h(b); h(a)=a=a=h(a),即h保持了A的运算。 (3)根据规范映射的定义有h

13、(k)=k。因此, h是从A到A/的同态。该定理说明一个同余该定理说明一个同余关系可以导出一关系可以导出一个同态。个同态。三、商代数和同态象的关系三、商代数和同态象的关系 定理定理2：设f是从A=到A=的同态,是A上由f诱导的同余关系, 那么, 从A/=到存在同构h。 证明证明：定义h: S/f(S), h(x)=f(x) (1) 证明h是良定的。如果x=y,那么x y, 所以,f(x)=f(y)。因为h(x)=f(x)和h(y)=f(y),所以h(x)=h(y)。 h是良定的。 (2) 证明h是双射函数。h: S/f(S)是单射：对任意x1、x2S, 若f(x1)=f(x2),则x1x2,

14、x1=x2。h: S/f(S)是满射：f(S)上的任一元素均可写成f(x),于是存在xS/使h(x)=f(x)。 (3) 证明h保持运算。h(x*y)=h(x*y)=f(x*y)=f(x)*f(y)=h(x)*h(y) h(x)=h(x)=f(x)=f(x)=h(x)。 (4) 证明常数对应。h(k) = f(k) = k。 所以所以, h是一同构。是一同构。 三、商代数和同态象的关系三、商代数和同态象的关系下图描述了同态象与同态映射诱导的商代数间的同构关系：同态映射ff 诱导的A上的同余关系A A= =S S, ,* *,k k规范映射g自然同态A A/ /= =S S/ /, ,* *,k kAA= =f f(S),(S),* *,k k同构映射h同态象商代数规范映射规范映射h h: : S SS S/ /，h h( (a a)=)=a a(a(aS S) )f 诱导的诱导的S S上的自然等价关上的自然等价关系，系，ab当且仅当h(a) = h(b)作业：作业：P186 P186 习题习题6.46.4 3 3、6 6 P191 P191 习题习题6.5 6.5 1 118谢谢同学们谢谢同学们! !