離散數(shù)學——有限集及無限集(課件)

1、第四章 有限集與無限集有限集與無限集基本概念有限集與無限集基本概念1有限集有限集2無限集的性質(zhì)無限集的性質(zhì)34.1 有限集與無限集基本概念問題：問題：1,2,3,與與2,4,6,哪個集合的元素更多？哪個集合的元素更多？p因為因為1,2,3, 2,4,6,，所以，所以1,2,3,里的個里的個數(shù)數(shù)多于多于2,4,6,的個數(shù)。的個數(shù)。p因為兩個集合可用函數(shù)因為兩個集合可用函數(shù)f(n)=2n表示，而表示，而f(n)=2n是是一一對應函數(shù)，所以一一對應函數(shù)，所以1,2,3,和和2,4,6,兩個集合兩個集合的個數(shù)的個數(shù)一樣多一樣多。結(jié)論：結(jié)論：無限集合無限集合無法用確切的個數(shù)來描述無法用確切的個數(shù)來描述，

2、有限，有限集合的一些特征也集合的一些特征也不能任意推廣不能任意推廣到無限集合中去。到無限集合中去。4.1 有限集與無限集基本概念定義定義4.1 一個集合一個集合S與集合與集合Nn=0,1,2(n-1)如果如果存在一存在一一一 對應函數(shù)對應函數(shù) f: NnS，則稱，則稱S 是是有限的有限的，并稱其有，并稱其有 基數(shù)基數(shù)n;如果如果 S不是有限的則稱其為不是有限的則稱其為無限的無限的。定義定義4.2 如果存在如果存在一一對應函數(shù)一一對應函數(shù) f: S S，使得，使得f(S) S，即，即f(S)是是S 的真子集，則的真子集，則S是是無限的無限的，否則，否則 S是是 有有 限限的的。說明：說明：要證明

3、一個集合是無限集，只需證明集合和它要證明一個集合是無限集，只需證明集合和它的它的的它的真真子集間子集間存在一一對應關(guān)系存在一一對應關(guān)系。如：。如：2n是是n的真子的真子集。集。4.1 有限集與無限集基本概念例例4.1 一個有一個有n個不同元素所組成的集合，它就是基個不同元素所組成的集合，它就是基數(shù)為數(shù)為n的有限集。的有限集。例例4.2 自然數(shù)集自然數(shù)集N是無限集。是無限集。例例4.3 實數(shù)集實數(shù)集R是無限集。是無限集。4.1 有限集與無限集基本概念自然數(shù)自然數(shù)N是無限的。是無限的。 分析：分析：x x N，找到一一對應的函數(shù)，找到一一對應的函數(shù)f(x) ， 且且y|y=f(x), x N N證

4、明：設函數(shù)證明：設函數(shù)f：N N 定義為定義為f(x)=2x，顯然，顯然f是是一對一的，而且有一對一的，而且有f(N) N ，所以，所以N是無限的。是無限的。4.1 有限集與無限集基本概念實數(shù)集實數(shù)集R是無限的。是無限的。 分析：分析：x x R，找到一一對應的函數(shù)，找到一一對應的函數(shù)f(x) ， 且且y|y=f(x), x R R1 x x 0f ( x ) =x x m 與與MM矛盾，推論得證。矛盾，推論得證。4.3 無限集的性質(zhì)n無限集定義無限集定義定義定義4.5 一個集合若一個集合若存在與其存在與其等勢等勢的的真真子集子集稱為無稱為無限集，限集， 否則稱為有限集。否則稱為有限集。4.3

