第三节 可数集合
第一章 集合及其基数
注,A可数 当且仅当
A可以写成无穷序列的形式 {a1,a2,a3,…}
1,2,3,4,5,6,…
a1,a2,a3,a4,a5,a6,…
例,1) Z = {0,1,-1,2,-2,3,-3,…}
与自然数集 N对等的集合称为可数
集或可列集,其基数记为
0?
1可数集的定义
2) [0,1]中的有理数全体
={0,1,1/2,1/3,2/3,1/4,3/4,1/5,2/5,…}
假设这是一个无限集 M
我们可以取出其中一个点 a1
显然 M\{a1}还是无限集
在 M\{a1}中 可以取出一点 a2
显然 M\{a1,a2}还是无限集
我们可以取出一个 可数子集 {a1,a2,a3,...}
任何无限集合均含有可数子集
(即可数集是无限集中具有最小势的的集合 )
2 可数集的性质(子集)
可数集的子集或为有限集或为可数集
:中的元素可以排列成是一个可数集,则证明:设 AA
??,,,,,321 naaaa
中的一个无穷子序列:
中的元素必是上述序列的无限子集,则是若
的有限子集,则得证;是若
**
*
AAA
AA
??,,,,,321 knnnn aaaa
是可数集。从而 },,,,,{ 321* ?? knnnn aaaaA ?
推论
可数集的性质(并集)
?有限集与可数集的并仍为可数集
A={a1,a2,a3,a4,a5,a6,…}
当集合有公共元素时,
不重复排。
假设 A,B,C两两不交,则
A∪ B={ b1,b2,b3,…,b n, a1,a2,a3,…}
?可数个可数集的并仍为可数集
?有限个可数集的并仍为可数集
C= {c1,c2,c3,c4,c5,c6,…}
B={b1,b2,b3,…,b n}
A∪ C={ c1,a1,c2,a2,c3,a3,…}
当 Ai互不相交时,按箭头所示,我们得到一个无穷序列 ;
当 Ai有公共元时,在排列的过程中除去公共元素;
.
1
是可数集因此 ?
?
?n
nA
1 1 1 2 1 3 1 4,,,a a a a,
2 1 2 2 2 3 2 4,,,a a a a,
3 1 3 2 3 3 3 4,,,a a a a,
4 1 4 2 4 3 4 4,,,a a a a,
,,,,
A1
A2
A3
A4
可数个可数集的并
仍为可数集的证明
说明,
?与 Hilbert旅馆问题比较 ;
?如何把无限集分解成无
限个无限集合的并?
首先 [0,1]中的有理数全体
={0,1,1/2,1/3,2/3,1/4,3/4,1/5,2/5,…} 是可数集,
????????????? ])1,2[(])2,1[(])0,1[(])1,0[( QQQQQ
例 全体有理数之集 Q是可数集
[ ][ ][ ][ ][ ][ ]
-2 -1 0 1 2 3 4
所以 Q是可数集(可数个可数集的并)
说明,有理数集在直线上稠密,但仍与稀疏分布在直线上
的整数集有 相同多 的点 (对等意义下 ),
有限个 可数集的 卡氏积 是可数集
设 A,B是可数集,则 A× B也是可数集
},|),{( ByAxyxBA ????
从而 A× B也是可数集(可数个可数集的并)
利用 数学归纳法 即得有限个乘积的情形
3 可数集的性质(卡氏积)
}|),{( Byyx
Ax
???
?
x固定,y在变
例 平面上以有理点为圆心,有理数为半径的圆全
体 A为可数集
证明:平面上的圆由其圆心 (x,y) 和半径 r
唯一决定,从而
},,|),,{(~ ?? ????? QrQyxryxQQQA
r
(x,y)
.,,00 ABABA ????? ?则 若
由于0 ? ? A
使得 中 可 以 取 出 子 集 故从0,? ? M M A
或 有 限 或 可 数 知 由B B,0 ? ?
B M M A B A? ? ?) \ ( ? 从而
A B A? ? 所以
) ( ) \ (B M M A? ? ?
A M M A? ? ) \ ( ~
例
?有限集与可数集的并仍为可数集
?可数集并可数集仍为可数集
A
A\
M
B
对上例的说明
.,,00 ABABA ????? ?则 若;集并可数集仍为可数集为可数集时,利用可数当 B
特殊情形,
? [0,1] ~ (0,1)
? R ~ R-Q;或为有限集或为可数集故 由于 BB,0??;集并有限集仍为可数集为有限集时,利用可数当 B
{ 1/2,1/3,?,1/5,…}
{ 0,1,?,1/3,1/4,…}
其他xx ?
整系数多项式方程的实根称为代数数;
不是代数数的实数成为超越数。
0
n
n
PP
?
?
? 为 可 数 集 ( 可 数 个 可 数 集 的 并 )
由代数基本定理知
任意整系数多项式
至多有有限个实根,
从而结论成立,
设 P 是 整系数多项式全体所成之集,P(n)是 n次整系数多项
式全体
110{ |,1,2,,,0 }nnn n n i nP a x a x a a Z i n a??? ? ? ? ? ? ?
0 ~
~ ( { 0 } ) ( )n
PZ
P Z Z Z Z n Z? ? ? ? ? ?个 相 乘 为 可 数 集 ( n 1 )
( 有 限 个 可 数 集 作 卡 氏 积 )
例 代数数全体是可数集
有关超越数的说明
? 1874年 Cantor开始研究无限集的计数问题 ;
? 1873年 C.埃尔米特证明了 e是超越数 ;
? 1882年 Lindemann证明了 π是超越数 ;
? 1934年 A.O.盖尔丰得证明了若 α不是 0和 1的
代数数,β是无理代数数,则 αβ是超越数 (此
问题为 Hilbert于 1900年提出的 23个问题中的
第 7问题 )。
我们证明了代数数全体是可数集合,
通过后面可知道超越数全体是不可
数集,故超越数比代数数多得多
是可数集。而
使得是一个无限集,则存在设
**
*
,~
,
AAAA
AAA
?
?
假设这是集合 A
从中可以取出可数子集 M
很容易将 M一分为二 M1,M2,
使得两个都是可数集
A\M
M={a1,a2,a3,a4,a5,a6,… }
M1 ={a1,a3,a5,…}
M2={a2,a4,a6,… }
取 A*=(A\M)∪ M1=A-M2即可
例
说明:由此我们可得任一无限集一定存在它的一个真子
集与它有相同多的元素个数
问,为什么
不直接令
A*=A\M?
思考,
)(
111
为可数集是否成立? nn
nn
N
nN
AAA
?
??
?
?
????
注:用现有语言不能对任意集合给出一描述
(集合有 描述法 与 列举法 两种 )
n
N
nN
A
11 ?
?
?
??
是可数集 (有限个可数集的卡氏积仍是可数集)
(可数个可数集的并仍是可数集)
nn A
?
?
?
1
是不可数集
思路:令每个 An={0,1,2,3,…,9},对
中每个点 (a1,a2,a3,a4,a5,a6,…)
对应一个小数 0,a1a2a3a4a5a6 …,则
的势比 [0,1]的势大,又 [0,1]为不可
数集,故 不可数
nn A
?
??1
nn A
?
??1
nn A
?
??1
第一章 集合及其基数
注,A可数 当且仅当
A可以写成无穷序列的形式 {a1,a2,a3,…}
1,2,3,4,5,6,…
a1,a2,a3,a4,a5,a6,…
例,1) Z = {0,1,-1,2,-2,3,-3,…}
与自然数集 N对等的集合称为可数
集或可列集,其基数记为
0?
1可数集的定义
2) [0,1]中的有理数全体
={0,1,1/2,1/3,2/3,1/4,3/4,1/5,2/5,…}
假设这是一个无限集 M
我们可以取出其中一个点 a1
显然 M\{a1}还是无限集
在 M\{a1}中 可以取出一点 a2
显然 M\{a1,a2}还是无限集
我们可以取出一个 可数子集 {a1,a2,a3,...}
任何无限集合均含有可数子集
(即可数集是无限集中具有最小势的的集合 )
2 可数集的性质(子集)
可数集的子集或为有限集或为可数集
:中的元素可以排列成是一个可数集,则证明:设 AA
??,,,,,321 naaaa
中的一个无穷子序列:
中的元素必是上述序列的无限子集,则是若
的有限子集,则得证;是若
**
*
AAA
AA
??,,,,,321 knnnn aaaa
是可数集。从而 },,,,,{ 321* ?? knnnn aaaaA ?
推论
可数集的性质(并集)
?有限集与可数集的并仍为可数集
A={a1,a2,a3,a4,a5,a6,…}
当集合有公共元素时,
不重复排。
假设 A,B,C两两不交,则
A∪ B={ b1,b2,b3,…,b n, a1,a2,a3,…}
?可数个可数集的并仍为可数集
?有限个可数集的并仍为可数集
C= {c1,c2,c3,c4,c5,c6,…}
B={b1,b2,b3,…,b n}
A∪ C={ c1,a1,c2,a2,c3,a3,…}
当 Ai互不相交时,按箭头所示,我们得到一个无穷序列 ;
当 Ai有公共元时,在排列的过程中除去公共元素;
.
1
是可数集因此 ?
?
?n
nA
1 1 1 2 1 3 1 4,,,a a a a,
2 1 2 2 2 3 2 4,,,a a a a,
3 1 3 2 3 3 3 4,,,a a a a,
4 1 4 2 4 3 4 4,,,a a a a,
,,,,
A1
A2
A3
A4
可数个可数集的并
仍为可数集的证明
说明,
?与 Hilbert旅馆问题比较 ;
?如何把无限集分解成无
限个无限集合的并?
首先 [0,1]中的有理数全体
={0,1,1/2,1/3,2/3,1/4,3/4,1/5,2/5,…} 是可数集,
????????????? ])1,2[(])2,1[(])0,1[(])1,0[( QQQQQ
例 全体有理数之集 Q是可数集
[ ][ ][ ][ ][ ][ ]
-2 -1 0 1 2 3 4
所以 Q是可数集(可数个可数集的并)
说明,有理数集在直线上稠密,但仍与稀疏分布在直线上
的整数集有 相同多 的点 (对等意义下 ),
有限个 可数集的 卡氏积 是可数集
设 A,B是可数集,则 A× B也是可数集
},|),{( ByAxyxBA ????
从而 A× B也是可数集(可数个可数集的并)
利用 数学归纳法 即得有限个乘积的情形
3 可数集的性质(卡氏积)
}|),{( Byyx
Ax
???
?
x固定,y在变
例 平面上以有理点为圆心,有理数为半径的圆全
体 A为可数集
证明:平面上的圆由其圆心 (x,y) 和半径 r
唯一决定,从而
},,|),,{(~ ?? ????? QrQyxryxQQQA
r
(x,y)
.,,00 ABABA ????? ?则 若
由于0 ? ? A
使得 中 可 以 取 出 子 集 故从0,? ? M M A
或 有 限 或 可 数 知 由B B,0 ? ?
B M M A B A? ? ?) \ ( ? 从而
A B A? ? 所以
) ( ) \ (B M M A? ? ?
A M M A? ? ) \ ( ~
例
?有限集与可数集的并仍为可数集
?可数集并可数集仍为可数集
A
A\
M
B
对上例的说明
.,,00 ABABA ????? ?则 若;集并可数集仍为可数集为可数集时,利用可数当 B
特殊情形,
? [0,1] ~ (0,1)
? R ~ R-Q;或为有限集或为可数集故 由于 BB,0??;集并有限集仍为可数集为有限集时,利用可数当 B
{ 1/2,1/3,?,1/5,…}
{ 0,1,?,1/3,1/4,…}
其他xx ?
整系数多项式方程的实根称为代数数;
不是代数数的实数成为超越数。
0
n
n
PP
?
?
? 为 可 数 集 ( 可 数 个 可 数 集 的 并 )
由代数基本定理知
任意整系数多项式
至多有有限个实根,
从而结论成立,
设 P 是 整系数多项式全体所成之集,P(n)是 n次整系数多项
式全体
110{ |,1,2,,,0 }nnn n n i nP a x a x a a Z i n a??? ? ? ? ? ? ?
0 ~
~ ( { 0 } ) ( )n
PZ
P Z Z Z Z n Z? ? ? ? ? ?个 相 乘 为 可 数 集 ( n 1 )
( 有 限 个 可 数 集 作 卡 氏 积 )
例 代数数全体是可数集
有关超越数的说明
? 1874年 Cantor开始研究无限集的计数问题 ;
? 1873年 C.埃尔米特证明了 e是超越数 ;
? 1882年 Lindemann证明了 π是超越数 ;
? 1934年 A.O.盖尔丰得证明了若 α不是 0和 1的
代数数,β是无理代数数,则 αβ是超越数 (此
问题为 Hilbert于 1900年提出的 23个问题中的
第 7问题 )。
我们证明了代数数全体是可数集合,
通过后面可知道超越数全体是不可
数集,故超越数比代数数多得多
是可数集。而
使得是一个无限集,则存在设
**
*
,~
,
AAAA
AAA
?
?
假设这是集合 A
从中可以取出可数子集 M
很容易将 M一分为二 M1,M2,
使得两个都是可数集
A\M
M={a1,a2,a3,a4,a5,a6,… }
M1 ={a1,a3,a5,…}
M2={a2,a4,a6,… }
取 A*=(A\M)∪ M1=A-M2即可
例
说明:由此我们可得任一无限集一定存在它的一个真子
集与它有相同多的元素个数
问,为什么
不直接令
A*=A\M?
思考,
)(
111
为可数集是否成立? nn
nn
N
nN
AAA
?
??
?
?
????
注:用现有语言不能对任意集合给出一描述
(集合有 描述法 与 列举法 两种 )
n
N
nN
A
11 ?
?
?
??
是可数集 (有限个可数集的卡氏积仍是可数集)
(可数个可数集的并仍是可数集)
nn A
?
?
?
1
是不可数集
思路:令每个 An={0,1,2,3,…,9},对
中每个点 (a1,a2,a3,a4,a5,a6,…)
对应一个小数 0,a1a2a3a4a5a6 …,则
的势比 [0,1]的势大,又 [0,1]为不可
数集,故 不可数
nn A
?
??1
nn A
?
??1
nn A
?
??1