离散数学第讲

离散数学第讲第一页，共二十三页，2022年，8月28日2023/2/161主要内容同态与同构同态核环特殊环环的同构与同态域第二页，共二十三页，2022年，8月28日2023/2/162同态与同构

本节研究的是一个代数系统与另外一个代数系统之间的关系，即撇开集合元素和运算的具体差异，只考虑两代数系统的运算性质上的差异，或者说在什么条件下两代数系统无差异或者相似。代数系统之间的这种相互关系是通过映射来反应的。映射有单射、满射和双射，相应本节讲的是单同态、满同态和同构以及性质。第三页，共二十三页，2022年，8月28日2023/2/163定义15.9

设〈X，*〉与〈Y,о〉是两个代数系统，如在集合X与Y之间存在映射f：XY，使得对a，bX，有：

f(a*b)=f(a)оf(b)

则称f是从〈X，*〉到〈Y,о〉的同态映射，简称为同态，此时代数系统〈X，*〉与代数系统〈Y,о〉称为同态的，记为X∽Y。

f(X)Y称为X的一个同态象。如果第四页，共二十三页，2022年，8月28日2023/2/164f：XY是一个单射，则称f是从〈X,*〉到〈Y,о〉的单一同态；f：XY是一个满射，则称f是从〈X,*〉到〈Y,о〉的满同态；f：XY是一个双射，则称f是从〈X,*〉到〈Y,о〉的同构，记为X≌Y。若集合X=Y，则此时对应的同态和同构分别称为自同态、单一自同态、满自同态和自同构。第五页，共二十三页，2022年，8月28日2023/2/165

例15-6.1证明代数系统〈R+，×〉与〈R，+〉是同构的。

证明：设f：R+R，且f（x）=ln（x），则：

1.f是一个R+R的映射；

2.对yR,均x=eyR+,使得f(x)=ln(x)=ln(ey)=y，所以f是一个满射；

3.对xyR+,有ln(x)ln(y)，所以f是一个单射；

由1、2、3知：f是一个双射。

4.对x，yR+，有：

f(x×y)=ln(x×y)=ln(x)+ln(y)=f(x)+f(y)

由1、2、3、4知：f是一个双射且满足

f(x*y)=f(x)оf(y)∴

R+≌

R第六页，共二十三页，2022年，8月28日2023/2/166

例15-6.2在自然数加半群〈N，+〉与剩余类加群<Z2

，>之间定义映射f：NZ2如下：证明f是N到Z2的满同态映射。证明：∵对n1,n2N，1）当n1和n2同奇偶时，f(n1+n2)=[0]，而f(n1)和f(n2)要么同为[0]，要么同为[1]，从而f(n1)f(n2)=[0]；2）当n1和n2不同奇偶时，f(n1+n2)=[1]，而f(n1)和f(n2)中一个为[0]，一个为[1]，从而f(n1)f(n2)=[1]；∴N～Z2

，而显然是一个满射，所以，结论成立。第七页，共二十三页，2022年，8月28日2023/2/167性质定理15.15设〈X，*〉与〈Y,о〉是两个代数系统，f：XY是一个同态映射，则：1）如果运算‘*’在X中是封闭的运算‘о’在f（X）Y中是封闭的；2）〈X，*〉满足结合律〈f（X）,о〉满足结合律；3）〈X，*〉满足交换律〈f（X）,о〉满足交换律;4）〈X，*〉满足消去律〈f（X）,о〉满足消去律；5）〈X，*〉存在幺元e1〈f（X）,о〉存在幺元e2；6）〈X，*〉存在零元θ1〈f（X）,о〉存在零元θ2；7）在X中每元关于运算‘*’有逆元f（X）中每元关于运算‘о’有逆元。该定理说明同态映射不仅确定了不同集合元素间的对应关系，而且还保持了代数系统的运算性质。因此，能够建立同态映射的代数系统之间有着很大的一致性。第八页，共二十三页，2022年，8月28日2023/2/168定理15.16设〈X，*〉与〈Y，о〉是两个代数系统，f：XY是满同态，则：

1)如果X是半群Y是半群；

2)如果X是群Y是群。

在同态映射下，像源的代数性质都为像集所具有。但是，像集所具有的代数性质却未必为像源所具有。（如<Z2

，>是群，而〈N，+〉不是群）如果f：XY是同构映射，则代数系统X与Y许多性质完全相同。而且代数系统之间的同构关系是等价关系。第九页，共二十三页，2022年，8月28日2023/2/169同态核

下面通过考察像源中被映射到像集幺元的那些元素具有的代数特征来揭示同态的分类特征。定义15.10

设f是群〈G，*〉到〈H，о〉的同态映射，令：K＝Kerf＝{a|aG∧f(a)＝e′}

