双射函数与集合的基数.ppt

8.38.3 集合的基数集合的基数离离 散散 数数 学学南京农业大学本科生课程南京农业大学本科生课程数学系数学系数学系数学系本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容–集合的等势及其性质集合的等势及其性质–重要的等势或不等势的结果重要的等势或不等势的结果–集合的优势及其性质集合的优势及其性质–自然数与自然数集合自然数与自然数集合–集合的基数集合的基数–可数集可数集 8.3.1 8.3.1 集合的等势与优势集合的等势与优势8.3.2 8.3.2 集合的基数集合的基数 本节小结本节小结 习题习题 作业作业本章内容本章内容本章内容本章内容定义定义8.88.8 设设A, BA, B是集合，如果存在着从是集合，如果存在着从A A到到B B的的双射函数双射函数，就，就称称A A和和B B是等势是等势（（same cardinality））的的，记作，记作A≈BA≈B 如果如果A A不与不与B B等势，则记作等势，则记作A BA B8.3.1 8.3.1 集合的等势与优势集合的等势与优势集合的等势与优势集合的等势与优势≈≈q通俗的说，集合的势是量度集合所含元素多少的量。

通俗的说，集合的势是量度集合所含元素多少的量q集合的势越大，所含的元素越多集合的势越大，所含的元素越多（（1））Z≈N则则f是是Z到到N的双射函数的双射函数 从而证明了从而证明了Z≈N等势集合的实例等势集合的实例等势集合的实例等势集合的实例(1)(1)(1)(1)等势集合的实例等势集合的实例等势集合的实例等势集合的实例(2)(2)(2)(2)（（2）） N×N≈N双射函数双射函数 等势集合的实例等势集合的实例等势集合的实例等势集合的实例(3)(3)(3)(3)（（3 3））N≈QN≈Q 把所有形式为把所有形式为p p/ /q q ( (p p, ,q q为整数且为整数且q q>0) >0) 的数排成一张表的数排成一张表2/1-2/1[5][5]-1/1-1/1[4][4]-3/1-3/1[18][18]2/12/1[10][10]3/13/1[11][11]0/10/1[0][0]1/11/1[1][1]-2/2-2/2-1/2-1/2[3][3]-3/2-3/2[17][17]2/22/23/23/2[12][12]0/20/21/21/2[2][2]-2/3-2/3[6][6]-1/3-1/3[7][7]-3/3-3/32/32/3[9][9]3/33/30/30/31/31/3[8][8]-2/4-2/4-1/4-1/4[15][15]-3/4-3/4[16][16]2/42/43/43/4[13][13]0/40/41/41/4[14][14]…………………………………………以以0/10/1作为第一个数，按照箭头规定的顺序可以作为第一个数，按照箭头规定的顺序可以“数遍数遍”表中表中所有的数。

计数过程中必须跳过第二次以及以后各次所遇到的所有的数计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数同一个有理数等势集合的实例等势集合的实例等势集合的实例等势集合的实例(4)(4)(4)(4)（（4））(0,1)≈R 其中实数区间其中实数区间 (0,1)={x| x∈∈R∧∧0

其中其中 A  是集合是集合A  的特征函数的特征函数1)(1)易证易证 f 是是单射的单射的2)(2)对于任意的对于任意的 g∈∈{0,1}A，，      那么有那么有 g：：A→{0,1}令令 B={x| x∈∈A∧∧g(x)=1}      则则B A，，且且 B=g，，即即 B∈∈P(A)，，使得使得f(B)=g     所以所以 f 是满射的是满射的由等势定义由等势定义得得P(A)≈{0,1}A例例例例8.108.108.108.10证明证明复习复习定理定理8.68.6 设设A，，B，，C是任意集合，是任意集合，（（1））A≈A2））若若A≈B，，则则B≈A3））若若A≈B，，B≈C，，则则A≈C1 1）） IA是从是从A到到A的双射，因此的双射，因此A≈A2）） 假设假设A≈B ，存在，存在  f : : AB是双射，是双射，那么那么 f 1 : : BA是从是从B到到A的双射，所以的双射，所以B≈A3）） 假设假设A≈B，，B≈C，，存在存在 f : :AB，，g: :BC是双射，是双射，则则f g : : AC是从是从 A 到到 C 的双射的双射。

