2023/7/22離散數(shù)學(xué)1§4.1

等勢(shì)

如何比較兩個(gè)集合中元素的多少呢？引入等勢(shì)的概念。定義4.1.1設(shè)A和B是集合，若存在A到B的雙射，則稱A與B等勢(shì)，記為A~B。(可形象理解為A與B的元素一樣多。)“~”是一個(gè)等價(jià)關(guān)系。例1

自然數(shù)集N與偶自然數(shù)集E是等勢(shì)的，其中定義N到E的雙射為：(n)=2nn∈N.2023/7/22離散數(shù)學(xué)2證明“～”是一個(gè)等價(jià)關(guān)系證明：設(shè)S={X|任意兩個(gè)元素之間存在雙射，X是集合}，～是S上的二元關(guān)系：～={<A,B>|A,B∈S,存在雙射:AB}對(duì)每個(gè)AS,存在恒等映射I:AA，I是雙射,于是A～A，故～是自反的。對(duì)任意A,BS，若A～B，則存在雙射:AB，顯然雙射-1:BA存在，于是B～A，故～是對(duì)稱的。對(duì)任意A,B,CS，若A～B,B～C,則存在雙射:AB和:BC，而·(A)=·((A))=(B)=C，即雙射·:AC存在，于是A～C，故～是傳遞的。綜上所述，～是等價(jià)關(guān)系。2023/7/22離散數(shù)學(xué)3有限與無(wú)限定義4.1.2：設(shè)Nn={0,1,,n–1},n1,若集合A與Nn等勢(shì)，則稱A為有限集；否則稱A為無(wú)限集。2023/7/22離散數(shù)學(xué)4無(wú)限多的自然數(shù)

定理4.1.1

自然數(shù)集合N是無(wú)限集。證明：設(shè)n∈N，n1,令是從Nn到N的映射，Nn={0,1,,n–1}，下證不是雙射。令k=1+max{(0),(1),,(n–1)},于是k∈N，但對(duì)任意x∈Nn,均有(x)≠k,因此，不是滿射，更不是雙射。由定義4.1.2知，N為無(wú)限集。啊哈！這下我們知道有無(wú)限多個(gè)自然數(shù)了！2023/7/22離散數(shù)學(xué)5抽屜原理（鴿巢原理）

我們知道，若A，B均為有限集，且A與B之間存在雙射，則A和B的元素個(gè)數(shù)相等，即A～B。但是：定理4.1.2

任何有限集均不能和其真子集等勢(shì)。此定理也稱為抽屜原則：若將n+1個(gè)物體放入n個(gè)抽屜中，則至少有一個(gè)抽屜中放了兩個(gè)或兩個(gè)以上的物體。抽屜原則對(duì)無(wú)限集并不總是成立，即無(wú)限集能夠與其真子集等勢(shì)。這是無(wú)限集合的一個(gè)非常重要的性質(zhì)。我們已經(jīng)看到自然數(shù)集等勢(shì)于它的真子集——偶數(shù)集合。下面我們?cè)倏磶讉€(gè)例子。2023/7/22離散數(shù)學(xué)6正實(shí)數(shù)和全體實(shí)數(shù)一樣多例2：令R和R+分別為實(shí)數(shù)集合和正實(shí)數(shù)集合，即R+={x∈R|x>0}，顯然，R+R，即R+是R的真子集。但是R~R+證明：定義映射f如下：

f(x)=ex,x∈R

于是，對(duì)任意的x∈R，存在唯一的y∈R+,使

y=ex=f(x)；另一方面，對(duì)任意的y∈R+,存在唯一的

x=lny∈R,使f(x)=ex=elny=y,

這說(shuō)明f是R到R+的一個(gè)雙射。因此，R~R+。

