离散数学--第3讲-同余关系和商代数

1离散数学（二）同余关系和商代数同余关系11商代数2主要内容:同余关系重点:商代数和同态象的关系难点:重点和难点:商代数和同态象的关系3一、同余关系关于运算的同余关系：设～是代数A=S,*,△的载体S上的等价关系,任取a,b,c∈S，(1)当a～b时,若有ac～bc和ca～cb,那么我们说等价关系～在运算*下具有置换性质，或者说等价关系～在运算*下仍能保持，称～是关于运算*的同余关系；(2)当a～b时,若有△a～△b,那么我们说等价关系～在运算△下具有置换性质,或者说等价关系～在运算△下仍能保持，称~是关于运算△的同余关系。一、同余关系abca*cb*cab△a△b同余关系定义:设R为代数A=S,*,△的载体S上的等价关系,如果在代数运算*下仍能保持,则称R是关于运算*的同余关系。一、同余关系例1：给定代数A=I,·，I：整数集合，运算·为普通乘法运算，R为I上的模k相等(k∈I+)关系,即xRy当且仅当x≡y(modk)，现在证明R是关于运算·的同余关系。证明：(a)容易看出R是I上的等价关系；(b)下面只需证明对任意a,b,c∈I，若aRb,则(a·c)R(b·c)和(c·a)R(c·b)。设aRb,即存在n∈I使得a-b=kn。于是(a·c)-(b·c)=tn,因此(a·c)R(b·c)。又乘法是可交换,有(c·a)R(c·b)。所以,R是关于·的同余关系。一、同余关系例2：给定代数A=I,△，I：整数集合，I上的一元运算△定义为：z∈I,△(z)=z2(modm)(m0)，I上的模m相等关系R为:z1Rz2当且仅当z1≡z2(modm)，问：R是关于运算△的同余关系吗？证明：(a)容易看出R是I上的等价关系,(b)因此只需证明对任意z1,z2∈I，若z1Rz2,则△(z1)R△(z2)。若z1Rz2,即z1≡z2(modm),设z1=m·a1+r,z2=m·a2+r(0≼r≼m-1,a1,a2∈I),△(z1)=(z1)2(modm)=(m·a1+r)2(modm)=((a1)2m2+2ma1+r2)(modm)=r2(modm)△(z2)=(z2)2(modm)=(m·a2+r)2(modm)=((a2)2m2+2ma2+r2)(modm)=r2(modm)所以，△(z1)≡△(z2)(modm),即△(z1)R△(z2)。一、同余关系代数A上的同余关系定义:设～是代数A=S,*,△的载体S上的等价关系，对一切元素a、b、c∈S，若(1)若a～b,则ac～bc和ca～cb,(2)若a～b,则△a～△b,都满足,则～称为代数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、d∈S,a～b和c～d时有ac～bd。证明：必要性：设～是关于运算*的同余关系,并对任意a、b、c、d∈S,假设a～b和c～d。a～b蕴含着ac～bc,而c～d蕴含着bc～bd。根据～的传递性,得出ac～bd。充分性：～是一等价关系,假设对任意a、b、c、d∈S,当a～b和c～d时,ac～bd。因为c～c,故如果a～b,那么ac～bc。类似地,ca～cb。所以～关于运算*是一同余关系。一、同余关系自然等价关系:h是A到A′的任一个同态,h：S→S′可诱导出一个S上的自然等价关系,这一关系定义如下:a、b∈S,a~b当且仅当h(a)=h(b)。定理2:设h是从A=S,*,△到A′=S′,*′,△′的一个同态。如果在A上定义二元关系R:aRb⇔h(a)=h(b)(a、b∈S),则R是代数A上的同余关系。证明：①先证R是等价关系。对任意a、b∈S，∵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=S,*,△到A′=S′,*′,△′的一个同态。如果在A上定义二元关系R:aRb⇔h(a)=h(b)(a、b∈S),则R是代数A上的同余关系。证明：②再证该等价关系R是A上的同余关系。对任意a、b、c、d∈S，i）如果aRb，则h(a)=h(b),∴△′h(a)=△′h(b),∵h为同态∴h(△a)=△′h(a)，h(△b)=△′h(b)∴h(△a)=h(△b),∴△aR△b，即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上的等价关系,称划分{[a]R｜a∈S}为S关于R的商集，记为S/R。即S/R={[a]R｜a∈S}。商代数的定义设～是代数A=S,*,Δ,k上的同余关系,A的关于～的商代数定义为A/～=S/～,*′,Δ′,[k],其中运算*′和Δ′的定义如下:对所有[a]、[b]∈S/～,[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],那么a~b。因为~是同余关系,Δa~Δb,所以[Δa]=[Δb]。由Δ′的定义知Δ′[a]=[Δa]和Δ′[b]=[Δb],这得出Δ′[a]=Δ′[b]。这样,运算Δ′是良定的。(3)证明*′是良定的,即证明如果[a]=[b]和[c]=[d],那么[a]*′[c]=[b]*′[d]。如果[a]=[b]和[c]=[d],那么a~b和c~d,因为~是一同余关系,a*c~b*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=S,*,Δ,k上的同余关系,那么规范映射h:S→S/～，h(a)=[a](a∈S),是从代数A到商代数A/～=S/～,*′,Δ′,[k]的同态,称为与～相关的自然同态。证明:(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=S,*,Δ,k到A′=S′,*′,Δ′,k′的同态,～是A上由f诱导的同余关系,那么,从A/～=S/～,*″,Δ″,[k]到f(S),*′,Δ′,k′存在同构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、x2∈S,若f(x1)=f(x2),则x1～x2,[x1]=[x2]。h:S/～→f(S)是满射：f(S)上的任一元素均可写成f(x),于是存在[x]∈S/～使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=〈S,*,Δ,k〉规范映射g自然同态A/～=〈S/～,*″,Δ″,［k］〉A’=〈f(S),*′,Δ′,k′〉同构映射h同态象商代数规范映射h:S→S/～，h(a)=[a](a∈S)f诱导的S上的自然等价关系～，a~b当且仅当h(a)=h(b)作业：P186习题6.43、6P191习题6.5118谢谢同学们!