离散数学——有限集及无限集(课件)

1、第四章 有限集与无限集有限集与无限集基本概念有限集与无限集基本概念1有限集有限集2无限集的性质无限集的性质34.1 有限集与无限集基本概念问题：问题：1,2,3,与与2,4,6,哪个集合的元素更多？哪个集合的元素更多？p因为因为1,2,3, 2,4,6,，所以，所以1,2,3,里的个里的个数数多于多于2,4,6,的个数。的个数。p因为两个集合可用函数因为两个集合可用函数f(n)=2n表示，而表示，而f(n)=2n是是一一对应函数，所以一一对应函数，所以1,2,3,和和2,4,6,两个集合两个集合的个数的个数一样多一样多。结论：结论：无限集合无限集合无法用确切的个数来描述无法用确切的个数来描述，

2、有限，有限集合的一些特征也集合的一些特征也不能任意推广不能任意推广到无限集合中去。到无限集合中去。4.1 有限集与无限集基本概念定义定义4.1 一个集合一个集合S与集合与集合Nn=0,1,2(n-1)如果如果存在一存在一一一 对应函数对应函数 f: NnS，则称，则称S 是是有限的有限的，并称其有，并称其有 基数基数n;如果如果 S不是有限的则称其为不是有限的则称其为无限的无限的。定义定义4.2 如果存在如果存在一一对应函数一一对应函数 f: S S，使得，使得f(S) S，即，即f(S)是是S 的真子集，则的真子集，则S是是无限的无限的，否则，否则 S是是 有有 限限的的。说明：说明：要证明

3、一个集合是无限集，只需证明集合和它要证明一个集合是无限集，只需证明集合和它的它的的它的真真子集间子集间存在一一对应关系存在一一对应关系。如：。如：2n是是n的真子的真子集。集。4.1 有限集与无限集基本概念例例4.1 一个有一个有n个不同元素所组成的集合，它就是基个不同元素所组成的集合，它就是基数为数为n的有限集。的有限集。例例4.2 自然数集自然数集N是无限集。是无限集。例例4.3 实数集实数集R是无限集。是无限集。4.1 有限集与无限集基本概念自然数自然数N是无限的。是无限的。 分析：分析：x x N，找到一一对应的函数，找到一一对应的函数f(x) ， 且且y|y=f(x), x N N证

4、明：设函数证明：设函数f：N N 定义为定义为f(x)=2x，显然，显然f是是一对一的，而且有一对一的，而且有f(N) N ，所以，所以N是无限的。是无限的。4.1 有限集与无限集基本概念实数集实数集R是无限的。是无限的。 分析：分析：x x R，找到一一对应的函数，找到一一对应的函数f(x) ， 且且y|y=f(x), x R R1 x x 0f ( x ) =x x m 与与MM矛盾，推论得证。矛盾，推论得证。4.3 无限集的性质n无限集定义无限集定义定义定义4.5 一个集合若一个集合若存在与其存在与其等势等势的的真真子集子集称为无称为无限集，限集， 否则称为有限集。否则称为有限集。4.3

5、 无限集的性质n可列集的定义可列集的定义定义定义4.6 凡与凡与自然数集自然数集 N等势等势的集合叫可列集。的集合叫可列集。 即：能与自然数即：能与自然数 N建立一一对应关系的集合建立一一对应关系的集合例：下列集合都是可数集合：例：下列集合都是可数集合： 1)Ox|x N，x是奇数是奇数; 2)E x|x N，x是偶数是偶数; 3)Px|x N，x是素数是素数;4.3 无限集的性质一无限集必包含一可列集。一无限集必包含一可列集。分析：分析：若无限集是可列集，定理显然成立。若无限集是可列集，定理显然成立。若无限集不是可列集，需要若无限集不是可列集，需要构造构造其无限子集，使其无限子集，使无无限子

6、集与限子集与N等势等势，即得无限子集为可列集。，即得无限子集为可列集。4.3 无限集的性质n可列集的重要性质可列集的重要性质证明：设证明：设A是一无限集是一无限集1、构造无限集、构造无限集A的一子集的一子集A 。先从先从A中任取一个元素中任取一个元素a0，剩余部分为，剩余部分为A-a0再从再从A-a0中任取一元素中任取一元素a1，剩余部分为，剩余部分为A-a0，a1继续下去，取出继续下去，取出a2，a3，得到一个，得到一个无限集合无限集合AA =a0，a1 ，显然，显然A A 2、证明、证明A NN：0 1 2 3 i A : a0 a1 a2 a3 ai 4.3 无限集的性质A为可列集，为可

7、列集，因为因为A A所以定理成立所以定理成立可列集的无限子集仍为一可列集。可列集的无限子集仍为一可列集。分析：分析：构造可列集的无限子集。构造可列集的无限子集。证明其证明其无限子集与无限子集与N等势等势，即得无限子集为可列集。，即得无限子集为可列集。4.3 无限集的性质证明：设证明：设A是一可列集，是一可列集，A= a0，a1， a2， a3，1、构造可列集、构造可列集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 无限集的性质可列集可列集是是无无限集中限集中的的最小最小元素元素分析：分析：在整数集在整数集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

