集合論13圖論3第二章

第二章映射

對于一個過程或系統(tǒng)中出現(xiàn)的量或事物，不能孤立地去研究他們，而要研究它們之間的相互聯(lián)系，從事物之間的聯(lián)系中找出事物之間的運動規(guī)律。這種量與量、事物與事物之間的相互聯(lián)系的數(shù)學表現(xiàn)，最簡單的情況就是單值依賴關系，即函數(shù)關系。在數(shù)學分析中，把函數(shù)的定義域和值域限制在數(shù)的集合上沒有必要的。若隨便用什么屬性的集合代替數(shù)集，就得了到函數(shù)的最一般的概念——映射。映射的概念及其重要特殊性質映射的一般性質本章的主要內容：

映射的合成

逆映射映射的應用----抽屜原理、置換、二（n）元運算、特征函數(shù)§1函數(shù)的一般概念

在數(shù)學分析中，函數(shù)概念是這樣引入的：設X和Y是兩個數(shù)集，若依據(jù)某一法則f，使得xX，都存在唯一的yY與之對應，則稱法則f為定義在Ｘ上取值于Ｙ中的函數(shù)。Ｘ稱為函數(shù)的定義域，而值域包含在Ｙ中。函數(shù)f給x規(guī)定的對應值y常記為y=f(x)。函數(shù)概念實質在于建立了量與量間的單值對應關系。

不僅量與量間有單值依賴關系，事物與事物間也可有單值的對應關系。若把Ｘ和Ｙ理解為具有不同屬性的集合，得到了函數(shù)的一般概念——映射。這樣，映射是函數(shù)概念的推廣，它既能描述量與量間的單值聯(lián)系，又能描述具有任何屬性的事物間的單值聯(lián)系。

1.1映射的定義定義1設Ｘ和Ｙ是兩個非空集合,若根據(jù)某一法則f，使得xX，都存在唯一的yY與之對應，則稱f為一個從Ｘ到Ｙ的映射。Ｘ稱為f的定義域。x對應元素y稱為x在f下的象，而x稱為y的原象。

x在f下的值或象，記為f(x)。

集合{f(x)xX}稱為f的值域或象集,記為Im(f)。

即{f(x)xX}=Im(f)?Y。

“f是Ｘ到Ｙ的映射”這句話常記為：f:XY。映射這個定義，直觀上是令人滿意的。但是，其中所用的“法則”概念是含混不清的。因此，定義1給出的映射并不是一個精確的定義了的對象。

19世紀后期，Cantor創(chuàng)立了集合論，數(shù)學家們把函數(shù)定義為笛卡兒乘積的子集，即把函數(shù)與它的圖像等同，這是嚴格的，其中不再含有含糊的概念。這就引導我們用圖像的定義代替用規(guī)則定義的映射。定義2

設X和Ｙ是兩個非空集合。若Ｘ×Ｙ的子集f滿足下列條件：xX，都存在唯一的yY，使得(x,y)f[或y=f(x)]，則稱f是X到Ｙ的映射。一、例題例：X＝{1,2,3}，Y＝{a,b,c}，則

X×Y={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)｝。子集:{(1,a),(2,b),(3,c)},{(1,a),(2,a),(3,a)}{(1,a),(2,c),(3,c)}…

都是映射。子集:{(1,a),(1,b),(2,b),(3,c)},{(1,a),(2,b)}不是

二、映射關系圖有限集合X到Ｙ的映射可以用圖示方法給出：先列出X和Y的元素，在圖上用點表示；若f(x)=y，則在代表x的點畫一條帶箭頭的線指向代表y的點，如此得到的圖就是映射關系圖。這種表示方法形象、直觀，便于理解。一般情況下，為了使映射關系圖清晰，都是把X畫在左右，Y畫在右邊。

例：令X={1,2,3},Ｙ={a,b,c,d}。f:X→Y，f(1)=b，f(2)=d,f(3)=a,于是用集合表示法：f={(1,b),(2,d),(3,a)}；用圖表示如下：1.2特殊的映射定義1

