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题,
§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题,
