集合論與圖論：第9講 函數(shù)

第9講函數(shù)內(nèi)容提要函數(shù),偏函數(shù),全函數(shù),真偏函數(shù)單射,滿射,雙射,計(jì)數(shù)問(wèn)題象,原象常數(shù)函數(shù),恒等函數(shù),特征函數(shù),單調(diào)函數(shù),自然映射合成(復(fù)合),反函數(shù),單邊逆(左逆,右逆)構(gòu)造雙射(有窮集,無(wú)窮集)2023/1/111《集合論與圖論》第9講函數(shù)(function),映射(mapping)單值的二元關(guān)系稱為函數(shù)或映射單值:xdomF,y,zranF,

xFyxFzy=zF(x)=y<x,y>FxFy是空函數(shù)常用F,G,H,…,f,g,h,…表示函數(shù).xyz非單值單值2023/1/112《集合論與圖論》第9講偏函數(shù)(partialfunction)偏函數(shù):domFAA到B的偏函數(shù):domFAranFB偏函數(shù)記作F:AB,稱A為F的前域,A到B的全體偏函數(shù)記為ABAB={F|F:AB}2023/1/113《集合論與圖論》第9講例1例1:設(shè)A={a,b},B={1,2},求AB.解:|A|=2,|B|=2,|AB|=4,|P(AB)|=24=16.f0=,f1={<a,1>},f2={<a,2>},f3={<b,1>},f4={<b,2>},f5={<a,1>,<b,1>},f6={<a,1>,<b,2>},f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.AB={f0,f1,f2,f3,f4,f5,f6,f7,f8}.#非函數(shù):{<a,1>,<a,2>},{<b,1>,<b,2>},{<a,1>,<a,2>,<b,1>},…2023/1/114《集合論與圖論》第9講全函數(shù)(totalfunction)全函數(shù):domF=A全函數(shù)記作F:AB

A到B的全體全函數(shù)記為BA或ABBA=AB={F|F:AB}2023/1/115《集合論與圖論》第9講關(guān)于BA的說(shuō)明BA=AB={F|F:AB}={F|F是A到B的全函數(shù)}|BA|=|B||A|.當(dāng)A=時(shí),BA={}當(dāng)A且B=時(shí),BA=AB=,但AB={}.2023/1/116《集合論與圖論》第9講真偏函數(shù)(properpartialfunction)真偏函數(shù):domFA,真偏函數(shù)記作F:AB,A到B的全體真偏函數(shù)記為ABAB={F|F:AB}2023/1/117《集合論與圖論》第9講例1(續(xù))例1(續(xù)):設(shè)A={a,b},B={1,2},求AB.解:f0=,f1={<a,1>},f2={<a,2>},f3={<b,1>},f4={<b,2>},f5={<a,1>,<b,1>},f6={<a,1>,<b,2>},f7={<a,2>,<b,1>},f8={<a,2>,<b,2>}.AB={f0,f1,f2,f3,f4}.#說(shuō)明:FABFdomFBFABFdomFB2023/1/118《集合論與圖論》第9講三者關(guān)系A(chǔ)B=ABAB偏函數(shù)AB

domFA全函數(shù)AB

domF=A真偏函數(shù)AB

domFA2023/1/119《集合論與圖論》第9講全函數(shù)性質(zhì)設(shè)F:AB,單射(injection):F是單根的滿射(surjection):ranF=B雙射(bijection):F既是單射又是滿射,亦稱為一一對(duì)應(yīng)(one-to-onemapping).非單射非滿射2023/1/1110《集合論與圖論》第9講例2例2:設(shè)A1={a,b},B1={1,2,3},A2={a,b,c},B2={1,2},A3={a,b,c},B3={1,2,3},求A1B1,A2B2,A3B3中的單射,滿射,雙射.2023/1/1111《集合論與圖論》第9講例2(解(1))例2:(1)A1={a,b},B1={1,2,3},解:(1)A1B1中無(wú)滿射,無(wú)雙射,單射6個(gè):f1={<a,1>,<b,2>},f2={<a,1>,<b,3>},f3={<a,2>,<b,1>},f4={<a,2>,<b,3>},f5={<a,3>,<b,1>},f6={<a,3>,<b,2>}.2023/1/1112《集合論與圖論》第9講例2(解(2))例2:(2)A2={a,b,c},B2={1,2},解:(2)A2B2中無(wú)單射,無(wú)雙射,滿射6個(gè):f1={<a,1>,<b,1>,<c,2>},f2={<a,1>,<b,2>,<c,1>},f3={<a,2>,<b,1>,<c,1>},f4={<a,1>,<b,2>,<c,2>},f5={<a,2>,<b,1>,<c,2>},f6={<a,2>,<b,2>,<c,1>}.2023/1/1113《集合論與圖論》第9講例2(解(3))例2:(3)A3={a,b,c},B3={1,2,3},解:(3)A2B2中雙射6個(gè):f1={<a,1>,<b,2>,<c,3>},f2={<a,1>,<b,3>,<c,2>},f3={<a,2>,<b,1>,<c,3>},f4={<a,2>,<b,3>,<c,1>},f5={<a,3>,<b,1>,<c,2>},f6={<a,3>,<b,2>,<c,1>}.#2023/1/1114《集合論與圖論》第9講計(jì)數(shù)(counting)問(wèn)題設(shè)|A|=n,|B|=m,問(wèn)AB中有多少單射,滿射,雙射?n<m時(shí),AB中無(wú)滿射,雙射,單射個(gè)數(shù)為m(m-1)…(m-n+1)n=m時(shí),AB中雙射個(gè)數(shù)為n!n>m時(shí),AB中無(wú)單射,雙射,滿射個(gè)數(shù)為2023/1/1115《集合論與圖論》第9講例3A,B是非空有窮集,討論下列函數(shù)的性質(zhì)1.f:AB,g:AAB,aA,g(a)=<a,f(a)>2.f:ABA,<a,b>AB,

