離散數學1/47第四章函數4-1函數概念4-2逆函數和復合函數4-4基數概念4-5可數集與不可數集4-6基數比較2/472第四章函數4-1函數概念4-2逆函數和復合函數4-4基數概念4-5可數集與不可數集4-6基數比較3/473函數概念定義4-1.1

設X

和Y是任何兩個集合。而f是X到Y一個關系，假如對于每一個x∈X

，有唯一y∈Y，使得﹤x,y﹥∈f，稱關系f

為函數，記作：f:X→Y

或概念：自變量、映像、定義域和值域注意：1函數與關系2函數亦稱映射或變換。習慣用小寫英文f,g,……

表示函數符。3在﹤x,y﹥∈f中，f前域就是函數定義域,記作domf(或Df)顯然由定義可知：Df=｛x∣x∈X∧(

y)(y∈Y∧y=f(x))｝=X4/4744f值域記為ranf(或Rf)，即：Rf=｛y∣y∈Y∧(x)(x∈X∧y=f(x))｝。問題：ranf=Y?5映像集：f(X)=ranf5/475實例例1設

X=｛1,5,p,張明｝，Y=｛2,q,7,9,G｝,f=｛﹤1,2﹥,﹤5,q﹥,﹤p,7﹥,﹤張明,G﹥｝。求：Domf和ranf例2判別以下關系中哪個能組成函數1f=｛﹤x1,x2﹥∣x1,x2∈N,且x1+x2<10｝。2f=｛﹤y1,y2﹥∣y1,y2∈R,y22=y1｝。3f=｛﹤x1,x2﹥∣x1,x2∈N,x2為小于x1素數個數｝。6/476函數相等定義4-1.2 (函數相等)設函數f:A→B,g:C→D,若A=C,B=D且對一切x

∈A,有

f(x)=g(x)，則稱函數

f和g相等。記為f=g。問題：函數相等兩個要素？問題：對于有限集合X和Y，而且|X|=m，|Y|=n：1X到Y關系有多少個？2X到Y函數有多少個？概念：符號YX

表示從X到Y全部函數集合，甚至當X和Y是無限集時，也用這個符號。7/477滿射函數定義4-1.3

對于f:X→Y映射中，若ranf=Y，即Y

每一個元素是X中一個或多個元素像點，則稱這個映射為滿射(或到上映射)。問題：怎樣說明或證實一個函數是滿射，請用謂詞公式進行說明。例1

A={a,b,c,d},B={1,2,3}假如f為A

到B

函數,且f(a)=1,f(b)=1,f(c)=3,f(d)=2，則f是A

到B上滿射。8/478入射函數定義4-1.4

從X到Y映射,X中沒有兩個元素有相同像，則稱這個映射為入射(或一對一映射)。問題：1怎樣說明或證實一個函數是入射，請用謂詞公式進行說明。

2建立在X和Y上滿射及雙射函數個數與集合大小關系。例

函數f:｛a,b｝→｛2,4,6｝,f(a)=2,f(b)=6則f是入射，但不是滿射。9/479雙射函數定義4-1.5 從X

到Y

一個映射，若既是滿射又是入射，則稱這個映射是雙射(或一一對應映射)。例函數f:{a,b}→{1,2},f(a)=1,f(b)=2，則f

為雙射。例在下列圖中,(a),(c)是滿射,(b),(c)是入射,(c)是雙射,(d)非滿射又非入射。

(a)(b)(c)(d)10/4710定理4-1.1 令X和Y

為有限集，若X和Y元素個數相同，即|X|=|Y|，則f:X→Y是入射，iff它是一個滿射。證實：注意：此定理僅在有限集情況下才能成立，在無限集上不一定成立。如：f:I→I,f(x)=2x,這里顯然f是一個入射，而不是滿射。11/4711第四章函數4-1函數概念4-2逆函數和復合函數4-4基數概念4-5可數集與不可數集4-6基數比較12/4712逆函數問題：給定一個關系R，顛倒R全部序偶，得到逆關系Rc

。給定一個函數