所以所以A≈C等势的性质等势的性质等势的性质等势的性质证明证明q N ≈ Z ≈ Q ≈ N×Nq R ≈ [0,1] ≈(0,1)q任何的实数区间（开区间、闭区间以及半开半闭的区间）任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合都与实数集合R R等势q问题：问题：N N和和R 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中不存在原中不存在原像或者使用反证法或者使用反证法定理定理8.78.7  康托定理康托定理（（1））N R2））对任意集合对任意集合A都有都有A P(A)康托定理康托定理康托定理康托定理≈≈≈≈≈≈≈≈分析分析（（1 1）首先规定）首先规定[0,1]中数的表示。

中数的表示     对任意的对任意的x∈∈[0,1]，，令令x = 0. .x1x2… ,         （（0 ≤ xi ≤ 9）） 注意：为了保证表示式的唯一性，如果遇到注意：为了保证表示式的唯一性，如果遇到0.24999…0.24999…，则将，则将x x表表示为示为0.25000…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康托定理康托定理康托定理康托定理≈≈康托定理康托定理康托定理康托定理q假设假设A A≈P(A)，，则必有函数则必有函数 f : A→P(A)是双射函数。

是双射函数如下构造集合如下构造集合B：：B＝＝{x| x∈∈A∧∧x  f (x)}     可知可知 B∈∈P(A)于是存在唯一一个元素于是存在唯一一个元素b∈∈A，，使得使得 f(b)＝＝B若若b∈∈B，，则由则由B的定义知，的定义知，b   f (b)，，即即 b B，，矛盾矛盾若若b B，，则则b    f (b)，，于是由于是由B的定义知，的定义知， b∈∈B，，矛盾（（2 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 ran g 即即P(A) 中存在元素中存在元素B，，在在A中找不到原像中找不到原像 所以所以，，g不是满射的不是满射的 所以所以，， A P(A)说说明明康托定理康托定理康托定理康托定理≈≈q根据这个定理可以知道根据这个定理可以知道N P(N)。

q综合前面的结果，可知综合前面的结果，可知N    {0,1}N q实际上，实际上，P(N)P(N)，，{0,1}{0,1}N N和和R R都是比都是比N N“更大更大”的集合 ≈≈≈≈定义定义8.98.9（（1 1）） 设设A, B是集合，如果存在从是集合，如果存在从A到到B的的单射单射函数，就称函数，就称B优优势于势于A，，记作记作A≤·≤·B  如果如果B不是优势于不是优势于A，， 则记作则记作A≤·≤·B2 2））设设A, B是集合，若是集合，若A≤·≤·B且且A B，，则称则称B真优势于真优势于A，，记作记作A＜＜··B如果如果B不是真优势于不是真优势于A，，则记作则记作A≮≮··B 例如：例如：N ≤≤· NN ≤≤· RA ≤≤· P(A)N ＜＜·· RA ＜＜·· P(A) R ≮≮·· N N ≮≮·· N优势优势优势优势≈≈R≤≤·N定理定理8.88.8 设设A, B, C是任意的集合，则是任意的集合，则（（1））A≤≤· A2））若若A ≤≤· B且且B ≤≤· A，，则则A≈B3））若若A ≤≤· B且且B ≤≤· C, 则则A ≤≤· C 。

