离散数学-有限集与无限集(课件)

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中按一定规律找到一可以排列的无限集M1，使得M为M中去掉M1中一元素。,4.3 无限集的性质,无限集的性质,证明： 1、构造无限集M的一真子集M 。 先从M中任取一个元素m1，剩余部分为M-m1无限集 再从M-m1中任取一元素m2，剩余部分为M-m1，m2 继续下去，取出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 继续下去，取出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 无限集的性质,分析： 有理数的形式： ，找出有理数的一定的排列规律，即得到一一对应的关系。,4.3 无限集的性质,证明：一切有理数均呈 状，现将所有 按下列次序 排列 正分数按其分子分母之和的大小顺序排列：从小到大 正分数的分子

11、分母之和相同者按分子大小顺序排列：从大到小 与正分数具有相同形式的负分数排于正分数之后 按上述规律可得一序列，即与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|不能用有限集的方法来定义，规定自然数集 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)实数集比可列集要“大”，它的基数不是阿列夫零，我们用(阿列夫数)表示-称为连续统的势； (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，