5、 無限集的性質(zhì)n可列集的定義可列集的定義定義定義4.6 凡與凡與自然數(shù)集自然數(shù)集 N等勢等勢的集合叫可列集。的集合叫可列集。 即：能與自然數(shù)即：能與自然數(shù) N建立一一對應關(guān)系的集合建立一一對應關(guān)系的集合例：下列集合都是可數(shù)集合：例：下列集合都是可數(shù)集合： 1)Ox|x N，x是奇數(shù)是奇數(shù); 2)E x|x N，x是偶數(shù)是偶數(shù); 3)Px|x N，x是素數(shù)是素數(shù);4.3 無限集的性質(zhì)一無限集必包含一可列集。一無限集必包含一可列集。分析：分析：若無限集是可列集，定理顯然成立。若無限集是可列集，定理顯然成立。若無限集不是可列集，需要若無限集不是可列集，需要構(gòu)造構(gòu)造其無限子集，使其無限子集，使無無限子

6、集與限子集與N等勢等勢，即得無限子集為可列集。，即得無限子集為可列集。4.3 無限集的性質(zhì)n可列集的重要性質(zhì)可列集的重要性質(zhì)證明：設證明：設A是一無限集是一無限集1、構(gòu)造無限集、構(gòu)造無限集A的一子集的一子集A 。先從先從A中任取一個元素中任取一個元素a0，剩余部分為，剩余部分為A-a0再從再從A-a0中任取一元素中任取一元素a1，剩余部分為，剩余部分為A-a0，a1繼續(xù)下去，取出繼續(xù)下去，取出a2，a3，得到一個，得到一個無限集合無限集合AA =a0，a1 ，顯然，顯然A A 2、證明、證明A NN：0 1 2 3 i A : a0 a1 a2 a3 ai 4.3 無限集的性質(zhì)A為可列集，為可

7、列集，因為因為A A所以定理成立所以定理成立可列集的無限子集仍為一可列集。可列集的無限子集仍為一可列集。分析：分析：構(gòu)造可列集的無限子集。構(gòu)造可列集的無限子集。證明其證明其無限子集與無限子集與N等勢等勢，即得無限子集為可列集。，即得無限子集為可列集。4.3 無限集的性質(zhì)證明：設證明：設A是一可列集，是一可列集，A= a0，a1， a2， a3，1、構(gòu)造可列集、構(gòu)造可列集A的一子集的一子集A 。先從先從A中任取一個元素中任取一個元素am0，剩余部分為，剩余部分為A-am0再從再從A-am0中依次順取一元素中依次順取一元素am1，剩余部分，剩余部分A-am0，am1依次順取下去，取出依次順取下去，

8、取出am2，am3，得到一個，得到一個無限集合無限集合AA =am0，am1 ，顯然，顯然A A 2、證明、證明A NN：0 1 2 3 A : am0 am1 am2 am3 綜合得證可列集的無限子集仍為一可列集。綜合得證可列集的無限子集仍為一可列集。4.3 無限集的性質(zhì)可列集可列集是是無無限集中限集中的的最小最小元素元素分析：分析：在整數(shù)集在整數(shù)集I和自然數(shù)集和自然數(shù)集N之間構(gòu)造一一對應關(guān)系。之間構(gòu)造一一對應關(guān)系。證明：整數(shù)集證明：整數(shù)集I和自然數(shù)集和自然數(shù)集N間的一一對應關(guān)系間的一一對應關(guān)系N：0 1 2 3 4 5 6 2n-1 2n I: 0 1 -1 2 -2 3 -3 n -n

9、4.3 無限集的性質(zhì)整數(shù)集整數(shù)集I是可列集。是可列集。4.3 無限集的性質(zhì)有理數(shù)集有理數(shù)集Q是可列集。是可列集。分析：分析：有理數(shù)的形式：有理數(shù)的形式： ，找出有理數(shù)的一定的，找出有理數(shù)的一定的排列規(guī)律，即得到一一對應的關(guān)系。排列規(guī)律，即得到一一對應的關(guān)系。nm 4.3 無限集的性質(zhì)證明：一切有理數(shù)均呈證明：一切有理數(shù)均呈 狀，現(xiàn)將所有狀，現(xiàn)將所有 按下列次序按下列次序 排列排列 正分數(shù)按其分子分母之和的大小順序排列：從小到正分數(shù)按其分子分母之和的大小順序排列：從小到大大 正分數(shù)的分子分母之和相同者按分子大小順序排列：從大正分數(shù)的分子分母之和相同者按分子大小順序排列：從大到小到小 與正分數(shù)具有

