離散數學有限集與無限集課件§4、1有限集與無限集基本概念定義4、1一個集合S與集合Nn={0,1,2…(n-1)}如果存在一一對應函數f:Nn→S,則稱S就是有限得,并稱其有基數n;如果S不就是有限得則稱其為無限得。定義4、2如果存在一一對應函數f:S→S′,使得f(S)

S,即f(S)就是S得真子集,則S就是無限得,否則S就是有限得。說明:要證明一個集合就是無限集,只需證明集合與她得她得真子集間存在一一對應關系。如:2n就是n得真子集。§4、1有限集與無限集基本概念例4、1一個有n個不同元素所組成得集合,她就就是基數為n得有限集。例4、2自然數集N就是無限集。例4、3實數集R就是無限集。§4、1有限集與無限集基本概念定理4.1自然數N是無限的。分析:?xN,找到一一對應得函數f(x),且{y|y=f(x),?xN}N證明:設函數f:N→N′定義為f(x)=2x,顯然f就是一對一得,而且有f(N)N,所以N就是無限得。§4、1有限集與無限集基本概念定理4.2實數集R是無限的。分析:?xR,找到一一對應得函數f(x),且{y|y=f(x),?xR}R證明：設函數f：R→R′為這個函數f是一對一的，而顯然有f(R)R，所以R是無限的。01f(R)的范圍§4、2有限集定義有限集得基數定義4、3有限集S得元素個數稱為S得基數,記為|S|。例:設A={a,b,c,d},則|A|=4§4、2有限集定理4.3如果A，B是分離的有限集合，則有|A∪B|=|A|+|B|定理4.4如果A，B是任意的有限集合，則有|A∪B|=|A|+|B|-|A∩B|定理4.5對任意三個有限集合A，B，C，則有|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|§4、2有限集定理4.6設有n個有限集合S1，S2，…Sn，則有奇數項就是加,偶數項就是減。§4、2有限集例4、4假定有120個學生,其中100個學生至少要學德、法、英三種語言得一種,還假定65人學法語,45人學德語,42人學英語;20人學法語與德語,25人學法語與英語,15人學德語與英語。請問同時學三種語言得有多少人？僅學一種語言得各有多少人？解:(1)設A、B、C分別表示學法語、德語與英語得學生得集合,由題意與定理4、5有:|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

100=65+45+42-20-25-15+|A∩B∩C|所以|A∩B∩C|=8§4、2有限集(2)由文氏圖可計算僅學一種語言得各有多少人法語人數為:65-(12+8+17)=28德語人數為:45-(12+8+7)=18英語人數為:42-(17+8+7)=10

英德法12

87§4、3無限集得性質等勢得定義定義4、4集合A,B得元素之間,如果存在一一對應得關系則稱集合A,B就是等勢得,記為

A~B

注意:根據定義對有限集而言,兩個集合等勢即表示兩個集合元素個數相同;對無限集而言,兩個集合等勢即表示兩個集合元素之間存在一一對應關系;說明:要想證等勢,必須找出一一對應得關系。大家學習辛苦了，還是要堅持繼續保持安靜§4、3無限集得性質例4、5自然數集

N={0,1,2,3……}與其子集S={1,3,5……}均為無限集,且N~SN:0123…n…???????S:1357…2n+1…此例說明了無限集得一個特性:一個無限集可以同她得一個真子集等勢。定理4.7一個集合為無限集，則它必含有與其等勢的真子集。分析:條件就是有一無限集M,結論就是必存在無限集M'有M'

M且M'~M需要利用構造法,構造滿足上述條件得M'。若無限集M就是可以排列得,即M={m1,m2…,mn,…},那么只需在M去掉元素m1,即可得M'。若無限集M就是不可以排列得,可在M中按一定規律找到一可以排列得無限集M1,使得M'為M中去掉M1中一元素。§4、3無限集得性質無限集得性質證明:1、構造無限集M得一真子集M'。先從M中任取一個元素m1,剩余部分為M-{m1}—無限集再從M-{m1}中任取一元素m2,剩余部分為M-{m1,m2}…繼續下去,取出m3,m4,…,得到一個無限集合M1M1={m1,m2

,…,},令M2=M-M1(若M可列,M2為空)M=M1∪M2={m1,m2

,…,}∪M2構造集合M'M'={m2,m3

,…,}∪M2顯然M'

M§4、3無限集得性質2、證明M~M'M:{m1m2

m3m4…mi…}∪M2????????M':{m2m3m4m5…mi+1…}∪M2§4、3無限集得性質因為無限,所以總能找到對應元素推論一集合為無限集的充分必要條件是它必含有與其等勢的真子集。分析:充分性:M~M'且M?M'?M為無限集必要性:M為無限集?她必含有與其等式得真子集充分性利用反正法證,即假設M為有限集推出矛盾。必要性即為定理4、7。§4、3無限集得性質證明:設一集合M含有與其等勢得真子集M'且M為有限集,設其元素個數為n個。