证明：证明：（（1 1））IA是是A到到A的单射的单射，，因此因此A≤≤· A2 2）证明略3 3）假设）假设A ≤≤· B且且B ≤≤· C，那么存在单射，那么存在单射 f:A→B:A→B，，g:B→C:B→C，， 于是于是 f g：：A→C也是单射的，因此也是单射的，因此A ≤≤· C 优势的性质优势的性质优势的性质优势的性质说说明明q该定理为证明集合之间的等势提供了有力的工具该定理为证明集合之间的等势提供了有力的工具q构造两个单射构造两个单射f：：A AB B 和和 g g：：B BA A函数容易集合等势函数容易集合等势例题例题例题例题例题：例题：证明证明[0,1][0,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证明证明证明证明 {0,1}{0,1}N N≈[0,1)≈[0,1)(1) 设设x [0,1)，，0.x1x2…是是x的的二进制表示二进制表示。

     为了使表示唯一，规定表示式中不允许出现连续无数个为了使表示唯一，规定表示式中不允许出现连续无数个1     例如例如 x＝＝0.1010111，，应按规定记为应按规定记为0.1011000     对于对于x，，如下定义如下定义f：：[0,1)→{0,1}N，，使得使得      f(x) = tx，，且且tx：：N→{0,1}，， tx(n) = xn+1，，n = 0,1,2,…     例如例如 x = 0.10110100…，，则对应于则对应于x的函数的函数tx是是：： n  0 1 2 3 4 5 6 7…tx(n)   1 0 1 1 0 1 0 0…     易见易见tx∈∈{0,1}N，，且对于且对于x,y∈∈[0,1)，，x≠y，，必有必有tx ≠ ty，，     即即f(x) ≠ f(y)     所以所以，，f：：[0,1)→{0,1}N是单射的是单射的 (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)证明证明证明证明 {0,1}{0,1}N N≈[0,1)≈[0,1)总结总结总结总结qN ≈ Z ≈ Q ≈ N×NqR ≈ [a,b] ≈ (c,d) ≈ {0,1}N ≈ P(N)其中其中[a,b]，，(c,d)代表任意的实数闭区间和开区间代表任意的实数闭区间和开区间q{0,1}A ≈ P(A)qN ＜＜·· RqA ＜＜·· P(A)8.3.2 8.3.2 8.3.2 8.3.2 集合的基数集合的基数集合的基数集合的基数 q上一节我们只是抽象地讨论了集合的上一节我们只是抽象地讨论了集合的等势与优势等势与优势。

q本节将进一步研究度量集合的势的方法本节将进一步研究度量集合的势的方法q最简单的集合是有穷集尽管前面已经多次用到最简单的集合是有穷集尽管前面已经多次用到““有穷集有穷集””这一概念，当时只是直观地理解成含有有限多个元素的集合，这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直没有精确地给出有穷集的定义为解决这个问题我们但一直没有精确地给出有穷集的定义为解决这个问题我们需要先定义自然数和自然数集合需要先定义自然数和自然数集合 定义定义8.10 8.10 设设a为为集合，称集合，称a∪{∪{a} }为为a的的后继后继，记作，记作a+，，即即 a+=a∪∪{a} 例例 考虑空集的一系列后继考虑空集的一系列后继   + =  ∪∪{}={}    ++ = {}+= {}∪∪{{}}= {,{}}= {, +}   +++ ={,{}}+= {,{}}∪∪{{,{}}}= {,{},{,{}}}= {, +, ++ }后继后继后继后继 说说明明q前边的集合都是后边集合的元素。

前边的集合都是后边集合的元素q前边的集合都是后边集合的子集前边的集合都是后边集合的子集利用后继的性质，可以考虑以构造性的方法用集合来给出自利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，然数的定义，即即 0=1=0+＝＝+ ＝＝{}＝＝{0}2=1+＝＝{}+ ＝＝{}∪∪{{}}＝＝{,{}}＝＝{0,1}3＝＝2+＝＝{,{}}+＝＝{,{},{,{}}}＝＝ {0,1,2}    …n＝＝{0, 1, …, n 1}…说说明明自然数的定义自然数的定义自然数的定义自然数的定义 这种定义没有概括出自然数的共同特征这种定义没有概括出自然数的共同特征定义定义8.11 8.11 设设A为为集合，如果满足下面的两个条件：集合，如果满足下面的两个条件：（（1））∈∈A（（2）） a(a∈∈A→a+∈∈A) 称称A是是归纳集归纳集例如例如：下面的集合：下面的集合{, +, ++, +++,…}{, +, ++, +++, … , a, a+, a++, a+++, …}           都是归纳集。

都是归纳集归纳集归纳集归纳集归纳集 定义定义8.128.12 自然数自然数（（1 1）一个）一个自然数自然数n是属于每一个归纳集的集合是属于每一个归纳集的集合2 2））自然数集自然数集N是所有归纳集的交集是所有归纳集的交集说明说明：：根据定义根据定义8.12得到的自然数集得到的自然数集 N 恰好由恰好由, +, ++,  +++,…等集合构成而这些集合正是构造性方法所定义等集合构成而这些集合正是构造性方法所定义的全体自然数的全体自然数 例如：例如：自然数都是集合，集合的运算对自然数都适用自然数都是集合，集合的运算对自然数都适用2∪∪5＝＝{0,1}∪∪{0,1,2,3,4}＝＝{0,1,2,3,4}＝＝53∩∩4＝＝{0,1,2}∩∩{0,1,2,3}＝＝{0,1,2}＝＝3    4-2＝＝{0,1,2,3}-{0,1}={2,3} 2××3＝＝{0,1}××{0,1,2}＝＝{<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>} 自然数自然数自然数自然数n n n n和自然数集合和自然数集合和自然数集合和自然数集合N N N 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,1>}f2 ＝＝{<0,0>,<1,1>,<2,0>}f3 ＝＝{<0,0>,<1,1>,<2,1>}f4 ＝＝{<0,1>,<1,0>,<2,0>}f5 ＝＝{<0,1>,<1,0>,<2,1>}f6 ＝＝{<0,1>,<1,1>,<2,0>}f7 ＝＝{<0,1>,<1,1>,<2,1>} 举例举例举例举例 （（1）） 对任何自然数对任何自然数n，，有有n ≈ n。