9、4.3 无限集的性质整数集整数集I是可列集。是可列集。4.3 无限集的性质有理数集有理数集Q是可列集。是可列集。分析：分析：有理数的形式：有理数的形式： ，找出有理数的一定的，找出有理数的一定的排列规律，即得到一一对应的关系。排列规律，即得到一一对应的关系。nm 4.3 无限集的性质证明：一切有理数均呈证明：一切有理数均呈 状，现将所有状，现将所有 按下列次序按下列次序 排列排列 正分数按其分子分母之和的大小顺序排列：从小到正分数按其分子分母之和的大小顺序排列：从小到大大 正分数的分子分母之和相同者按分子大小顺序排列：从大正分数的分子分母之和相同者按分子大小顺序排列：从大到小到小 与正分数具有

10、相同形式的负分数排于正分数之后与正分数具有相同形式的负分数排于正分数之后按上述规律可得一序列，即与按上述规律可得一序列，即与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证明方法二：有理数和自然数的对应关系4.3 无限集的性质n 集合的大小问题集合的大小问题n 集合的基数集合的基数集合的基数可用集合的基数可用|A| 来表示。来表示。对有限集对有限集A，|A|=集合集合A中元素的个数中元素的个数；对无限集对无限集A， |A|不能用有限集的方法来定义，规定不能用有限集的方法来定义，规定自然数集自然数集 N的基数为的基数为?0(阿列夫零阿列夫零)，即，即|N|= ?

12、04.3 无限集的性质(2)集合大小的比较集合大小的比较有限集大小的比较，用有限集大小的比较，用“相等相等”、“不相等不相等” 无限集大小的比较，用无限集大小的比较，用“等势等势”、“不等势不等势”等势即为基数相同，由此立即可知：等势即为基数相同，由此立即可知：所有可列集的基所有可列集的基数均为数均为?0。(3)可列集是最小的无限集可列集是最小的无限集 没有比基数没有比基数?0更小的无限集，但存在比基数更小的无限集，但存在比基数?0更大的更大的无限集。如无限集。如实数集实数集。4.3 无限集的性质分析：分析：1、证、证(0，1)内的实数不可列，利用内的实数不可列，利用反正法反正法，即假设其是，

13、即假设其是可列的，当将其列出时总能找到一个元素不属于列出的集可列的，当将其列出时总能找到一个元素不属于列出的集合。合。2、证、证(0，1)内的实数与内的实数与R等势，即等势，即R不可列。不可列。实数集是不可列的。实数集是不可列的。证明：证明：1、定义在、定义在(0，1)内的实数集内的实数集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 无限集的性质构造一构造一S内的实数内的实数r=0.b0b1b2bn其中当其中当aii1时，时，bi=1 当当aii=1时，时，bi=2因为因为b0a00，所以，所以r x0因为因为b1a11，所以，所以r x1 因为总有一位不同，所以因为总有一位不同，所以r xi ，这与，这与r S矛盾，矛盾，即即(0，1)是不可列的。是不可列的。2、证明、证明SR，即建立一一对应关系。设，即建立一一对应关系。设R中的元素为中的元素为y，S中的元中的元素为素为x，因为，因为S不可列，所以只能建立关系式：不可列，所以只

15、能建立关系式：4.3 无限集的性质4.3 无限集的性质y1111- 1, 0 x- 1, 0 x2x22x21111+ 1, x1+ 1, x12(x - 1)22(x - 1)2当当x (0，1/2，根据上式有，根据上式有y (0，+)当当x 1/2 ，1)，根据上式有，根据上式有y ( ，0)综上所述综上所述x (0，1)，有，有y ( ， +)根据上式根据上式还需证还需证y ( ， +)，有，有x (0，1)，才能，才能证得上式试证得上式试R和和S之间满足一一对应关系。转变上式，之间满足一一对应关系。转变上式，得得4.3 无限集的性质x01 1, y0, y02(y+ 1)2(y+ 1)

16、1 1+ 1, y+ 1, y2(y- 1)2(y- 1)当当y (0，+) ，根据上式有，根据上式有x (0，1/2当当y ( ，0)，根据上式有，根据上式有x 1/2 ，1)综上所述综上所述y ( ， +)，有，有x (0，1)从而建立了一一对应关系，由此整个定理得证。从而建立了一一对应关系，由此整个定理得证。4.3 无限集的性质n 结论结论(1)实数集比可列集要实数集比可列集要“大大”，它的基数不是阿列夫，它的基数不是阿列夫零，我们零，我们用用?(阿列夫数阿列夫数)表示表示-称为连续统的势；称为连续统的势；(2)在无限集中除了阿列夫零和阿列夫数以外在无限集中除了阿列夫零和阿列夫数以外还有

17、更还有更大基数的集合大基数的集合；(3)无限集也有大小，无限集也有大小，可列集是最小的无限集可列集是最小的无限集，其次，其次是是实数集实数集；(4)对于任意一个无限集，总存在一个基数大于这个对于任意一个无限集，总存在一个基数大于这个集合的集合，即集合的集合，即无限集的大小也是无限的无限集的大小也是无限的。小结p掌握有限集和无限集的概念。掌握有限集和无限集的概念。p掌握有限集的计数方法。掌握有限集的计数方法。p熟练掌握无限集的性质，无限集计数方法，根据势熟练掌握无限集的性质，无限集计数方法，根据势的定义对无限集进行分类。能够证明一个集合是无限的定义对无限集进行分类。能够证明一个集合是无限集，可列

18、集等。集，可列集等。习题1求下列集合的基数。求下列集合的基数。(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的整数构成全集的整