离散数学第九章集合的基数.ppt

离散数学课件第九章离散数学课件第九章集合的基数集合的基数现在学习的是第1页，共45页本章说明本章说明q本章的主要内容 集合的等势及其性质 重要的等势或不等势的结果 集合的优势及其性质 自然数与自然数集合 集合的基数 可数集 现在学习的是第2页，共45页9.1 9.1 集合的等势与优势集合的等势与优势9.2 9.2 集合的基数集合的基数 本章小结本章小结 习题习题 作业作业本章内容本章内容现在学习的是第3页，共45页定义定义9.19.1 设设A,BA,B是集合，如果存在着从是集合，如果存在着从A A到到B B的的双射函数双射函数，就称就称A A和和B B是等势是等势（same cardinality）的的，记作，记作ABAB。如果如果A A不与不与B B等势，则记作等势，则记作A BA B。9.1 集合的等势与优势集合的等势与优势q通俗的说，集合的势是量度集合所含元素多少的量。q集合的势越大，所含的元素越多。现在学习的是第4页，共45页（1）ZN。20:,()210 xxfZNf xxx则f是Z到N的双射函数。从而证明了ZN。等势集合的实例等势集合的实例(1)(1)现在学习的是第5页，共45页等势集合的实例等势集合的实例(2)(2)（2）NNN。(1)():,(,)2mnmnfNNNfm nm 双射函数 现在学习的是第6页，共45页等势集合的实例等势集合的实例(3)(3)（3 3）NQNQ。把所有形式为把所有形式为p p/q q(p p,q q为整数且为整数且q q0)0)的数排成一张表。的数排成一张表。-2/15-1/14-3/1182/1103/1110/101/11-2/2-1/23-3/2172/23/2120/21/22-2/36-1/37-3/32/393/30/31/38-2/4-1/415-3/4162/43/4130/41/414以0/1作为第一个数，按照箭头规定的顺序可以“数遍”表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。现在学习的是第7页，共45页等势集合的实例等势集合的实例(4)(4)（4）(0,1)R。其中实数区间(0,1)=x|xR0 x1。21:(0,1),()tan2xfRf x令双射函数则 f 是(0,1)到R的双射函数。从而证明了(0,1)R。现在学习的是第8页，共45页等势集合的实例等势集合的实例(5)(5)（5 5）0,1(0,1)。其中其中(0,1)和和0,1分别为实数开区间和闭区间。分别为实数开区间和闭区间。211/201/21()1/21/2,1,2,.nnxxf xxnxx其它双射函数 f:0,1(0,1)，n n3 32 22 21 12 21 12 21 12 21 110 02 22 21 12 21 12 2n n5 54 43 32 21 12 21 12 21 12 21 12现在学习的是第9页，共45页等势集合的实例等势集合的实例(6)(6)（6）对任何a,bR，ab，0,1a,b。双射函数f：0,1a,b，f(x)(ba)x+a。现在学习的是第10页，共45页例9.2 设A为任意集合，则P(A)0,1A。构造f：P(A)0,1A，f(A)=A，AP(A)。其中A 是集合A 的特征函数。(1)易证 f 是单射的。(2)对于任意的 g0,1A，那么有 g：A0,1。令 B=x|xAg(x)=1 则BA，且B=g，即BP(A)，使得f(B)=g。所以 f 是满射的。由等势定义得P(A)0,1A。例例9.29.2证明复习现在学习的是第11页，共45页定理定理9.19.1 设设A，B，C是任意集合，是任意集合，（1）AA。（2）若若AB，则则BA。（3）若若AB，BC，则则AC。（1）IA是从A到A的双射，因此AA。（2）假设AB，存在 f:AB是双射，那么 f1:BA是从B到A的双射，所以BA。（3）假设AB，BC，存在 f:AB，g:BC是双射，则fg:AC是从 A 到 C 的双射。所以AC。等势的性质等势的性质证明现在学习的是第12页，共45页q N Z Q NNq R 0,1(0,1)q 任何的实数区间（开区间、闭区间以及半开半闭的区间）任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合都与实数集合R R等势。等势。q 问题：问题：N N和和R R是否等势？是否等势？若干等势集合若干等势集合现在学习的是第13页，共45页（1）如果能证明N 0,1，就可以断定N R。只需证明任何函数f：N0,1都不是满射的。构造一个0,1区间的小数b，使得b在N中不存在原像。（2）任取函数f：AP(A)，构造BP(A)，使得B在A中不存在原像。或者使用反证法。定理定理9.29.2 康托定理康托定理（1）N R。（2）对任意集合对任意集合A都有都有A P(A)。康托定理康托定理分析现在学习的是第14页，共45页（1 1）首先规定）首先规定0,1中数的表示。中数的表示。对任意的对任意的x0,1，令令x=0.x1x2,（0 xi 9）注意：为了保证表示式的唯一性，如果遇到注意：为了保证表示式的唯一性，如果遇到0.249990.24999，则将，则将x x表示为表示为0.250000.25000。设设 f:N0,1是从是从N到到0,1的任何一个函数。的任何一个函数。f的所有函数值为的所有函数值为：f(0)=0.a1(1)a2(1)f(1)=0.a1(2)a2(2)f(n 1)=0.a1(n)a2(n)令令y的表示式为的表示式为0.b1b2，并且满足并且满足bi ai(i)，i=1,2,，则则y0,1，但但y与上面列出的任何一个函数值都不相等与上面列出的任何一个函数值都不相等。即即f不是满射的。不是满射的。所以所以，N R。康托定理康托定理现在学习的是第15页，共45页康托定理康托定理q 假设假设A AP(A)，则必有函数则必有函数 f:AP(A)是双射函数。是双射函数。如下构造集合如下构造集合B：Bx|xAx f(x)可知可知 BP(A)。于是存在唯一一个元素于是存在唯一一个元素bA，使得使得 f(b)B。若若bB，则由则由B的定义知，的定义知，b f(b)，即即 b B，矛盾矛盾。若若b B，则则b f(b)，于是由于是由B的定义知，的定义知，bB，矛盾。矛盾。现在学习的是第16页，共45页（2 2）设）设g：AP(A)是从是从A到到P(A)的任意函数，的任意函数，如下构造集合如下构造集合B：Bx|xAx g(x)则则BP(A)。但是但是对任意对任意xA，都有都有xB x g(x)所以，对任意的所以，对任意的xA都有都有Bg(x)，即即B ran ran g 即即P(A)中存在元素中存在元素B，在在A中找不到原像。中找不到原像。所以所以，g不是满射的。不是满射的。所以所以，A P(A)。康托定理康托定理q根据这个定理可以知道N P(N)。q综合前面的结果，可知N 0,1N。q实际上，P(N)，0,1N和R都是比N“更大”的集合。现在学习的是第17页，共45页定义定义9.29.2（1 1）设设A,B是集合，如果存在从是集合，如果存在从A到到B的的单射单射函数，就称函数，就称B优优势于势于A，记作记作AB。如果如果B不是优势于不是优势于A，则记作则记作AB。（2 2）设设A,B是集合，若是集合，若AB且且A B，则称则称B真优势于真优势于A，记记作作AB。如果如果B不是真优势于不是真优势于A，则记作则记作AB。例如：例如：N NN RA P(A)N RA P(A)R N N N优势优势RN现在学习的是第18页，共45页定理9.3 设A,B,C是任意的集合，则（1）A A。（2）若A B且B A，则AB。（3）若A B且B C,则A C。证明：（1）IA是A到A的单射，因此A A。（2）证明略。（3）假设A B且B C，那么存在单射 f:AB，g:BC，于是 fg：AC也是单射的，因此A C。优势的性质优势的性质q 该定理为证明集合之间的等势提供了有力的工具。q构造两个单射f：AB 和 g：BA函数容易集合等势。现在学习的是第19页，共45页例题例题例题：例题：证明证明0,10,1与与(0,1)(0,1)等势。等势。证明：证明：构造两个单射函数构造两个单射函数f:(0,1)0,1:(0,1)0,1，f(x)xg:0,1(0,1):0,1(0,1)，g(x)x/2+1/4/2+1/4现在学习的是第20页，共45页证明证明 0,1N0,1)(1)设x0,1)，0.x1x2是x的二进制表示。为了使表示唯一，规定表示式中不允许出现连续无数个1。例如 x0.1010111，应按规定记为0.1011000。对于x，如下定义f：0,1)0,1N，使得 f(x)=tx，且tx：N0,1，tx(n)=xn+1，n=0,1,2,例如 x=0.10110100，则对应于x的函数tx是：n 0 1 2 3 4 5 6 7tx(n)1 0 1 1 0 1 0 0 易见tx0,1N，且对于x,y0,1)，xy，必有tx ty，即f(x)f(y)。所以，f：0,1)0,1N是单射的。现在学习的是第21页，共45页(2)定义函数g：0,1N0,1)。g的映射法则恰好与 f 相反，即 t0,1N，t：N0,1，g(t)=0.x1x2,其中xn+1=t(n)。但不同的是，将0.x1x2看作数x的十进制表示。例如t1，t20,1N，且g(t1)0.0111，g(t2)0.1000，若将g(t1)和g(t2)都看成二进制表示，则g(t1)g(t2)；但若看成十进制表示，则g(t1)g(t2)。所以，g：0,1N0,1)是单射的。根据定理9.3，有0,1N0,1)。证明证明 0,1N0,1)现在学习的是第22页，共45页总结总结q N Z Q NNq R a,b (c,d)0,1N P(N)其中a,b，(c,d)代表任意的实数闭区间和开区间。q 0,1A P(A)q N Rq A P(A)现在学习的是第23页，共45页9.2 9.2 集合的基数集合的基数 q 上一节我们只是抽象地讨论了集合的等势与优势。上一节我们只是抽象地讨论了集合的等势与优势。q 本节将进一步研究度量集合的势的方法。本节将进一步研究度量集合的势的方法。q 最简单的集合是有穷集。尽管前面已经多次用到最简单的集合是有穷集。尽管前面已经多次用到“有穷集有穷集”这一概念，当时只是直观地理解成含有有限多个元素的这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义。为解决这个集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。问题我们需要先定义自然数和自然数集合。现在学习的是第24页，共45页定义9.3 设a为集合，称aa为a的后继，记作a+，即 a+=aa。例9.3 考虑空集的一系列后继。+=+=+=,=,+=,+=,=,=,+,+后继后继 q 前边的集合都是后边集合的元素。q 前边的集合都是后边集合的子集。现在学习的是第25页，共45页利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，即 0=1=0+02=1+,0,132+,+,0,1,2 n0,1,n1自然数的定义自然数的定义 这种定义没有概括出自然数的共同特征。现在学习的是第26页，共45页定义定义9.4 9.4 设设A为为集合，如果满足下面的两个条件：集合，如果满足下面的两个条件：（1）A（2）a(aAa+A)称称A是是归纳集归纳集。例如：下面的集合,+,+,+,+,+,+,a,a+,a+,a+,都是归纳集。归纳集归纳集 现在学习的是第27页，共45页定义定义9.59.5 自然数自然数（1 1）一个）一个自然数自然数n是属于每一个归纳集的集合。是属于每一个归纳集的集合。（2 2）自然数集自然数集N是所有归纳集的交集。是所有归纳集的交集。说明说明：根据定义根据定义9.5得到的自然数集得到的自然数集 N 恰好由恰好由,+,+,+,等集合构成。而这些集合正是构造性方法所定义的等集合构成。而这些集合正是构造性方法所定义的全体自然数。全体自然数。例如：自然数都是集合，集合的运算对自然数都适用。250,10,1,2,3,40,1,2,3,45340,1,20,1,2,30,1,23 4-20,1,2,3-0,1=2,3 230,10,1,2,自然数自然数n n和自然数集合和自然数集合N N的定义的定义 现在学习的是第28页，共45页P(1)P(0),00,1230,10,1,2f|f：0,1,20,1f0,f1,f7其中其中f0,f1,f2,f3,f4,f5,f6,f7,举例举例 现在学习的是第29页，共45页（1）对任何自然数对任何自然数n，有有n n。（2）对任何自然数对任何自然数n,m，若若m n，则则m n。（3）对任何自然数对任何自然数n,m，若若mn，则则m n。（4）对任何自然数对任何自然数n和和m，以下三个式子：以下三个式子：mn，m n，nm必成立其一且仅成立其一。必成立其一且仅成立其一。（5）自然数的相等与大小顺序自然数的相等与大小顺序 对任何自然数对任何自然数m和和n，有有m=n m n m n mn 自然数的性质自然数的性质 现在学习的是第30页，共45页定义9.6 有穷集、无穷集（1）一个集合是有穷的当且仅当它与某个自然数等势；（2）如果一个集合不是有穷的，就称作无穷集。例如：q a,b,c是有穷集，因为30,1,2，且a,b,c0,1,23qN和R都是无穷集，因为没有自然数与N和R等势。q任何有穷集只与唯一的自然数等势。有穷集和无穷集有穷集和无穷集 现在学习的是第31页，共45页定义9.7（1）对于有穷集合A，称与A等势的那个唯一的自然数为A的基数，记作card A，即 card A n A n（对于有穷集A，card A也可以记作|A|）（2）自然数集合N的基数记作0，即card N=0（3）实数集R的基数记作（读作阿列夫），即card R=基数基数(cardinality)现在学习的是第32页，共45页定义定义9.8 9.8 设设A,B为集合，则为集合，则（1）card Acard B AB（2）card Acard B A B（3）card A card B card Acard Bcard Acard B例如：例如：q card Z card Q card NN 0q card P(N)card 2N card a,b card(c,d)q 0说明说明：集合的基数就是集合的势，基数越大，势就越大。：集合的基数就是集合的势，基数越大，势就越大。基数的相等和大小基数的相等和大小 现在学习的是第33页，共45页关于基数的说明关于基数的说明 q 由于对任何集合由于对任何集合A都满足都满足A P(A)，所以有所以有 card A card P(A)，这说明这说明不存在最大的基数不存在最大的基数。q 将已知的基数按从小到大的顺序排列就得到：将已知的基数按从小到大的顺序排列就得到：0,1,2,n,0,q 0,1,2,n,是全体自然数，是是全体自然数，是有穷基数有穷基数。q 0,是是无穷基数无穷基数。q 0是最小的无穷基数是最小的无穷基数，后面还有更大的基数，如后面还有更大的基数，如 card P(R)等。等。现在学习的是第34页，共45页可数集可数集定义9.9 设A为集合，若card A0，则称A为可数集(enumerable)或可列集。例如：q a,b,c、5、整数集Z、有理数集Q、NN等都是可数集。q 实数集R不是可数集，与R等势的集合也不是可数集。对于任何的可数集，都可以找到一个“数遍”集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。现在学习的是第35页，共45页（1 1）可数集的任何子集都是可数集。）可数集的任何子集都是可数集。一个集合的无限子集若不可数，则该集合也不可数。一个集合的无限子集若不可数，则该集合也不可数。（2 2）两个可数集的并是可数集。）两个可数集的并是可数集。（3 3）两个可数集的笛卡儿积是可数集。）两个可数集的笛卡儿积是可数集。（4 4）可数个可数集的笛卡儿积仍是可数集。）可数个可数集的笛卡儿积仍是可数集。（5 5）无穷集）无穷集A A的幂集的幂集P P(A A)不是可数集。不是可数集。可数集的性质可数集的性质 现在学习的是第36页，共45页例例9.49.4 求下列集合的基数。求下列集合的基数。（1）Tx|x是单词是单词“BASEBALL”中的字母中的字母（2）Bx|xRx2=92x=8（3）CP(A),A=1,3,7,11（1）由TB,A,S,E,L知，card T5。（2）由B可知，card B0。（3）由|A|4可知，card Ccard P(A)|P(A)|2416。解答例例9.4 9.4 现在学习的是第37页，共45页方法一由card A0，card Bn，可知A,B都是可数集。令A=a0,a1,a2,，B=b0,b1,b2,bn1。对任意的，AB，有 i kj l定义函数 f：ABNf()in+j,i0,1,j0,1,n1由于 f 是AB到N的双射函数，所以card ABcard N。例例9.59.5解答例9.5 设A,B为集合，且card A0，card Bn，n是自然数，n0。求card AB。现在学习的是第38页，共45页例例9.59.5方法二因为card A0，card Bn，所以A,B都是可数集。根据性质（3）可知，AB也是可数集，所以，card AB0 当B时，card Acard AB，这就推出0card AB综合所述，card AB 0现在学习的是第39页，共45页本章主要内容本章主要内容q 集合等势的定义q 等势的性质q 集合优势的定义q 优势的性质q 重要的集合等势以及优势的结果q 自然数及其自然数集合的定义q 可数集与不可数集q 集合的基数 现在学习的是第40页，共45页本章学习要求本章学习要求q 能够证明两个集合等势。能够证明两个集合等势。q 能够证明一个集合优势于另一个集合。能够证明一个集合优势于另一个集合。q 知道什么是可数集与不可数集。知道什么是可数集与不可数集。q 会求一个简单集合的基数。会求一个简单集合的基数。现在学习的是第41页，共45页等势的证明方法等势的证明方法q 证明集合证明集合A A与与B B等势的方法等势的方法直接构造从直接构造从A A到到B B的双射函数的双射函数 f需要证明需要证明 f 的满射性和的满射性和f f的单射性。的单射性。构造两个单射函数构造两个单射函数f f：A AB B 和和 g g：B BA A。给出函数给出函数f f和和g g，证明证明f f和和g g的单射性。的单射性。利用等势的传递性利用等势的传递性直接计算直接计算A A与与B B的基数，得到的基数，得到card card A A card card B B。q 证明集合证明集合A A与自然数集合与自然数集合N N等势的方法等势的方法找到一个找到一个“数遍数遍”A A中元素的顺序。中元素的顺序。现在学习的是第42页，共45页例题选讲例题选讲1 1已知已知An7 7|nN，B n109|n N，求下列各题：求下列各题：（1 1）card A（2 2）card B（3 3）card(AB)（4 4）card(AB)（1）构造双射函数 f：NA，f(n)=n7，因此 card A0。（2）构造双射函数 g：NA，g(n)=n109，因此 card B0。（3）可数集的并仍旧是可数集(或者由于AB N)，因此card(AB)0，但是 0 card Acard(AB)，从而得到 card(AB)0。（4）因为7与109互素，card(AB)n7109|nN，与（1）类似得到 card(AB)0。解答现在学习的是第43页，共45页例题选讲例题选讲2.2.已知已知card A0，且且card B card A，求求card(A B)。由ABA，得到 card(AB)card A，即card(AB)0。由card Bcard A可知，B为有穷集，即存在自然数n，使得card B=n。假设card(AB)0，那么存在自然数m，使 card(AB)m。从而得到，card Acard(AB)B)n+m与card A0矛盾。因此，card(AB)0。解答现在学习的是第44页，共45页作业作业习题九习题九：1 1、2 2、3 3、6 6、7 7、8 8、9 9、1111现在学习的是第45页，共45页