2023/7/22離散數(shù)學(xué)7例3：A=[0,1）,B=[0,1],A,BR.顯然AB.構(gòu)造一A到B的雙射,說(shuō)明A～B.解:令A(yù)1={0,1/2,1/3,…,1/n,…}.作f:AB為:

任取x1,x2∈A,x1≠x2,顯然,f(x1)≠f(x2),且對(duì)任意y∈B:⑴若y=0,則取x=0,有f(0)=0⑵若y=1,則取x=1/2∈A1,于是f(1/2)=1/(2-1)=y⑶若y=1/n,取x=1/(n+1)∈A1,故f(1/(n+1))=1/n=y⑷若y∈B－A1,則取x=y,于是f(x)=x=y

綜上所述f是A到B的雙射,于是A～B.

f(0)=0f(1/n)=1/(n-1)(n>1,1/n∈A1,n∈N)f(x)=x(x∈[0,1)－A1)2023/7/22離散數(shù)學(xué)8§4.2

集合的基數(shù)幾個(gè)記號(hào)：同有限集合中元素的個(gè)數(shù)的記法一樣，集合A的基數(shù)用|A|表示。每個(gè)有限集合都恰與某個(gè)集合Nn={0,1,,n–1}等勢(shì)，其中n0,N0=。如果A~Nn,則A中有n個(gè)元素，即|A|=n;若A為無(wú)限集，則用一個(gè)特殊的符號(hào)i(讀作阿列夫i，i是一個(gè)正整數(shù))來(lái)表示它的基數(shù)。例如，對(duì)于自然數(shù)集合N，令|N|=0(讀作“阿列夫零”)。2023/7/22離散數(shù)學(xué)9如何比較集合的大小(1)若A~B,則稱A的基數(shù)與B的基數(shù)相等,記為|A|=|B|，否則記為|A|≠|(zhì)B|。(2)若存在A到B的單射，則稱A的基數(shù)小于或等于B的基數(shù)，記為|A||B|；或稱B的基數(shù)大于或等于A的基數(shù)，記為|B||A|。(3)若|A||B|，且|A|≠|(zhì)B|，則稱A的基數(shù)小于B的基數(shù)，記為|A|<|B|?；蛘叻QB的基數(shù)大于A的基數(shù)，記為|B|>|A|。

根據(jù)集合的基數(shù)來(lái)比較它們的大小。定義4.2.1

令A(yù)、B為兩個(gè)集合，

由定義，|A|=|B|可形象地理解為A中的元素與B中的元素一樣多。2023/7/22離散數(shù)學(xué)10集合大小是可比的

定理4.2.1

設(shè)A和B為兩個(gè)集合，總有|A||B|或者|B||A|。即任意兩個(gè)集合總可比較大小。

像實(shí)數(shù)一樣，任何兩個(gè)基數(shù)都可以比較大小，所以有2023/7/22離散數(shù)學(xué)11基數(shù)之間的相等關(guān)系是等價(jià)關(guān)系定理4.2.2基數(shù)之間的相等關(guān)系“=”是一個(gè)等價(jià)關(guān)系,即對(duì)任何集合A,B和C,有:(1)|A|=|A|;(2)若|A|=|B|,則|B|=|A|;(3)若|A|=|B|且|B|=|C|,則|A|=|C|.2023/7/22離散數(shù)學(xué)12基數(shù)間的≤是偏序關(guān)系定理4.2.3

基數(shù)之間的小于或等于關(guān)系“”是一個(gè)偏序關(guān)系,即對(duì)任何集合A,B和C,有:(1)|A||A|;(2)若|A||B|且|B||A|,則|A|=|B|;(3)若|A||B|且|B||C|,則|A||C|.2023/7/22離散數(shù)學(xué)13幾個(gè)關(guān)于基數(shù)的問(wèn)題我們知道自然數(shù)有無(wú)限多個(gè)。那么自然數(shù)集合是不是就是最大集合的呢？如果自然數(shù)集合不是最大的，那么比它更大的集合是什么樣的呢？是不是存在最大的基數(shù)呢？不！不存在最大的集合。山外有山，天外有天。我們的口號(hào)是：只有更大，沒(méi)有最大！2023/7/22離散數(shù)學(xué)14山外青山樓外樓定理4.2.4

對(duì)任意集合A,均有|A|<|(A)|,其中(A)為A的冪集。證明：令f:A(A)。f(a)={a}，a∈A。顯然，f是單射,于是|A||(A)|.

顯然，象集{{a}|a∈A}是(A)的真子集，所以，f不是滿射，從而不是雙射。于是我們有|A|＜|(A)|?！痢痢铃e(cuò)！錯(cuò)！錯(cuò)！錯(cuò)誤是：雖然f不是雙射，但不能說(shuō)明A與

(A)之間不存在其它的映射是雙射。正確的作法是證明A與

(A)存在任何的雙射都是不可能的。2023/7/22離散數(shù)學(xué)15山外青山樓外樓

假設(shè)|A|=|(A)|，則存在A到(A)的雙射g.

令B={a∈A|a

g(a)}(g(a)是a所對(duì)應(yīng)的A的子集)，顯然B∈(A)。b∈A,使g(b)=B。但是

(1)若b∈B，則由B之定義有bg(b)，即bB;(2)若bB，即bg(b)，則由B之定義有b∈B。

總之有b∈B當(dāng)且僅當(dāng)bB，矛盾。故|A|≠|(zhì)(A)|。綜合以上，定理得證。定理4.2.4

對(duì)任意集合A,均有|A|<|(A)|,其中(A)為A的冪集。證明：令f

：A(A)。f(a)={a}，a∈A。顯然，f是單射，于是|A||(A)|。

討論B的存在性：∵雙射g：A(A)，∴a∈A，g(a)∈(A)即：g(a)是A的子集。又：作集合D=A－A’，A’A，顯然，DA，即D∈(A)。令：a∈A’，g(a)=D，于是，aD，即ag(a)，但a∈A’A。2023/7/22離散數(shù)學(xué)16無(wú)限集也分大小，且無(wú)最大者

定理4.2.4說(shuō)明：對(duì)任意無(wú)限集，它的冪集就比它大。因此對(duì)任意無(wú)限集都存在更大的集合。我們記自然數(shù)集合N的冪集的基數(shù)為1，也就是|(N)|=1，由定理4.2.4知，0<

1。可以證明

|R|=|(N)|,其中R為實(shí)數(shù)集，于是，|N

|<|R|。實(shí)際上N是最小的無(wú)限集。依次可以推得實(shí)數(shù)集合的冪集的基數(shù)為2，…2023/7/22離散數(shù)學(xué)17§4.3可數(shù)集與不可數(shù)集定義4.3.1：設(shè)A是一個(gè)集合，若A與N等勢(shì)，則稱A為可數(shù)無(wú)限集；若A是有限集，則稱A為可數(shù)集。有時(shí)也將可數(shù)無(wú)限集簡(jiǎn)稱為可數(shù)集。（遇到討論可數(shù)集的問(wèn)題時(shí)要注意區(qū)分無(wú)限和有限兩種情況。）不是可數(shù)集的集合就稱為不可數(shù)集。2023/7/22離散數(shù)學(xué)18整數(shù)集是可數(shù)集例1：整數(shù)集Z是可數(shù)集。證明：可定義N到Z的映射如下：

(n)=n/2(n為偶數(shù)）(n)=(1-n)/2(n為奇數(shù)）不難驗(yàn)證為雙射,故N~Z,則Z是可數(shù)集。說(shuō)明：映射將10，偶數(shù)正整數(shù)，

奇數(shù)（除1外）負(fù)整數(shù)。2023/7/22離散數(shù)學(xué)19定理4.3.1A是可數(shù)無(wú)限集當(dāng)且僅當(dāng)A的所有元素可以如下編號(hào)排出：

a1,a2,a3,,an,此定理告訴我們，任何集合只要它的元素可以排序，就是可數(shù)的。如何判別一集合是可數(shù)的2023/7/22離散數(shù)學(xué)20可數(shù)集的子集仍是可數(shù)的定理4.3.2可數(shù)集的子集仍是可數(shù)集。證明：設(shè)A是可數(shù)集，若A是有限集，則它的子集仍是有限集，當(dāng)然也是可數(shù)集。若A是無(wú)限集，則由定理4.3.1知，A的元素可排列成：

a1,a2,a3,,an,(3.3)

顯然，A的無(wú)限子集可如下得到：從左向右看式(3.3)，可以依據(jù)子集中元素出現(xiàn)的次序?qū)⒃撟蛹脑嘏帕袨椋?/p>

ai1,ai2,ai3,,ain,

由定理4.3.1知，該子集是可數(shù)集。2023/7/22離散數(shù)學(xué)21有理數(shù)集Q是可數(shù)集。例2：有理數(shù)集是可數(shù)集。證明：已知任何非零有理數(shù)均可表示成確定的既約分?jǐn)?shù)，故把全體有理數(shù)按如下方式排列：