10、相同形式的負分數(shù)排于正分數(shù)之后與正分數(shù)具有相同形式的負分數(shù)排于正分數(shù)之后按上述規(guī)律可得一序列，即與按上述規(guī)律可得一序列，即與N的一一對應關(guān)系：的一一對應關(guān)系：N：0 1 2 3 4 5 6 7 8 9 10 Q:nm nm .1122113322110 - - - - - -111122112233-2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3

11、/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414PLAY證明方法二：有理數(shù)和自然數(shù)的對應關(guān)系4.3 無限集的性質(zhì)n 集合的大小問題集合的大小問題n 集合的基數(shù)集合的基數(shù)集合的基數(shù)可用集合的基數(shù)可用|A| 來表示。來表示。對有限集對有限集A，|A|=集合集合A中元素的個數(shù)中元素的個數(shù)；對無限集對無限集A， |A|不能用有限集的方法來定義，規(guī)定不能用有限集的方法來定義，規(guī)定自然數(shù)集自然數(shù)集 N的基數(shù)為的基數(shù)為?0(阿列夫零阿列夫零)，即，即|N|= ?

12、04.3 無限集的性質(zhì)(2)集合大小的比較集合大小的比較有限集大小的比較，用有限集大小的比較，用“相等相等”、“不相等不相等” 無限集大小的比較，用無限集大小的比較，用“等勢等勢”、“不等勢不等勢”等勢即為基數(shù)相同，由此立即可知：等勢即為基數(shù)相同，由此立即可知：所有可列集的基所有可列集的基數(shù)均為數(shù)均為?0。(3)可列集是最小的無限集可列集是最小的無限集 沒有比基數(shù)沒有比基數(shù)?0更小的無限集，但存在比基數(shù)更小的無限集，但存在比基數(shù)?0更大的更大的無限集。如無限集。如實數(shù)集實數(shù)集。4.3 無限集的性質(zhì)分析：分析：1、證、證(0，1)內(nèi)的實數(shù)不可列，利用內(nèi)的實數(shù)不可列，利用反正法反正法，即假設其是，

13、即假設其是可列的，當將其列出時總能找到一個元素不屬于列出的集可列的，當將其列出時總能找到一個元素不屬于列出的集合。合。2、證、證(0，1)內(nèi)的實數(shù)與內(nèi)的實數(shù)與R等勢，即等勢，即R不可列。不可列。實數(shù)集是不可列的。實數(shù)集是不可列的。證明：證明：1、定義在、定義在(0，1)內(nèi)的實數(shù)集內(nèi)的實數(shù)集S=x|x R且且0 x1 x S，可表示為，可表示為x=0.y1y2y3(yi 0,1,9) 假設假設S是可列的，則它的元素可依次排列：是可列的，則它的元素可依次排列：x0，x1，x2，且我們有且我們有x0=0.a00a01a02a0nx1=0.a10a11a12a1nxm=0.am0am1am2amn只需

14、證還能找到一個元素只需證還能找到一個元素r S，但，但r不在不在x0，x1，x2，中中4.3 無限集的性質(zhì)構(gòu)造一構(gòu)造一S內(nèi)的實數(shù)內(nèi)的實數(shù)r=0.b0b1b2bn其中當其中當aii1時，時，bi=1 當當aii=1時，時，bi=2因為因為b0a00，所以，所以r x0因為因為b1a11，所以，所以r x1 因為總有一位不同，所以因為總有一位不同，所以r xi ，這與，這與r S矛盾，矛盾，即即(0，1)是不可列的。是不可列的。2、證明、證明SR，即建立一一對應關(guān)系。設，即建立一一對應關(guān)系。設R中的元素為中的元素為y，S中的元中的元素為素為x，因為，因為S不可列，所以只能建立關(guān)系式：不可列，所以只

