離散數(shù)學(xué)-有限集與無限集(課件)

1、第四章 有限集與無限集,4.1 有限集與無限集基本概念,問題：1,2,3,與2,4,6,哪個(gè)集合的元素更多？ 因?yàn)?,2,3, 2,4,6,，所以1,2,3,里的個(gè)數(shù)多于2,4,6,的個(gè)數(shù)。 因?yàn)閮蓚€(gè)集合可用函數(shù)f(n)=2n表示，而f(n)=2n是一一對(duì)應(yīng)函數(shù)，所以1,2,3,和2,4,6,兩個(gè)集合的個(gè)數(shù)一樣多。,結(jié)論：無限集合無法用確切的個(gè)數(shù)來描述，有限集合的一些特征也不能任意推廣到無限集合中去。,4.1 有限集與無限集基本概念,定義4.1 一個(gè)集合S與集合Nn=0,1,2(n-1)如果存在一一 對(duì)應(yīng)函數(shù) f: NnS，則稱S 是有限的，并稱其有 基數(shù)n;如果 S不是有限的則稱其為無限的。

2、 定義4.2 如果存在一一對(duì)應(yīng)函數(shù) f: S S，使得f(S) S，即f(S)是S 的真子集，則S是無限的，否則 S是 有 限的。,說明：要證明一個(gè)集合是無限集，只需證明集合和它的它的真子集間存在一一對(duì)應(yīng)關(guān)系。如：2n是n的真子集。,4.1 有限集與無限集基本概念,例4.1 一個(gè)有n個(gè)不同元素所組成的集合，它就是基數(shù)為n的有限集。 例4.2 自然數(shù)集N是無限集。 例4.3 實(shí)數(shù)集R是無限集。,4.1 有限集與無限集基本概念,分析：xN，找到一一對(duì)應(yīng)的函數(shù)f(x) ， 且y|y=f(x), xN N,證明：設(shè)函數(shù)f：N N 定義為f(x)=2x，顯然f是一對(duì)一的，而且有f(N) N ，所以N是無

3、限的。,4.1 有限集與無限集基本概念,分析：xR，找到一一對(duì)應(yīng)的函數(shù)f(x) ， 且y|y=f(x), xR R,證明：設(shè)函數(shù)f：RR 為 這個(gè)函數(shù)f是一對(duì)一的，而顯然有f(R) R，所以R是無限的。,4.2 有限集,定義有限集的基數(shù) 定義4.3 有限集S的元素個(gè)數(shù)稱為S的基數(shù)，記為 |S|。,例：設(shè)A=a，b，c，d，則|A|=4,4.2 有限集,4.2 有限集,奇數(shù)項(xiàng)是加，偶數(shù)項(xiàng)是減。,4.2 有限集,例4.4 假定有120個(gè)學(xué)生，其中100個(gè)學(xué)生至少要學(xué)德、法、英三種語言的一種，還假定65人學(xué)法語，45人學(xué)德語，42人學(xué)英語；20人學(xué)法語和德語，25人學(xué)法語和英語，15人學(xué)德語和英語。

4、請(qǐng)問同時(shí)學(xué)三種語言的有多少人？?jī)H學(xué)一種語言的各有多少人？ 解： （1）設(shè)A、B、C分別表示學(xué)法語、德語和英語的學(xué)生的集合，由題意和定理4.5有： |AB C |=|A|+|B|+|C|- |AB|-|AC|- |BC| +|AB C | 100= 65+45+42-20-25-15+ |AB C | 所以 |AB C |=8,4.2 有限集,（2）由文氏圖可計(jì)算僅學(xué)一種語言的各有多少人 法語人數(shù)為： 65-(12+8+17)=28 德語人數(shù)為： 45-(12+8+7)=18 英語人數(shù)為： 42-(17+8+7)=10,4.3 無限集的性質(zhì),等勢(shì)的定義 定義4.4 集合A，B的元素之間，如果存在

5、一一對(duì)應(yīng) 的關(guān)系 則稱集合A，B是等勢(shì)的，記為 AB 注意：根據(jù)定義 對(duì)有限集而言，兩個(gè)集合等勢(shì)即表示兩個(gè)集合元素個(gè)數(shù)相同； 對(duì)無限集而言，兩個(gè)集合等勢(shì)即表示兩個(gè)集合元素之間存在一一對(duì)應(yīng)關(guān)系； 說明：要想證等勢(shì)，必須找出一一對(duì)應(yīng)的關(guān)系。,4.3 無限集的性質(zhì),例4.5 自然數(shù)集 N=0,1,2,3與其子集S=1,3,5均為無限集，且NS N：0 1 2 3 n S: 1 3 5 7 2n+1 此例說明了無限集的一個(gè)特性：一個(gè)無限集可以同它的一個(gè)真子集等勢(shì) 。,分析：條件是有一無限集M， 結(jié)論是必存在無限集M有M M且MM 需要利用構(gòu)造法，構(gòu)造滿足上述條件的M 。 若無限集M是可以排列的，即M=