(1)0排在最前面；

(2)對(duì)正分?jǐn)?shù)，按它的分子與分母的和數(shù)由小到大排列，若和數(shù)相等，則分子小的排前面；

(3)對(duì)負(fù)分?jǐn)?shù)，把它緊排在相應(yīng)的正分?jǐn)?shù)后面。顯然，任意有理數(shù)總會(huì)排入此序列中。由定理4.3.1知，Q是可數(shù)集。這種排序的方法稱為字典排序法。2023/7/22離散數(shù)學(xué)22三角形方法有理數(shù)還可以按下表排序：顯然用此方法可將所有的有理數(shù)排序。分子分母

123456……1234...①③⑥⑩②⑤⑨④⑧⑦此方法稱為三角形方法，是很有用的方法。2023/7/22離散數(shù)學(xué)23符號(hào)串的集合是可數(shù)的令∑為一字母表，∑上的符號(hào)串為∑+：

∞∑+=∑1+∑2+∑3+∑4+…=∪∑ii=1這里∑i為長(zhǎng)度為i的符號(hào)串的集合。

∑+為可數(shù)集。

事實(shí)上，若|∑|=k，則每一個(gè)符號(hào)串就是一個(gè)k進(jìn)制的數(shù)，顯然它們是可以按序排列起來(lái)。所以∑+為可數(shù)集。

