§6.5 同构及同态(离散数学)

§6.5同构及同态6.5.1同态映射6.5.2同构映射6.5.3同态核6.5.1同态映射定义.设G是一个群，其运算是*；K是一个乘法系统，其运算为•，称G到K的一个映射σ是一个同态映射，如果对G中任意元素a，b，有σ(a*b)=σ(a)•σ(b)注意：这个映射既不一定是单射也不一定是满射。例.设(G，*)，(K，+)是两个群，令σ：xe，x∈G，其中e是K的单位元。则σ是G到K内的映射，且对任意a,b∈G，有σ(a*b)=e=e+e=σ(a)+σ(b)。即，σ是G到K的同态映射。σ(G)={e}是K的一个子群,记G～σ(G)。例.设G1是整数加法群，G2是模n的整数加法群，G2上的运算⊕如下：a⊕b=令σ：xx(modn)，x∈G1，则σ是G1到G2的满射，且对任意a,b∈G1，有σ(a+b)=a+b(modn)=a(modn)⊕b(modn)=σ(a)⊕σ(b)。σ是G1到G2的满同态映射。nbanbanbaba当当,,,例.设G为整数加群，G’为实数加群，令σ：x-x，x∈G，则σ是G到G’内的映射，且对任意x1,x2∈G，有σ(x1+x2)=-(x1+x2)=(-x1)+(-x2)=σ(x1)+σ(x2)，所以σ是G到G’的同态映射，显然是单射但不是满射，σ(G)=Z是G’的子群。设G是一个群，K是一个乘法系统，σ是G到K中的一个同态映射，G’=σ(G)，则G’是一个群，G’的单位元1’就是G的单位元1的映像σ(1)，即，1’=σ(1)；对任意a∈G，（σ(a)）-1=σ(a-1)。称G和G′同态，记为G～G′。定理6.5.1例.对群(Z，+)和(C*，·)，若令σ：nin，n∈Z，其中i是C的虚数单位。则σ是Z到C*内的一个映射，且对m,n∈Z，有σ(m+n)=im+n=im·in=σ(m)·σ(n)。即，σ是(Z，+)到(C*，·)的同态映射，Z～σ(Z)。σ(Z)={1，-1，i，-i}是C*的一个子群。例.群（R，+）和(R+,·)是同态的，因为若令σ：xex，x∈R，则σ是R到R+的1-1映射，且对任意x1,x2∈R，有σ(x1+x2)=ex1+x2=ex1·ex2=σ(x1)·σ(x2)，σ是（R，+）到(R+,·)的满同态映射。证明(1)因为群G非空，至少1∈G，故至少σ(1)∈G′，即G′非空。(2)任取a’∈G′，b’∈G′，往证a’b’∈G′。因有a,b∈G,使得a’=σ(a),b’=σ(b)，故按σ的同态性，a’b’=σ(a)σ(b)=σ(ab)，而ab∈G,因而a’b’=σ(ab)∈σ(G),即a’b’∈G′。(3)往证G’中有结合律成立：任取a’,b’,c’∈G’，往证a’(b’c’)=(a’b’)c’。因有a,b,c∈G,使得a’=σ(a),b’=σ(b),c’=σ(c)，故按σ的同态性，a’(b’c’)=σ(a)(σ(b)σ(c))=σ(a(bc))(a’b’)c’=(σ(a)σ(b))σ(c)=σ((ab)c)因群G中有结合律成立,所以a(bc)=(ab)c。于是σ(a(bc))=σ((ab)c)。因此，a’(b’c’)=(a’b’)c’。(4)往证G′有左壹而且就是σ(1)，即证对于任意的a’∈G’，有σ(1)a’=a’。因有a∈G,使得a’=σ(a)，按σ的同态性σ(1)a’=σ(1)σ(a)=σ(1a)=σ(a)=a’。(5)往证G’中任意元素σ(a)有左逆且就是σ(a-1)。由a∈G，且G是群，知a-1∈G，故σ(a-1)∈G’。由σ的同态性σ(a-1)σ(a)=σ(a-1a)=σ(1)。综上，G’做成一个群，G’的壹1’=σ(1)，G’中σ(a)的逆是σ(a-1)。6.5.2同构映射定义.设G是一个群，K是一个乘法系统，σ是G到K内的一个同态映射，如果σ是G到σ(G)上的1-1映射，则称σ是同构映射。称G与σ(G)同构，记成Gσ(G)。例.群（R+，·）和（R，+）是同构的。因为若令σ：xlogx，x∈R+，则σ是R+到R上的1-1映射，且对任意a,b∈R+，σ(a·b)=log(a·b)=loga+logb=σ(a)+σ(b)。故σ是（R+，·）到（R，+）上的同构映射。Logx是以e为底的x的对数，若取σ(x)=log2x，或若取σ(x)=log10x，则得到R+到R上的不同的同构映射。由此可见，群间可存在好多个甚至是无限多个同构映射。例.（R*，·）与（R，+）不可能同构。证明：用反证法。假设（R*，·）与（R，+）同构，可设映射σ为R*到R上的一个同构映射，于是必有σ：10，-1a，a≠0。从而，σ(1)=σ((-1)·(-1))=σ(-1)+σ(-1)=a+a=2a。则有2a=0，a=0，与a≠0矛盾。故，原假设不对，（R*，·）与（R，+）不可能同构。例.无限循环群同构于整数加法群。证明：设G=（g）是无限循环群，Z为整数加法群，则对a∈G，n∈Z，使得a=gn，令f：an。不难验证f是G到Z上的1-1映射；任取a,b∈G，则存在i,j∈Z，使得a=gi，b=gj，f(gigj)=f(gi+j)=i+j=f(gi)+f(gj),因此，f是G到Z上的同构映射，即GZ。自同构映射定义.设G是一个群，若σ是G到G上的同构映射，则称σ为自同构映射。例.恒等映射，称为恒等自同构映射。例.设（Z，+）是整数加法群，令σ：n-n，n∈Z，则σ是Z的一个自同构映射。例.设G是一个Abel群，将G的每个元素都映到其逆元素的映射σ：aa-1(a∈G）是G的一个自同构映射:σ(ab)=(ab)-1=b-1a-1=a-1b-1=σ(a)σ(b)6.5.3同态核定义.设σ是G到G′上的一个同态映射，命N为G中所有变成G′中1′的元素g的集合，记为σ-1(1′)，即N=σ-1(1′)={g∣g∈G,σ(g)=1′}则称N为σ的核。例.设G是整数加法群，G′是模3的加法群：{0，1，2}，σ：xx（mod3），x∈G，则σ是G到G′上的同态映射。σ的核为3G。群的第一同态定理定理6.5.2设σ是群G到Gˊ上的一个同态映射，于是，σ的核N是G的一个正规子群，对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G,σ(x)=aˊ}是N在G中的一个陪集，因此，Gˊ的元素和N在G中的陪集一一对应。证明先证N是G的子群。1）证N非空。因为σ(1)=1ˊ，所以1∈N。2）若a∈N，b∈N，往证ab-1∈N。由σ（a）=1′，σ（b）=1′，可得σ(ab-1)=σ(a)σ(b-1)=σ(a)(σ(b))-1=1’(1’)-1=1’，故ab-1∈N。再证N是G的正规子群，即证对于任意的g∈G，gNg-1N。事实上，σ(gNg-1)=σ(g)σ(N)σ(g-1)=σ(g)1’σ(g)-1=σ(g)σ(g)-1=1’。故gNg-1N。（任取x∈gNg-1,则有n∈N，使得x=gng-1,故σ(x)=σ(gng-1)=σ(g)σ(n)σ(g-1))=σ(g)1’σ(g-1)=σ(g)(σ(g))-1=1’，因此，x∈N。最后证明：若a′∈G′而σ(a)=a′,往证σ-1(a’)=Na。事实上，对任意的b∈G，b∈σ-1(a’)iffσ（b）=a′iffσ(b)(a′)-1=1′iffσ(b)(σ(a))-1=σ(b)σ(a-1)=σ(ba-1)=1’iffba-1∈Niffb∈Na引理1设N是群G的正规子群。若A，B是N的陪集，则AB也是N的陪集。证明：因为N是正规子群，故Nb=bN，今设A=aN，B=bN，则AB=aNbN=abNN=abN，所以AB也是N的陪集。群的第二同态定理定理6.5.3设N是群G的正规子群，于是按照陪集的乘法，N的所有陪集作成一个群。命σ：a→aN，a∈G,则σ是G到上的一个同态映射，且σ的核就是N。称为G对于N的商群，记为G∕N。若G是有限群，则商群中元素个数等于N在G中的指数，即等于陪集的个数。GGG证明首先证明G～。1)显然，σ是G到上的映射。2）任取a,b∈G，σ(a)σ(b)=aNbN=abN=σ(ab)，故σ是G到上的同态映射.因此，是一个群。其次证明σ的核是N。因单位元就是N本身，所以，核σ={g∣σ(g)=N,g∈G}={g∣gN=N,g∈G}={g∣g∈N}=N。GGGGG例.设R是整数环，N=5I={…,-10,-5,0,5,10,…}，则N是G的正规子群。令为G中N的所有陪集作成的集合：{，，，，}，={…,-10,-5,0,5,10,…}=N=0+N，={…,-9,-4,1,6,11,…}=1+N，……用⊕表示陪集间的加法，则⊕=(1+N)⊕(4+N)=(1+4)+N=N=，在陪集加法下是一个群，若命σ：a→a+N，则σ是G到上的同态映射,且σ的核就是N。0012341G140GG群的第三同态定理定理6.5.4设σ是群G到G′上的一个同态映射，若σ的核为N，则G′G/N。例.设G是整数加法群，σ：x→x（mod5），x∈G，则G′=σ（G）={0，1，2，3，4}是模5的加法群，σ是G到G′上的同态映射。σ的核为N=5G，G/N={,,,,}，则G′G/N。01234证明因为G′的元素和G/N的元素一一对应，设在这个一一对应之下，G′的元素a′和b′分别对应G/N的元素aN和bN：a′aN，b′bN。于是a′=σ（a），b′=σ（b），而且a′b′=σ（ab），可见G′的元素a′b′所对应的G/N的元素是abN=aNbN：a′b′aNbN。所以G′和G/N同构。证法二：建立映射τ：a’→σ-1(a’),a’∈G’。往证τ是G’到G/N上的同构映射。证τ是G’到G/N内的映射。任取a’∈G’,则有a∈G,使a’=σ(a)。由定理6.5.2，知σ-1(a’)=aN。由τ定义，τ(a’)=σ-1(a’)=aN∈G/N。证τ是满映射。任取aN∈G/N，设σ(a)=a’，则a’∈G’，由定理6.5.2，知τ(a’)=σ-1(a’)=aN。证τ是单射。任取a’,b’∈G’,若a’≠b’，证τ(a’)≠τ(b’)。若不然,τ(a’)=τ(b’)。设a’=σ(a),b’=σ(b),a,b∈G,于是，σ-1(a’)=σ-1(b’)，即aN=bN。又a=a1∈aN,故a∈bN，即有n∈N，使a=bn。因此，σ(a)=σ(bn)=σ(b)σ(n)=σ(b)，与a’≠b’矛盾。证τ是G’到G/N的同态映射。任取a’,b’∈G’,设a’=σ(a),b’=σ(b),a,b∈G,则τ(a’b’)=τ(σ(a)σ(b))=τ(σ(ab))=σ-1(σ(ab))=abN=aNbN=σ-1(a’)σ-1(b’)=τ(a’)τ(b’).综上，τ是G’到G/N上的同构映射，即G′G/N。G中子群与G′中子群的关系设σ为群G到G′上的同态映射。结论1.若H为G之子群，则H′=σ(H)亦为G′之子群。证明：由H为G之子群，知H为群，再由σ为群G到G′上的同态映射知，σ为群H到H′上的同态映射,由定理6.5.1知，H′亦为群，而H′=σ(H)G′，故为G′之子群。结论2.若H′为G′之子群，则H=σ-1（H′）亦必为G之子群，其中σ-1（H′）={x|x∈G,σ(x)∈H′}。证明：σ-1（H′）非空，因σ(1)=1′∈H′,所以1∈σ-1（H′）；若a，b∈σ-1(H′)，即σ(a),σ(b)∈H′，因H′为子群，故σ(ab-1)=σ(a)σ(b-1)=σ(a)σ(b)-1∈H′，因之ab-1∈σ-1（H′）。思考题σ(σ-1(H′))等于H′吗？σ-1(σ(H))等于H吗？例.G是模12的整数加法群，G={0,1,…,11},G’是模4的整数加法群，G’={0,1,2,3},令σ：xx(mod4)，x∈G，则σ为G到G’上的同态映射，σ的核为N={0,4,8}。取G的子群H={0,6}，则H’=σ(H)={0,2}是G’的子群，而σ-1(σ(H))=