2）） 对任何自然数对任何自然数n, m，，若若m   n，，则则m ≈ n3）） 对任何自然数对任何自然数n, m，，若若m∈∈n，，则则m   n4）） 对任何自然数对任何自然数n和和m，，以下三个式子：以下三个式子：       m∈∈n，，m ≈ n，， n∈∈m必成立其一且仅成立其一必成立其一且仅成立其一5）） 自然数的相等与大小顺序自然数的相等与大小顺序       对任何自然数对任何自然数m和和n，，有有m = n  m ≈ n m < n  m∈∈n 自然数的性质自然数的性质自然数的性质自然数的性质 定义定义8.138.13 有穷集、无穷集有穷集、无穷集（（1 1）一个集合是）一个集合是有穷的有穷的当且仅当它与某个自然数当且仅当它与某个自然数等势等势；；（（2 2）如果一个集合不是有穷的，就称作）如果一个集合不是有穷的，就称作无穷集无穷集例如：例如：q {a,b,c}是有穷集，是有穷集，    因为因为3＝＝{0,1,2}，且，且{a,b,c}≈{0,1,2}＝＝3qN和和R都是无穷集，都是无穷集，     因为没有自然数与因为没有自然数与N和和R等势。

等势q任何有穷集只与唯一的自然数等势任何有穷集只与唯一的自然数等势说说明明有穷集和无穷集有穷集和无穷集有穷集和无穷集有穷集和无穷集 定义定义8.14 8.14 （（1 1）对于有穷集合）对于有穷集合A，，称与称与A等势等势的那个唯一的自然数为的那个唯一的自然数为A的基的基数数，，记作记作card A，，即即   card A＝＝ n  A ≈ n （（对于有穷集对于有穷集A，， card A也可以记作也可以记作|A|））（（2 2））自然数集合自然数集合N的基数记作的基数记作0，即，即card N =0（（3 3））实数集实数集R的基数记作的基数记作（读作阿列夫），即（读作阿列夫），即card R =基数基数基数基数( ( ( (cardinalitycardinality) ) ) ) 定义定义8.15 8.15 设设A, B为集合，则为集合，则（（1））card A＝＝card B  A≈B（（2））card A≤card B  A ≤·≤· B（（3））card A < < card B  card A≤card B∧∧card A≠card B例如：例如：qcard Z ＝＝ card Q ＝＝ card N×N ＝＝ 0qcard P(N) ＝＝ card 2N ＝＝ card [a,b] ＝＝ card (c,d) ＝＝q0<说明说明：集合的基数就是集合的势，基数越大，势就越大。