設f:Ｘ→Y，A?X，當把f的定義域限制在Ａ上時，就得到了一個:A→Y，xA,(x)=f(x),則稱為f在Ａ上的限制。反過來，f是在Ｘ上的擴張。定義2設f:A→Y,A?X，則稱f是X到Y（或Ｘ上）的一個部分映射。在這里，X到Y不一定有映射，只是X的一部分有映射，故稱為部分映射。假定空集￠到Y有一個唯一映射（空映射），它也是Ｘ到Ｙ的部分映射。定義3設f,g:Ｘ→Y，則f=gxX，有f(x)=g(x)。

f≠gxX，使得f(x)≠

g(x)定義4

設f:Ｘ→Y，若x1，x2X，只要x1x2，就有f(x1)f(x2),則稱f為Ｘ到Ｙ的單射(入射)。定義5

設f:Ｘ→Y，若yY，xX,使得f(x)=y，則稱f為Ｘ到Ｙ上的映射，或稱f為滿射。定義6

設f:Ｘ→Y，若f既是滿射又是單射，則稱f為雙射，或一一對應。這時也稱Ｘ與Ｙ對等，記Ｘ～Ｙ。定義7

設f:Ｘ→Ｘ，若xX，f(x)=x，則稱f為Ｘ上的恒等映射。Ｘ上的恒等映射常記為Ix、I或1x

。1.3習題例題討論下列映射的性質例1X={1,2,3,4},Y={a,b,c,d,e},f(1)=a,f(2)=a,f(3)=c,f(4)=d。例2

令N={1,2,3,…}，S:N→N，則(1)nN，S(n)=n+1，Ｓ稱為自然數(shù)集N上的后繼函數(shù)。(2)S(1)=1,nN,S(n)=n-1,n≥2,Ｓ稱為自然數(shù)集N上的前仆函數(shù)。例3令Ｅ為全體偶自然數(shù)之集，f:E→N，2mE，

f(2m)=m。例4設Ｘ為整數(shù)的有限集，定義集合X-X={x-x’|x,x’

X}。試證：若A,B?{1,2,…,n}且|A|·|B|≥2n-1,n>1，則(A-A)?(B-B)中有一個正整數(shù)。例5設f:N×NN，f((x,y))=xy。則（1）說明f是單射、滿射或雙射？（2）求f(N×{1}),f-1({0})，N包含0。

答案：(1)(1,4)≠(2,2),f((1,4))=f((2,2))=4；yN,f((1,y))=1·y=y,y都有原象；

[f不是單射，f是滿射](2)f(N×{1})={n·1|nN}=N；f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。

1.4幾個重要的結論定理1

設Ａ,B是有限集合，f:AB。則（1）若f是單射，則AB；（2）若f是滿射，則AB；（3）若f是雙射，則A=B。定理2設Ａ,B是有限集合且A=B，則f:AB是單射f是滿射。說明:(1)f是單射也是滿射，從而f是雙射；

(2)定理中Ａ,Ｂ為有限集合是必要條件，若Ａ,Ｂ不是有限集合，則結論不成立（習題例2）。例題例1設R、Z、N是實數(shù)、整數(shù)、自然數(shù)集合，下面定義映射f1,f2,f3,f4,f5,f6，試確定它們的性質。（0N）（1）f1:RR,f1(x)=2x；（2）f2:ZN,f2(x)=|x|；

f1單射，不是滿射。f2不是單射，滿射。（3）f3:NN,f3(n)=n(mod3)；（4）f4:NN×N,f4(n)=(n,n+1)；

f3不是單射,滿射；

f4單射,不是滿射。（(0,0)無原象）（5）f5:RR,f5(x)=x+2；（6）f6:RR,f6(x)=x2,x≥0,f6(x)=-2,x<0；

f5是雙射；f6不是單射,不是滿射。例2設R為實數(shù)集，映射f:R→R，f(x)=2x

，則f是什么映射？(1)滿射、不是單射；(2)單射、不是滿射；(3)不是滿射、不是單射；(4)雙射。例3設R為實數(shù)集，f:R→R，g:R→R，且f(x)=2x+1，g(x)=x/2,則f與g的合成映射gf是什么映射？(1)滿射、不是單射；(2)單射、不是滿射；(3)不是滿射、不是單射；(4)雙射?！?抽屜原理抽屜原理：n+1個物體放到n個抽屜里，則一定存在某一抽屜里面至少有兩個物體。例1(1)13個人中至少有兩個人是在同一個月份出生。

(2)一年365天，今有366個人，則至少有兩個人生日相同。

