chapter計算機科學(xué)與技術(shù)學(xué)院

設(shè)X=｛1,5,p,張明｝，Y=｛2,q,7,9,G｝（1）f｛﹤1,2﹥﹤5,q﹥﹤p,7﹥﹤張明G﹥｝。f為函數(shù)，且domf=X，ranf=｛2,q,7,G｝（2）二元關(guān)系f’｛﹤1,2﹥﹤5,q﹥﹤張明G﹥｝，f’YXf|f：X→Y，有|Y||X|個不同的函數(shù)。

定義4- (函數(shù)相等)設(shè)f，g為函數(shù)，則f=gf∧g domf=dom x∈domf，都有f(x例

對于函數(shù)f:X→Y，若ranf=Y，即Y的每一個元素都是X中一個或多個元素的映像，則稱函數(shù)ff:X→Y是滿射 對于y∈Y,x∈X使得y=f(x)成 A={a,b,c,d},B={1,2,3}，如果f為A到B的函數(shù)，且f(a)=1,f(b)=1,f(c)=3,f(d)=2，則fA到B

從X到Y(jié)的函數(shù)f，X中沒有兩個元素有相同f:X→Yx1,x2∈X，x1x2f(x1f 函數(shù)f:｛a,b｝→｛2,4,6｝,f(a)=2,f(b)=

例f:{a,b}→{1,2},fa)=1,fb)=2f例在下圖表示函數(shù)的中,

