集合的基数讲稿.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《集合的基数讲稿.ppt》由会员分享,可在线阅读,更多相关《集合的基数讲稿.ppt(46页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 1关于集合的基数关于集合的基数第一页,讲稿共四十六页哦 2定义定义9.19.1 设设A,BA,B是集合,如果存在着从是集合,如果存在着从A A到到B B的的双射函数双射函数,就,就称称A A和和B B是等势是等势(same cardinality)的的,记作,记作ABAB。如果如果A A不与不与B B等势,则记作等势,则记作A BA B。9.1 9.1 集合的等势与优势集合的等势与优势集合的等势与优势集合的等势与优势q通俗的说,集合的势是量度集合所含元素多少的量。通俗的说,集合的势是量度集合所含元素多少的量。q集合的势越大,所含的元素越多。集合的势越大,所含的元素越多。第二页,讲稿共四十六页
2、哦 3(1)ZN。则则f是是Z到到N的双射函数。的双射函数。从而证明了从而证明了ZN。等势集合的实例等势集合的实例等势集合的实例等势集合的实例(1)(1)(1)(1)第三页,讲稿共四十六页哦 4等势集合的实例等势集合的实例(2)(2)(2)NNN。双射函数双射函数 第四页,讲稿共四十六页哦 5等势集合的实例等势集合的实例(3)(3)(3 3)NQNQ。把所有形式为把所有形式为p p/q q(p p,q q为整数且为整数且q q0)0)的数排成一张表。的数排成一张表。-2/1-2/155-1/1-1/144-3/1-3/118182/12/110103/13/111110/10/1001/11/
3、111-2/2-2/2-1/2-1/233-3/2-3/217172/22/23/23/212120/20/21/21/222-2/3-2/366-1/3-1/377-3/3-3/32/32/3993/33/30/30/31/31/388-2/4-2/4-1/4-1/41515-3/4-3/416162/42/43/43/413130/40/41/41/41414以以0/10/1作为第一个数,按照箭头规定的顺序可以作为第一个数,按照箭头规定的顺序可以“数遍数遍”表中所有的表中所有的数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有理数。计数过程中必须跳过第二次以及以后各次所遇到的同一个有
4、理数。数。第五页,讲稿共四十六页哦 6等势集合的实例等势集合的实例(4)(4)(4)(0,1)R。其中实数区间其中实数区间(0,1)=x|xR0 x1。令双射函数令双射函数则则 f 是是(0,1)到到R的双射函数。从而证明了的双射函数。从而证明了(0,1)R。第六页,讲稿共四十六页哦 7等势集合的实例等势集合的实例(5)(5)(5 5)0,1(0,1)。其中其中(0,1)和和0,1分别为实数开区间和闭区分别为实数开区间和闭区间。间。双射函数双射函数 f:0,1(0,1),2 2第七页,讲稿共四十六页哦 8等势集合的实例等势集合的实例(6)(6)(6 6)对任何)对任何a,bR,ab,0,1a,
5、b。双射函数双射函数f:0,1a,b,f(x)(b a)x+a。第八页,讲稿共四十六页哦 9例例9.29.2 设设A为任意集合,则为任意集合,则P(A)0,1A。构造构造f:P(A)0,1A,f(A)=A ,A P(A)。其中其中 A 是集合是集合A 的特征函数的特征函数。(1)(1)易证易证 f 是单射的是单射的。(2)(2)对于任意的对于任意的 g0,1A,那么有那么有 g:A0,1。令令 B=x|xAg(x)=1 则则B A,且且 B=g,即即 BP(A),使得使得f(B)=g。所以所以 f 是满射的。是满射的。由等势定义得由等势定义得P(A)0,1A。例例例例9.29.29.29.2证
6、证明明复习复习第九页,讲稿共四十六页哦 10定理定理9.19.1 设设A,B,C是任意集合,是任意集合,(1)AA。(2)若若AB,则则BA。(3)若若AB,BC,则则AC。(1 1)IA是从是从A到到A的双射,因此的双射,因此AA。(2)假设假设AB,存在,存在 f:AB是双射,是双射,那么那么 f 1:BA是从是从B到到A的双射,所以的双射,所以BA。(3)假设假设AB,BC,存在存在 f:AB,g:BC是双射,是双射,则则f g:AC是从是从 A 到到 C 的双射的双射。所以所以AC。等势的性质等势的性质等势的性质等势的性质证明证明第十页,讲稿共四十六页哦 11q N Z Q NNq R
7、 0,1(0,1)q任何的实数区间(开区间、闭区间以及半开半闭的区间)任何的实数区间(开区间、闭区间以及半开半闭的区间)都与实数集合都与实数集合R R等势。等势。q问题:问题:N N和和R R是否等势?是否等势?若干等势集合若干等势集合若干等势集合若干等势集合第十一页,讲稿共四十六页哦 12(1)如果能证明)如果能证明N 0,1,就可以断定就可以断定N R。只需证明任何函数只需证明任何函数f:N0,1都不是满射的。都不是满射的。构造一个构造一个0,1区间的小数区间的小数b,使得使得b在在N中不存在原像。中不存在原像。(2)任取函数)任取函数f:AP(A),构造构造BP(A),使得使得B在在A中
8、不存在原像。中不存在原像。或者使用反证法。或者使用反证法。定理定理9.29.2 康托定理康托定理(1)N R。(2)对任意集合对任意集合A都有都有A P(A)。康托定理康托定理康托定理康托定理分析分析第十二页,讲稿共四十六页哦 13(1 1)首先规定)首先规定0,1中数的表示。中数的表示。对任意的对任意的x0,1,令令x=0.x1x2,(0 xi 9)注意:为了保证表示式的唯一性,如果遇到注意:为了保证表示式的唯一性,如果遇到0.249990.24999,则将,则将x x表表示为示为0.250000.25000。设设 f:N0,1是从是从N到到0,1的任何一个函数。的任何一个函数。f的所有函数
9、值为的所有函数值为:f(0)=0.a1(1)a2(1)f(1)=0.a1(2)a2(2)f(n 1)=0.a1(n)a2(n)令令y的表示式为的表示式为0.b1b2,并且满足并且满足bi ai(i),i=1,2,,则则y0,1,但但y与上面列出的任何一个函数值都不相等与上面列出的任何一个函数值都不相等。即即f不是满射的。不是满射的。所以所以,N R。康托定理康托定理康托定理康托定理第十三页,讲稿共四十六页哦 14康托定理康托定理q假设假设A AP(A),则必有函数则必有函数 f:AP(A)是双射函数。是双射函数。如下构造集合如下构造集合B:Bx|xAx f(x)可知可知 BP(A)。于是存在唯
10、一一个元素于是存在唯一一个元素bA,使得使得 f(b)B。若若bB,则由则由B的定义知,的定义知,b f(b),即即 b B,矛盾矛盾。若若b B,则则b f(b),于是由于是由B的定义知,的定义知,bB,矛盾。矛盾。第十四页,讲稿共四十六页哦 15(2 2)设)设g:AP(A)是从是从A到到P(A)的任意函数,的任意函数,如下构造集合如下构造集合B:Bx|xAx g(x)则则BP(A)。但是但是对任意对任意xA,都有都有xB x g(x)所以,对任意的所以,对任意的xA都有都有Bg(x),即即B ran ran g 即即P(A)中存在元素中存在元素B,在在A中找不到原像。中找不到原像。所以所
11、以,g不是满射的。不是满射的。所以所以,A P(A)。说明说明康托定理康托定理康托定理康托定理q根据这个定理可以知道根据这个定理可以知道N P(N)。q综合前面的结果,可知综合前面的结果,可知N 0,1N。q实际上,实际上,P(N)P(N),0,10,1N N和和R R都是比都是比N“N“更大更大”的集合。的集合。第十五页,讲稿共四十六页哦 16定义定义9.29.2(1 1)设设A,B是集合,如果存在从是集合,如果存在从A到到B的的单射单射函数,就称函数,就称B优优势于势于A,记作记作AB。如果如果B不是优势于不是优势于A,则记作则记作AB。(2 2)设设A,B是集合,若是集合,若AB且且A
12、B,则称则称B真优势于真优势于A,记作记作AB。如果如果B不是真优势于不是真优势于A,则记作则记作AB。例如:例如:N NN RA P(A)N RA P(A)R N N N优势优势优势优势RN第十六页,讲稿共四十六页哦 17定理定理9.39.3 设设A,B,C是任意的集合,则是任意的集合,则(1)A A。(2)若若A B且且B A,则则AB。(3)若若A B且且B C,则则A C。证明:证明:(1 1)IA是是A到到A的单射的单射,因此因此A A。(2 2)证明略。)证明略。(3 3)假设)假设A B且且B C,那么存在单射,那么存在单射 f:AB:AB,g:BC:BC,于是于是 f g:AC
13、也是单射的,因此也是单射的,因此A C。优势的性质优势的性质优势的性质优势的性质说明说明q该定理为证明集合之间的等势提供了有力的工具该定理为证明集合之间的等势提供了有力的工具。q构造两个单射构造两个单射f:A AB B 和和 g g:B BA A函数容易集合等势函数容易集合等势。第十七页,讲稿共四十六页哦 18例题例题例题:例题:证明证明0,10,1与与(0,1)(0,1)等势。等势。证明:证明:构造两个单射函数构造两个单射函数f:(0,1)0,1:(0,1)0,1,f(x)xg:0,1(0,1):0,1(0,1),g(x)x/2+1/4/2+1/4第十八页,讲稿共四十六页哦 19证明证明 0
14、,1N0,1)(1)设设x 0,1),0.x1x2是是x的的二进制表示二进制表示。为了使表示唯一,规定表示式中不允许出现连续无数个为了使表示唯一,规定表示式中不允许出现连续无数个1。例如例如 x0.1010111,应按规定记为应按规定记为0.1011000。对于对于x,如下定义如下定义f:0,1)0,1N,使得使得 f(x)=tx,且且tx:N0,1,tx(n)=xn+1,n=0,1,2,例如例如 x=0.10110100,则对应于则对应于x的函数的函数tx是是:n 0 1 2 3 4 5 6 7tx(n)1 0 1 1 0 1 0 0 易见易见tx0,1N,且对于且对于x,y0,1),xy,
15、必有必有tx ty,即即f(x)f(y)。所以所以,f:0,1)0,1N是单射的。是单射的。第十九页,讲稿共四十六页哦 20(2)定义函数定义函数g:0,1N0,1)。g的映射法则恰好与的映射法则恰好与 f 相反,相反,即即 t0,1N,t:N0,1,g(t)=0.x1x2,其中其中xn+1=t(n)。但不同的是,将但不同的是,将0.x1x2看作数看作数x的十进制表示的十进制表示。例如例如t1,t20,1N,且且g(t1)0.0111,g(t2)0.1000,若将若将g(t1)和和g(t2)都看成二进制表示,则都看成二进制表示,则g(t1)g(t2);但若看成十进制表示,则但若看成十进制表示,
16、则g(t1)g(t2)。所以所以,g:0,1N0,1)是单射的。是单射的。根据定理根据定理9.3,有,有0,1N0,1)。证明证明证明证明 0,10,1N N0,1)0,1)第二十页,讲稿共四十六页哦 21总结总结qN Z Q NNqR a,b (c,d)0,1N P(N)其中其中a,b,(c,d)代表任意的实数闭区间和开区间代表任意的实数闭区间和开区间。q0,1A P(A)qN RqA P(A)第二十一页,讲稿共四十六页哦 229.2 9.2 集合的基数集合的基数 q上一节我们只是抽象地讨论了集合的等势与优势。上一节我们只是抽象地讨论了集合的等势与优势。q本节将进一步研究度量集合的势的方法。
17、本节将进一步研究度量集合的势的方法。q最简单的集合是有穷集。尽管前面已经多次用到最简单的集合是有穷集。尽管前面已经多次用到“有穷集有穷集”这一概念,当时只是直观地理解成含有有限多个元素的这一概念,当时只是直观地理解成含有有限多个元素的集合,但一直没有精确地给出有穷集的定义。为解决这个集合,但一直没有精确地给出有穷集的定义。为解决这个问题我们需要先定义自然数和自然数集合。问题我们需要先定义自然数和自然数集合。第二十二页,讲稿共四十六页哦 23定义定义9.3 9.3 设设a为为集合,称集合,称aa 为为a的的后继后继,记作,记作a+,即即 a+=aa。例例9.39.3 考虑空集的一系列后继。考虑空
18、集的一系列后继。+=+=+=,=,+=,+=,=,=,+,+后继后继后继后继 说明说明q前边的集合都是后边集合的元素。前边的集合都是后边集合的元素。q前边的集合都是后边集合的子集。前边的集合都是后边集合的子集。第二十三页,讲稿共四十六页哦 24利用后继的性质,可以考虑以构造性的方法用集合来给出自然数的定义,利用后继的性质,可以考虑以构造性的方法用集合来给出自然数的定义,即即 0=1=0+02=1+,0,132+,+,0,1,2 n0,1,n 1说明说明自然数的定义自然数的定义自然数的定义自然数的定义 这种定义没有概括出自然数的共同特征。这种定义没有概括出自然数的共同特征。第二十四页,讲稿共四十
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 集合 基数 讲稿
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内