集合的基数就是集合的势，基数越大，势就越大基数的相等和大小基数的相等和大小基数的相等和大小基数的相等和大小 关于基数的说明关于基数的说明关于基数的说明关于基数的说明 q由于对任何集合由于对任何集合A都满足都满足A ≤ P(A)，，所以有所以有 card A < < card P(A)，，这说明这说明不存在最大的基数不存在最大的基数q将已知的基数按从小到大的顺序排列就得到：将已知的基数按从小到大的顺序排列就得到： 0, 1, 2, …, n, …, 0, , …q0, 1, 2…, n, … 是全体自然数，是是全体自然数，是有穷基数有穷基数q0, , … 是是无穷基数无穷基数q0是最小的无穷基数是最小的无穷基数，，后面还有更大的基数，如后面还有更大的基数，如 card P(R)等可数集可数集可数集可数集定义定义8.168.16 设设A为集合，若为集合，若card A≤0，，则称则称A为为可数集可数集(enumerable)或或可列集例如：例如： q{a,b,c}、、5、、整数集整数集Z、、有理数集有理数集Q、、N×N等都是可数集等都是可数集。

q实数集实数集R不是可数集，与不是可数集，与R等势的集合也不是可数集等势的集合也不是可数集 对于任何的可数集，都可以找到一个对于任何的可数集，都可以找到一个“数遍数遍”集合中全体集合中全体元素的顺序回顾前边的可数集，特别是无穷可数集，都元素的顺序回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的是用这种方法来证明的说说明明（（1 1）可数集的任何子集都是可数集可数集的任何子集都是可数集 一个集合的无限子集若不可数，则该集合也不可数一个集合的无限子集若不可数，则该集合也不可数2 2）两个可数集的并是可数集两个可数集的并是可数集3 3）两个可数集的笛卡儿积是可数集两个可数集的笛卡儿积是可数集4 4）可数个可数集的笛卡儿积仍是可数集可数个可数集的笛卡儿积仍是可数集5 5）无穷集）无穷集A A的幂集的幂集P P( (A A) )不是可数集不是可数集可数集的性质可数集的性质可数集的性质可数集的性质 例例8.118.11 求下列集合的求下列集合的基数基数1））T＝＝{x | x是单词是单词“BASEBALL”中的字母中的字母}（（2））B＝＝{x | x∈∈R∧∧x2=9∧∧2x=8}（（3））C＝＝P(A), A={1, 3, 7, 11}（（1））由由T＝＝{B, A, S, E, L}知知，，card T＝＝5。