M'也為有限集,設其元素個數為m個根據條件有M?M',即有n>m

與M~M'矛盾,推論得證。§4、3無限集得性質無限集定義定義4、5一個集合若存在與其等勢得真子集稱為無限集,否則稱為有限集。§4、3無限集得性質可列集得定義定義4、6凡與自然數集N等勢得集合叫可列集。即:能與自然數N建立一一對應關系得集合例:下列集合都就是可數集合:

1)O＝{x|xN,x就是奇數};2)E＝{x|xN,x就是偶數};

3)P＝{x|xN,x就是素數};§4、3無限集得性質定理4.8一無限集必包含一可列集。分析:若無限集就是可列集,定理顯然成立。若無限集不就是可列集,需要構造其無限子集,使無限子集與N等勢,即得無限子集為可列集。§4、3無限集得性質可列集得重要性質證明:設A就是一無限集1、構造無限集A得一子集A'。先從A中任取一個元素a0,剩余部分為A-{a0}再從A-{a0}中任取一元素a1,剩余部分為A-{a0,a1}…繼續下去,取出a2,a3,…,得到一個無限集合A'A'={a0,a1

,…,},顯然A

A'2、證明A'~NN:012

3…i…???????A':a0a1a2a3…ai…§4、3無限集得性質A'為可列集,因為A

A'所以定理成立定理4.9可列集的無限子集仍為一可列集。分析:構造可列集得無限子集。證明其無限子集與N等勢,即得無限子集為可列集。§4、3無限集得性質證明:設A就是一可列集,A={a0,a1,a2,a3,…}1、構造可列集A得一子集A'。先從A中任取一個元素am0,剩余部分為A-{am0}再從A-{am0}中依次順取一元素am1,剩余部分A-{am0,am1}…依次順取下去,取出am2,am3,…,得到一個無限集合A'A'={am0,am1

,…,},顯然A

A'2、證明A'~NN:012

3…?????A':am0am1am2

am3…綜合得證可列集得無限子集仍為一可列集。§4、3無限集得性質※可列集就是無限集中得最小元素分析:在整數集I與自然數集N之間構造一一對應關系。證明:整數集I與自然數集N間得一一對應關系N:0123456…2n-12n…???????????I:01-12-23-3…n-n…§4、3無限集得性質定理4.10整數集I是可列集。§4、3無限集得性質定理4.11有理數集Q是可列集。分析:有理數得形式:,找出有理數得一定得排列規律,即得到一一對應得關系。§4、3無限集得性質證明：一切有理數均呈狀，現將所有按下列次序排列正分數按其分子分母之和的大小順序排列：從小到大正分數的分子分母之和相同者按分子大小順序排列：從大到小與正分數具有相同形式的負分數排于正分數之后按上述規律可得一序列，即與N的一一對應關系：N：012345678910…????????????Q:-2/1[5]-1/1[4]-3/1[18]2/1[10]3/1[11]0/1[0]1/1[1]-2/2-1/2[3]-3/2[17]2/23/2[12]0/21/2[2]-2/3[6]-1/3[7]-3/32/3[9]3/30/31/3[8]-2/4-1/4[15]-3/4[16]2/43/4[13]0/41/4[14]……………………PLAY證明方法二:有理數與自然數得對應關系§4、3無限集得性質集合得大小問題集合得基數集合得基數可用|A|來表示。對有限集A,|A|=集合A中元素得個數;對無限集A,|A|不能用有限集得方法來定義,規定自然數集N得基數為?0(阿列夫零),即|N|=?0§4、3無限集得性質(2)集合大小得比較有限集大小得比較,用“相等”、“不相等”無限集大小得比較,用“等勢”、“不等勢”等勢即為基數相同,由此立即可知:所有可列集得基數均為?0。(3)可列集就是最小得無限集沒有比基數?0更小得無限集,但存在比基數?0更大得無限集。如實數集。§4、3無限集得性質分析:1、證(0,1)內得實數不可列,利用反正法,即假設其就是可列得,當將其列出時總能找到一個元素不屬于列出得集合。2、證(0,1)內得實數與R等勢,即R不可列。定理4.12實數集是不可列的。證明:1、定義在(0,1)內得實數集S={x|xR且0<x<1}?x

S,可表示為x=0、y1y2y3…(yi{0,1,…9})

假設S就是可列得,則她得元素可依次排列:x0,x1,x2,…且我們有x0=0、a00a01a02…a0n…x1=0、a10a11a12…a1n……xm=0、am0am1am2…amn……只需證還能找到一個元素