6、m1，m2，mn，,那么只需在M去掉元素m1，即可得M 。 若無限集M是不可以排列的，可在M中按一定規(guī)律找到一可以排列的無限集M1，使得M為M中去掉M1中一元素。,4.3 無限集的性質(zhì),無限集的性質(zhì),證明： 1、構(gòu)造無限集M的一真子集M 。 先從M中任取一個(gè)元素m1，剩余部分為M-m1無限集 再從M-m1中任取一元素m2，剩余部分為M-m1，m2 繼續(xù)下去，取出m3，m4，得到一個(gè)無限集合M1 M1=m1，m2 ，令M2=M-M1(若M可列，M2為空) M=M1M2= m1，m2 ， M2 構(gòu)造集合M M =m2，m3 ， M2 顯然M M,4.3 無限集的性質(zhì),2、證明MM M ：m1 m2

7、 m3 m4 mi M2 M : m2 m3 m4 m5 mi+1 M2,4.3 無限集的性質(zhì),因?yàn)闊o限，所以總能找到對(duì)應(yīng)元素,分析：充分性：MM且MM M為無限集 必要性：M為無限集它必含有與其等式的真子集 充分性利用反正法證，即假設(shè)M為有限集推出矛盾。 必要性即為定理4.7。,4.3 無限集的性質(zhì),證明：設(shè)一集合M含有與其等勢(shì)的真子集M 且M為有限集，設(shè)其元素個(gè)數(shù)為n個(gè)。 M也為有限集，設(shè)其元素個(gè)數(shù)為m個(gè) 根據(jù)條件有M M，即有nm 與MM矛盾，推論得證。,4.3 無限集的性質(zhì),無限集定義 定義4.5 一個(gè)集合若存在與其等勢(shì)的真子集稱為無限集， 否則稱為有限集。,4.3 無限集的性質(zhì),可列

8、集的定義 定義4.6 凡與自然數(shù)集 N等勢(shì)的集合叫可列集。 即：能與自然數(shù) N建立一一對(duì)應(yīng)關(guān)系的集合 例：下列集合都是可數(shù)集合： 1)Ox|xN，x是奇數(shù); 2)E x|xN，x是偶數(shù); 3)Px|xN，x是素?cái)?shù);,4.3 無限集的性質(zhì),分析： 若無限集是可列集，定理顯然成立。 若無限集不是可列集，需要構(gòu)造其無限子集，使無限子集與N等勢(shì)，即得無限子集為可列集。,4.3 無限集的性質(zhì),可列集的重要性質(zhì),證明：設(shè)A是一無限集 1、構(gòu)造無限集A的一子集A 。 先從A中任取一個(gè)元素a0，剩余部分為A-a0 再從A-a0中任取一元素a1，剩余部分為A-a0，a1 繼續(xù)下去，取出a2，a3，得到一個(gè)無限集

9、合A A =a0，a1 ，顯然A A 2、證明A N N：0 1 2 3 i A : a0 a1 a2 a3 ai ,4.3 無限集的性質(zhì),A為可列集， 因?yàn)锳 A 所以定理成立,分析： 構(gòu)造可列集的無限子集。 證明其無限子集與N等勢(shì)，即得無限子集為可列集。,4.3 無限集的性質(zhì),證明：設(shè)A是一可列集，A= a0，a1， a2， a3， 1、構(gòu)造可列集A的一子集A 。 先從A中任取一個(gè)元素am0，剩余部分為A-am0 再從A-am0中依次順取一元素am1，剩余部分A-am0，am1 依次順取下去，取出am2，am3，得到一個(gè)無限集合A A =am0，am1 ，顯然A A 2、證明A N N：0

10、 1 2 3 A : am0 am1 am2 am3 綜合得證可列集的無限子集仍為一可列集。,4.3 無限集的性質(zhì),可列集是無限集中的最小元素,分析： 在整數(shù)集I和自然數(shù)集N之間構(gòu)造一一對(duì)應(yīng)關(guān)系。 證明：整數(shù)集I和自然數(shù)集N間的一一對(duì)應(yīng)關(guān)系 N：0 1 2 3 4 5 6 2n-1 2n I: 0 1 -1 2 -2 3 -3 n -n ,4.3 無限集的性質(zhì),4.3 無限集的性質(zhì),分析： 有理數(shù)的形式： ，找出有理數(shù)的一定的排列規(guī)律，即得到一一對(duì)應(yīng)的關(guān)系。,4.3 無限集的性質(zhì),證明：一切有理數(shù)均呈 狀，現(xiàn)將所有 按下列次序 排列 正分?jǐn)?shù)按其分子分母之和的大小順序排列：從小到大 正分?jǐn)?shù)的分子

11、分母之和相同者按分子大小順序排列：從大到小 與正分?jǐn)?shù)具有相同形式的負(fù)分?jǐn)?shù)排于正分?jǐn)?shù)之后 按上述規(guī)律可得一序列，即與N的一一對(duì)應(yīng)關(guān)系： N：0 1 2 3 4 5 6 7 8 9 10 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/2,3/2,12,0/2,1/2,2,-2/3,6,-1/3,7,-3/3,2/3,9,3/3,0/3,1/3,8,-2/4,-1/4,15,-3/4,16,2/4,3/4,13,0/4,1/4,14,PLAY,證明方法二：有理數(shù)和自然數(shù)的對(duì)應(yīng)關(guān)系,4.3 無限集的性質(zhì)