(3)抽屜里有10雙手套，從中取出11只來，則其中至少有兩只是完整配對的。

(4)某次會議有n位代表參加，每一位代表至少認識其余n-1位中的一位，則在這n位代表中，至少有兩位認識的人數(shù)相等。例2坐標平面上有五個整數(shù)點，則存在兩個點的連線的中點一定是整數(shù)點。例3(1)證明：從一個邊長為1的等邊三角形中任意選5個點，則必有2個點之間的距離至多為1/2。(2)證明：從一個邊長為1的等邊三角形中任意10個點，則必有2個點之間的距離至多是1/3。(3)確定一個整數(shù)Mn，使得如果在一個邊長為1的等邊三角形中任意選擇Mn個點，則必有2個點之間的距離至多是1/n。(Mn取n2+1個)例4(1)證明從{1,2,…,2n}中任選n+1個數(shù)，則總存在2個數(shù)，使得它們之間的差為1。(2)證明從{1,2,…,3n}中任選n+1個數(shù)，則總存在2個數(shù)，使得它們之間的差最多為2。(3)證明從{1,2,…,kn}中任選n+1個數(shù)，則總存在2個數(shù)，使得它們之間的差最多為k-1。{1,2,…,k},{k+1,k+2,…,2k},…,…,{(n-1)k+1,(n-1)k+2,…,nk}

例5

證明從1,2,…,2n中，任選n+1個數(shù)，則在這n+1個數(shù)中必有兩個數(shù)，使得其中一個能整除另一個。例6

證明：在52個正整數(shù)中，必有兩個整數(shù)，使得這兩個整數(shù)之和或差能被100整除。

抽屜原理也稱為鴿巢原理、重疊原理。這個原理十分簡單，但若用得好卻會得到意想不到的有趣結論。但也應當注意，抽屜原理并未告訴我們怎樣實際地去尋找含有兩個或更多個物體的那個抽屜，而只是肯定了確有這樣的抽屜。例7已知m個整數(shù)a1,a2,…,am，試證：存在兩個整數(shù)k,l,0klm，使得ak+1+ak+2+…+al能被m整除。例8證明：對任意正整數(shù)N，存在N的一個倍數(shù)，使得它僅由數(shù)字0和7組成。（例如N＝3,有259×3＝777；N＝4,有1925×4＝7700；N＝5,有14×5＝70；N＝6,有1295×6＝7770等）。例9

在一個邊長為1的正方形內（包括邊界），任意地畫七個點，則其中必有三個點，以它們?yōu)轫旤c所組成的三角形面積小于等于1/6。例10

證明：在任意６個人中，或有3個人相互認識，或有3個人相互不認識。上面的例9、例10使用的抽屜原理實際上是抽屜原理的一種推廣形式，稱為“平均值原理”，即若把m只物體放到n個抽屜里，則一定存在某一個抽屜，它里面至少有[(m-1)/n]+1個物體。這里[x]表示不大于x的最大整數(shù)。例115個整數(shù)中必有3個整數(shù)其和能被3整除。例12

設a1,a2,…,an為1，2，3，…，n的任一排列,若n是奇數(shù)且(a1-1)(a2-2)…(an-n)0，則乘積為偶數(shù)。2.2抽屜原理強形式抽屜原理強形式:設m1,m2,…,mn都是正整數(shù),若把m1+m2+…+mn-n+1個物體放到n個抽屜里,則或第一個抽屜里至少有m1個物體,或第二個抽屜里至少有m2個物體,…,或第n個抽屜里至少有mn個物體。說明:當m1=m2=…=mn=2時，m1+m2+…+mn-n+1=n+1。抽屜原理是強形式的一種特殊情況。推論1

若有m個物體放到n個抽屜里，則一定存在某一個抽屜，它里面至少有[(m-1)/n]+1個物體。推論2

若把n(m-1)+1個物體放進n個抽屜里，則一定存在一個抽屜，里面至少有m個物體。此推論是強形式中，當m1=m2=…=mn=m時的特殊情況。推論3