15、能建立關(guān)系式：4.3 無限集的性質(zhì)4.3 無限集的性質(zhì)y1111- 1, 0 x- 1, 0 x2x22x21111+ 1, x1+ 1, x12(x - 1)22(x - 1)2當當x (0，1/2，根據(jù)上式有，根據(jù)上式有y (0，+)當當x 1/2 ，1)，根據(jù)上式有，根據(jù)上式有y ( ，0)綜上所述綜上所述x (0，1)，有，有y ( ， +)根據(jù)上式根據(jù)上式還需證還需證y ( ， +)，有，有x (0，1)，才能，才能證得上式試證得上式試R和和S之間滿足一一對應關(guān)系。轉(zhuǎn)變上式，之間滿足一一對應關(guān)系。轉(zhuǎn)變上式，得得4.3 無限集的性質(zhì)x01 1, y0, y02(y+ 1)2(y+ 1)

16、1 1+ 1, y+ 1, y2(y- 1)2(y- 1)當當y (0，+) ，根據(jù)上式有，根據(jù)上式有x (0，1/2當當y ( ，0)，根據(jù)上式有，根據(jù)上式有x 1/2 ，1)綜上所述綜上所述y ( ， +)，有，有x (0，1)從而建立了一一對應關(guān)系，由此整個定理得證。從而建立了一一對應關(guān)系，由此整個定理得證。4.3 無限集的性質(zhì)n 結(jié)論結(jié)論(1)實數(shù)集比可列集要實數(shù)集比可列集要“大大”，它的基數(shù)不是阿列夫，它的基數(shù)不是阿列夫零，我們零，我們用用?(阿列夫數(shù)阿列夫數(shù))表示表示-稱為連續(xù)統(tǒng)的勢；稱為連續(xù)統(tǒng)的勢；(2)在無限集中除了阿列夫零和阿列夫數(shù)以外在無限集中除了阿列夫零和阿列夫數(shù)以外還有

17、更還有更大基數(shù)的集合大基數(shù)的集合；(3)無限集也有大小，無限集也有大小，可列集是最小的無限集可列集是最小的無限集，其次，其次是是實數(shù)集實數(shù)集；(4)對于任意一個無限集，總存在一個基數(shù)大于這個對于任意一個無限集，總存在一個基數(shù)大于這個集合的集合，即集合的集合，即無限集的大小也是無限的無限集的大小也是無限的。小結(jié)p掌握有限集和無限集的概念。掌握有限集和無限集的概念。p掌握有限集的計數(shù)方法。掌握有限集的計數(shù)方法。p熟練掌握無限集的性質(zhì)，無限集計數(shù)方法，根據(jù)勢熟練掌握無限集的性質(zhì)，無限集計數(shù)方法，根據(jù)勢的定義對無限集進行分類。能夠證明一個集合是無限的定義對無限集進行分類。能夠證明一個集合是無限集，可列

18、集等。集，可列集等。習題1求下列集合的基數(shù)。求下列集合的基數(shù)。(1)A=0,2,4,6,50; (2)B=x|x R并且并且x2+1=0；(3)S=0,3,6,9,; (4)T=10,11,12,13,(1) A的基數(shù)的基數(shù)|A|=26(2) B=x|x R并且并且x2+1=0= ，故，故|B|=0；(3) S=0,3,6,9,=3x|x N，S與與N能夠建立一一對應能夠建立一一對應關(guān)系，關(guān)系，SN，|S|= ?0； (4) T=10,11,12,13,=x+10|x N ，T與與N能夠建立一能夠建立一一對應關(guān)系，一對應關(guān)系，TN，|T|= ?0； 習題2.求求1到到1000之間（包含之間（包含1和和1000在內(nèi)）既不能被在內(nèi)）既不能被5和和6整整除，也不能被除，也不能被8整除的數(shù)有多少個？整除的數(shù)有多少個？解：設解：設1到到1000的整數(shù)構(gòu)成全集的整