12、,集合的大小問題 集合的基數(shù) 集合的基數(shù)可用|A| 來表示。 對(duì)有限集A，|A|=集合A中元素的個(gè)數(shù)； 對(duì)無限集A， |A|不能用有限集的方法來定義，規(guī)定自然數(shù)集 N的基數(shù)為0(阿列夫零)，即|N|= 0,4.3 無限集的性質(zhì),(2)集合大小的比較 有限集大小的比較，用“相等”、“不相等” 無限集大小的比較，用“等勢(shì)”、“不等勢(shì)” 等勢(shì)即為基數(shù)相同，由此立即可知：所有可列集的基數(shù)均為0。 (3)可列集是最小的無限集 沒有比基數(shù)0更小的無限集，但存在比基數(shù)0更大的無限集。如實(shí)數(shù)集。,4.3 無限集的性質(zhì),分析： 1、證(0，1)內(nèi)的實(shí)數(shù)不可列，利用反正法，即假設(shè)其是可列的，當(dāng)將其列出時(shí)總能找到一

13、個(gè)元素不屬于列出的集合。 2、證(0，1)內(nèi)的實(shí)數(shù)與R等勢(shì)，即R不可列。,證明： 1、定義在(0，1)內(nèi)的實(shí)數(shù)集S=x|x R且0x1 x S，可表示為x=0.y1y2y3(yi 0,1,9) 假設(shè)S是可列的，則它的元素可依次排列：x0，x1，x2， 且我們有 x0=0.a00a01a02a0n x1=0.a10a11a12a1n xm=0.am0am1am2amn 只需證還能找到一個(gè)元素rS，但r不在x0，x1，x2，中,4.3 無限集的性質(zhì),構(gòu)造一S內(nèi)的實(shí)數(shù)r=0.b0b1b2bn 其中當(dāng)aii1時(shí)，bi=1 當(dāng)aii=1時(shí)，bi=2 因?yàn)閎0a00，所以r x0 因?yàn)閎1a11，所以r

14、x1 因?yàn)榭傆幸晃徊煌詒 xi ，這與r S矛盾， 即(0，1)是不可列的。 2、證明SR，即建立一一對(duì)應(yīng)關(guān)系。設(shè)R中的元素為y，S中的元素為x，因?yàn)镾不可列，所以只能建立關(guān)系式：,4.3 無限集的性質(zhì),4.3 無限集的性質(zhì),當(dāng)x (0，1/2，根據(jù)上式有y (0，+) 當(dāng)x 1/2 ，1)，根據(jù)上式有y ( ，0) 綜上所述x (0，1)，有y ( ， +) 根據(jù)上式還需證y ( ， +)，有x (0，1)，才能證得上式試R和S之間滿足一一對(duì)應(yīng)關(guān)系。轉(zhuǎn)變上式，得,4.3 無限集的性質(zhì),當(dāng)y (0，+) ，根據(jù)上式有x (0，1/2 當(dāng)y ( ，0)，根據(jù)上式有x 1/2 ，1) 綜上所

15、述y ( ， +)，有x (0，1) 從而建立了一一對(duì)應(yīng)關(guān)系，由此整個(gè)定理得證。,4.3 無限集的性質(zhì),結(jié)論 (1)實(shí)數(shù)集比可列集要“大”，它的基數(shù)不是阿列夫零，我們用(阿列夫數(shù))表示-稱為連續(xù)統(tǒng)的勢(shì)； (2)在無限集中除了阿列夫零和阿列夫數(shù)以外還有更大基數(shù)的集合； (3)無限集也有大小，可列集是最小的無限集，其次是實(shí)數(shù)集； (4)對(duì)于任意一個(gè)無限集，總存在一個(gè)基數(shù)大于這個(gè)集合的集合，即無限集的大小也是無限的。,小結(jié),掌握有限集和無限集的概念。 掌握有限集的計(jì)數(shù)方法。 熟練掌握無限集的性質(zhì)，無限集計(jì)數(shù)方法，根據(jù)勢(shì)的定義對(duì)無限集進(jìn)行分類。能夠證明一個(gè)集合是無限集，可列集等。,習(xí)題,1求下列集合的

16、基數(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ù)|A|=26 (2) B=x|x R并且x2+1=0= ，故|B|=0； (3) S=0,3,6,9,=3x|x N，S與N能夠建立一一對(duì)應(yīng)關(guān)系，SN，|S|= 0； (4) T=10,11,12,13,=x+10|x N ，T與N能夠建立一一對(duì)應(yīng)關(guān)系，TN，|T|= 0；,習(xí)題,2.求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整 除，也不能被8整除的數(shù)有多少個(gè)？,解：設(shè)1到1000的整數(shù)構(gòu)成全集U，用A，B，C分別表示能被5，6，