其中e′是H的单位元，则称Kerf为f的同态核，f(G)＝{f(a)|a∈G}称为f的像集。第十页，共二十三页，2022年，8月28日2023/2/1610定理15.17设f是群〈G，*〉到〈H，о〉的同态映射，e，e′分别是G和H的单位元，则同态核Kerf是G的不变（正规）子群。证明由定义Kerf＝{a|a∈G∧f(a)＝e′}，因为f是同态映射，所以有f(e)＝e′。故e∈Kerf，所以Kerf是G的非空子集。 对任意的a，b∈Kerf，由定义有f(a)＝e′，f(b)＝e′

又因为f是同态映射，所以有

f(a*b-1)＝f(a)оf(b-1)

＝f(a)о(f(b))-1＝e′оe′-1＝e′为什么？f(b-1)=(f(b))-1第十一页，共二十三页，2022年，8月28日2023/2/1611

即a*b-1∈Kerf，由定理15.8所以<Kerf，*>是<G，*>的子群。 另一方面，对任意的k∈Kerf，a∈G，我们有

f(a*k*a-1)＝f(a)оf(k)оf(a-1)

＝f(a)оe′о(f(a))-1＝f(a)о(f(a))-1＝e′

所以有a*k*a-1∈Kerf，由定理15.14

故<Kerf，*>是<G，*>的不变子群。在例15-6.2中，[0]是Z2中的幺元，因而映射的同态核是集合Kerf={0，2，4，6，‥‥}。可以进一步证明，在同态映射下,像源集G具有陪集分解式，其中每个陪集是像集中某个元素的像源。第十二页，共二十三页，2022年，8月28日2023/2/1612环和域

前面讨论了具有一个二元运算的代数系统——半群、含幺半群、群、子群。下面讨论具有两个二元运算的代数系统。给定两个代数系统<A,+>，<A,*>可将它们组合成一个具有两个二元运算的代数系统<A,+,*>,而这两个二元运算符+和*之间是有联系的。

环在计算机科学的很多领域，诸如编码理论的研究中起着重要作用；而域，特别是有限域是纠错码理论的基础。第十三页，共二十三页，2022年，8月28日2023/2/1613环Ring定义16.1

一个代数系统<R,+,*>，如果满足：（1）<R，+>是阿贝尔群；（2）<R,*>是半群；（3）运算*在运算+上可分配。即对任意a，b，cR有

a*(b+c)=（a*b）+（a*c）

(b+c)*a=（b*a）+（c*a)

则称<R,+,*>是一个环。(联系两个二元运算，否则就不是一个系统而是两个系统)第十四页，共二十三页，2022年，8月28日2023/2/1614例16-1.1在加法和乘法运算下，整数、实数、有理数、偶数和复数都能构成环。<Z,+,×><R,+,×><Q,+,×><E,+,×><C,+,×>+可以交换，0是+的幺元，i的逆为-i；+,×可结合,×对+可分配第十五页，共二十三页，2022年，8月28日2023/2/1615例16-1.2设Zk表示整数集Z上的模k剩余类集合，即Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余类加群），<Zk

，>是半群（剩余类乘半群），∵对[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是环，称为（模k）剩余类环。特别，k=2时，称为布尔环。第十六页，共二十三页，2022年，8月28日2023/2/1616定理16.1

设<R,+,*>是一个环，θ是加法幺元，对任意a，b，cR,则

a+b=ca+b-c=θ(移项法则)第十七页，共二十三页，2022年，8月28日2023/2/1617定理16.2

设<R,+,*>是一个环，θ是加法幺元，对任意a，b，cR有a*θ=θ*a=θ(加法幺元是乘法零元)(-a)*b=a*(-b)=-(a*b)(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c第十八页，共二十三页，2022年，8月28日2023/2/1618特殊环定义16.3

设<R,+,*>是一个环如果<R,*>是可交换的，称<R,+,*>是交换环；如果<R,*>是含幺半群，称<R,+,*>是含幺环；如果对于某些非零元素a,bR,能使a*b=0,称<R,+,*>是含零因子环；a,b称为零因子；如果<R,+,*>是可交换的，含幺，而无零因子，则称它是整环。第十九页，共二十三页，2022年，8月28日2023/2/1619例16-2.1

证明（模k）剩余类环<Zk

，，>无零因子当且仅当k是素数。证明：

∵当k是合数时，a≥2，b≥2，k=ab而[a][b]=[k]=[0]，即[a]、[b]都是零因子，又∵当k是素数时，不a≥2，b≥2，k=ab因而无零因子∴结论成立。例如<Z6，，>中，[2][3]=[0]，

[4][3]=[0]第二十页，共二十三页，2022年，8月28日2023/2/1620定理16.3

设<R,+,*>是一个环，则R中无零因子当且仅当对a,x,yR，当a≠0时，

a*x=a*yx=y或x*a=y*ax=y

（即在环中无零因子与消去律是等价的）定义16.4

设<R,+,*>是一个环，S是R的非空集合，如果<S,+,*>也是一个环，则称S是R的子环。例如：<{[0]，[2]，[4]}，，>