離散數(shù)學(xué)第17講課件

2023/12/5計(jì)算機(jī)學(xué)院1主要內(nèi)容集合的基數(shù)有限集、無限集可數(shù)集和不可數(shù)集2023/12/5計(jì)算機(jī)學(xué)院2§6.4集合的基數(shù)、可數(shù)集和不可數(shù)集

先看幾個(gè)問題：有限集同無限集的區(qū)別是什么？兩個(gè)無限集之間可不可以比較大?。孔匀粩?shù)集中元素的個(gè)數(shù)同有理數(shù)集中元素的個(gè)數(shù)那一個(gè)多？有理數(shù)集中元素的個(gè)數(shù)同無理數(shù)集中元素的個(gè)數(shù)那一個(gè)多？無理數(shù)集中元素的個(gè)數(shù)同實(shí)數(shù)集中元素的個(gè)數(shù)那一個(gè)多？有沒有最大的集合，它包含了所有的集合？

2023/12/5計(jì)算機(jī)學(xué)院3集合的基數(shù)

集合的基數(shù)就是集合中元素的個(gè)數(shù),是集合容量的度量。一般是在兩個(gè)集合的元素間建立一一對應(yīng)關(guān)系,其中一個(gè)作為尺度。比如我們在計(jì)算一群人和一堆物品時(shí)，就是將人和物品同數(shù)字1、2、3等一一對應(yīng)起來，其本質(zhì)就是在兩個(gè)集合的元素之間建立了一一對應(yīng)關(guān)系（即雙射）。

定義6.7

設(shè)X，Y是兩個(gè)集合，若在X，Y之間存在1-1對應(yīng)的關(guān)系（在集合X和Y之間建立雙射），則稱集合X與Y是對等的或等勢的，記為：X

Y

集合X的基數(shù)一般記為card(X),如果A是有限集合,A的基數(shù)通常記為︱A︱（它是A中元素的個(gè)數(shù)）。2023/12/5計(jì)算機(jī)學(xué)院4定理6.4

等勢是集合族上的等價(jià)關(guān)系。即對任意的集合A、B、C，A

A

A

BB

A

A

B、B

CA

C

而等價(jià)關(guān)系決定等價(jià)類，因此，所有等勢的集合構(gòu)成一個(gè)等價(jià)類。

一般地：

若X＝Y(jié)，則X

Y。反之不然。2023/12/5計(jì)算機(jī)學(xué)院5

記Nm={x|x是正整數(shù)，且x≤m}

問題：對同一個(gè)集合X，是否會出現(xiàn)X

Nm

，同時(shí)又出現(xiàn)X

Nn，而m≠n？定理6.5

如果正整數(shù)m＜n，則不存在從Nn到Nm的單射。定義6.8

設(shè)X，Y是兩個(gè)集合，若存在從X到Y(jié)的單射，則card(X)≤card(Y)；如果不存在從X到Y(jié)的雙射，則card(X)＜card(Y)。

下面，我們對集合按照基數(shù)進(jìn)行分類。2023/12/5計(jì)算機(jī)學(xué)院6自然數(shù)集合N的定義

N，若nN，則n′:＝n∪{n}N。也即：0:＝，1:＝∪{}＝{}={0}，2:＝{}∪{{}}＝{,{}}={0,1}....n:＝{0,1,2,3,....n-1}....N＝{0,1,2,3,....,n,....}

二十世紀(jì)初，集合成為數(shù)學(xué)的基本概念之后，由馮?諾依曼（VonNeumann，J.）用集合的方式來定義自然數(shù)取得了成功。2023/12/5計(jì)算機(jī)學(xué)院7定義6.9

如果X是空集,或者自然數(shù)m，

X

Nm

,則稱X為有限集,否則稱X為無限集。定理6.6

自然數(shù)集N是無限集。定理6.7

非空集合X是無限集當(dāng)且僅當(dāng)存在從N到X的單射。將自然數(shù)集N的基數(shù)記為（讀為“阿列夫0”）。2023/12/5計(jì)算機(jī)學(xué)院8可數(shù)集例6.8下列集合都是可數(shù)集合：定義6.10凡是與自然數(shù)集合等勢的集合，統(tǒng)稱為可數(shù)集合或可列集合。O+＝{x|xN，x是奇數(shù)}E+＝{x|xN-{0}，x是偶數(shù)}P＝{x|xN，x是素?cái)?shù)}整數(shù)集合Z2023/12/5計(jì)算機(jī)學(xué)院9解：（1）在O+與N之間建立1-1對應(yīng)的關(guān)系f：N→O+

如下：f：N→O+f（n)=2n+1N０１２３４...ｎ...ｆ↓↓↓↓↓...