若m1,m2,…,mn是n個正整數(shù)，且(m1+m2+…+mn)/n>r-1，則m1,m2,…,mn中至少有一個大于或等于r。2.3例題例1一籃子水果中有蘋果、橘子、梨。為保證籃子里或者至少有8個蘋果、或者至少有6個橘子、或者至少有9個梨。則放入籃子中的水果數(shù)至少是多少？例2一個袋子里裝了100個蘋果、100個橘子、100個梨、100個香蕉。如果每分鐘從袋子里取出一個水果，則需要多長時間肯定能拿出至少12個相同的水果？

21；q1+q2+q3+q4-n+1=12+12+12+12-4+1=45。例3一個人步行了十小時，共走45公里，已知他第一個小時走了6公里，而最后一小時只走了3公里，證明一定存在連續(xù)的兩個小時，在這兩個小時之內至少走了9公里。例4

一個園環(huán)等分36段,將36個數(shù)字1,2,…,36任意地寫在每一段上,使每一段上恰有一個數(shù)字,證明：一定存在連續(xù)的三段,在這三段上的數(shù)字之和至少為56。

§3映射的一般性質3.1象、原象的概念定義1

設f:XY，AX，由f和Ａ可以唯一的確定Ｙ中的一個子集，設為f(A)，于是，f(A)={f(x)xA}。稱f(A)為集合Ａ在f下的象集（象）。說明：利用這種方法，由f可以確定一個從2X到2Ｙ的映射，稱為導出映射，仍記為f。顯然

定義2

設f:XY，BY，則由f和Ｂ可以唯一確定X上的一個子集記為：f-1(B)，即

f-1(B)={xf(x)B，xX}

稱f-1(B)為在f下B的原象。例：設f:XY，X={1,2,3,4}，y={a,b,c,d,e}，

f(1)=a,f(2)=b,f(3)=b,f(4)=c,

令A={1,2}，B={b,c,d}，則

f(A)={a,b},f-1(B)={2,3,4}，特別地有：f-1(j0ese7d)=，f-1()={2,3}。

為書寫簡單：f({1})=>f(1),f-1()=>f-1(b)。注意：f(1),f-1(b)在這里都是集合。3.2性質定理1

設f:XY

，C，DY，則定理2

設f:XY

，A，BX，則

說明：（1）注意，兩個集合的交（差、對稱差）的象不一定與它們的象的交（差、對稱差）相重合。（2）設X={a,b,c},Y={1,2,3}，f:XY，f(a)=1，f(b)=2，f(c)=2，令A={a,b},B={c}。于是，A∩B=,f(A∩B)=。

但是，f(A)∩f(B)={1,2}∩{2}={2}≠，因此，f(A∩B)f(A)∩f(B)

同理，可以求其它幾個式子也是不等。（3）定理1和定理2可以推廣到有窮多個或無窮多個集合的并與交集的情況。例1設f:XY，A?X，B?Y。以下四個小題中，每個小題均有四個命題，這四個命題有且僅有一個正確，請找出正確的那個。(1)(a)若f(x)f(A)，則x未必在A中;(b)若f(x)f(A)，則xA;(c)若f(x)f(A)，則x?A;(d)若f(x)f(A)，則xAc。(2)(a)f(f-1(B))=B;(b)f(f-1(B))?B;(c)f(f-1(B))B;(d)f(f-1(B))=B。(3)(a)f-1(f(A))=A;(b)f-1(f(A))?A;(c)f-1(f(A))A;(d)以上都不對。(4)(a)f(A)≠;(b)f-1(B)≠;(c)若yY,則f-1(y)X;(d)若yY,則f-1(y)?X。例2設f:N×NN，f((x,y))=xy。則（1）說明f是單射、滿射或雙射？（2）求f(N×{1}),f-1({0})，N包含0。

答案：(1)(1,4)≠(2,2),f((1,4))=f((2,2))=4；yN,f((1,y))=1·y=y,y都有原象；

[f不是單射，f是滿射](2)f(N×{1})={n·1|nN}=N；f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}?！?映射的合成4.1定義定義1設f:AB，g:BC。若存在一個從A到C的映射記為h，并且xA，h(x)=g(f(x))，則稱h為映射f與g的合成。h記為gof(gf)，即h=gof=gf說明:

1.由定義知:xA，有：

h(x)=gof(x)=gf(x)=g(f(x))。

2．f與g的合成記為gf,而不記為fg。

3．映射的合成可用如圖所示。3．映射的合成可用如圖所示。

f的定義域dom(f)=A，f的值域ran(f)B；

