離散數學-有限集與無限集(課件)

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

2、 定義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 有限集與無限集基本概念,分析：xN，找到一一對應的函數f(x) ， 且y|y=f(x), xN N,證明：設函數f：N N 定義為f(x)=2x，顯然f是一對一的，而且有f(N) N ，所以N是無

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

4、請問同時學三種語言的有多少人？僅學一種語言的各有多少人？ 解： （1）設A、B、C分別表示學法語、德語和英語的學生的集合，由題意和定理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）由文氏圖可計算僅學一種語言的各有多少人 法語人數為： 65-(12+8+17)=28 德語人數為： 45-(12+8+7)=18 英語人數為： 42-(17+8+7)=10,4.3 無限集的性質,等勢的定義 定義4.4 集合A，B的元素之間，如果存在

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

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

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

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

9、合A A =a0，a1 ，顯然A A 2、證明A N N：0 1 2 3 i A : a0 a1 a2 a3 ai ,4.3 無限集的性質,A為可列集， 因為A A 所以定理成立,分析： 構造可列集的無限子集。 證明其無限子集與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 N N：0

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

11、分母之和相同者按分子大小順序排列：從大到小 與正分數具有相同形式的負分數排于正分數之后 按上述規(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,證明方法二：有理數和自然數的對應關系,4.3 無限集的性質

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

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

14、x1 因為總有一位不同，所以r xi ，這與r S矛盾， 即(0，1)是不可列的。 2、證明SR，即建立一一對應關系。設R中的元素為y，S中的元素為x，因為S不可列，所以只能建立關系式：,4.3 無限集的性質,4.3 無限集的性質,當x (0，1/2，根據上式有y (0，+) 當x 1/2 ，1)，根據上式有y ( ，0) 綜上所述x (0，1)，有y ( ， +) 根據上式還需證y ( ， +)，有x (0，1)，才能證得上式試R和S之間滿足一一對應關系。轉變上式，得,4.3 無限集的性質,當y (0，+) ，根據上式有x (0，1/2 當y ( ，0)，根據上式有x 1/2 ，1) 綜上所

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

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