f，顛倒f

全部序偶，得到逆關系fc是函數嗎？假如不是，在什么情況下其是逆函數？13/4713定理4-2.1設f:X→Y是一雙射函數，則fc是Y→X

雙射函數。證實思緒：分兩步，（1）證fc

為函數；（2）證fc

為雙射)定義4-2.1設f:X→Y是一雙射函數，稱Y→X雙射函數f

c為f逆函數，記作f

-1。14/4714復合函數定義4-2.2 設函數f:X→Y,g:W→Z，若f(X)

W，則g

?f={<x,z>|x∈X∧z∈Z∧(

y)(y∈Y∧y=f(x)∧z=g(y))}稱g在函數f

左邊可復合。注意：1、關系復合與函數復合在記法上區分。2、若ranf

domg

這個條件不成立，則定義g

?f為空。3、定理4-2.3兩個函數復合是一個函數。4、定義4-2.2中，當W=Y是，則函數g

?f稱為復合函數，或稱g

?f為g對f左復合。5、g

?f(x)=

g(f(x))。6、因為函數復合仍為函數，故可推廣到有限個函數復合。15/4715例

f:R→R,g:R→R,h:R→R,f(x)=x+2,g(x)=x-2,h(x)=3x

問題：函數復合滿足可結合性嗎？定理4-2.3 令g

?f是一個復合函數。a)若g

和f是滿射，則g

?f是滿射。b)若g

和f是入射，則g

?f是入射。c)若g

和f是雙射，則g

?f是雙射。證實思緒：利用滿射、入射和雙射定義直接證實16/4716常函數和恒等函數定義4-2.3函數f:X→Y叫做常函數，假如存在某個y0∈Y，對于每個x∈X都有f(x)=y0，即f(X)=｛y0｝。定義4-2.4假如IX={﹤x,x﹥|x∈X}，則稱函數IX:X→X

為恒等函數。定理4-2.4設函數f:X→Y，則f=f

?IX=IY?f。證實思緒：證實定義域相同，對應關系相同。定理4-2.5假如函數f:X→Y有逆函數f-1:Y→X，f-1

?

f=IX,

f

?

f–1=IY。17/4717逆函數逆函數與復合函數逆函數

定理4-2.6 若f:X→Y是雙射函數，則(f

–1)–1=f

。定理4-2.7 若f:X→Y,g:Y→Z

均為雙射，則(g

?f)-1=f-1

?

g

-1。證實：因為f,g為雙射，由定理4-2.3知g

?f是雙射。由逆函數定義可知：f–1=fc,g–1=g

c,(g

?f)-1=(g

?f)c。再由復合關系逆性質知：(g

?f)c=f

c

?gc。所以(g

?f)-1=(g

?f)c=fc

?gc=f-1

?g-1。18/4718第四章函數4-1函數概念4-2逆函數和復合函數4-4基數概念4-5可數集與不可數集4-6基數比較19/4719集合大小有限集合大小無限集合大小問題：怎樣比較兩個集合大小？20/4720G.Peano公理定義4-4.1設A是任意集合，A后繼集定義為集合：

A+=A∪｛A｝。(G.Peano公理)自然數N是以下集合：(1)0∈N(其中0=?)。(2)假如n

∈N，那么n+

∈N，(其中n=n+∪｛n｝)。(3)假如一個子集SN含有性質：a.0∈S; b.假如n

∈S，有n+

∈S，則S=N。21/4721說明：1上述自然數定義稱為歸納定義。其中(1)為基礎，(2)為歸納，(3)為極小性(指明了自然數系統是滿足公理(1)和(2)最小集合)。2從N定義可見，任意一個自然數可看作是一個集合名。問題：自然數系統是什么呢？22/4722等勢集合定義4-4.2 給定兩個集合P與Q，若對P中每個不一樣元素，與Q中每個元素能夠分別兩兩成對，則說P元素與Q元素間存在著一一對應。定義4-4.3

iff