2023/7/22離散數(shù)學(xué)24不是所有的集合都能排序如果一個(gè)集合的元素可以排序，那么我們就可以一個(gè)一個(gè)地去數(shù)。是不是所有的集合的元素都能排序呢？不！不是所有的集合都能排序。比如[0，1]中實(shí)數(shù)的集合。讓我們來(lái)設(shè)想一下將它的元素排一個(gè)序：

0理所當(dāng)然排在第一位。但是0之后應(yīng)該排哪個(gè)呢？0.1？不！0.01？不！0.001？不！…..？你會(huì)發(fā)現(xiàn)第二個(gè)就不知道排哪個(gè)好了。這樣看來(lái)實(shí)數(shù)集合是沒(méi)法去數(shù)了！?2023/7/22離散數(shù)學(xué)25實(shí)數(shù)集是不可數(shù)的定理4.3.3

實(shí)數(shù)集是不可數(shù)的。證明：取R的子集(0,1)={x∈R|0<x<1},由定理4.3.2知，只需證明(0,1)是不可數(shù)集即可。

若(0,1)可數(shù)，則可將(0,1)中的數(shù)排成序列：

1：0.a11a12

a13···2：0.a21a22a23···3：0.a31a32a33·········

考慮數(shù)r=0.r1r2···

rk···，其中當(dāng)akk≠1則rk=1;當(dāng)akk=1則rk=2，k=1,2,···。這樣就保證了r不等于序列中任何數(shù)，因?yàn)閷?duì)任意k，r的第k位rk與序列中第k號(hào)數(shù)的第k位akk不相等。

