实变函数：§1.2--§1.4 集合的基数与（不）可数集合

8 § 1.2~§ 1.4 集合的基数与（不）可数集合 教学目的 介绍映射, 基数, 可数集与不可数集等概念和它们的属性. 本节要点 一一对应的思想与方法是贯穿本节 的核心.基数的概念，可 数集的讨论都要用一一对应的方法.证明两个集对等或具 有相同的基数, , 有时需要一定的技巧, 因而具有一定难度, 通过较多的例题和习题, 使学 生逐步掌握其中的技巧. 映射 在数学分析课程中我们对函数已经很熟悉 . 其中函数的定义域 通常是 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 9 的一一的到上的映射 , 有时我们称 f 是 X 与 Y 之间的一个一一对应 . 映射的逆与复合 设 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 的复合映射 , 记为 .fgo 显然复合映 射是复合函数概念的推广 . 利用复合映射的记号 , (1)式可以写成 ., 11 YX iffiff == ?? oo 其中 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 具有同样多的元素. 如果 10 A与 B 的一个真子集之间能建立一个一一对应, 则 A的元素比 B 的元素少. 这种方法也适用于无限集的情形. 先看两个例子. 例1 数集 )1,0( 与实数集 1 R 对等 . 对任意 ),1,0(∈x 令 π? ) 2 1 tan()( ?= xx . 则 ? 是 )1,0( 到 1 R 的一一对应 的映射 . 因此 )1,0(~ 1 R . 在例1中, )1,0( 是 1 R 的真子集, 但 )1,0( 与 1 R 对等. 一个集和自己的 一个真子集对等,这在有限集是不可能. 可以证明这是无限集的一个特征. 由于 )1,0( 与 1 R 对等, 在这个意义下, 我们可以说, )1,0( 与 1 R 具有一 样多的元素. 例2 数集 )1,0( 与自然数集 N 不对等 . 证明 首先注意到 , 区间 )1,0( 的实数可以表示为十进制无穷小数: L 321 .0 aaax = , 其中 i a 是 9,,1,0 L 中的数字, 并且有无限多个 i a 不为零.例如 5.0 表示为 ,499.0 L 不表示为 L500.0 . 这样, )1,0( 中每个实数的表示是惟一的. 用反证法. 若 )1,0( 中的实数可以与自然数建立一一对应的关系 . 则 )1,0( 的全部实数可以排序成为一个无穷序列: },,,,{)1,0( 321 Lxxx= . ,.0 ,.0 ,.0 )3( 3 )3( 2 )3( 13 )2( 3 )2( 2 )2( 12 )1( 3 )1( 2 )1( 11 LLLLLLLLL L L L aaax aaax aaax = = = 现在考虑小数 L 3210 .0 aaax = , 其中 i a 是 9,,1,0 L 中的数字, L,,, )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( L=i (因为至少 0 x 与 i x 的第 i 位数字不同).这与假设矛盾! 因此 )1,0( 中的实数不能与自然数建立一一对应的关系 . 11 由于自然数集 N 与区间 )1,0( 的一个子集 }, 1 1 ,, 3 1 , 2 1 { LL +n 对等, 结 合例 1, 我们有理由说自然数集 N 比区间 )1,0( 的元素少. 以上两个例子表明, 利用一一对应的思 想, 可以比较两个无限集的元 素的多与少. 下面我们把这种想法精确化. 定义 3 对于所有相互对等的集 , 我们给予它们同一个记号 , 称为这其 中每一个集的基数 . 集 A的基数记为 .A 由基数的定义 , 如果 A与 B 对等 , 则 .BA = 规定集 },,2,1{ nL 的基数为 n , 空集 ?的基数为 0. 用符号 ω 表示自然 数集 N 的基数 . 实数集 1 R 的基数用 c 表示 , 称之为连续基数 . 因此有限集 的基数等于该集中元素的个数 . 这样 , 集的基数就是有限集的元素个数的 推广 . 定义 4 设 BA, 是两个集 . 若 A与 B 的一个子集对等 , 则称 A的基数小 于或等于 B 的基数 , 记为 .BA ≤ 若 A与 B 的一个子集对等 , 但 A与 B 不对 等 , 则称 A的基数小于 B 的基数 , 记为 .BA < 有限集与无限集 利用对等的概念, 我们可以给出有限集和无限集的 严格定义. 设 A是一非空集， 若存在一个自然数 ,n 使得 A与集 },,2,1{ nL 对 等, 则称 A为有限集. 规定空集是有限集. 若 A 不是有限集, 则称 A 为无 限集. 在无限集中, 有一类重要的也是最简单的集—可数集,即具有可数基 数的集，以后我们会经常遇到的. 定义 5 与自然数集 N 对等的集称为可数集 . 由可数集的定义知道 , 集 A 是可数集当且仅当 A 的所有元素可以编号 排成一个无穷序列 : }.,,,,{ 21 LL n aaaA = 自然数集 N , 整数集 Z , 奇自然数集 , 偶自然数集都给我们以可数集的例 . 因为它们的元素可以分别排成为无穷序列 },,,,,2,2,1,1,0{ LL nn ??? },,12,,5,3,1{ LL ?n }.,2,,6,4,2{ LL n 12 由例 1 知道 , 区间 )1,0( 和实数集 1 R 都不是可数集. 下面定理表明, 可数集在无限集中具有最小基数. 定理 1 任何无限集必包含一个可数子集 . 换言之 , 若 A为无限集 , 则 .A≤ω 证明 在 A中任取一个元 , 记为 . 1 a 假定 11 ,, ?n aa L 已经取定 . 由于 A是 无限集 , 故 },,{ 11 ? ? n aaA L不空. 在 },,{ 11 ? ? n aaA L 中任取一个元 , 记为 . n a 这样一直作下去 , 就得到 A中的一个无穷序列 }.{ n a 令 },,,{ 211 LaaA = 则 1 A 是 A的一个可数子集 . ■ 推论 .c<ω 证明 由定理 1, .c≤ω 由例 1 和例 2, .)1,0( ω≠=c 因此 .c<ω ■ 定理 2 若 A是可数集 , B 是有限集 , 则 BA∪ 是可数集 . 证明 不妨设 .?=∩ BA 若不然 , 由于 ),( ABABA ?∪=∪ 用 AB ? 代替 B 即可 . 设 },,,{ 21 LaaA = }.,,{ 1 n bbB L= 则 BA∪ 得元素可以编号排 序为 }.,,,,{ 211 LL aabbBA n =∪ 因此 BA∪ 是可数集 . ■ 定理 3 可数集的任何无限子集还是可数集 . 证明 设 A 为可数集 , 则 A 的所有元素可以编号排成一个无穷序列 .,,,, 21 LL n aaa 设 B 是 A 的一个无限子集 . 则 B 中的元素是上述序列的一个子列 .,,, , 21 LL k nnn aaa 将 k n a 与 k 对应 , 即知 B 是可数集 . ■ 定理 4 若 ),2,1( L=nA n 是一列可数集 , 则 U n i i A 1= 和 U ∞ =1i i A 都是可数集 . 即可数集的有限并或可数并还是可数集 . 证明 设 ,,2,1},,,,{ ,21 LLL == naaaA nmnnn 是一列可数集 . 在有限并的情形 : U n i i A 1= 的元素可以按下面的方式编号排序 : 13 L LLLLLLLLLL L L 321 2322212 1312111 nnnn aaaA aaaA aaaA → ↑↓ ↓↑↓ ↓↑↓ → 可数并的情形 : U ∞ =1n n A 的元素可按如下方式编号排序 : 1 A 11 a → 12 a 13 a → L 14 a ↙ ↗ ↙ 2 A 21 a 22 a 23 a 24 a L ↓ ↗ ↙ 3 A 31 a 32 a 33 a L ↙ 4 A 41 a 42 a 43 α L ………………………………… 在编号排序时, 若碰到前面已编号的重复元素, 则跳过去不再编号排序. 于是 U n i i A 1= 和 U ∞ =1n n A 的元素都可以按上述方式编号排序成为一无穷序列 . 所 以 U n i i A 1= 和 U ∞ =1n n A 都是可数集 . ■ 思考题 (1) 若 ),2,1( L=nA n 是一列有限集 , 则 U ∞ =1n n A 是有限集或可 数集 . (2) 任意个可数集的并是否一定是可数集? 14 利用可数集的运算性质,从一些已知的 可数集,可以得到更多的可数 集. 例 3 有理数集 Q 是可数集 . 事实上 , 对每个 ,,2,1 L=n 令 },, 3 , 2 , 1 { L nnn A n = 则每个 n A 是可数集 . 由于正有理数集 + Q =, 1 U ∞ =n n A 由定理 4 知道 + Q 是可 数集 . 类似地 , 可以证明负有理数集 ? Q 是可数集 . 因此 =Q + Q ∪ ? Q }0{∪ 是可数集 . 定理 5 若 n AA ,, 1 L 是可数集 , 则它们的乘积集 n AA ××L 1 是可数集 . 证明 用数学归纳法 . 当 1=n 时定理的结论当然成立 . 假定 11 ? ×× n AA L 是可数集 . 设 }.,,{ 21 LaaA n = 对每个 ,1≥k 令 }.{ 11 knk aAAE ×××= ? L 则 k E 与 11 ? ×× n AA L 对等 , 故每个 k E 是可数集 . 由于 . 1 1 U L ∞ = =×× k kn EAA 因此由定理 4 知道 n AA ××L 1 是可数集 . ■ 推论 设 n II L, 1 是 n 个可数集 . 则 },,:{ 11,, 1 nnii IiIiaA n ∈∈= L L 是可数 集 . 证明 将 n ii a ,, 1 L 与 ),,( 1 n ii L 对应 , 即知 A 与 n II ××L 1 对等 . 由定理 6, n II ××L 1 是可数集 , 故 A是可数集 . ■ 例 4 设 n Q 是 n R 中的有理点 (即座标全为有理数的点 )的全体所成的集 . 则 . 43421 L n QQQ ××= n 由例 3 和定理 6, n Q 是可数集 . 15 例 5 整系数多项式的全体是可数集 . 证明 对任意自然数 ,n 令 n P 是 n 次整系数多项式的全体 . 则 ),,()( 10 0 n n i i i aaaxaf L= ∑ = 是 n P 到 ∏ + = 1 1 n i i Z (其中 ZZ = i ， }0{ 1 ?= + ZZ n )的 一一的到上的映射 . 因此 n P ~ ∏ + = 1 1 n i i Z .由定理 6, ∏ + = 1 1 n i i Z 是可数集 , 故 n P 是 可数集 . 由定理 4, U ∞ =0n n P 是可数集 , 即整系数多项式的全体是可数集 .■ 实数 x 称为是一个代数数 , 若 x 是某个整系数多项式的根 . 定理 6 代数数的全体是可数集 . 证明 由于每个整系数多项式的根只有有限个 , 由例 5 知道 , 代数数 的全体可以表示成可数个有限集的并 . 又显然代数数的全体是一个无限集 . 因此由定理 3 知道 , 代数数的全体是可数集 . ■ 下面简单讨论具有连续基数的集 . 定理 7 若 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 =∪? 这表明 .ABA =∪ ■ 由定理 8 知道 , 若 A的基数是 ,c 则 A加上或去掉一个可数集后 , 其基 数不变 . 换言之 , 相对应具有连续基数的集而言 , 可数集是无足轻重的 . 例 6 无理数集的基数为 .c 证明 记无理数集为 ,A 有理数集为 Q . 则由定理 8, 我们有 . 1 cAA ==∪= RQ 16 因此无理数集的基数为 .c ■ 设 x 是一个实数 . 若 x 不是代数数 , 则称 x 为超越数 . 若类似于例 6 可 以知道 , 超越数的全体具有基数 .c 这表明超越数是存在的 , 而且要比代数 数多得多 . 定理 8 直线上的任何区间的基数都是 .c 证明 由例 1 知道区间 )1,0( 具有基数 .c 由于 },1,0{)1,0(]1,0[ ∪= 由定 理 8, .)1,0(]1,0[ c== 类似可以证明区间 ]1,0( 和 )1,0[ 都具有基数 .c 由此 利用伸缩变换可以证明任何有界区间都具有基数 .c 利用类似于例 1 的方 法可以证明任何无界区间都具有基数 .c ■ 思考题 试直接给出区间 ]1,0[ 与 )1,0( 的元素之间的一个对应关系, 从 而证明 .]1,0[ c= p 进制小数 设 1>p 为一自然数 , }{ n a 是一个数列 , 其中 n a 只取 1,,1,0 ?pL 为值 . 则级数 LL ++++ n n p a p a p a 2 2 1 1 (1) 收敛 , 并且其和 ].1,0[∈x 我们可以把级数 (2)的和记为 ..0 21 LL n aaax = (2) 称上式的右边为 p 进制小数 . 在 p 进制小数 (2)中 , 若有无穷个 ,0≠ n a 则 称之为无限 p 进制小数 , 否则称之为有限 p 进制小数 . 这样 , 一个无限 p 进制小数表示区间 ]1,0( 中的一个实数 . 引理 9 无限 p 进制小数与区间 ]1,0( 中的实数一一对应 . 证明 以 2=p 为例 . 一般情形是类似的 . 上面我们已经知道 , 一个无 限二进制小数表示区间 ]1,0( 中的一个实数 . 反过来 , 设 ].1,0(∈x 则存在 0 1 =k 或 1, 使得 , 2 1 2 11 + ≤< k x k 令 . 11 ka = 又存在 0 2 =k 或 1, 使得 . 2 1 222 2 21 2 21 + +≤<+ kk x kk 17 令 . 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 LL n aaax = 引理证毕 . 二元数列 若 }{ n a 为一数列 , 并且每个 n a 只取 0 或 1 两个可能的值 , 则称 }{ n a 为二元数列 . 定理 10 ).i( 二元数列的全体所成的集具有连续基数 .c ).ii( 设 X 为一可数集 , 则由 X 的全体子集所成的集 )(XP 具有连续 基数 .c 证明 ).i( 将二元数列的全体所成的集记为 ,A 无限二进制小数的全 体记为 .E 则由引理 10, .]1,0( cE == 对每个自然数 ,1≥n 令 }.,0:),,{( 21 niaAaaB in >=∈= L 再令 . 1 U ∞ = = n n BB 则 B 是可数个有限集的并 . 由定理 4, B 是可数集 . 作映射 ,: EBAf →? 使得 ..0)),,(( 2121 LL aaaaf = 则 f 是一一的到上的 , 故 BA? ~ .E 因此 .cEBA ==? 由定理 8 知道 , .cBAA =?= ).ii( 设 }.,,,,{ 21 LL n xxxX = 作 )(XP 到二元数列的集 A的映射 ? ,使得 ),,,()( 21 LaaC =? ∈C ).(XP 其中 ? ? ? ? ∈ = .0 ,1 Cx Cx a n n n 若 若 则 ?是一一的到上的 . 故 )(XP ~ A , 因此 .)( cAX ==P 定理证毕 . 18 注 1 从定理 11 的证明过程知道 , 集 },0,10:),,{( 21 ≠== ii aaaaA 并且有无限个或L 也具有连续基数 .c 这个结果在后面§ 1.4 例 1 中会用到 . 若 A 是一个有限集 , 其元素的个数为 .n 容易知道 A 有 n 2 个子集 . 用 基数表示就是 .2)( A A =P 由于这个原因 , 对一个有限集或无限集 A , 若 ,aA = 则用 a 2 表示 )(XP 的基数 . 这样 , 定理 11 )ii( 的结论可表示成 .2 c= ω 小结 本节利用一一对应的思想 , 给出了集的基数和可数集的定义 . 集 的基数是有限集元素个数推广 . 可数集是具有最小基数的无限集 . 可数集 经过有限或可数并运算后仍是可数集 . 有理数集是一个重要的可数集 . 直 线上的区间是典型的不可数集 . 证明一个给定的集是可数集或不可数集是 应当掌握的基本技巧 . 习题 1.见 P18 习题,第 1 题—第 2 题. 2.见 P22 习题,第 1 题—第 6 题.