离散数学：第9章 集合的基数

1、 1第第9 9章章 集合的基数集合的基数离散数学离散数学 2本章说明本章说明q本章的主要内容本章的主要内容集合的等势及其性质集合的等势及其性质重要的等势或不等势的结果重要的等势或不等势的结果集合的优势及其性质集合的优势及其性质自然数与自然数集合自然数与自然数集合集合的基数集合的基数可数集可数集 39.1 9.1 集合的等势与优势集合的等势与优势9.2 9.2 集合的基数集合的基数 本章小结本章小结 习题习题 作业作业本章内容本章内容 4定义定义9.19.1 设设A, BA, B是集合，如果存在着从是集合，如果存在着从A A到到B B的的双射函数双射函数，就，就称称A A和和B B是等势是等势（

2、same cardinality）的的，记作，记作ABAB。 如果如果A A不与不与B B等势，则记作等势，则记作A BA B。9.1 集合的等势与优势集合的等势与优势q通俗的说，集合的势是量度集合所含元素多少的量。通俗的说，集合的势是量度集合所含元素多少的量。q集合的势越大，所含的元素越多。集合的势越大，所含的元素越多。 5（1）ZN。20:,( )210 xxfZNf xxx则则f是是Z到到N的双射函数。的双射函数。 从而证明了从而证明了ZN。等势集合的实例等势集合的实例(1)(1) 6等势集合的实例等势集合的实例(2)(2)（2） NNN。(1)():,(,)2mnmnfNNNfm nm

3、 双射函数双射函数 7等势集合的实例等势集合的实例(3)(3)（3 3）NQNQ。 把所有形式为把所有形式为p p/ /q q ( (p p, ,q q为整数且为整数且q q0) 0) 的数排成一张表。的数排成一张表。-2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/

4、4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414以以0/10/1作为第一个数，按照箭头规定的顺序可以作为第一个数，按照箭头规定的顺序可以“数遍数遍”表中表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。同一个有理数。 8等势集合的实例等势集合的实例(4)(4)（4）(0,1)R。 其中实数区间其中实数区间 (0,1)=x| xR0 x1。21:(0,1),( )tan2xfRf x令双射函数令双射函数则则 f 是是(0,1)到到R的双射函数。从而证明了的

5、双射函数。从而证明了(0,1)R 。 9等势集合的实例等势集合的实例(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 2 10等势集合的实例等势集合的实例(6)(6)（6 6）对任何）对任何a, bR，ab， 0,1a,

6、b。 双射函数双射函数f：0,1a,b，f(x)(b a)x+a。 11例例9.29.2 设设A为任意集合，则为任意集合，则P(A)0,1A。构造构造f：P(A)0,1A， f(A )= A ， A P(A)。其中其中 A 是集合是集合A 的特征函数的特征函数。(1)(1)易证易证 f 是单射的是单射的。(2)(2)对于任意的对于任意的 g0,1A， 那么有那么有 g：A0,1。令令 B=x| xAg(x)=1 则则B A，且且 B=g，即即 BP(A)，使得使得f(B)=g。 所以所以 f 是满射的。是满射的。由等势定义得由等势定义得P(A)0,1A。例例9.29.2证明证明复习复习 12定

7、理定理9.19.1 设设A，B，C是任意集合，是任意集合，（1）AA。（2）若若AB，则则BA。（3）若若AB，BC，则则AC。（1 1） IA是从是从A到到A的双射，因此的双射，因此AA。（2） 假设假设AB ，存在，存在 f : : AB是双射，是双射，那么那么 f 1 : : BA是从是从B到到A的双射，所以的双射，所以BA。（3） 假设假设AB，BC，存在存在 f : :AB，g: :BC是双射，是双射，则则f g : : AC是从是从 A 到到 C 的双射的双射。所以所以AC。等势的性质等势的性质证明证明 13q N Z Q NNq R 0,1 (0,1)q 任何的实数区间（开区间、

8、闭区间以及半开半闭的区间）任何的实数区间（开区间、闭区间以及半开半闭的区间）都与实数集合都与实数集合R R等势。等势。q 问题：问题：N N和和R R是否等势？是否等势？若干等势集合若干等势集合 14（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 康托定理

9、康托定理（1）N R。（2）对任意集合对任意集合A都有都有A P(A)。康托定理康托定理分析分析 15（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.

10、a1(n)a2(n) 令令y的表示式为的表示式为0.b1b2，并且满足并且满足bi ai(i)，i=1,2, ,，则则y0,1， 但但y与上面列出的任何一个函数值都不相等与上面列出的任何一个函数值都不相等。即即f不是满射的。不是满射的。 所以所以，N R。康托定理康托定理 16康托定理康托定理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

11、，矛盾矛盾。若若b B，则则b f (b)，于是由于是由B的定义知，的定义知， bB，矛盾。矛盾。 17（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(

12、N)。q综合前面的结果，可知综合前面的结果，可知N 0,1N 。q实际上，实际上，P(N)P(N)，0,10,1N N和和R R都是比都是比N“N“更大更大”的集合。的集合。 18定义定义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

13、) R N N N优势优势RN 19定理定理9.39.3 设设A, B, C是任意的集合，则是任意的集合，则（1）A A。（2）若若A B且且B A，则则AB。（3）若若A B且且B C, 则则A C 。证明：证明：（1 1）IA是是A到到A的单射的单射，因此因此A A。（2 2）证明略。）证明略。（3 3）假设）假设A B且且B C，那么存在单射，那么存在单射 f:AB:AB，g:BC:BC， 于是于是 f g：AC也是单射的，因此也是单射的，因此A C 。优势的性质优势的性质说说明明q 该定理为证明集合之间的等势提供了有力的工具该定理为证明集合之间的等势提供了有力的工具。q 构造两个单射构