2））由由B＝＝可知，可知，card B＝＝03））由由|A|＝＝4可知可知，，card C＝＝card P(A)＝＝|P(A)|＝＝24＝＝16解答解答例例例例8.11 8.11 8.11 8.11 方法一方法一由由card A＝＝0，，card B＝＝n，，可知可知A, B都是可数集都是可数集令令A={a0, ,a1 , , a2 , , …}，，B={b0 , , b1 , , b2 , ,… , , bn 1}对任意的对任意的，， ∈∈A×B，，有有         ＝＝   i ＝＝ k∧∧j ＝＝ l定义函数定义函数 f：：A×B→Nf()＝＝in+j,  i＝＝0,1,…,  j＝＝0,1,…,n 1由于由于 f 是是A×B到到N的的双射双射函数，所以函数，所以card A×B＝＝card N＝＝例例例例8.128.128.128.12解答解答例例例例8.128.128.128.12 设设设设A A,  , B B为集合为集合为集合为集合，，，，且且且且card card A A＝＝＝＝0 0，，，， card  card B B＝＝＝＝n n，，，，n n是自然是自然是自然是自然数数数数，，，，n n≠0≠0。

求求求求card card A A× ×B B例例例例8.128.128.128.12方法二方法二方法二方法二因为因为因为因为card card A A＝＝＝＝0 0，，，，card card B B＝＝＝＝n n，，，，所以所以所以所以A A,  , B B都是可数集都是可数集都是可数集都是可数集根据性质（根据性质（根据性质（根据性质（3 3）可知，）可知，）可知，）可知，A A× ×B B也是可数集，所以，也是可数集，所以，也是可数集，所以，也是可数集，所以，card card A A× ×B B≤ ≤0 0   当当当当B B≠ ≠时，时，时，时，card card A A≤ ≤card card A A× ×B B，，，，   这就推出这就推出这就推出这就推出0 0≤ ≤card card A A× ×B B综合所述，综合所述，综合所述，综合所述，card card A A× ×B B ＝＝＝＝ 0 0本章主本章主本章主本章主要内容要内容要内容要内容q集合等势的定义集合等势的定义q等势的性质等势的性质q集合优势的定义集合优势的定义q优势的性质优势的性质q重要的集合等势以及优势的结果重要的集合等势以及优势的结果q自然数及其自然数集合的定义自然数及其自然数集合的定义q可数集与不可数集可数集与不可数集q集合的基数集合的基数   本章学习要求本章学习要求本章学习要求本章学习要求q能够证明两个集合等势。

能够证明两个集合等势q能够证明一个集合优势于另一个集合能够证明一个集合优势于另一个集合q知道什么是可数集与不可数集知道什么是可数集与不可数集q会求一个简单集合的基数会求一个简单集合的基数  等势的证明方法等势的证明方法等势的证明方法等势的证明方法q证明集合证明集合A A与与B B等势的方法等势的方法–直接构造从直接构造从A A到到B B的双射函数的双射函数 f需要证明需要证明 f 的满射性和的满射性和f f的单射性的单射性–构造两个单射函数构造两个单射函数f f：：A AB B 和和 g g：：B BA A 给出函数给出函数f f和和g g，，证明证明f f和和g g的单射性的单射性–利用等势的传递性利用等势的传递性–直接计算直接计算A A与与B B的基数，得到的基数，得到card card A A＝＝ card card B Bq证明集合证明集合A A与自然数集合与自然数集合N N等势的方法等势的方法–找到一个找到一个““数遍数遍””A A中元素的顺序中元素的顺序例题选讲例题选讲例题选讲例题选讲1 1．已知．已知A＝＝{n7 7|n∈∈N}，，B ＝＝{n109|n ∈∈N }，，求下列各题：求下列各题：（（1 1））card  A（（2 2））card B（（3 3））card (A∪∪B)（（4 4））card (A∩B)（（1））构造双射函数构造双射函数 f：：NA，， f(n)=n7 7 ，，因此因此 card A＝＝0。

