离散数学__有限集与无限集(课件).ppt

§4.3 无限集的性质 集合的大小问题 集合的基数 集合的基数可用|A| 来表示。 对有限集A，|A|=集合A中元素的个数； 对无限集A， |A|不能用有限集的方法来定义，规定自然数集 N的基数为?0(阿列夫零)，即|N|= ?0 §4.3 无限集的性质 (2)集合大小的比较 有限集大小的比较，用“相等”、“不相等” 无限集大小的比较，用“等势”、“不等势” 等势即为基数相同，由此立即可知：所有可列集的基数均为?0。 (3)可列集是最小的无限集 没有比基数?0更小的无限集，但存在比基数?0更大的无限集。如实数集。 §4.3 无限集的性质 分析： 1、证(0，1)内的实数不可列，利用反正法，即假设其是可列的，当将其列出时总能找到一个元素不属于列出的集合。 2、证(0，1)内的实数与R等势，即R不可列。 定理4.12 实数集是不可列的。 证明： 1、定义在(0，1)内的实数集S={x|x ?R且0x1} ?x ?S，可表示为x=0.y1y2y3…(yi ?{0,1,…9}) 假设S是可列的，则它的元素可依次排列：x0，x1，x2，… 且我们有 x0=0.a00a01a02…a0n… x1=0.a10a11a12…a1n… … xm=0.am0am1am2…amn… … 只需证还能找到一个元素r?S，但r不在x0，x1，x2，…中 §4.3 无限集的性质 构造一S内的实数r=0.b0b1b2…bn… 其中当aii≠1时，bi=1 当aii=1时，bi=2 因为b0≠a00，所以r ≠x0 因为b1≠a11，所以r ≠x1 … 因为总有一位不同，所以r ≠xi ，这与r ?S矛盾， 即(0，1)是不可列的。 2、证明S~R，即建立一一对应关系。设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) 综上所述y ?(－∞ ， +∞)，有x ?(0，1) 从而建立了一一对应关系，由此整个定理得证。 §4.3 无限集的性质 结论 (1)实数集比可列集要“大”，它的基数不是阿列夫零，我们用?(阿列夫数)表示---称为连续统的势； (2)在无限集中除了阿列夫零和阿列夫数以外还有更大基数的集合； (3)无限集也有大小，可列集是最小的无限集，其次是实数集； (4)对于任意一个无限集，总存在一个基数大于这个集合的集合，即无限集的大小也是无限的。 小结 掌握有限集和无限集的概念。 掌握有限集的计数方法。 熟练掌握无限集的性质，无限集计数方法，根据势的定义对无限集进行分类。能够证明一个集合是无限集，可列集等。 习题 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能够建立一一对应关系，S~N，|S|= ?0； (4) T={10,11,12,13,…}={x+10|x ?N} ，T与N能够建立一一对应关系，T~N，|T|= ?0； 习题 2.求1到1000之间（包含1和1000在内）既不能被5和6整 除，也不能被8整除的数有多少个？ 解：设1到1000的整数构成全集U，用A，B，C分别表示能被5，6，8整除的数构成的集合 |U| = 1000 |A|=?1000/5?=200, |B|=?1000/6?=166, |C|=?1000/8?=125 |A∩B| = ?1000/30? = 33 |A∩C| = ?1000/40? = 25 |B∩C| = ?1000/24? = 41 |A∩B∩C| = ?1000/120? = 8 习题 |A∪B ∪C |=|A|+|B|+|C|- |A∩B|-|A∩C|- |B∩C| +|A∩B ∩C | = 200+166+125-33-25-41+8 =400