14、造两个单射f：A AB B 和和 g g：B BA A函数容易集合等势函数容易集合等势。 20例题例题例题：例题：证明证明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 21证明证明 0,1N0,1)(1) 设设x 0,1)，0.x1x2是是x的的二进制表示二进制表示。 为了使表示唯一，规定表示式中不允许出现连续无数个为了使表示唯一，规定表示式中不允许出现连续无数个1。 例如例如 x0.1010111，

15、应按规定记为应按规定记为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是单射的。是单射的。 22(2) 定义函数定义函数g：0,1N0,1)。 g的映射法则恰好与的映射法则恰好与

16、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) 23总结总结q N Z Q NNq

17、 R a,b (c,d) 0,1N P(N)其中其中a,b，(c,d)代表任意的实数闭区间和开区间代表任意的实数闭区间和开区间。q 0,1A P(A)q N Rq A P(A) 249.2 9.2 集合的基数集合的基数 q 上一节我们只是抽象地讨论了集合的等势与优势。上一节我们只是抽象地讨论了集合的等势与优势。q 本节将进一步研究度量集合的势的方法。本节将进一步研究度量集合的势的方法。q 最简单的集合是有穷集。尽管前面已经多次用到最简单的集合是有穷集。尽管前面已经多次用到“有穷集有穷集”这一概念，当时只是直观地理解成含有有限多个元素的这一概念，当时只是直观地理解成含有有限多个元素的集合，但一直

18、没有精确地给出有穷集的定义。为解决这个集合，但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。问题我们需要先定义自然数和自然数集合。 25定义定义9.3 9.3 设设a为为集合，称集合，称aa 为为a的的后继后继，记作，记作a+，即即 a+=aa。 例例9.39.3 考虑空集的一系列后继。考虑空集的一系列后继。 + = = + = += = ,= , + + =,+= ,= ,= , +, + 后继后继 说说明明q 前边的集合都是后边集合的元素。前边的集合都是后边集合的元素。q 前边的集合都是后边集合的子集。前边的集合都是后边集合的子集。 26利用后继的性质，可

