离散数学课件章集合的基数9、1集合得等势与优势9、2集合得基数本章小结习题作业定义9、1设A,B就是集合,如果存在着从A到B得双射函数,就称A与B就是等势(samecardinality)得,记作A≈B。如果A不与B等势,则记作AB。(1)Z≈N。等势集合得实例(2)等势集合得实例(3)等势集合得实例(4)等势集合得实例(5)等势集合得实例(6)例9、2设A为任意集合,则P(A)≈{0,1}A。定理9、1设A,B,C就是任意集合,(1)A≈A。(2)若A≈B,则B≈A。(3)若A≈B,B≈C,则A≈C。大家学习辛苦了，还是要坚持N≈Z≈Q≈N×NR≈[0,1]≈(0,1)任何得实数区间(开区间、闭区间以及半开半闭得区间)都与实数集合R等势。问题:N与R就是否等势？(1)如果能证明N[0,1],就可以断定NR。只需证明任何函数f:N→[0,1]都不就是满射得。构造一个[0,1]区间得小数b,使得b在N中不存在原像。(2)任取函数f:AP(A),构造B∈P(A),使得B在A中不存在原像。或者使用反证法。(1)首先规定[0,1]中数得表示。对任意得x∈[0,1],令x=0、x1x2…,(0≤xi≤9)注意:为了保证表示式得唯一性,如果遇到0、24999…,则将x表示为0、25000…。设f:N→[0,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,…,则y∈[0,1],但y与上面列出得任何一个函数值都不相等。即f不就是满射得。所以,NR。康托定理(2)设g:A→P(A)就是从A到P(A)得任意函数,如下构造集合B:B＝{x|x∈A∧xg(x)}则B∈P(A)。但就是对任意x∈A,都有x∈Bxg(x)所以,对任意得x∈A都有B≠g(x),即Brang即P(A)中存在元素B,在A中找不到原像。所以,g不就是满射得。所以,AP(A)。定义9、2(1)设A,B就是集合,如果存在从A到B得单射函数,就称B优势于A,记作A≤·B。如果B不就是优势于A,则记作A≤·B。(2)设A,B就是集合,若A≤·B且AB,则称B真优势于A,记作A＜·B。如果B不就是真优势于A,则记作A≮·B。例如:定理9、3设A,B,C就是任意得集合,则(1)A≤·A。(2)若A≤·B且B≤·A,则A≈B。(3)若A≤·B且B≤·C,则A≤·C。证明:(1)IA就是A到A得单射,因此A≤·A。(2)证明略。(3)假设A≤·B且B≤·C,那么存在单射f:A→B,g:B→C,于就是fg:A→C也就是单射得,因此A≤·C。例题证明{0,1}N≈[0,1)(2)定义函数g:{0,1}N→[0,1)。g得映射法则恰好与f相反,即t∈{0,1}N,t:N→{0,1},g(t)=0、x1x2…,其中xn+1=t(n)。但不同得就是,将0、x1x2…看作数x得十进制表示。例如t1,t2∈{0,1}N,且g(t1)＝0、0111…,g(t2)＝0、1000…,若将g(t1)与g(t2)都看成二进制表示,则g(t1)＝g(t2);但若看成十进制表示,则g(t1)≠g(t2)。所以,g:{0,1}N→[0,1)就是单射得。根据定理9、3,有{0,1}N≈[0,1)。总结9、2集合得基数定义9、3设a为集合,称a∪{a}为a得后继,记作a+,即a+=a∪{a}。利用后继得性质,可以考虑以构造性得方法用集合来给出自然数得定义,即0=1=0+＝+＝{}＝{0}2=1+＝{}+＝{}∪{{}}＝{,{}}＝{0,1}3＝2+＝{,{}}+＝{,{},{,{}}}＝{0,1,2}…n＝{0,1,…,n1}…定义9、4设A为集合,如果满足下面得两个条件:(1)∈A(2)a(a∈A→a+∈A)称A就是归纳集。定义9、5自然数(1)一个自然数n就是属于每一个归纳集得集合。(2)自然数集N就是所有归纳集得交集。说明:根据定义9、5得到得自然数集N恰好由,+,++,+++,…等集合构成。而这些集合正就是构造性方法所定义得全体自然数。P(1)＝P({0})＝{,{0}}＝{0,1}23＝{0,1}{0,1,2}＝{f|f:{0,1,2}→{0,1}}＝{f0,f1,…,f7}其中f0＝{<0,0>,<1,0>,<2,0>}f1＝{<0,0>,<1,0>,<2