《离散数学--第3讲-同余关系和商代数课件》由会员分享，可在线阅读，更多相关《离散数学--第3讲-同余关系和商代数课件（18页珍藏版）》请在金锄头文库上搜索。
1、1,离散数学（二）,同余关系和商代数,主要内容:,重点和难点:,一、同余关系,关于运算的同余关系： 设是代数A=的载体S上的等价关系,任取a,b,cS， (1) 当ab时, 若有acbc和cacb, 那么我们说等价关系在运算*下具有置换性质，或者说等价关系在运算*下仍能保持，称是关于运算*的同余关系； (2) 当ab时, 若有ab, 那么我们说等价关系在运算下具有置换性质, 或者说等价关系在运算下仍能保持，称是关于运算的同余关系。,一、同余关系,同余关系定义: 设R为代数A=的载体S上的等价关系, 如果在代数运算*下仍能保持, 则称R是关于运算*的同余关系。,一、同余关系,例1：给定代数A=，
2、I：整数集合，运算为普通乘法运算，R为I上的模k相等(kI+)关系, 即xRy当且仅当xy(mod k)，现在证明R是关于运算的同余关系。 证明： (a)容易看出R是I上的等价关系； (b)下面只需证明对任意a,b,cI，若aRb,则(ac)R(bc)和(ca)R(cb)。 设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
3、当且仅当z1z2(mod m)，问：R是关于运算的同余关系吗？ 证明： (a)容易看出R是I上的等价关系, (b)因此只需证明对任意z1, z2I，若z1Rz2, 则(z1)R(z2)。 若z1Rz2, 即z1z2(mod m),设z1=ma1+r, z2=ma2+r(0rm-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
4、 m) 所以，(z1)(z2)(mod m), 即(z1)R(z2)。,一、同余关系,代数A上的同余关系定义: 设是代数A=的载体S上的等价关系，对一切元素a、 b、cS，若 (1) 若ab, 则acbc 和 cacb , (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, 但是
5、d与a不等价，即b*c与 b*d不等价，所以R不是关于运算*的同余关系。,一、同余关系,定理1：等价关系关于二元运算*是一个同余关系当且仅当对 任意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可诱导出一个
6、S上的自然等价关系, 这一关系定义如下: a、bS, ab当且仅当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上的同余关系。,一、
7、同余关系,定理2：设h是从A=到A=的一个同态。如果在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(
8、b*d)， (a*c)R(b*d)，即R是关于运算*的同余关系。,由定理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/是一个代数必须证明*和都是良定的, 即运算*和的结 果不依赖于参加运算的等价类中的表示元素。 (1)
9、证明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) 证明*是良定的,即证明如果a=b和c=d, 那么a*c=b*d。 如果a=b和c=d, 那么ab和cd, 因为是一同余关系, a*cb*d。所以, a*c=b*d。由*的定义知
10、因为a*c=a*c和b*d=b*d, 得a*c=b*d。所以, *是良定的。 综上所述, 和*都是S/上良定的运算, 因此A/是具有与A相同构成成分的代数。 证毕。,二、商代数,商代数的运算和常数保留了许多原代数的性质: (1) 代数A中如果运算*是可交换的, 那么A/中 *也是可交换的； (2) 如果*是可结合的, *也是可结合的； (3) A中如果k是关于*的么元,那么 A/中k是关于*的么元； (4) 如果k是关于*的零元, 那么k是关于*的零元。 定理1：如果是代数A=上的同余关系, 那么规范映射h: S S/，h(a)=a(aS),是从代数A到商代数A/=的同态,称 为与相关的自然同
11、态。 证明: (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(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)=
12、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, 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是一同构。,三、商代数和同态象的关系,下图描述了同态象与同态映射诱导的商代数间的同构关系：,规范映射h: SS/，h(a)=a(aS),f 诱导的S上的自然等价关系， ab当且仅当h(a) = h(b),作业：P186 习题6.4 3、6 P191 习题6.5 1,18,谢谢同学们!,