19、以考虑以构造性的方法用集合来给出自利用后继的性质，可以考虑以构造性的方法用集合来给出自然数的定义，然数的定义，即即 0=1=0+ 02=1+ ,0,132+,+, 0,1,2 n0, 1, , n 1说说明明自然数的定义自然数的定义 这种定义没有概括出自然数的共同特征。这种定义没有概括出自然数的共同特征。 27定义定义9.4 9.4 设设A为为集合，如果满足下面的两个条件：集合，如果满足下面的两个条件：（1）A（2） a(aAa+A) 称称A是是归纳集归纳集。例如例如：下面的集合：下面的集合, +, +, +, +, +, +, , a, a+, a+, a+, 都是归纳集。都是归纳集。归纳集

20、归纳集 28定义定义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

21、-20,1,2,3-0,1=2,3 230,10,1,2, 自然数自然数n n和自然数集合和自然数集合N N的定义的定义 29P(1)P(0),00,1230,10,1,2f | f：0,1,20,1f0,f1,f7其中其中f0,f1 ,f2 ,f3 ,f4 ,f5 ,f6 ,f7 , 举例举例 30（1） 对任何自然数对任何自然数n，有有n n。（2） 对任何自然数对任何自然数n, m，若若m n，则则m n。（3） 对任何自然数对任何自然数n, m，若若mn，则则m n。（4） 对任何自然数对任何自然数n和和m，以下三个式子：以下三个式子： mn，m n， nm必成立其一且仅成立其一。必成

22、立其一且仅成立其一。（5） 自然数的相等与大小顺序自然数的相等与大小顺序 对任何自然数对任何自然数m和和n，有有m = n m n m n mn 自然数的性质自然数的性质 31定义定义9.69.6 有穷集、无穷集有穷集、无穷集（1 1）一个集合是）一个集合是有穷的有穷的当且仅当它与某个自然数等势；当且仅当它与某个自然数等势；（2 2）如果一个集合不是有穷的，就称作）如果一个集合不是有穷的，就称作无穷集无穷集。例如：例如：q a,b,c是有穷集，是有穷集， 因为因为30,1,2，且，且a,b,c0,1,23qN和和R都是无穷集，都是无穷集， 因为没有自然数与因为没有自然数与N和和R等势。等势。q

23、任何有穷集只与唯一的自然数等势。任何有穷集只与唯一的自然数等势。说说明明有穷集和无穷集有穷集和无穷集 32定义定义9.7 9.7 （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 =基数基数( (cardinality) ) 33定义定义9

24、.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说明说明：集合的基数就是集合的势，基数越大，势就越大。：集合的基数就是集合的势，基数越大，势就越大。基数的相等和大小基数的相等和大小 34关于基数的说明关于基数的说明 q 由于对任何集合由于对任何集合A都满足都满足A P(A)，所以有所以有 card

25、 A card P(A)，这说明这说明不存在最大的基数不存在最大的基数。q 将已知的基数按从小到大的顺序排列就得到：将已知的基数按从小到大的顺序排列就得到： 0, 1, 2, , n, , 0, , q 0, 1, 2, n, 是全体自然数，是是全体自然数，是有穷基数有穷基数。q 0, , 是是无穷基数无穷基数。q 0是最小的无穷基数是最小的无穷基数，后面还有更大的基数，如后面还有更大的基数，如 card P(R)等。等。 35可数集可数集定义定义9.99.9 设设A为集合，若为集合，若card A0，则称则称A为为可数集可数集(enumerable)或或可列集。可列集。例如：例如： q a,

26、b,c、5、整数集整数集Z、有理数集有理数集Q、NN等都是可数集。等都是可数集。q 实数集实数集R不是可数集，与不是可数集，与R等势的集合也不是可数集。等势的集合也不是可数集。 对于任何的可数集，都可以找到一个对于任何的可数集，都可以找到一个“数遍数遍”集合中全体集合中全体元素的顺序。回顾前边的可数集，特别是无穷可数集，都元素的顺序。回顾前边的可数集，特别是无穷可数集，都是用这种方法来证明的。是用这种方法来证明的。说说明明 36（1 1）可数集的任何子集都是可数集。）可数集的任何子集都是可数集。 一个集合的无限子集若不可数，则该集合也不可数。一个集合的无限子集若不可数，则该集合也不可数。（2