因?yàn)閞不在序列中，所以，(0,1)是不可數(shù)集。2023/7/22離散數(shù)學(xué)26對(duì)角線方法定理4.3.3中所使用的方法稱為對(duì)角線方法。a11a22a33r1r2r3123……對(duì)角線方法是一種非常有用的方法。2023/7/22離散數(shù)學(xué)27連續(xù)統(tǒng)問(wèn)題已知N是可數(shù)集，而|N|<|R|.能否找到一個(gè)實(shí)數(shù)集R的子集A，使得：

NAR,但又不存在A到R的雙射？這個(gè)問(wèn)題稱為“連續(xù)統(tǒng)問(wèn)題”?，F(xiàn)已證明：在現(xiàn)有公理系統(tǒng)中，證明它成立與否都不可能。2023/7/22離散數(shù)學(xué)28新春曉

信息時(shí)代到，處處有電腦。

夜來(lái)打字聲，程序知多少？

答曰：

詩(shī)中的問(wèn)題是計(jì)算機(jī)上所有程序有多少？為何如此？有詩(shī)為證：計(jì)算機(jī)，靠程序，它的本事知底細(xì)。程序都是符號(hào)串，理應(yīng)是個(gè)可數(shù)集。程序時(shí)時(shí)新，落花處處飄。它們同為0，數(shù)數(shù)便知道。2023/7/22離散數(shù)學(xué)29集合論總結(jié)集合；關(guān)系；映射；可數(shù)集與不可數(shù)集。集合論的主要內(nèi)容有：2023/7/22離散數(shù)學(xué)30集合基本概念：集合、子集、冪集。集合之間的關(guān)系：(真)含于(/)，相等(＝)。集合的基本運(yùn)算：

并(∪)、交(∩)、差(－)和對(duì)稱差()。笛卡爾直積：n個(gè)集合的笛卡爾直積是它們的n元有序組的集合。它仍然是個(gè)集合。集合的表示：列舉法和描述法。2023/7/22離散數(shù)學(xué)31關(guān)系關(guān)系的概念：A到B的二元關(guān)系R是笛卡爾直積A×B的子集。關(guān)系仍然是集合。關(guān)系的表示：仍然可以采用集合的表示方法。若A、B是有限集合，或者說(shuō)R是有限集上的關(guān)系，則R的表示還可以采用：關(guān)系矩陣和關(guān)系圖。2023/7/22離散數(shù)學(xué)32關(guān)系的性質(zhì)自反性：x

A

xRx。

反自反性：x

A

(xRx)。對(duì)稱性：x

，yA，若xRy

yRx。反對(duì)稱性：x

，yA，若xRy且yRxx=y。傳遞性：x

，y，zA，若xRy且yRzxRz。令R是定義在集合A上的關(guān)系。2023/7/22離散數(shù)學(xué)33關(guān)系的運(yùn)算關(guān)系是集合，可具有集合的各種運(yùn)算。復(fù)合運(yùn)算：R·S={x，z|yB：xRy且ySz}，其中，R，S分別為A到B和B到C的關(guān)系。逆關(guān)系：R-1={y，x|x，yR}。注意復(fù)合運(yùn)算的逆：(R·S)–1=S-1·R-1。在一個(gè)集合A上的關(guān)系的冪運(yùn)算：

R0={x，x|xA},Rk=Rk-1·R

。2023/7/22離散數(shù)學(xué)34關(guān)系的閉包某關(guān)系的具有某種性質(zhì)的閉包是：包含該關(guān)系的最小的有此性質(zhì)的關(guān)系。依據(jù)關(guān)系的性質(zhì)有：r(R)、s(R)和t(R)，即自反閉包、對(duì)稱閉包和傳遞閉包。r(R)=R∪R0。s(R)=R∪R-1。

∞t(R)=∪Ri。

i=12023/7/22離散數(shù)學(xué)35用關(guān)