集合A元素與集合B元素之間存在著一一對應，集合A與集合B稱為是等勢(或稱同濃)，記作A～B。23/4723實例例1：N1={x|x=2*i,i∈N}，證實N1～N例2：設R為實數集合，S={x|x∈R∧0<x<1}。證實：R～S。證實：令f:R→S，f(x)=(arctgx/π)+1/2。顯然f:R→S

是一個雙射函數。故R～S。24/4724定理4-4.1 (等勢性質)在集合族上等勢關系是一個等價關系。證實：設S為集合族。1)對于

A∈S，可作恒等函數IA:A→A,IA(x)=x。顯然IA:A→A

為一個雙射函數。故A～A。即等勢關系為自反關系。2)對于

A,B∈S，假如A～B，那么存在雙射函數f:A→B。由定理4-2.1可知

f-1:B→A

存在，且為雙射函數，故B～A，即等勢關系為對稱關系。3)對于

A,B,C∈S，假如A～B,B～C那么存在f:A→B,g:B→C均為雙射函數。由定理4-2.3可知g?

f:A→C

為雙射函數，故A～C，即等勢關系為一個傳遞關系。由(1)、(2)、(3)可知集合族上等勢關系是一個等價關系。＃25/4725有限集合和無限集合定義4-4.4假如有一個從集合{0，1，…，n-1}到集合A雙射函數，則稱集合A是有限；假如集合A不是有限，則它是無限。概念：Nn=｛0,1,2,…,n-1｝稱為N初始段，Nn

可用于證實集合N為有限集。故Nn

又作為一個“標準集合”。定理4-4.2

自然數集N是無限。證實：26/4726基數-無限集合大小定義4-4.5 全部與集合A等勢集合所組成集合，叫做集合A基數，記作

K[A](或、|A|

)說明：1、定義4-4.5是由G.弗雷格與B.A.W.羅素分別在1884年與19給出。但在ZFC系統中不能證實它組成一個集合。按照康托爾原意，認為集合A基數是量詞抽象結果，一次從A元素中抽去質特征，另一次是抽去元素之間次序關系。A

基數是一切與A含有等勢關系集共同特征。故用或|A|中兩個杠表示二次抽象。2、依據康托爾原意，通常將基數定義描述為：度量集合大小量叫基數(或勢)。如

K[Nn]=n。約定K[Φ]=0。故有限集合基數為集合所含元素個數。假如A,B

為無限集合，而且A～B，則有K[A]=K[B]。27/4727實例證實區間[0,1]與（0,1）基數相同。證實：設定義f:[0,1]→（0,1）,顯然f

是[0,1]到（0,1）上雙射函數。（以下列圖所表示）。＃28/4728第四章函數4-1函數概念4-2逆函數和復合函數4-4基數概念4-5可數集與不可數集4-6基數比較29/4729可數集說明：N

是無限集，不過并非全部沒有限集都能夠與N

等勢。故無限集合之間也是有大小。定義4-5.1 與自然數集合等勢任意集合稱為可數，可數集合基數為。即K[N]=例：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,…}均為可數集，且K[A]=K[B]=K[C]=K[D]=。

30/4730定理4-5.1

A為可數集充分必要條件是A能夠排列成A=｛a1,a2,….,an,…｝形式。證實：假如A=｛a1,a2,….,an,…｝，那么存在f:A→N

且f(an)=n-1(n=1,2,…)f

為雙射函數。故A～N，即A

為可數集。反之，假如A可數，那么A～N，則存在雙射函數f:N→A,令f(n)=an+1(n=0,1,2,…)故A=｛a1,a2,….,an,…｝。說明：此定理能夠作為A是可數集一個等價定義，也是證實A可數一個實用方法。31/4731定理4-5.2 任一無限集必含有可數子集。證實：定理4-5.3 任一無限集必與其某一個真子集等勢。證實：設M

為無限集，由定理4-5.2可知A=｛a1,a2,….,an,…｝,且A

M。設M-A=B，定義函數f:M→M-｛a1｝，且

