§12映射可数集与基数 教学目的继续介绍集合论的基础内容,如映射,基数,可数集与不可 数集等 本节要点一一对应的思想与方法贯穿本节的核心基数的概念可数 集的讨论都要用的一一对应的方法证明两个不同的集对等,从而具有相 同的基数,特别地,要证明一个集是可数集,有时需要一定的技巧,因而具 有一定的难度,通过较多的例题和习题,使学生逐步掌握其方法和技巧 映射在数学分析课程中我们对函数已经很熟悉.在数学分析中函数的定义域通常 是R"的子集,值域是实数集或者复数集.若将函数的定义域和值域换成一般的集,就得 到映射的概念 定义1设X,Y是两个非空集.∫是某一法则,使得按照这个法则,对每个 ∈X,有唯一的的y∈Y与之对应,则称∫为从X到Y的映射,记为 ∫:X→Y 当y与x对应时,称y为x在映射∫下的像,记为y=f(x).称X为∫的定义域 在上述定义中,若Y是实数集或复数集,习惯上仍称∫为函数 设A为X的子集.称Y的子集 {y:存在x∈A,使得y=f(x)} 为A在映射∫下的像,记为∫(A).特别地,称∫(X)为∫的值域.设B是Y的子集称 X的子集 x:f(x)∈B} 为集B在映射∫下的原像,记为f-(B) 在数学分析课程中研究的函数当然是一种映射.除此之外,我们还经常会遇到许多 其它的映射.例如,定积分可以看作是可积函数集到实数集的映射,求导运算可以看作是 可导函数集到函数集的映射,线性代数中的线性变换就是线性空间到线性空间的映射等 设∫:X→Y是X到Y的映射.若f(x)=Y,则称∫为到上的(或满射)若当 x1≠x2时,f(x1)≠∫(x2),则称∫是一一的(或单射).如果厂是X到Y的一一的到上 的映射,有时我们称∫是X与Y之间的一个一一对应 映射的逆与复合设∫是x到Y的一一的到上的映射则对每个y∈Y,存在唯一
11 1.2 映射 可数集与基数 教学目的 继续介绍集合论的基础内容, 如映射, 基数, 可数集与不可 数集等. 本节要点 一一对应的思想与方法贯穿本节的核心.基数的概念.可数 集的讨论,都要用的一一对应的方法.证明两个不同的集对等, 从而具有相 同的基数, 特别地, 要证明一个集是可数集, 有时需要一定的技巧, 因而具 有一定的难度, 通过较多的例题和习题, 使学生逐步掌握其方法和技巧. 映射 在数学分析课程中我们对函数已经很熟悉. 在数学分析中函数的定义域通常 是 n R 的子集, 值域是实数集或者复数集. 若将函数的定义域和值域换成一般的集, 就得 到映射的概念. 定义 1 设 X , Y 是两个非空集. f 是某一法则 使得按照这个法则, 对每个 x ∈ X , 有唯一的的 y ∈Y 与之对应, 则称 f 为从 X 到Y 的映射, 记为 f : X → Y. 当 y 与 x 对应时, 称 y 为 x 在映射 f 下的像, 记为 y = f (x). 称 X 为 f 的定义域. 在上述定义中, 若Y 是实数集或复数集, 习惯上仍称 f 为函数. 设 A 为 X 的子集. 称Y 的子集 {y : 存在x ∈ A, 使得y = f (x)} 为 A 在映射 f 下的像, 记为 f (A). 特别地, 称 f (X ) 为 f 的值域. 设 B 是Y 的子集. 称 X 的子集 {x : f (x) ∈ B} 为集 B 在映射 f 下的原像, 记为 ( ). 1 f B − 在数学分析课程中研究的函数当然是一种映射. 除此之外, 我们还经常会遇到许多 其它的映射. 例如, 定积分可以看作是可积函数集到实数集的映射, 求导运算可以看作是 可导函数集到函数集的映射, 线性代数中的线性变换就是线性空间到线性空间的映射等. 设 f : X → Y 是 X 到Y 的映射. 若 f (X ) = Y, 则称 f 为到上的(或满射). 若当 1 2 x ≠ x 时 ( ) ( ), 1 2 f x ≠ f x 则称 f 是一一的(或单射). 如果 f 是 X 到Y 的一一的到上 的映射, 有时我们称 f 是 X 与Y 之间的一个一一对应. 映射的逆与复合 设 f 是 X 到Y 的一一的到上的映射. 则对每个 y ∈Y, 存在唯一
的x∈X使得f(x)=y.因此我们可以定义一个到X的映射g如下:对每个y∈Y, 令g()=x,其中x是X中的唯一存在的满足f(x)=y的元.称这样定义的映射g为 f的逆映射,记为∫-1.显然逆映射是反函数概念的推广.若f是X到Y的一一的到上 的映射,则由逆映射的定义知道成立以下等式 f-(f(x)=x,x∈X,f(f(y)=y,y∈Y 设∫:X→Y和g:Y→>Z分别是x到Y的和Y到Z的映射.令 h(x)=g((x),x∈X 则h是X到Z的映射称h为∫与g的复合映射,记为go∫.显然复合映射是复合函 数概念的推广.利用复合映射的记号,(1)式可以写成 f-°f=ix,fof=iy 其中x和i分别为X和y上的恒等映射 设A是X的子集,∫和∫分别是A到Y的和X到Y的映射.若对每个x∈A成立 f(x)=f(x),则称厂是∫在X上的延拓,称∫是在A上的限制,记为f=f4 定义2设A,B是两个非空集.若存在一个从A到B的一一的到上的映射,则称A 与B是对等的,记为A~B.此外规定~②. A与B是对等就是两个集的元素可以建立一一对应的关系 对等关系具有如下性质 (i).A~A.(反身性) (i)若A~B,则B~A(对称性) (i).若A~B,B~C,则A~C.(传递性 基数有时我们需要比较两个集的元素的多与少.对于有限集,我们可以通过数出 每个集的元素的个数的方法比较两个集的元素的多与少.两个无限集是否可以比较元素 的多与少?初看起来,既然无限集都有无限多个元素,似乎两个无限集不能比较元素的 多与少.现在我们换一种方式来来考虑这个问题.在比较两个有限集的元素的多与少的 时候,还可以采用另一种方法,即“一一对应”的方法.如果A与B之间能建立一个 对应,则A与B具有同样多的元素.如果A与B的一个真子集之间能建立一个 对应,则A的元素比B的元素少.这种方法也适用于无限集的情形.先看两个例子. 例1数集(0,1)与实数集R对等 对任意x∈(0,1),令Q(x)=tan(x-)x.则Q是(0,1)到R的一一对应的映射 因此(0,1)~R.(见图2-1)
12 的 x ∈ X 使得 f (x) = y. 因此我们可以定义一个Y 到 X 的映射 g 如下: 对每个 y ∈Y, 令 g( y) = x, 其中 x 是 X 中的唯一存在的满足 f (x) = y 的元. 称这样定义的映射 g 为 f 的逆映射, 记为 . −1 f 显然逆映射是反函数概念的推广. 若 f 是 X 到Y 的一一的到上 的映射, 则由逆映射的定义知道成立以下等式: ( ( )) , , ( ( )) , . 1 1 f f x = x x ∈ X f f y = y y ∈Y − − 设 f : X → Y 和 g :Y → Z 分别是 X 到Y 的和Y 到 Z 的映射. 令 h(x) = g( f (x)), x ∈ X. 则 h 是 X 到 Z 的映射. 称 h 为 f 与 g 的复合映射, 记为 g o f . 显然复合映射是复合函 数概念的推广. 利用复合映射的记号, (1)式可以写成 , . 1 1 X Y f f = i f f = i − − o o 其中 Xi 和 Yi 分别为 X 和Y 上的恒等映射. 设 A 是 X 的子集, f 和 f ~ 分别是 A 到Y 的和 X 到Y 的映射. 若对每个 x ∈ A 成立 ( ) ( ), ~ f x = f x 则称 f ~ 是 f 在 X 上的延拓, 称 f 是 f ~ 在 A 上的限制, 记为 . ~ A f = f 定义 2 设 A, B 是两个非空集. 若存在一个从 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 数集(0, 1) 与实数集 1 R 对等. 对任意 x ∈ (0, 1), 令ϕ )π 2 1 (x) = tan(x − . 则ϕ 是 (0, 1) 到 1 R 的一一对应的映射. 因此(0, 1) ~ 1 R . (见图 2 1)
F y=tan(x-÷)丌 X 图 在例1中,(0,1)是R的真子集,但(0,1)与R对等.一个集和自己的一个真子集 对等,这在有限集是不可能.可以证明这是无限集的一个特征 由于(0,1)与R对等,在这个意义下,我们可以说,(0,1)与R具有一样多的元 素.又如圆周去掉一点后与全直线对等.两个半径不同的圆作为平面上的点集是对等的 (图2-2 图2-2 例2数集(0,1)与自然数集M不对等 证明首先注意到,区间(0,1)的实数可以表示为十进制无穷小数 x=oaa
13 图 2 1 在例 1 中, (0, 1) 是 1 R 的真子集, 但(0, 1) 与 1 R 对等. 一个集和自己的一个真子集 对等,这在有限集是不可能. 可以证明这是无限集的一个特征. 由于 (0, 1) 与 1 R 对等, 在这个意义下, 我们可以说, (0, 1) 与 1 R 具有一样多的元 素.又如圆周去掉一点后与全直线对等. 两个半径不同的圆作为平面上的点集是对等的 (图 2-2). 图 2-2 例 2 数集(0, 1) 与自然数集N 不对等. 证明 首先注意到, 区间(0, 1) 的实数可以表示为十进制无穷小数: x = 0.a1 a2 a3L, P x′ X Y O x x x′ O )π 2 1 y = tan(x − X Y y O x 2 1 1
其中a1是0,1,…,9中的数字,并且有无限多个a1不为零.例如0.5表示为0.49…,不 表示为0.500…这样,(0,1)中每个实数的表示是惟一的 用反证法.若(0,1)中的实数可以与自然数建立一一对应的关系.则(0,1)的全部 实数可以排序成为一个无穷序列 (0,1)={x1,x2,x3,…}, x,=0.aaa x3=0.a0)a3)a 现在考虑小数 x0=0.a1a2a3… 其中a1是0,1…9中的数字,a1≠a,a2≠a2),a3≠a,…,(例如,若a≠1 令a1=1.若a1=1,则令a1=2).则x0∈(0,1),但是x≠x;(=12,3,…)(因 为至少x与x的第i位数字不同).这与假设矛盾!因此(0,1)中的实数不能与自然数建 立一一对应的关系 由于自然数集N与区间(0,1)的一个子集 23n+1…}对等,结合例1,我 们有理由说自然数集M比区间(0,1)的元素少 以上两个例子表明,利用一一对应的思想,可以比较两个无限集的元素的多与少.下 面我们把这种想法精确化 定义3对于所有相互对等的集,我们称他们给予同一个记号,称为这其中每一个集 的基数.集A的基数记为A 由基数的定义,如果A与B对等,则A=B 规定集{1,2,…,m}的基数为n,空集的基数为0.用符号O表示自然数集N的 基数实数集R的基数用c表示,称之为连续基数因此有限集的基数等于该集中元素 的个数.这样,集的基数就是有限集的元素个数的推广 定义4设A,B是两个集.若A与B的一个子集对等,则称A的基数小于或等于B 的基数,记为A≤B.若A与B的一个子集对等,但A与B不对等,则称A的基数小于 B的基数,记为A<B
14 其中 i a 是 0,1,L,9 中的数字, 并且有无限多个 i a 不为零.例如 0.5表示为 0.499L, 不 表示为0.500L. 这样, (0, 1) 中每个实数的表示是惟一的. 用反证法. 若 (0, 1) 中的实数可以与自然数建立一一对应的关系. 则 (0, 1) 的全部 实数可以排序成为一个无穷序列: (0, 1) { , , , }, = x1 x2 x3 L 0. , (1) 3 (1) 2 (1) x1 = a1 a a L 0. , (2) 3 (2) 2 (2) x2 = a1 a a L 0. , (3) 3 (3) 2 (3) x3 = a1 a a L LLLLLLLLL. 现在考虑小数 x0 = 0.a1 a2 a3L, 其中 i a 是 0,1,L,9 中的数字, a1 ≠ a1 (1) , a2 ≠ a2 (2) , a3 ≠ a3 (3) ,L. (例如, 若 1 ( ) ≠ i i a , 令 = 1 i a . 若 1, ( ) = i i a 则令 = 2 i a ).则 (0, 1) x0 ∈ , 但是 i x ≠ x 0 (i = 1, 2, 3,L) (因 为至少 0 x 与 i x 的第i 位数字不同).这与假设矛盾! 因此(0, 1) 中的实数不能与自然数建 立一一对应的关系. 由于自然数集N 与区间(0, 1) 的一个子集 , } 1 1 , , 3 1 , 2 1 { L L n + 对等, 结合例 1, 我 们有理由说自然数集N 比区间(0, 1) 的元素少. 以上两个例子表明, 利用一一对应的思想, 可以比较两个无限集的元素的多与少. 下 面我们把这种想法精确化. 定义 3 对于所有相互对等的集, 我们称他们给予同一个记号, 称为这其中每一个集 的基数. 集 A 的基数记为 A. 由基数的定义, 如果 A 与 B 对等, 则 A = B. 规定集{1, 2,L,n}的基数为 n , 空集∅ 的基数为 0. 用符号ω 表示自然数集 N 的 基数. 实数集 1 R 的基数用 c 表示, 称之为连续基数. 因此有限集的基数等于该集中元素 的个数. 这样, 集的基数就是有限集的元素个数的推广. 定义 4 设 A, B 是两个集. 若 A 与 B 的一个子集对等, 则称 A 的基数小于或等于 B 的基数, 记为 A ≤ B. 若 A 与 B 的一个子集对等, 但 A 与 B 不对等, 则称 A 的基数小于 B 的基数, 记为 A < B
有限集与无限集利用对等的概念,我们可以给出有限集和无限集的严格定义.设 A是一非空集.若存在一个自然数n,使得A与集{2…,n}对等,则称A为有限集.规 定空集是有限集.若A不是有限集,则称A为无限集 下面先讨论一类重要的集一可数集,即具有可数基数的集 可数集在无限集中,有一类是以后会经常遇到的,也是最简单的,就是下面要讨 论的可数集. 定义5与自然数集N对等的集称为可数集 换言之,具有可数基数的集称为可数集.由可数集的定义知道,若A是可数集,B 与A对等,则B是可数集 等价定义:集A是可数集当且仅当A的所有元素可以编号排序成为一个无穷序列 编号排序必须既无遗漏,也无重复 A={a1,a2,…,an,… 可数集的简单例:自然数集N,整数集Z,奇自然数集,偶自然数集 它们的元素可以分别排序成为无穷序列 {0,1,-1,2,-2,…,n,-n,…} {1,3,5, 由例1知道,区间(0,1)和实数集R都不是可数集 后面我们将要看到更多的可数集,它们的可数性不是这样显而易见的.例如我们马 上要证明有理数集是可数集.以下定理表明,可数集在无限集中具有最小基数. 定理1任何无限集必包含一个可数子集.换言之,若A为无限集,则O≤A 证明在A中任取一个元,记为a1假定a1,…,an1已经取定.由于A是无限集,故 A-{a1,…,an}不空.在A-{a12…,an1}中任取一个元,记为an这样一直作下去 就得到A中的一个无穷序列{an}.令A1={a1,a2,…},则A1是A的一个可数子集 推论O<c 证明由定理1,O≤C.由例1和例2,c=(0,1)≠O.因此O<c■ 定理2若A是可数集,B是有限集,则A∪B是可数集 证明不妨设A∩B=∞.若不然,由于A∪B=A∪(B-A),用B-A代替B即 可设A={a1,a2,…},B={b1,…,bn}则A∪B得元素可以编号排序为 A∪B={b1,…bn,a1 因此A∪B是可数集■ 定理3可数集的任何无限子集还是可数集 证明设A为可数集,则A的所有元素可以编号排序成为一个无穷序列
15 有限集与无限集 利用对等的概念, 我们可以给出有限集和无限集的严格定义. 设 A 是一非空集. 若存在一个自然数n, 使得 A 与集{1,2,L,n}对等, 则称 A 为有限集. 规 定空集是有限集. 若 A 不是有限集, 则称 A 为无限集. 下面先讨论一类重要的集 可数集,即具有可数基数的集. 可数集 在无限集中, 有一类是以后会经常遇到的, 也是最简单的, 就是下面要讨 论的可数集. 定义 5 与自然数集 N 对等的集称为可数集. 换言之, 具有可数基数的集称为可数集. 由可数集的定义知道, 若 A 是可数集, B 与 A 对等, 则 B 是可数集. 等价定义: 集 A 是可数集当且仅当 A 的所有元素可以编号排序成为一个无穷序列 (编号排序必须既无遗漏, 也无重复.): { , , , , }. A = a1 a2 L an L 可数集的简单例: 自然数集 N , 整数集 Z , 奇自然数集, 偶自然数集. 它们的元素可以分别排序成为无穷序列 {0,1,−1,2,− 2,L, n,− n,L}, {1, 3, 5,L, 2n −1,L}, {2, 4, 6,L, 2n,L}. 由例 1 知道, 区间(0, 1) 和实数集 1 R 都不是可数集. 后面我们将要看到更多的可数集, 它们的可数性不是这样显而易见的. 例如我们马 上要证明有理数集是可数集. 以下定理表明, 可数集在无限集中具有最小基数. 定理 1 任何无限集必包含一个可数子集. 换言之, 若 A 为无限集, 则ω ≤ A. 证明 在 A 中任取一个元, 记为 . 1 a 假定 1 1 , , a L an− 已经取定. 由于 A 是无限集, 故 { , , } − 1 n−1 A a L a 不空. 在 { , , } − 1 n−1 A a L a 中任取一个元, 记为 . n a 这样一直作下去, 就得到 A 中的一个无穷序列{ }. n a 令 { , , }, A1 = a1 a2 L 则 A1 是 A 的一个可数子集. 推论 ω < c. 证明 由定理 1, ω ≤ c. 由例 1 和例 2, c = (0, 1 ) ≠ ω. 因此ω < c. 定理 2 若 A 是可数集, B 是有限集, 则 A∪ B 是可数集. 证明 不妨设 A ∩ B = ∅. 若不然, 由于 A ∪ B = A ∪ (B − A), 用 B − A 代替 B 即 可.设 { , , }, A = a1 a2 L { , , }. 1 n B = b L b 则 A ∪ B 得元素可以编号排序为 { , , , , }. A ∪ B = b1 Lbn a1 a2 L 因此 A∪ B 是可数集. 定理 3 可数集的任何无限子集还是可数集. 证明 设 A 为可数集,则 A 的所有元素可以编号排序成为一个无穷序列