2））构造双射函数构造双射函数 g：：NA，， g(n)=n109，，因此因此 card B＝＝03 3））可数集的并仍旧是可数集可数集的并仍旧是可数集( (或者由于或者由于A∪∪B  N) )，， 因此因此card (A∪∪B)≤0，，          但是但是 0 ＝＝card A≤card (A∪∪B)，，          从而得到从而得到 card (A∪∪B)＝＝04 4））因为因为7与与109互素互素，，card (A∩B)＝＝{n7 109 | n N}，， 与（与（1 1）类似得到）类似得到 card (A∩B)＝＝0 解答解答例题选讲例题选讲例题选讲例题选讲2.2.已已知知card A＝＝0，，且且card B<

假设假设card (A B)< < 0，，那么存在自然数那么存在自然数m，，使使                   card (A B)＝＝m从而得到，从而得到，card A＝＝card ((A B)∪∪B)≤n+m与与card A＝＝0矛盾因此，因此，card (A B)＝＝0解答解答复习复习复习复习————特特特特征函数征函数征函数征函数q设设A为集合，对于任意的为集合，对于任意的A  A，，A 的的特征函数特征函数      A   : A→{0,1}定义为定义为1，，a∈∈A   0，， a∈∈A A   A  (a) ＝＝q举例举例: : A的每一个子集的每一个子集A 都对应于一个特征函数，不同的子都对应于一个特征函数，不同的子集对应于不同的特征函数集对应于不同的特征函数例如例如A＝＝{a,b,c}, 则有则有     ＝＝{<{,<>,,<>,}>}，， {a} ＝＝{<{,<>,,<>,}>} {a,b} ＝＝{<{,<>,,<>,}>}例题选讲例题选讲例题选讲例题选讲( ( ( (略略略略) ) ) )1．． 设设A, B为二集合，证明：如果为二集合，证明：如果A≈B，，则则P(A)≈P(B)。

因为因为A≈B，，因此存在双射函数因此存在双射函数f：：AB，，存在反函数存在反函数f  1：：BA，，构造函数构造函数g：：P(A) P(B),             g(T) = f(T)，， T A （（这里的这里的f(T)是是T在函数在函数f的像的像））首先，证明首先，证明g的满射性的满射性     对于任何对于任何S B，，存在存在f  1(S)  A，，且且g(f  1(S)) = f f  1(S) = S 所以所以g是满射的是满射的其次，证明其次，证明g的单射性的单射性         g(T1) = g(T2)  f(T1) = f(T2)                                 f  1(f(T1) = f  1(f(T2))                                 IA(T1) = IA(T2)  T1=T2     综合上述，可知综合上述，可知P(A)≈P(B)两个可数集的并集为可数集两个可数集的并集为可数集两个可数集的并集为可数集两个可数集的并集为可数集设设A A、、B B为可数集，不妨设为可数集，不妨设A∩BA∩B＝＝。

1 1)若两个集合都是有穷集，比如若两个集合都是有穷集，比如A A＝＝{a{a0 0,a,a1 1,…,a,…,an-1n-1} }，，B B＝＝{b{b0 0,b,b1 1,…,b,…,bm-1m-1} }，，那么那么card (A∪B)card (A∪B)＝＝n+m≤n+m≤0 2)如果其中一个集合是有穷集，另一个是无穷可数集，比如如果其中一个集合是有穷集，另一个是无穷可数集，比如A A＝＝{a{a0 0,a,a1 1,…,a,…,an-1n-1} }，，card Bcard B＝＝0如下构造双射如下构造双射h：：A∪∪B→N，，当当x∈∈A时，时，x＝＝ai，，h(x)＝＝i；；当当x∈∈B时，时，x＝＝bj，，j＝＝0,1,…，，那么那么h(x)＝＝j+n3)如果如果card A＝＝card B＝＝ 0 ，，那么存在双射那么存在双射f：：A→N和和g：：B→N如下构造函数如下构造函数h：：A∪∪B→N当当x∈∈A且且f(x)＝＝i时，时，h(x)＝＝2i当当x∈∈B且且g(x)＝＝j时，时，h(x)＝＝2j+1显然显然h为双射综上所述，综上所述，card (A∪∪B)＝＝ 0 。