g的定義域dom(g)=B，g的值域ran(g)C；

h的定義域dom(h)=A，h的值域

ran(h)={h(x)xA}C；4.例

設A={a，b，c}，B={0，1}，C={2，3}。

f:AB，f(a)=f(b)=0，f(c)=1；

g:BC，g(0)=2，g(1)=3，則gf:AC

且gf(a)=g(f(a))=g(0)=2;gf(b)=g(f(b))=g(0)=2;gf(c)=g(f(c))=g(1)=3。故gf={(a,2),(b,2),(c,3)}。但fg無意義。

f與g合成如圖所示。例2設A={a,b,c},f:AA,g:AA，

f={(a,a),(b,b),(c,a)}，

g={(a,b),(b,a),(c,c)}，

gf={（a,b),(b,a),(c,b)},fg={（a,b),(b,a),(c,a)}，故gf≠fg

由例題可以看出gf≠fg，即交換律不成立。3.2性質雖然交換律不成立，但卻有結合律成立。定理1設f:XY，g:YZ，h:ZW，則h(gf)=(hg)f。定理2設f:XY,則fIX=IYf=f。定理3設f:XY,g:YZ，則（1）若f與g都是單射，則gf也是單射；（2）若f與g都是滿射，則gf也是滿射；（3）若f與g都是雙射，則gf也是雙射。定理4

設f:XY，g:YZ，則（1）若gf是單射，則f是單射；（2）若gf是滿射，則g是滿射；（3）若gf是雙射，則f是單射，g是滿射。說明：1.gf是單射時，f是單射，但g不一定是單射；

gf是滿射時，g是滿射，但f不一定是滿射。2.例:設f:AB,g:BC,A={a,b},B={1,2,3},C={c,d}。

f={(a,1),(b,3)},

g={(1,c),(2,c),(3,d)}，則gf={(a,c),(b,d)}。

gf是單射，但g不是單射；gf是滿射，但f不是滿射。例題例1令X={x1,x2,…,xm},Y={y1,y2,…,yn},問：(1)有多少個不同的由X到Y的映射？(2)有多少個不同的由X到Y的雙射？(3)有多少個不同的從X到Y的單射？例2設f:XY，則(1)若X={1,2,3},Y={a,b},求X到Y滿射的個數(shù);(2)若X={1,2,3,4,5},Y={a,b},求X到Y的滿射的個數(shù);(3)若X={1,2,…,n},Y={a,b}，求X到Y的滿射的個數(shù).例3設X是一個有限集合，從X到X的部分映射有多少？例4

設f:XY，A?X，B?Y。以下四個小題中，每個小題均有四個命題，這四個命題有且僅有一個正確，請找出正確的那個。(1)(a)若f(x)f(A)，則x未必在A中;(b)若f(x)f(A)，則xA;(c)若f(x)f(A)，則x?A;(d)若f(x)f(A)，則xAc。(2)(a)f(f-1(B))=B;(b)f(f-1(B))?B;(c)f(f-1(B))B;(d)f(f-1(B))=B。(3)(a)f-1(f(A))=A;(b)f-1(f(A))?A;(c)f-1(f(A))A;(d)以上都不對。(4)(a)f(A)≠;(b)f-1(B)≠;(c)若yY,則f-1(y)X;(d)若yY,則f-1(y)?X。

§5逆映射5.1定義定義1設f:XY。若存在一個映射g:YX,使得gf=IX且fg=IY，則稱映射f是可逆的，而g稱為f的逆映射。

由定義，f可逆gf=IX與fg=IY同時成立，缺一不可。若只有一個條件成立時，便有:定義2

設f:XY，則(1)若存在一個映射g:YX,使得gf=IX，則稱f是左可逆的，g稱為f的左逆映射。(2)若存在一個映射h:YX,使得fh=IY，則稱f是右可逆的，而h稱為f的右逆映射。

一般說來，一個映射的逆映射未必存在，那么在什么條件下，一個映射才能存在逆映射呢？5.2性質定理1設f:XY，則f是可逆的f為雙射。定理2設f:XY，則若f是可逆的，那么f的逆映射是唯一的。f逆記為f-1。定理3設f:XY，g:YZ，若f和g都是可逆的，則gf也是可逆的且(gf)-1=f–1g-1，（f–1)-1=f。公式(gf)-1=f–1g-1稱為“穿脫原則”，脫的次序正好與穿的次序相反。說明：由定理可知：若f是可逆的，則f是雙射。若f是左可逆的,f如何？若f是右可逆的,f又如何？（2）例

