关于集合可数的若干证明方法

毕业论文题目关于集合可数的若干证明方法学生姓名王中华学号0312014414所在院(系)数学系专业班级数学与应用数学专业2003级4班指导教师李金龙2007年5月22日陕西理工学院毕业论文第1页共9页关于集合可数的若干证明方法王中华（陕西理工学院数学系数学与应用数学专业2003级4班,陕西汉中723000）指导教师：李金龙[摘要]本文主要介绍了有关集合可数的五种证明方法,这些方法是:一.依据定义构造无穷序列证明集合可数;二.依据伯恩斯坦定理通过建立映射证明集合可数;三.通过集合之间取并集来证明有些集合可数;四.用数学归纳法证明集合可数;五.运用转化的思想.通过以上方法的讨论,本文对有关集合可数的证明做了一个比较全面的介绍.[关键词]可数集;1-1映射;无穷序列１引言集合是整个数学理论的基础,可数集是实变函数中的一个最基本的概念,对后续的测度论以及Lebesgue积分的学习起着很重要的作用而且作为一类最简单的集合在数学的各个分支中也有广泛的应用.基于此判断并证明集合可数便显得尤为重要,虽然可数集合数目众多,种类繁杂,但集合可数的证明方法无分就几类.本文将主要介绍其中常用的五种方法.作者通过阅读大量的参考文献,从中搜集了大量的习题,通过认真演算,其中少数难度较大的题目之证明来自相应的参考文献,并对这些证明方法做了系统的归纳和总结.由于本文的主要内容是介绍解题方法,所以,本文会以大量的例题进行讲解说明.２预备知识定义2.1[1]设,AB是两个集合,如果存在二者元素之间的一个对应关系,使A中任意元素x,通过都恰与B中某一个元素y对应,而B中任意的元素y也一定是A中某一x通过在B中的对应元素,则我们就说A和B是对等的.记为AB.定义2.2[2]凡与自然数集对等的集合称为可列集.可列集与有限集统称可数集.定理2.1[3](Cantor—Bernstein)若**,XYYYXX,则XY.定理2.2[4]任何无穷集合必有可数子集.基于以上两个定理,我们给出集合可数的如下两个充分条件.定理2.3设A为任意无穷集,X为一可数集,且存在满射:fXA,则A可数.证明由已知必存在集合MX,使得f在M上的限制是一个双射,即存在集合MX,使得:fMA为一个双射,也就是说AMX.又由定理2.2,A必有可数子集,即存在BA,且BX,也就是说XBA.从而由定理2.1知AX,又XN,故AN即A可数.陕西理工学院毕业论文第2页共9页定理2.4设A为任意无穷集,X为一可数集,且存在单射:fAX,则A可数.证明由已知()fAX,而:()fAfA显然为一双射,故()AfAX.由定理2.2知A必有可数子集,即存在B,使得XBA,因此由定理2.1知AX,即A可数.定理2.5[5]若,AB都是可数集合,则AB是可数的.用数学归纳法不难把定理2.7的结论推广到n个集合的情形,即推论2.1[1]若对于每一个,(1)iiinA是可数集合,则1niiA是可数集合.下面的定理2.6我们再将结论进一步推广到可数个集合的情形.定理2.6[6]如果1,2,3,iAi的每一个都是可数集合,则1iiA也是可数集合.3关于集合可数的一些证明方法以下文中例题选自参考文献[7,8,9,10].3.1依据定义构造无穷序列证明集合可数依据上面的定义无穷集合可数与可列等价,那么要证明一个无穷集合可数只要找到其元素的一个无穷序列便可.例3.1全体有理数构成的集合Q可数.证明由于任意有理数都可以用分数表示,我们构造集合集合序列如下,1111222212123123123,,,,,,,,,,,,,,,,,,iiiiijjjAAA,则这些所有集合的全体元素可做排列312121112123,,,,,,,,ij,其排列规则为11排第一位,当2ij时,ij排在第n位,21ijknjk,将上述排列中的重复元素只取其一个最简形式,便可得到一个全体有理数的无穷序列为,3121111213,,,,,,,ij,故而由定义可知全体有理数构成一可数集.例3.2证明直线上以有理数为端点的区间全体所组成的集合可数.证明设直线上的全体有理点为12,,,,naaa,令(,)(,)ijijijAaaijaa,则{}ijA中的元素可排列如下：1213141,,,,,nAAAA,23242,,,,nAAA,343,,,nAA,陕西理工学院毕业论文第3页共9页将以上排列重排成无穷序列如下：1213232434123,,,,,,,,nnnAAAAAAAA.故{}ijA可数.例3.3证明整数集可数.证明整数集中的元素可做如下无穷序列:0,1,1,2,2,3,3,,故整数集可数.根据定义构造无穷序列来证明集合可数的方法关键在于构造无穷序列,而这其中是有很多技巧的,还要通过多做练习,细加揣摩,还有多注意总结前人的经验才能掌握.3.2依据伯恩斯坦定理通过建立映射证明集合可数例3.4直线上互不相交的开区间构成的集合可数.证明记直线上互不相交的开区间构成的集合为F,建立有理数集Q到M的映射如下,(),(,)YfxxYQY其中F,对于任意的YF,由有理数的稠密性知,存在xYQ,即存在x,使得()fxY,故:fQF是一个满射,从而根据定理2.3,F可数.例3.5若直线上的集合E的任意两点间的距离大于１,则集合E可数.证明用点0,1,2,3,将直线分成可数个闭区间.易知每一个闭区间至多含有已知集合E的一个点,因而在集合E中的点到闭区间之间存在一个单射,故集合E可数.例3.6直线上的集合A称为离散集是指,对任意给定的xA,存在0使得(;)Ux与A不相交,即x不是A的聚点.求证直线上的离散集为可数集.证明依据题意,,,,xxxAabQ使得(,){}xxabAx.于是我们可以建立如下这般映射:(,)xxfxab,其中,xxab满足(,){}xxabAx.易见f是一单射,而(,)|,xxxxababQ是可数集.从而根据定理2.4知集合A是可数集.例3.7函数()fx的真正极值是指,对于定义域内一点0x,如果存在0,使0()()fxfx对于任意(;)xUx均成立,则称0()fx为函数()fx的真正极大值,相应的称0x为()fx的真正极大值点.设:fRR为实函数,令()|MfxxRf为的真正极大值点,则M为一可数集.证明设x为f的真正极大值点,选区间(,)xx,使得(,),,xxxxx为有理数且对于任意的(,),xxuux,有()()fufx,.由真正极大值的定义知映射:,()(,)xxMQQyfx,陕西理工学院毕业论文第4页共9页为单射.于是由定理2.4M为一可数集.此法主要建立在伯恩斯坦定理的基础之上,根据集合对等的定义,通过建立映射来证明集合可数.集合对等的定义中要求两个集合之间存在双射,此方法在伯恩斯坦定理的基础之上得到两个定理,并通过此二定理将集合可数的条件减弱为单射或满射.映射是数学中的一个基本的概念,在数学的各个分支中均可看见映射的踪影,映射也是一个大家都很熟悉的概念,因此在证明集合可数时不妨试试建立映射.此法的关键是建立合适的映射.3.3通过集合之间取并集来证明有些集合可数.例3.8证明平面上坐标为有理数的点组成可数集合.证明首先记平面上坐标为有理数的点组成的集合为E,将（－,＋）中有理数全体排列起来12,,,,naaa.记横坐标为na,纵坐标为有理数的点的全体构成的集合为nA,显然1nnEA,而且易知(1,2,)nAn为可数集合,故E为可数集合.例3.9所有系数为有理数的多项式组成一个可数集.证明记所有系数为有理数的多项式组成的集合为A,记1n次有理系数多项式为12121nnnnaxaxaxa,（0na）.由于多项式由其系数所唯一确定,因此所有1n次有理系数多项式组成的集合可记为1,2(,,);0nninAaaaaQa且令12(,,,);nniBbbbbQ,易知nB可数.建立映射,:()nnfABfxx显然这是一个单射,于是由定理2.4nA可数.又1nnAA,故A可数.例3.10全体代数数所组成的集合可数.证明首先我们基于这样一个事实,对于任意给定的自然数,n全体n次整系数多项式所组成的集合可数.由代数学知识可知,n次多项式至多有n个根.从而对于任意自然数n,所有n次整系数多项式的全体根所组成的集合可数,记为nE.令1nnEE,易知E即为全体代数数所组成的集合.而且易见E可数.例3.11当g取遍所有正整数时,所有g进制有限小数组成一可数集.证明记所有g进制有限小数组成的集合为E,下证E可数.对于任意的给定的g,g进制有限小数全体显然组成可数集记为gE,则1ggEE,由定理2.6知E为一可数集.数学中有这么一句话,所谓的复杂问题只不过是简单问题的组合而已.这句话说得有一点夸大,但是对我们处理有些数学问题还是有一些启示的.比如在证明集合可数时,当我们没有办法证明一个比较复杂的集合可数时,不妨把它分解成很多个（当然不能超过可数多个）简单集合的并集,再证明每一个简单集合可数,从而根据定理说明并起来的复杂集合也是可数的.当然分解的时候至多分解为可数多个简单集合.此法的关键是找出合适的简单集合,使之并起来为所要证明的复杂集合.这部分主要是利用定理2.5、2.6以及推论2.1采用分解之法,其它化复杂为简单之法将在3.5有所体现.陕西理工学院毕业论文第5页共9页3.4用数学归纳法证明集合可数例3.12n维空间中以有理数为坐标的点构成的集合可数.证明记12(,,,,);,1,2,nniAxxxxQi.当1n时,1AQ是可数集合,命题成立.假设nk时命题成立,即kA可数,我们将其表示成无穷序列的形式,12,,,,kkkknAaaa,其中每一个kia是一个k维向量.给每一个kia（1,2,i）添加一个有理数坐标便可以将其扩展成一个1k维向量,当添加的坐标取遍所有理数时,每一个kia被扩展成可数个1k维向量,我们将这可数个1k维向量组成的集合记为iB,易见11kiiAB,故1kA可数.综上,由归纳法原理,对于任意自然数n,nA可数.原命题成立.例3.13可数集合的所有有限子集所组成的集合可数.证明记A为一可数集合,则A可以表示为12{,,,}naaa,记12{,,,}iiiinEeee,其中对于任意(1)jjn,ije是A的i元子集,用E表示A的所有有限子集所组成的集合,则显然1niiEE.下面用数学归纳法证明对于任意n,nE可数,从而证明E可数.首先112{{},{},,{},}nEaaa显然可数.假设nE可数,下证1nE可数,1nE中的元素可以按照这样的方式构成,给nE中的每一个元素集添加一个元素.即njneE给nje添加一个元素,使之变成11njneE,从这个变换过程还可以看出实际上已经建立了一个从A到nE的满射111:;,nnjjjjnfaeaAeE,其中ja为从nje变到1nje所添加的那个元素.故1nE可数.综上根据归纳法原理,对于任意自然数,nnE可数.其实从以上证明可以看出可数集合的所有可数子集所组成的集合也是可数的.数学归纳法是一个应用很广泛的而又很基本的数学方法,可以说凡是有自然数的地方都可以看到数学归纳法.而在处理与自然数相关的问题时使用数学归纳法也的确会得心应手,需要注意的是数学归纳法基本的三个步骤缺一不可.集合可数的命题中也有很多与自然数相关,尤其是n维空间的子集,可谓和自然数直接相关,譬如例3.12,因此在证明此类集合可数时数学归纳法也不失为一种可行之法.3.5运用转化的思想陕西理工学院毕业论文第6页共9页解决数学问题的基本的思路之一便是将复杂问题转化为简单问题,将陌生问题转化为熟知问题,将未知问题转化为已知问题.在集合可数性的证明中这一方法也可派上用场.我们通过六个例题简单地介绍了此法,转化与化