f(<a,b>)=a3.f:ABBA,<a,b>AB,

f(<a,b>)=<b,a>2023/1/1116《集合論與圖論》第9講例3(解)1.f:AB,g:AAB,aA,g(a)=<a,f(a)>當(dāng)|B|>1時(shí),g是單射,非滿射,非雙射當(dāng)|B|=1時(shí),g是單射,滿射,雙射2.f:ABA,<a,b>AB,f(<a,b>)=a當(dāng)|B|>1時(shí),f非單射,是滿射,非雙射當(dāng)|B|=1時(shí),f是單射,滿射,雙射3.f:ABBA,<a,b>AB,f(<a,b>)=<b,a>f是單射,滿射,雙射2023/1/1117《集合論與圖論》第9講象(image),原象(preimage)設(shè)f:AB,A’A,B’BA’的象是f(A’)={y|x(xA’f(x)=y)}Bf(A)=ranfB’的原象是f-1(B’)={x|y(yB’f(x)=y)}AA’f(A’)f-1(B’)B’2023/1/1118《集合論與圖論》第9講象,原象(舉例)例:f:NN,f(x)=2x.

A’=N偶={0,2,4,6,…}={2k|kN},

f(A’)={0,4,8,12,…}={4k|kN}

B’={2+4k|kN}={2,6,10,14,…},

f-1(B’)={1+2k|kN}={1,3,5,7,…}=N奇#2023/1/1119《集合論與圖論》第9講定理3.1設(shè)f:CD為單射,C為C的非空子集族.C1,C2C,則1.f(C)={f(A)|AC}2.f(C)={f(A)|AC}3.f(C1-C2)=f(C1)-f(C2).證明:利用定理2.9和f的單射性.#2023/1/1120《集合論與圖論》第9講定理3.2設(shè)f:CD,D1,D2D,D是D的非空子集族.則1.f-1(D)={f-1(D)|DD}2.f-1(D)={f-1(D)|DD}3.f-1(D1-D2)=f-1(D1)-f-1(D2).證明:利用定理2.9.#2023/1/1121《集合論與圖論》第9講特殊函數(shù)常數(shù)函數(shù):f:AB,

bB,xA,f(x)=b恒等函數(shù):IA:AA,IA(x)=x特征函數(shù):A:E{0,1},A(x)=1xA單調(diào)函數(shù):f:AB,<A,A>,<B,B>偏序集單調(diào)增:x,yA,xAyf(x)Bf(y)單調(diào)減:x,yA,xAyf(y)Bf(x),嚴(yán)格單調(diào):把換成<自然映射:f:AA/R,f(x)=[x]R,R為A上等價(jià)關(guān)系

2023/1/1122《集合論與圖論》第9講自然映射(舉例)例:A={a,b,c,d,e,f},A/R={{a,b},{c,d,e},{f}},[a]=[b]={a,b},[c]=[d]=[e]={c,d,e},[f]={f},F:AA/R,F(x)=[x].F(a)={a,b},F(b)={a,b},F(c)={c,d,e},F(d)={c,d,e},F(e)={c,d,e},F(f)={f}.#abcdef2023/1/1123《集合論與圖論》第9講函數(shù)運(yùn)算合成(復(fù)合):性質(zhì),左(右)單位元,單調(diào)性反函數(shù):存在條件(雙射才有反函數(shù))單邊逆:左逆,右逆,存在條件2023/1/1124《集合論與圖論》第9講函數(shù)合成(composite)定理3:設(shè)g:AB,f:BC,則