設f1:{a，b}{0，1，2}，f2:{a，b，c}{0，1}，

f3:{a，b，c}{0，1，2}，如圖所示。則

f1是左可逆的，g1是f1的左逆映射，但不是右逆映射。

f2是右可逆的，g2是f2的右逆映射，但不是左逆映射。

f3的既是左可逆的，又是右可逆的，因此f3是可逆的。定理4設f:AB，A，則（1）f是左可逆的，當且僅當f是單射；（2）f是右可逆的，當且僅當f是滿射；（3）f既是左可逆的又是右可逆的f是雙射；（4）若f是雙射，則f的左逆映射等于右逆映射。由定理（1）和（2）的證明可以看出，若f左可逆，則其左逆映射未必唯一，甚至可以有無窮多個；若f右可逆，則其右逆映射也未必唯一，也可能有無窮多個。習題(1)例1設f:XY，X=m，Y=n，則(1)若f是左可逆的，則f有多少個左逆映射？(2)若f是右可逆的，則f有多少個右逆映射？例2是否存在一個從X到X的一一對應f，使得f=f-1，但f≠IX。例3

設f:XY，則(1)若存在唯一的一個映射g:YX,使得gf=IX,則f是可逆的嗎？(2)若存在唯一的一個映射g:YX,使得fg=IY,則f是可逆的嗎？例4設N={1,2,3,…},試構造兩個映射

f,g:NN，使得gf=IN，但fgIN。例5設N={1,2,3,…},試構造兩個映射

f,g:NN，使得fg=IN，但gfIN。例6

設f:N→N,g:N→N,f(n)=n+1,g(n)=max{0,n-1}，證明：gf=I,fg≠I

。第二章映射習題課（2）例1令X={x1,x2,…,xm},Y={y1,y2,…,yn},問：(1)有多少個不同的由X到Y的映射？(2)有多少個不同的由X到Y的雙射？(3)有多少個不同的從X到Y的單射？例2設f:XY，則(1)若X={1,2,3},Y={a,b},求X到Y滿射的個數(shù);(2)若X={1,2,3,4,5},Y={a,b},求X到Y的滿射的個數(shù);(3)若X={1,2,…,n},Y={a,b}，求X到Y的滿射的個數(shù).例3設X是一個有限集合，從X到X的部分映射有多少？例4設f:X→Y，A,B?X,證明:(1)f(A?B)=f(A)?f(B);(2)f(A∩B)?f(A)∩f(B);(3)f(A)\f(B)?f(A\B);(4)f(A)f(B)?f(AB)。例:X={a,b,c},Y={1,2,3},f:X→Y,f(a)=1,f(b)=f(c)=2。A={a,b},B={c}。例5

設u1,u2,…,umn+1是一個兩兩不相同的整數(shù)構成的數(shù)列，則必有長至少為n＋1(m+1)的遞增子序列或有長至少為m＋1(n+1)的遞減子序列。例6

設f:XY，證明：(1)f是單射F2X，f–1(f(F))=F；(2)f是滿射E2Y，f(f–1(E))=E。例7設f:X→Y，A?X，B?Y，證明：f(f-1(B)∩A)=B∩f(A)。例8設f:A→B,證明:T?B，有f(f-1(T))=T∩f(A)。例9設有映射f:A→B,H?A，令HC是H對A中的余集,當f分別是單射和滿射時，給出f(HC)和(f(H))C之間的關系，并給予證明。例10設X是一個無窮集合，f:XX。證明:存在X的一個真子集E，使得f(E)?E?！?置換本節(jié)討論有限集合上的一一對應6.1置換定義定義1

有限集合S到自身的一一對應稱為S上的一個置換。若S=n，則S上的置換稱為n次置換。一個n次置換就是S中的n個元素的一個全排列。n階有限群同構于n階置換群;n階置換群之間的代數(shù)運算就是置換的乘法運算。6.2置換的表示

用1，2，…，n表示n元集S的各元素。設S={1,2,…,n}，是S上置換，即:SS,是一一對應。于是，

iS