27、2）两个可数集的并是可数集。）两个可数集的并是可数集。（3 3）两个可数集的笛卡儿积是可数集。）两个可数集的笛卡儿积是可数集。（4 4）可数个可数集的笛卡儿积仍是可数集。）可数个可数集的笛卡儿积仍是可数集。（5 5）无穷集）无穷集A A的幂集的幂集P P( (A A) )不是可数集。不是可数集。可数集的性质可数集的性质 37例例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

28、可知，可知，card B0。（3）由由|A|4可知可知，card Ccard P(A)|P(A)|2416。解答解答例例9.4 9.4 38方法一方法一由由card A0，card Bn，可知可知A, B都是可数集。都是可数集。令令A=a0, ,a1 , , a2 , , ，B=b0 , , b1 , , b2 , , , , bn 1。对任意的对任意的， AB，有有 i kj l定义函数定义函数 f：ABNf()in+j, i0,1, j0,1,n 1由于由于 f 是是AB到到N的双射函数，所以的双射函数，所以card ABcard N。例例9.59.5解答解答例例9.59.5 设设A, B

29、为集合为集合，且且card A0， card Bn，n是自然数是自然数，n0。求求card AB。 39例例9.59.5方法二方法二因为因为card A0，card Bn，所以所以A, B都是可数集。都是可数集。根据性质（根据性质（3）可知，）可知，AB也是可数集，所以，也是可数集，所以，card AB0 当当B时，时，card Acard AB， 这就推出这就推出0card AB综合所述，综合所述，card AB 0 40本章主要内容本章主要内容q 集合等势的定义集合等势的定义q 等势的性质等势的性质q 集合优势的定义集合优势的定义q 优势的性质优势的性质q 重要的集合等势以及优势的结果重要

30、的集合等势以及优势的结果q 自然数及其自然数集合的定义自然数及其自然数集合的定义q 可数集与不可数集可数集与不可数集q 集合的基数集合的基数 41本章学习要求本章学习要求q 能够证明两个集合等势。能够证明两个集合等势。q 能够证明一个集合优势于另一个集合。能够证明一个集合优势于另一个集合。q 知道什么是可数集与不可数集。知道什么是可数集与不可数集。q 会求一个简单集合的基数。会求一个简单集合的基数。 42等势的证明方法等势的证明方法q 证明集合证明集合A A与与B B等势的方法等势的方法直接构造从直接构造从A A到到B B的双射函数的双射函数 f需要证明需要证明 f 的满射性和的满射性和f f

31、的单射性。的单射性。构造两个单射函数构造两个单射函数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中元素的顺序。中元素的顺序。 43例题选讲例题选讲1 1已知已知An7 7|nN，B n109|n N ，求下列各题：求下列各题：（1 1）card A（2 2）c

32、ard B（3 3）card (AB)（4 4）card (AB)（1）构造双射函数构造双射函数 f：NA， f(n)=n7 7 ，因此因此 card A0。（2）构造双射函数构造双射函数 g：NA， g(n)=n109，因此因此 card B0。（3 3）可数集的并仍旧是可数集可数集的并仍旧是可数集( (或者由于或者由于AB N) )， 因此因此card (AB)0， 但是但是 0 card Acard (AB)， 从而得到从而得到 card (AB)0。（4 4）因为因为7与与109互素互素，card (AB)n7 109 | n N， 与（与（1 1）类似得到）类似得到 card (AB)0 。解答解答 44例题选讲例题选讲2.2.已知已知card A0，且且card B card A，求求card (A B) 。由由A B A，得到得到 card (A B)card A，即即card(A B)0 。由由card B card A可知，可知，B为有穷集，为有穷集，即存在自然数即存在自然数n，使得使得card B=n。假设假设card (A B) 0，那么存在自然数那么存在自然数m，使使 card (A B)m。从而得到，从而得到，card Acard (A B)B)n+m与与card A0矛盾。矛盾。因此，因此，card (A B)0。解答解答