↓...

O+１３５７９...2n+1...所以，O+也是可數(shù)集合。2023/12/5計(jì)算機(jī)學(xué)院10（2）在N與E+之間建立1-1對應(yīng)的關(guān)系f：N→E+

如下：f：N→E+f（n)=2n+2N０１２３４...ｎ...ｆ↓↓↓↓↓...

↓...

E+２４６８10...2n+2...所以，E+也是可數(shù)集合。2023/12/5計(jì)算機(jī)學(xué)院11（3）在P與N之間建立1-1對應(yīng)的關(guān)系f：N→P如下：N０１２３４...ｆ↓↓↓↓↓...P２３５７11...所以，P也是可數(shù)集合。枚舉法2023/12/5計(jì)算機(jī)學(xué)院12（4）在N與Z之間建立1-1對應(yīng)的關(guān)系f：N→Z如下：f：N→ZN０１２３４...2n-12n...ｆ↓↓↓↓↓...

↓

↓...

Z０１-1２-2...n-n...所以，Z也是可數(shù)集合。2023/12/5計(jì)算機(jī)學(xué)院13可數(shù)集的性質(zhì)定理6.8每個(gè)無限集必含有子集是可數(shù)集。定理6.9可數(shù)個(gè)可數(shù)集的并集為可數(shù)集。推論6.9.1:

N×N是可數(shù)集。

證明：令A(yù)i={（i，0），（i，1），（i，2），‥}，i≥0

顯然，Ai（i≥0）是可數(shù)集

N×N=A0∪A1∪A2∪A3‥‥

由定理6.9知，N×N是可數(shù)集。2023/12/5計(jì)算機(jī)學(xué)院14定理6.10有理數(shù)是可數(shù)集。證明：由推論6.9.1知：N×N是可數(shù)集。構(gòu)造S={(m,n)

N×N|m和n互素且mn≠0}顯然，S是可數(shù)集。令g:S→Q+，

g((m,n)）=m/n，則g是雙射，所以，正有理數(shù)集是可數(shù)集。同理，可證負(fù)有理數(shù)集也是可數(shù)集。再由定理6.9知，Q=Q+∪{0}∪Q-是可數(shù)集。2023/12/5計(jì)算機(jī)學(xué)院15不可數(shù)集定理6.11

實(shí)數(shù)集合R是不可數(shù)集合。證明：1)首先證明（0，1）是不可數(shù)集。約定（0，1）中的任何數(shù)都可用無限位小數(shù)表示。例如0.32用無限位小數(shù)表示時(shí)應(yīng)為0.31999…。假設(shè)（0，1）是可數(shù)集，那么，可在（0，1）和N之間建立雙射，即（0，1）中的元素可依序列出為。

2023/12/5計(jì)算機(jī)學(xué)院16設(shè)這些元素的無限位為現(xiàn)在構(gòu)造實(shí)數(shù)，其中可見r與中的任何一個(gè)都不同。但是，r∈（0，1），這與（0，1）是可數(shù)集相2023/12/5計(jì)算機(jī)學(xué)院17矛盾，所以（0，1）不是可數(shù)集。2）要證明實(shí)數(shù)集合R是不可數(shù)集合，只需證明R與（0，1）等勢就行了。

建立映射f：R→（0，1）

f(y)=(arctany)/π+1/2

yR(∵當(dāng)x(-π/2,π/2),y=tanxR∴x=arctany(-π/2,π/2),

那么x/π+1/2(0,1),即f(y)=(arctany)/π+1/2(0,1))顯然，函數(shù)f是一個(gè)雙射，所以R

（0，1）2023/12/5計(jì)算機(jī)學(xué)院18本定理中使用的證明方法，是一種著名的對角化方法。開區(qū)間(0,1)稱為不可數(shù)集合，其基數(shù)設(shè)為

(讀作阿列夫)；凡是與區(qū)間(0,1)等勢的集合都是不可數(shù)集合。2023/12/5計(jì)算機(jī)學(xué)院19Cantor定理

設(shè)M是任意集合,S是M的冪集,那么,card(M)<card(S)(︱M︱<︱(M)︱)證明：1）當(dāng)M=

時(shí)，S={}，則card(M)=0,card(S)=1,結(jié)論成立。2）當(dāng)M≠

時(shí)，構(gòu)造f:M→S,對aM有f(a)={a},則f(M)S,∴card(M)≤card(S)下面證明等號不成立（反證法）

2023/12/5計(jì)算機(jī)學(xué)院20設(shè)

:M→S（

是雙射），構(gòu)造B={xM|x(x)},則BS?！呤请p射，∴cM(c)=B。①如果cB，由B的定義，cB，矛盾②