令X和Y為有限集，若X和Y的元素個數(shù)相同，即|X|=|Y|，則f:X→Y是入射的，iff它是一個滿f是入射，則|X||f(x)|又因為|X||Y|，故|f(x)||Y|f定義知f(XY|Y|f(XY，f是滿射。f是滿射，由滿射定義知f(XY于是由|X||Y||f(x)||X||f(X)||X|是有限的，故f是一個入射。如：f:I→Ifx)2x,f

fffc不一定f:X→Yf:X→Y為此，對函數(shù)求逆需規(guī)定一些條件：既是滿射，又是入射

設(shè)f:X→Y是一雙射函數(shù)，則fc是Y→X的(證明思路：分兩步，（1）證fc為函數(shù)；（2）證fc為雙射 設(shè)f=｛﹤x,y﹥|x∈Xy∈Y∧yf(xfc=｛﹤y,x﹥|(fc為函數(shù)：根據(jù)函數(shù)定義去證明。1ff為關(guān)系，故fc2、(證明像的存在性，即證y∈Yx∈X，使得﹤y,x﹥∈fc。y∈Y由于f是滿射，故x∈X使得﹤x,y﹥∈fx∈X﹤y,x﹥∈fc3、(證明像的唯一性，即證y∈Y存在唯一x∈X﹤y,x﹥∈fc假設(shè)y∈Yx1,x2∈Xx1x2f(x1f(x2)=y

由于f為入射，故當(dāng)x1≠x2時，可得f(x1)≠f(x2)與f(x1)=f(x2) 所以y∈Y,存在唯一x∈X，使得﹤x,y﹥∈fy∈Y,存在唯一x∈X，使得﹤y,x﹥∈fc。由1 f (證fc是滿射又是入射1、(fc為滿射，即證x∈Xy∈Y使得﹤y,x﹥∈fc),因為f為函數(shù)，由f的像的存在性可知：x∈Xy∈Y，使得﹤x,y﹥∈fx∈Xy∈Y，使得﹤y,x﹥∈fcfc為滿射。2、(證fc為入射：即證y1,y2∈Yy1y2,x1,x2∈X,x1x2使得﹤y1,x1﹥﹤y2,x2﹥∈fcy1,y2∈Y,y1≠y2，由于fc是函數(shù)已證明。故x1,x2∈X﹤y1,x1﹥﹤y2,x2﹥∈fc

x1,x2∈X使得﹤x1,y1﹥﹤x2,y2﹥∈f又由于f是雙射可知x1≠x2。所以,y1,y2∈Yy1y2x1,x2∈X﹤y1,x1﹥﹤y2,x2﹥∈fc，故fc由1、2可知fc為雙射 定義4-2.1設(shè)f:X→YfY→X為f的逆函數(shù)，記作f-1

定義4- 設(shè)函數(shù)f:X→Y,g:W→Z，若f(X)W，gf={<x,z>|x∈X∧z∈Z∧(y)(y∈Y∧y=f(x)∧z=g(y))注1gf(xg(f(x2、若ranfW這個條件不成立，則定義gf定理4- g:W→Z,f:X→Y為左復(fù)合,則gf

f:R→Rg:R→R,h:R→R,f(x)=x+2,g(x)=x-2,h(x)=3x求:gf 解:gf=｛﹤x,x﹥|x∈R｝ f)=｛﹤x,3x﹥|x∈R一般地， h f g定理4- 令gf是一個復(fù)合函數(shù)若gf是滿射，則gf若gf是入射，則gf若gf是雙射，則gf

證明afX→YgY→ZgfX→Z,g是滿射的。故對于z∈Z,y∈Y使得g(y)=z。f是滿射的，故對于上述y∈Yx∈X,使得f(xy。z∈Zx∈X，使得gf(xg(f(xg(yz。所gf是滿射的。因為f為入射，所以x1,x2∈X當(dāng)x1x2時，有f(x1)≠f(x2)。有g(shù)(f(x1g(f(x2即：x1,x2∈X,且x1≠x2時,有 f(x1)≠ f(x2)所以gf

y0∈Y，對于每個x∈Xf(xy0，即f(X｛y0｝ IX:X→X為恒等函數(shù)。

定理4-2.4f:X→YffIXIYf證明：因為fX→Y，IXX→XfIXX→Y，所以domfdomfIXX又因為x∈Xy∈Yyf且fIX(x)=f(IX(x))=f(x)=y。所以f=fIX。同理可證f=IXf

定理4-

如果函數(shù)f:X→Y有逆函數(shù)f-1:Y→Xf fIX, f–1IY證明：因為f:X→Yf-1:Y→X故f- f

X→X。所以domf- f=domIX= 又因為x∈X,y∈Y使得y=f(x)且f-1(y)=x。故f-1 f(x)=f-1(f(x))=f-1(y)=x=IX(x)。所以f- f=IX。同理可證 f–1=IY

定理4- 若f:X→Y是雙射函數(shù)，則(f–1)–1=f證明：因為fX→Y是雙射，由定理4-2.1f-1再由定理4-2.1可知(f–1)–1也是雙射，且(f–1)–1=(f–1)c=(fc)c。由逆關(guān)系性質(zhì)知(fc)c =f。所以(f–1)–1=f

定理4- 若f:X→Y,g:Y→Z均為雙射函數(shù)，(gf)-1f- g-1證明：因為fg為雙射，由定理4-2.3知gf由逆函數(shù)定義可知：f–1=fc,g–1=gc,(gf)-1=(gf)c。再由復(fù)合關(guān)系逆的性質(zhì)知：(gf)c=fc 所以(gf)-1=(gf =f gc=f- g-1

A+A∪｛A｝若A?，則????,{?{?,{?},{?,{?若命名?為0，則

0∈N(其中0?如果n∈Nn+∈N如果一個子集SN0∈S如果n∈S，有n+∈S，則SN注例如3{???,{?

數(shù)，就稱A和B是等勢的，記作A～B。注：此定義給出了證明A～B的法。例：設(shè)R為實數(shù)集合，S={x|x∈R∧0<x<1}R～S。。證明：令f:R→S，f(x)=(arctgx。顯然f: 是一個雙射函數(shù)。故R～S

對于A∈SIA:A→AIA(xx。顯然IA:A→A為一個雙射函數(shù)。故A～A。即等勢關(guān)系為自反關(guān)系。對于A,B∈S如果A～Bf:A→B。由定理4-2.1f-1:B→A存在，且為雙射函數(shù)，故B～A對于A,B,C∈S，如果A～B,B～Cf:A→B,g:B→C均為雙射函數(shù)。由定理4-2.3gf:A→CA～C，由(1)、(2)、(3)可知集合族上的等勢關(guān)系是一個等價關(guān)系。＃

定理4- (證明思路：證明Nn到N不存在雙射證明：設(shè)n∈N，fNnN的函數(shù)。設(shè)k=1+max{f(0),f(1),…,f(n-1)}。那么k∈N，但對每一個x∈Nn，有f(xkf:Nn→Nf由于n和f均為任意的，故N是無限的

的集合叫做集合A的基數(shù)，記作K[A](或A 、|A|)。

A

,L ,L,A f(0)義f:[0,1] n f ) nf(x)x,x[0,1]f是[0,1到（0,1）上的雙射函數(shù)。（如下圖所示） 21 由定理4-4.2N是無限集，但是并非所有無限集都可以與N等勢。故無限集合之間也是有大小的。我們通過首先我們選取N為“標(biāo)準(zhǔn)集合”，記K[N] 數(shù)集合的基數(shù)為0。

A={1,4,9,16,…,n2,…}，B={1,8,27,64,…,n3,C={2,5,10,17,…,n2+1,…}，D={1,1?2,1?3,…,1?n,均為可數(shù)集，且K[A]=K[B]=K[C]=K[D]=0 定理4- A=｛a1,a2an｝證明：如果A=｛a1,a2,….,an,…｝，那么存在f: f(an)=n-1(n=1,2,f為雙射函數(shù)。故A～NAAA～NfN→A 令f(n)=an+1(n=0,1,2,故A=｛a1,a2,….,an,…｝

定理4- a1而耗盡，所以從A｛a1｝中可取元素a2則A-｛a1,a2｝a3就得到A的可數(shù)子集 證明：設(shè)M為無限集，由定理4-5.2可知A=｛a1,a2,….,an,…｝,且AM。設(shè)M-A=B，定義函數(shù)f:M→M-｛a1｝，且f(x)=an+1(x=an,n=1,2,f(x)=顯然M-｛a1｝M，且f為雙射函數(shù)

定理4- AA=｛a1,a2,….,an,…｝,BA為一無限Aa1B中ai1,ai2,…,ain,…,故B=｛ai1,ai2,…,ain,…｝，即B是可數(shù)的

,a1n,｝,a2n,｝,a3n,｝令S=S1∪S2=Uk

a a a a a41 a42 a43 a44

即S=｛a11,a21,a11,a13,a22,a31,a41,a32,…｝，所以S是可數(shù)集。 注：1、定理4-5.5中S中的元素的排列方法是不唯一的。

令S1｛<0,0>,<0,1>,<0,2>,…,<0,n>,…｝S2｛<1,0>,<1,1>,<1,2>,…,<1,n｝S3｛<2,0>,<2,1>,<2,22,n｝

。由定理4-5.5N×N注

定理4- 證明：一切有理數(shù)均呈±n/m(n,m∈N,m≠0)?，F(xiàn)將所有±n/m按下列后。按照故所有呈±n/m狀的數(shù)所組Q為其無限子集，由定理4-5.4Q為可數(shù)集。＃

Si0.y1y2y3…yi∈｛0,1,2（注：0.2和0.123可分別記為0.1999…設(shè)S1=0.a11a12a13,…a1n…S2=0.a21a22a23S3

0.122999…這樣，rS1,S2Sn 記（0,1）A～(0,1)，那么K[A

定理4- 因為S是不可數(shù)集，則R

定義（4-6.1）若從集合A到集合B存在一個入射，則稱A的基數(shù)不大于B的基數(shù)，K[A]≤K[B]。若從A到B存記作K[A]<K[B]。

a)K[A]< b)K[A]> c)K[A]=設(shè)A和B是集合，如果K[AK[BK[BK[AK[AK[B

f:(0,1)g:[0,1]

f(xx（恒等函數(shù)g(x)注：此兩個函數(shù) 不唯一。如f(x)=x/2

g(x)例設(shè)A=N,B=(0,1),K[A]=0,K[B]= 證明：作入射函數(shù)f f(n,x)=故：K[A×B]≤K[R] 作入射函數(shù)g:(0,1)A×B,g(x故≤K[A×B]，因此K[A×B]=

設(shè)A是有限集合，

K[A]0K[AnA～NnfNn→N,f(xK[AK[N]，即K[A]<0。再定義入射函數(shù)：g:N→(0,1),