双射函数和集合基数.ppt

8.3 集合的基数;本章说明;8.3.1 集合的等势与优势 8.3.2 集合的基数 本节小结 习题 作业;定义8.8 设A, B是集合，如果存在着从A到B的双射函数，就称A和B是等势（same cardinality）的，记作A≈B。 如果A不与B等势，则记作A B。;（1）Z≈N。;等势集合的实例(2);等势集合的实例(3);等势集合的实例(4);等势集合的实例(5);等势集合的实例(6);例8.10 设A为任意集合，则P(A)≈{0,1}A。;定理8.6 设A，B，C是任意集合， （1）A≈A。 （2）若A≈B，则B≈A。 （3）若A≈B，B≈C，则A≈C。; N ≈ Z ≈ Q ≈ N×N R ≈ [0,1] ≈(0,1) 任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合R等势。 问题：N和R是否等势？;（1）如果能证明N [0,1]，就可以断定N R。 只需证明任何函数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不是满射的。 所以，N R。;康托定理;（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?ran g 即P(A) 中存在元素B，在A中找不到原像。 所以，g不是满射的。 所以， A P(A)。;定义8.9 （1） 设A, B是集合，如果存在从A到B的单射函数，就称B优势于A，记作A≤·B。 如果B不是优势于A， 则记作A≤·B。 （2）设A, B是集合，若A≤·B且A B，则称B真优势于A，记作A＜·B。如果B不是真优势于A，则记作A≮·B。 例如：;定理8.8 设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)。;总结;8.3.2 集合的基数 ;定义8.10 设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} …;定义8.11 设A为集合，如果满足下面的