离散数学第3讲 同余关系和商代数ppt课件.ppt
1,离散数学（二）,同余关系和商代数,主要内容:,重点和难点:,一、同余关系,关于运算的同余关系：设是代数A=的载体S上的等价关系,任取a,b,cS，(1)当ab时,若有acbc和cacb,那么我们说等价关系在运算*下具有置换性质，或者说等价关系在运算*下仍能保持，称是关于运算*的同余关系；(2)当ab时,若有ab,那么我们说等价关系在运算下具有置换性质,或者说等价关系在运算下仍能保持，称是关于运算的同余关系。,一、同余关系,同余关系定义:设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)。设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,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 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,但是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可诱导出一个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上的同余关系。,一、同余关系,定理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(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)证明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。由*的定义知因为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: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(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,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,谢谢同学们!,