f○g:AC,f○g(x)=f(g(x)).證明思路:

f○g是函數(shù)(即f○g單值)

domf○g=Aranf○gC,f○g(x)=f(g(x))2023/1/1125《集合論與圖論》第9講定理3(證明)證明:(1)f○g是函數(shù),即f○g是單值的.xdom(f○g),

若z1,z2ran(f○g),則x(f○g)z1x(f○g)z2

y1(y1Bxgy1y1fz1)y2(y2Bxgy2y2fz2)y1y2(y1By2Bxgy1xgy2y1fz1y2fz2)y(yBy1=y2=yy1fz1y2fz2)z1=z2

2023/1/1126《集合論與圖論》第9講定理3(證明)證明:(2)dom(f○g)=A.顯然dom(f○g)A,下證Adom(f○g),

x,xA!y(yBxgy)!y!z(yBzCxgyyfz)!z(zCx(f○g)z)

xdom(f○g).2023/1/1127《集合論與圖論》第9講定理3(證明)證明:(3)f○g(x)=f(g(x)).

由(1)(2)知ran(f○g)C,x,xA!z(zCz=f○g(x))!z!y(zCyBy=g(x)z=f(y))!z(zCz=f(g(x)))所以對(duì)任意xA,有,f○g(x)=f(g(x)).#2023/1/1128《集合論與圖論》第9講定理4定理4:設(shè)g:AB,f:BC,f○g:AC,則(1)f,g均為滿射,則f○g也是滿射.(2)f,g均為單射,則f○g也是單射.(3)f,g均為雙射,則f○g也是雙射.#2023/1/1129《集合論與圖論》第9講定理5定理5:設(shè)g:AB,f:BC,則(1)若f○g為滿射,則f是滿射.(2)若f○g為單射,則g是單射.(3)若f○g為雙射,則g是單射,f是滿射.#ggf2023/1/1130《集合論與圖論》第9講定理6定理6:設(shè)f:AB,則f=f○IA=IB○f.#AABBIAIBf2023/1/1131《集合論與圖論》第9講定理7(單調(diào)性)定理7:設(shè)f:RR,g:RR,且f,g按是單調(diào)增的,則f○g也是單調(diào)增的.證明:xy

g(x)g(y)

f(g(x))f(g(y)).#2023/1/1132《集合論與圖論》第9講反函數(shù)(inversefunction)定理8:設(shè)A為集合,則A-1為函數(shù)A為單根的.#推論:設(shè)R為二元關(guān)系,則R為函數(shù)R-1為單根的.#定理9:設(shè)f:AB,且為雙射,則f-1:BA,且也為雙射.#反函數(shù):若f:AB為雙射,則f-1:BA稱為f的反函數(shù).2023/1/1133《集合論與圖論》第9講構(gòu)造雙射及求反函數(shù)|A|=m,|B|=n,AB存在雙射n=m|A|=,|B|=,BA,AB可存在雙射,如f:NN-{0,1,2},f(n)=n+3[0,1](0,1)?R(0,1)?NNN?0123456780123456782023/1/1134《集合論與圖論》第9講例6:構(gòu)造NNN雙射?2023/1/1135《集合論與圖論》第9講方法1:用自然數(shù)性質(zhì)

nNn0,,N,為奇數(shù),使得n=2例:1=201,2=211,3=203,…,6=213,…,100=2225,…令n=2-1,可以去掉n0的條件令=2j+1,為奇數(shù)nN,n=2i(2j+1)-1,i,jN,此表示唯一.2023/1/1136《集合論與圖論》第9講方法1:f:NNNf:NNN,f-1:NNN,<i,j>NN,f(<i,j>)=2i(2j+1)-1,f-1(n)=f-1(2i(2j+1)-1)=<i,j>.例:f(<0,0>)=0,f(<0,1>)=2,f(<1,0>)=1,…

f-1(5)=<1,1>,f-1(101)=<1,25>,f-1(200)=<0,100>,…2023/1/1137《集合論與圖論》第9講方法2:Cantor編碼—對(duì)角線法<m,n><m,0><m+n,0>1+2+3+…+(m+n)+(m+1)=(m+n)(m+n+1)/2+(m+1)對(duì)應(yīng)的自然數(shù)為(m+n)(m+n+1)/2+m2023/1/1138《集合論與圖論》第9講方法2:f:NNNf:NNN,f-1:NNN,<m,n>NN,f(<m,n>)