，存在唯一kiS對應，即(i)=ki。由于S只有n個元素，所以可把S的n個元素寫在一行上，而把每個元素在下的象ki寫在這個元素的下面，就得到如下的一個表:

……(1)….(1)顯然，表(1)與置換是等價的。表(1)是置換的一個方便的表示。說明：1.一個n次置換就是S中的元素的一個全排列。2.表(1)只是置換的一種習慣的表示法。3.例：設S={1,2,3}，而(1)=3，(2)=1,(3)=2。則可表示為:習慣上用表示。4.不要把表(1)看成是2行n列的矩陣，有限集合間的映射也可用這種方法表示。6.3置換的乘積（合成）1.乘積的表示方法

與的乘積（合成）就可記為，并且(i)=((i))

，或簡記為(i)

。2.例：S={1,2,3}，S上的置換,則若與是兩個置換，當把的表示式中的上一行按的下一行順序寫出時，則的下一行就是的新表示式中的下一行。即6.4幾種特殊的置換1.S上的恒等置換記為I，即2.置換的逆置換：

·-1=-1·=I

即的逆-1就是的表示式的上下兩行交換后所得到的表達式。3.循環(huán)置換、對換定義1

設是S上的一個n次置換，若i1=i2,i2=i3,…,ik-1=ik,ik=i1,而iS\{i1,i2,…,ik},i=i，則稱是一個k—循環(huán)置換，記為(i1i2…ik)。即

(i1i2…ik)=(i2i3…iki1)=(i3i4…iki1i2)==…=(iki1i2…ik-1)

當k＝2時，2－循環(huán)置換也稱為對換,簡記為(i,j)。

(i,j)=

恒等置換簡記為(1)或(2),…或(n),并把(i)稱為1-循環(huán)置換。4.循環(huán)置換的逆、對換的逆循環(huán)置換的逆為:

對換的逆為:

對換的逆就是其本身。6.5循環(huán)置換的性質映射的合成運算不滿足交換律，故置換的乘積也不滿足交換律。即,Sn，。但對于兩個沒有共同數(shù)字的循環(huán)置換卻是可交換的。定義1

設(i1i2…ik)與(j1j2…jr)是兩個循環(huán)置換，若(i1i2…ik)∩(j1j2…jr)=，則稱這兩個循環(huán)置換是沒有共同數(shù)字的循環(huán)置換（或稱不相交）。定理1

設=(i1i2…ik)與=(j1j2…jr)是兩個沒有共同數(shù)字的循環(huán)置換，則與是可交換的，即=。定理2

結合律成立。定理3（置換的循環(huán)分解）每個置換都能分解成若干個沒有共同數(shù)字的循環(huán)置換的乘積。

若不計這些循環(huán)置換的順序，則這種分解是唯一的。例：定理3每個置換都能分解成若干個沒有共同數(shù)字的循環(huán)置換的乘積。定理4

每個循環(huán)置換可被分解成若干個對換的乘積。定理5

每個置換能被分解成若干個對換的乘積。

但這種分解不唯一。卻有：定理6

若把置換分解成若干個對換的乘積，則對換的個數(shù)的奇偶性是不變的。定義2

若一個置換能被分解為偶數(shù)個對換的乘積，則稱這個置換為偶置換。若一個置換能被分解奇數(shù)個對換的乘積，則稱這個置換為奇置換。1個奇置換×1個偶置換＝奇置換；1個奇置換×1個奇置換＝偶置換；

任意偶數(shù)個奇置換乘積是偶置換；任意奇數(shù)個偶置換乘積是偶置換；任意奇數(shù)個奇置換乘積是奇置換。1.(i1i2i3…ik)=(i1i2)(i1i3)(i1i4)…(i1ik)(i1i2i3…ik)=(ik-1ik)(ik-2ik-1)…(i2i3)(i1i2)2.例：(123)=(12)(13)=(23)(12)

具有相同數(shù)字的兩個對換是不可交換的。即(12)(13)≠(13)(12)，(23)(12)≠(12)(23)。

左=(123)右=(132)，左=(123)右=(132)3.若循環(huán)長度K為偶數(shù)，則該循環(huán)可分解為奇數(shù)個對換的乘積；若循環(huán)長度K為奇數(shù)，則該循環(huán)可分解為偶數(shù)個對換的乘積。(1234)=(12)(13)(14)(1