f(x)=an+1(x=an,n=1,2,…),f(x)=x(x

B)顯然M-｛a1｝M，且f為雙射函數。32/4732說明：1、定理4-5.3中某一個真子集不是指全部真子集，如真子集為有限集，則有限集與無限集是不可能等勢。2、能夠證實A

有限集是不滿足定理4-5.3（怎樣證實）。故有A

無限集當且僅當與其某一個真子集等勢，能夠作為無限集等價定義。33/4733定理4-5.4 可數集任何無限子集都是可數。證實：設A

是可數集合，則A=｛a1,a2,….,an,…｝,B

A為一無限子集，將A

中元素從

a1開始，向后檢驗，不停地刪去不在B

中元素，則得到新一列ai1,ai2,…,ain,…,故B=｛ai1,ai2,…,ain,…

｝，即B

是可數.34/4734即S=｛a11,a21,a11,a13,a22,a31,a41,a32,…｝，所以S

是可數集。定理4-5.5 可數個兩兩不相交可數集合并集，依然是一可數集。證實：（用排隊方法證實）設可數個可數集分別表示為：

S1=｛a11,a12,a13,…,a1n,…｝

S2=｛a21,a22,a23,…,a2n,…｝

S3=｛a31,a32,a33,…,a3n,…｝………………令S=S1

∪S2∪…=，對S

元素作以下排列：35/4735說明：1、定理4-5.5中

S

中元素排列方法是不唯一。2、利用定理4-5.4和定理4-5.5能夠證實：可數個可數集并是可數。（怎樣證實）36/4736定理4-5.6：N×N是可數集。證實：令S1=｛<0,0>,<0,1>,<0,2>,…,<0,n>,…｝

S2=｛<1,0>,<1,1>,<1,2>,…,<1,n>,…｝

S3=｛<2,0>,<2,1>,<2,2>,…,<2,n>,…}………………則N×N=由定理4-5.5可知N×N是可數集。說明：注意此種證實方法與教材上方法差異37/4737定理4-5.7 有理數集Q

為可數集。（用排隊法證實）證實：一切有理數均呈±n/m(n,m∈N,m≠0)。現將全部±n/m按以下次序排列：（1）正分數按其分子、分母之和大小次序排列：從小到大。（2）正分數分子、分母之和相同者按分子大小次序排列：從大到小。（3）將0放在首位，與正分數含有相同形式負分數排于正分數之后。按照上述規則可得：0,1/1,-1/1,2/1,-2/1,1/2,-1/2,3/1,-3/12/2,-2/2,1/3,-1/3,…故全部呈±n/m

狀數所組成集合為可數集，而Q

為其無限子集，由定理4-5.4知Q為可數集。38/4738不可數無限集概念：連續統并非全部無限集均為可數集。選取（0,1）作為新“標準集合”，記（0,1）基數為，假如A～(0,1)，那么K[A]=。也稱作連續統勢。39/4739定理4-5.8 實數集R是不可數。（用反證法證實）證實：40/4740關于定理4-5.8證實幾點說明：1、僅由0,1組成無限序列集合是不可數。即T=｛a0a1a2…an…|n∈N,an=0or1｝為不可數集。2、將(1)推廣由0,1,2,…,9組成無限序列集合也是不可數集。3、S

=｛(x,y)|x.y∈R∧0<x,y<1｝為不可數集。(提醒：構作f:S→(0,1)

為雙射函數)4、證實：R×R×…×R=Rn

是不可數集。41/4741第四章函數4-1函數概念4-2逆函數和復合函數4-4基數概念4-5可數集與不可數集4-6基數比較42/4742基數比較說明：經過結構雙射函數證實集合等勢需要高度技巧性。定義4-6.1若從集合A到集合B存在一個入射，則稱A基數小于B基數，記作K[A]≤K[B]。若從A到B存在一個入射，但不存在雙射，則稱A基數小于B基數，記作K[A]<K[B]。43/4743定理4-6.1（Zermelo定理或稱三岐性定理）令A和B是任意集合，則以下三條中恰由一條成立。a)K[A]<K[B]b)K[A]>

K[B]c