7 §1.2 映射 可数集与基数 教学目的 继续介绍集合论的基础内容, 如映射, 基数, 可数集与不 可数集等. 本节要点 一一对应的思想与方法贯穿本节的核心.基数的概念.可数 集的讨论,都要用的一一对应的方法.证明两个不同的集对等, 从而具有相 同的基数, 特别地, 要证明一个集是可数集, 有时需要一定的技巧, 因而 具有一定的难度, 通过较多的例题和习题, 使学生逐步掌握其方法和技巧. 映射 在数学分析课程中我们对函数已经很熟悉. 在数学分析中函数的定义域通常是 n R的子集, 值域是实数集或者复数集. 若将函数的定义域和值域换成一般的集, 就得到映 射的概念. 定义1设,X Y是两个非空集. f是某一法则，使得按照这个法则, 对每个,Xx∈ 有 唯一的的Yy∈与之对应, 则称f为从X到Y的映射, 记为 .: YXf → 当y与x 对应时, 称y为x在映射f下的像, 记为).(xfy = 称X为f的定义域. 在上述定义中, 若Y是实数集或复数集, 习惯上仍称f为函数. 设A为X的子集. 称Y的子集 )}(,:{ xfyAxy =∈使得存在 为A在映射f下的像, 记为).(Af 特别地, 称)(Xf为f的值域. 设B是Y的子集. 称X 的子集 })(:{ Bxfx ∈ 为集B在映射f下的原像, 记为).( 1 Bf ? 在数学分析课程中研究的函数当然是一种映射. 除此之外, 我们还经常会遇到许多其 它的映射. 例如, 定积分可以看作是可积函数集到实数集的映射, 求导运算可以看作是可导 函数集到函数集的映射, 线性代数中的线性变换就是线性空间到线性空间的映射等. 设YXf →:是X到Y的映射. 若,)( YXf = 则称f为到上的(或满射). 若当 21 xx ≠时，),()( 21 xfxf ≠ 则称f是一一的(或单射). 如果f是X到Y的一一的到上的 映射, 有时我们称f是X与Y之间的一个一一对应. 8 映射的逆与复合 设f是X到Y的一一的到上的映射. 则对每个,Yy∈ 存在唯一的 Xx∈使得.)( yxf = 因此我们可以定义一个Y到X的映射g如下: 对每个,Yy∈ 令 ,)( xyg = 其中x是X中的唯一存在的满足yxf =)(的元. 称这样定义的映射g为f的 逆映射, 记为. 1? f 显然逆映射是反函数概念的推广. 若f是X到Y的一一的到上的映射, 则由逆映射的定义知道成立以下等式: .,))((,,))(( 11 YyyyffXxxxff ∈=∈= ?? 设YXf →:和ZYg →:分别是X到Y的和Y到Z的映射. 令 .)),(()( Xxxfgxh ∈= 则h是X到Z的映射. 称h为f与g的复合映射, 记为.fgnull 显然复合映射是复合函数 概念的推广. 利用复合映射的记号, (1)式可以写成 ., 11 YX iffiff == ?? nullnull 其中 X i和 Y i分别为X和Y上的恒等映射. 设A是X的子集, f和f ~ 分别是A到Y的和X到Y的映射. 若对每个Ax∈成立 ),()( ~ xfxf = 则称f ~ 是f在X上的延拓, 称f是f ~ 在A上的限制, 记为. ~ A ff = 定义2设BA,是两个非空集. 若存在一个从A到B的一一的到上的映射, 则称A与B 是对等的, 记为A ~ .B 此外规定?~ .? A与B是对等就是两个集的元素可以建立一一对应的关系. 对等关系具有如下性质: ).i( A ~ .A (反身性) . ).ii(若A ~ ,B 则B ~ .A (对称性). ).iii(若A ~ ,B B ~ ,C 则A ~ .C (传递性) . 基数 有时我们需要比较两个集的元素的多与少. 对于有限集, 我们可以通过数出每个 集的元素的个数的方法比较两个集的元素的多与少. 两个无限集是否可以比较元素的多与 少? 初看起来, 既然无限集都有无限多个元素, 似乎两个无限集不能比较元素的多与少. 现 在我们换一种方式来来考虑这个问题. 在比较两个有限集的元素的多与少的时候,还可以采 用另一种方法, 即“一一对应”的方法. 如果A与B之间能建立一个一一对应, 则A与B具 有同样多的元素. 如果A与B的一个真子集之间能建立一个一一对应, 则A的元素比B的 元素少.这种方法也适用于无限集的情形. 先看两个例子. 例1 数集)1,0(与实数集 1 R对等. 对任意),1,0(∈x 令π? ) 2 1 tan()( ?= xx . 则?是)1,0(到 1 R的一一对应的映射. 因 9 此)1,0( ~ 1 R . (见图2—1). 图2—1 在例1中, )1,0(是 1 R的真子集, 但)1,0(与 1 R对等. 一个集和自己的一个真子集对等, 这在有限集是不可能. 可以证明这是无限集的一个特征. 由于)1,0(与 1 R对等, 在这个意义下, 我们可以说, )1,0(与 1 R具有一样多的元素.又 如圆周去掉一点后与全直线对等. 两个半径不同的圆作为平面上的点集是对等的(图2-2). 图2-2 例2 数集)1,0(与自然数集N不对等. 证明 首先注意到, 区间)1,0(的实数可以表示为十进制无穷小数: null 321 .0 aaax = , P x′ X Y O x x x′ O π) 2 1 tan( ?= xy X Y y x O 2 1 1 10 其中 i a是9,,1,0 null中的数字, 并且有无限多个 i a不为零.例如5.0表示为,499.0 null 不表示 为null500.0 . 这样, )1,0(中每个实数的表示是惟一的. 用反证法. 若)1,0(中的实数可以与自然数建立一一对应的关系. 则)1,0(的全部实数 可以排序成为一个无穷序列: },,,,{)1,0( 321 nullxxx= ,.0 )1( 3 )1( 2 )1( 11 nullaaax = ,.0 )2( 3 )2( 2 )2( 12 nullaaax = ,.0 )3( 3 )3( 2 )3( 13 nullaaax = .nullnullnullnullnullnullnullnullnull 现在考虑小数 null 3210 .0 aaax = , 其中 i a是9,,1,0 null中的数字, null,,, )3( 33 )2( 22 )1( 11 aaaaaa ≠≠≠ . (例如, 若1 )( ≠ i i a ,令 1= i a . 若,1 )( = i i a 则令2= i a ).则)1,0( 0 ∈x , 但是 i xx ≠ 0 ),3,2,1( null=i (因为至少 0 x与 i x的第i位数字不同).这与假设矛盾! 因此)1,0(中的实数不能与自然数建立一一对应 的关系. 由于自然数集N与区间)1,0(的一个子集}, 1 1 ,, 3 1 , 2 1 { nullnull +n 对等, 结合例1, 我们有 理由说自然数集N比区间)1,0(的元素少. 以上两个例子表明, 利用一一对应的思想, 可以比较两个无限集的元素的多与少. 下面 我们把这种想法精确化. 定义3 对于所有相互对等的集, 我们称他们给予同一个记号, 称为这其中每一个集的 基数. 集A的基数记为.A 由基数的定义, 如果A与B对等, 则.BA = 规定集},,2,1{ nnull的基数为n , 空集?的基数为0. 用符号ω表示自然数集N的基数. 实数集 1 R的基数用c表示, 称之为连续基数. 因此有限集的基数等于该集中元素的个数. 这样, 集的基数就是有限集的元素个数的推广. 定义4 设BA,是两个集. 若A与B的一个子集对等, 则称A的基数小于或等于B的 基数, 记为.BA ≤ 若A与B的一个子集对等, 但A与B不对等, 则称A的基数小于B的 基数, 记为.BA < 有限集与无限集 利用对等的概念, 我们可以给出有限集和无限集的严格定义. 设A 11 是一非空集. 若存在一个自然数,n 使得A与集},,2,1{ nnull对等, 则称A为有限集. 规定空 集是有限集. 若A不是有限集, 则称A为无限集. 下面先讨论一类重要的集—可数集,即具有可数基数的集. 可数集 在无限集中, 有一类是以后会经常遇到的, 也是最简单的, 就是下面要讨论的 可数集. 定义5 与自然数集N对等的集称为可数集. 换言之, 具有可数基数的集称为可数集. 由可数集的定义知道, 若A是可数集, B与 A对等, 则B是可数集. 等价定义: 集A是可数集当且仅当A的所有元素可以编号排序成为一个无穷序列 (编 号排序必须既无遗漏, 也无重复.): }.,,,,{ 21 nullnull n aaaA = 可数集的简单例: 自然数集N , 整数集Z , 奇自然数集, 偶自然数集. 它们的元素可以分别排序成为无穷序列 },,,,,2,2,1,1,0{ nullnull nn ??? },,12,,5,3,1{ nullnull ?n }.,2,,6,4,2{ nullnull n 由例1知道, 区间)1,0(和实数集 1 R都不是可数集. 后面我们将要看到更多的可数集, 它们的可数性不是这样显而易见的. 例如我们马上 要证明有理数集是可数集. 以下定理表明, 可数集在无限集中具有最小基数. 定理1 任何无限集必包含一个可数子集. 换言之, 若A为无限集, 则.A≤ω 证明 在A中任取一个元, 记为. 1 a 假定 11 ,, ?n aa null已经取定. 由于A是无限集, 故 },,{ 11 ? ? n aaA null不空. 在},,{ 11 ? ? n aaA null中任取一个元, 记为. n a 这样一直作下去, 就 得到A中的一个无穷序列}.{ n a 令},,,{ 211 nullaaA = 则 1 A是A的一个可数子集. ■ 推论 .c<ω 证明 由定理1, .c≤ω 由例1和例2, .)1,0( ω≠=c 因此.c<ω ■ 定理2 若A是可数集, B是有限集, 则BA∪是可数集. 证明 不妨设.?=∩ BA 若不然, 由于),( ABABA ?∪=∪用AB ?代替B即可. 设},,,{ 21 nullaaA = }.,,{ 1 n bbB null=则BA∪得元素可以编号排序为 }.,,,,{ 211 nullnull aabbBA n =∪ 因此BA∪是可数集.■ 定理3 可数集的任何无限子集还是可数集. 证明 设A为可数集,则A的所有元素可以编号排序成为一个无穷序列 12 .,,,, 21 nullnull n aaa 设B是A的一个无限子集. 则B中的元素是上述序列的一个子列 .,,, , 21 nullnull k nnn aaa 将 k n a与k对应, 即知B是可数集. ■ 定理 4 若),2,1( null=nA n 是一列可数集, 则 ∪ n i i A 1= 和 ∪ ∞ =1i i A都是可数集. 即可数集的 有限并或可数并还是可数集. 证明 设,,2,1},,,,{ ,21 nullnullnull == naaaA nmnnn 是一列可数集. 有限并的情形: ∪ n i i A 1= 的元素可以按下面的方式编号排序: null nullnullnullnullnullnullnullnullnullnull null null 321 2322212 1312111 nnnn aaaA aaaA aaaA ↓↓↓ ↓↓↓ ↓↓↓ 可数并的情形: ∪ ∞ =1n n A的元素可按如下方式编号排序: 1 A 11 a 12 a 13 a null 14 a 2 A 21 a ↗ 22 a↗ 23 a ↗null 24 a 3 A 31 a ↗ 32 a↗null 33 a 4 A 41 a ↗null 42 a ………………………………… 在编号排序时, 若碰到前面已编号的重复元素, 则跳过去不再编号排序. 于是 ∪ n i i A 1= 和 ∪ ∞ =1n n A的元素都可以按上述方式编号排序成为一无穷序列. 所以 ∪ n i i A 1= 和 ∪ ∞ =1n n A都是可数 集.■ 定理5 若),2,1( null=nA n 是一列有限集, 则 ∪ ∞ =1n n A是有限集或可数集. 证明 留作习题. 13 思考题 任意个有限集或可数集的并是否一定是可数集. 为什么? 利用可数集的运算性质,从一些已知的可数集,可以得到更多的可数集. 例3 有理数集Q是可数集. 事实上, 对每个,,2,1 null=n 令}., 3 , 2 , 1 { null nnn A n = 则每个 n A是可数集. 由于正 有理数集 + Q = , 1 ∪ ∞ =n n A 由定理4知道 + Q是可数集. 类似地, 可以证明负有理数集 ? Q是 可数集. 因此=Q + Q ∪ ? Q }0{∪是可数集. 定理6 若 n AA ,, 1 null是可数集, 则它们的乘积集 n AA ××null 1 是可数集. 证明 用数学归纳法. 当1=n时定理的结论当然成立. 假定 11 ? ×× n AA null是可数集. 设}.,,{ 21 nullaaA n = 对每个,1≥k 令 }.{ 11 knk aAAE ×××= ? null 则 k E与 11 ? ×× n AA null对等, 故每个 k E是可数集. 由于 . 1 1 ∪ null ∞ = =×× k kn EAA 因此由定理4知道 n AA ××null 1 是可数集. 图2—3是2=n的情形.■ 图2—3 推论 设 n II ,, 1 null是n个可数集. 则},,:{ 11,, 1 nnii IiIiaA n ∈∈= null null 是可数集. k E 1 A 2 A 1 a 2 a 3 a i a 1 b 2 b k b 14 证明 将 n ii a ,, 1 null 与),,( 1 n ii null对应, 即知A与 n II ××null 1 对等. 由定理6, n II ××null 1 是 可数集, 故A是可数集.■ 例4设 n Q是 n R中的有理点(即座标全为有理数的点)的全体所成的集. 则 . nullnullnullnullnull null n QQQ ××= n 由例3和定理6, n Q是可数集. 例5 整系数多项式的全体是可数集. 证明 对任意自然数,n 令 n P是n次整系数多项式的全体. 将n次整系数多项式 n n xaxaa +++ null 10 与),,( 10 n aaa null对应, 即知 n P ~ ∏ = n i i 0 Z (其中ZZZ = ?10 ,, n null， }0{?= ZZ n ). 由定理5, ∏ = n i i 0 Z是可数集, 故 n P是可数集. 再利用定理4, ∪ ∞ ?0n n P是可数 集. 即整系数多项式的全体是可数集.■ 实数x称为是一个代数数, 若x是某个整系数多项式的根. 定理7 代数数的全体是可数集. 证明 由例5, 可以设整系数多项式的全体为}.,,{ 21 nullpp又设 },:{是代数数xxA = }:{的零点是 nn pxxA = , .,2,1 null=n 则每个 n A是有限集, 并且 . 1 ∪ ∞ = = n n AA 即A可以表示为一列有限集的并. 利用定理5, 代数数的全体是可数集.■ 具有连续基数的集 定理8 若A为无限集, B为有限集或可数集, 则.ABA =∪ 证明 不妨设,?=∩ BA 否则用AB ?代替B即可. 因为A为无限集, 由定理1, A 包含一个可数子集. 1 A 由于BA ∪ 1 是可数集, 故)( 1 BA ∪ ~ 1 A . 又因为 ,)()( 11 ?=∪∩? BAAA 因此我们有 BAAABA ∪∪?=∪ 11 )( )()( 11 BAAA ∪∪?= ~ ..)( 11 AAAA =∪? 15 这表明.ABA =∪ ■ 由定理8知道, 若A的基数是,c 则A加上或去掉一个可数集后, 其基数不变. 换言之, 相对应具有连续基数的集而言, 可数集是无足轻重的. 例6 无理数集的基数为.c 证明 记无理数集为,A 有理数集为Q . 则由定理8, 我们有 . 1 cAA ==∪= RQ 因此无理数集的基数为.c ■ 设x是一个实数. 若x不是代数数, 则称x为超越数. 若类似于例6可以知道, 超越数 的全体具有基数.c 这表明超越数是存在的, 而且要比代数数多得多. 定理9 直线上的任何区间的基数都是.c 证明 由例1知道区间)1,0(具有基数.c 由于},1,0{)1,0(]1,0[ ∪= 由定理8, .)1,0(]1,0[ c== 类似可证区间]1,0(和)1,0[都具有基数.c令 ),,()1,0(: ba→? xabax )()( ?+=? . 则?一一对应的映射. 因此.),( cba = 类似可证任何有界区间都具有基数.c 利用函数 xtan作适当的映射, 可以证明任何无界区间都具有基数.c ■ 思考题 试直接给出区间]1,0[与)1,0(的元素之间的一个对应关系, 从而证明 .]1,0[ c= p进制小数 设1>p为一自然数, }{ n a是一个数列, 其中 n a只取1,,1,0 ?pnull为值. 则级数 nullnull ++++ n n p a p a p a 2 2 1 1 (1) 收敛, 并且其和].1,0[∈x 我们可以把级数(2)的和记为 ..0 21 nullnull n aaax = (2) 称上式的右边为p进制小数. 在p进制小数(2)中, 若有无穷个,0≠ n a 则称之为无限p进 制小数, 否则称之为有限p进制小数. 这样, 一个无限p进制小数表示区间]1,0(中的一个 实数. 引理10无限p进制小数与区间]1,0(中的实数一一对应. 证明 以2=p为例. 一般情形是类似的. 上面我们已经知道, 一个无限二进制小数表 示区间]1,0(中的一个实数. 反过来, 设].1,0(∈x 则存在0 1 =k或1, 使得 , 2 1 2 11 + ≤< k x k 16 令. 11 ka = 又存在0 2 =k或1, 使得 . 2 1 222 2 21 2 21 + +≤<+ kk x kk 令. 22 ka = 这样一直作下去, 得到一个数列},{ n a 其中.10或= n a 并且容易知道有无穷 个.1= n a 显然由这样的数列}{ n a构成的级数(1)的部分和 n s满足 .1, 2 1 0 ≥<?< nsx n n 令∞→n得到.lim n n sx ∞→ = 即x是级数(1)的和. 于是x可以唯一地表示成无限二进制小数 ..0 21 nullnull n aaax = ■ 二元数列 若}{ n a为一数列, 并且每个 n a只取0或1两个可能的值, 则称}{ n a为二元数 列. 定理11 ).i(二元数列的全体所成的集具有连续基数.c ).ii(设X为一可数集, 则由X的全体子集所成的集)(XP具有连续基数.c 证明 ).i(将二元数列的全体所成的集记为,A 无限二进制小数的全体记为.E 则由引 理10, .]1,0( cE == 对每个自然数,1≥n 令 }.,0:),,{( 21 niaAaaB in >=∈= null 再令. 1 ∪ ∞ = = n n BB 则B是可数个有限集的并. 由定理4, B是可数集. 作映射 ,: EBAf →? 使得 ..0)),,(( 2121 nullnull aaaaf = 则f是一一的到上的, 故BA? ~ .E 因此.cEBA ==? 由定理8知道, .cBAA =?= ).ii(设}.,,,,{ 21 nullnull n xxxX =作)(XP到二元数列的集A的映射? ,使得 ),,,()( 21 nullaaC =? ∈C ).(XP 其中 ? ? ? ? ∈ = .0 ,1 Cx Cx a n n n 若 若 则?是一一的到上的. 故)(XP ~ A , 因此.)( cAX ==P ■ 注1 从定理11的证明过程知道, 集 }0,10:),,{( 21 ≠== ii aaaaA并且有无限多个或null 17 也具有连续基数.c 这个结果在后面§1.4例1中会用到. 若A是一个有限集, 其元素的个数为.n 容易知道A有 n 2个子集. 用基数表示就是 .2)( A A =P 由于这个原因, 对一个有限集或无限集A , 若,aA = 则用 a 2表示)(XP的 基数. 这样, 定理11 )ii(的结论可表示成.2 c= ω 小 结 本节利用一一对应的思想, 给出了集的基数和可数集的定义. 集的基数是有限 集元素的个数在无限集的推广. 可数集是具有最小基数的无限集. 可数集经过有限或可数 并运算后仍是可数集. 有理数集是一个重要的可数集. 直线上的区间是典型的不可数集. 证 明一个给定的集是可数集或不可数集是应当掌握的基本技巧. 习 题 见习题一,第10题—第17题.