4-4 基数的概念

4-4.1集合的递归定义定义4-4.1:集合A的递归(归纳)定义由三部分组成:(1)基础:设置某些对象是在所要定义的集合A中的(作为A的基本元素,目的说明集合A是非空的)。(2)归纳(递归):建立一种由集合A的现有元素产生A中新元素的方法。(实质上就是给出一组规则,以确定如何从集合A的现有元素得到A的其他元素。)(3)闭合：除了有限次应用(1)和(2)产生集合A的元素外,A中再没有其它元素。4.4基数的概念关于闭合还有其他的等价叙述，1)除了有限次应用(1)和(2)产生集合A的元素外,A中再没有其它元素。2)集合A是满足(1)和(2)的最小集合。3)集合A满足(1)和(2),但不存在A的真子集能满足(1)和(2),即若SA,且S满足(1)和(2),则S=A。4)集合A是满足由(1)和(2)给定性质的所有集合之交。以上四种闭合的说法虽然形式上不同,但它们是等价的。证明从略。例：设整数集Z是全集,非负偶整数集E+={x|x≧0,且x=2y,yZ},它可以递归定义如下:(1)(基础)0E+。(2)(归纳)如果nE+,则n+2E+。(3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在E+中。例：下面的归纳定义所给出的是怎样的集合？(1)(基础)3S。(2)(归纳)如果x,yS,则x+yS。(3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在S中。答案是3的正整数倍全体。例：设Σ是一个有限非空字符集,称为字母表。从Σ中选取有限个字符组成的串称为Σ上的字符串或字。设x是Σ上的一个字,x=a1a2…an,其中aiΣ,1≦i≦n,n是正整数,表示字的长度长度为0的字称为空串,记为。若x,y是Σ上的两个字,x=a1a2…an,y=b1b2…bm,其中ai,bjΣ(1≦i≦n,1≦j≦m),则由x和y毗连得到新的字记为xy。即:xy=a1a2…anb1b2…bm。例:设Σ是一个字母表,Σ上所有的有限非空字符串集合记为Σ+,递归定义如下:(1)(基础)如果aΣ,则aΣ+。(2)(归纳)如果xΣ+,且aΣ,则axΣ+(ax表示字符a与字x毗连得到的新的字)。(3)(闭合)除有限次应用(1)和(2)产生Σ+中的字外,Σ+中再没有其它字。集合Σ+包含长度为1,2,3,…的字,即Σ+包含无限个字,但每个字的字符个数是有限的。例:设Σ是一个字母表,Σ上所有的有限字符串集合记为Σ*,Σ*包含空串，即Σ*=Σ+∪{},可递归定义如下:(1)(基础)Σ*。(2)(归纳)如果xΣ*,且aΣ,则axΣ*。(3)(闭合)除有限次应用(1)和(2)产生Σ*中的字外,Σ*中再没有其它字。例如,若Σ={0,1},则Σ*={,0,1,00,01,10,11,000,001…},是有限二进制序列的集合,其中包含空序列。算术表达式集合是包含整数,一元运算符+,-,以及二元运算符+,-,*,/的符号序列所组成的集合,其中包含如“((3+5)/4)”,“(((-5)+6)*3)”等算术表达式。算术表达式集合的递归定义如下:(1)(基础)如果D={0,1,2,3,4,5,6,7,8,9}和xD+,则x是算术表达式。其中D+是D上所有非空数字串的集合。(2)(归纳)如果x和y都是算术表达式,则(+x)是算术表达式;(-x)是算术表达式;(x+y)是算术表达式;(x-y)是算术表达式;(x*y)是算术表达式;(x/y)是算术表达式。(3)(闭合)一个符号序列是一个算术表达式当且仅当它能通过有限次应用(1)和(2)而得到。下面给出自然数集(即非负整数集)的定义。由于自然数的加法定义必须建立在自然数集N上,所以不能用加法运算来形式地定义自然数集N,否则将会产生循环。为了避免这种定义上的循环,我们引进后继集合的概念:设A是任一给定集合,A∪{A}称为A的后继集合,简称后继,记为A+。4-4.2自然数集的定义定义4-4.2:设N为自然数集,它的递归定义如下:(1)(基础)N。(2)(归纳)如果nN,则n+N(这里n+=n∪{n})。(3)(闭合)如果SN,且S满足(1)、(2),则S=N。按照这个定义,自然数集的元素为:,+,(+)+,((+)+)+,…,即为:,∪{},∪{}∪{∪{}}…,可以简化为:,{},{,{}},…。用记号:=给这些集合命名,例如命名为数0,记为0:=。0:=;1:=0+={}={0};2:=1+={,{}}={0,1};3:=2+={,{},{,{}}}={0,1,2};…一般地,若已给出n,则n+1:=n+={0,1,2,…,n}自然数集N={0,1,2,3,…},其中除0外每一个自然数是它前一个自然数的后继。定理4-4.1:(1)0不是任何自然数的后继。(2)任何自然数的后继是唯一的。(3)如果n+=m+,则n=m。证明从略。贝安诺(G.Peano)公理(1)0N;(2)对每一个nN,恰存在一个n+N(称n+为n的后继);(3)不存在一个nN,使n+=0;(4)如果n+=m+,则n=m;(5)如果SN,且①0S;②如果nS,就必有n+S,则S=N。4-4.3基数4-4.3.1基数概念首先我们从古老的传说来引进个数。在64个小方格组成的棋盘中放米的问题：印度的舍罕王要重赏国际象棋的发明人达依尔，达依尔要求：“在棋盘的第一个方格内放一粒米，以后每一小格内都比前一小格加一倍，最后摆满所有64格，将这些米赏给我”。国王认为他的要求不高，爽快地答应了。可结果却无法满足。1+2+22++263=264-1,约合140亿升所有整数的个数，一条线上所有几何点个数(即区间[a,b]上个数)，上面两个数哪个大些？这个问题最初是由Cantor提出的。从原始部落物品交换中得到启发。在古代原始部落中，不存在比3大的数，若问他们当中的一个人有几个孩子，当孩子多于3个时，其回答是很多。在比较一堆珠子和一堆铜币哪个多时，他们将怎么完成呢？他们是通过把珠子和铜币逐个比较，最后看哪堆有多余，若同时没有则两者相同。对于无穷大数比较，我们面临的也类似于原始部落问题。Cantor的解决办法与上述方法相同：给两组元素无穷多的序列中的各个数一一配对，若最后这两组元素恰配对完毕，则认为这两个无穷大数就是相等的，若有一组还没配完，则该组就比另一组大。正是基于这一基本设想，我们可给出对于两个集合比较其元素个数大小的方法。定义4-4.3：设A,B是任意两个集合,若存在一个双射f:A→B,则称A和B是等势的(或同浓的),记为A～B。例题1（P162）例题2定理4-4.2在集合族上等势关系是等价关系。4-4.3.2无限集定义4-4.4：设A为一个集合,若A为空集或与集合{0,1,2,…,n-1}存在双射,则称A为有限集,且|A|=nN。若集合A不是有限集,则称A为无限集。定理4-4.3:自然数集N是无限集。即证明N不是有限集.关键证明对任何nN，不存在从{0,1,2,n-1}到N的双射。证明：设n是N中任一元素，f是从{0,1,2,n-1}到N的任一函数，令K=1+max{f(0),f(1),,f(n-1)}。则KN，但对于K，对任意a{0,1,2,n-1}，有f(a)K，所以f不是满射。由n和f的任意性知N是无限集。定义4-4.5:所有与集合A等势的集合所组成的集合族的共同性质，称为集合A的基数，记为K[A]（或A）。从基数的定义可以看到，有限集合的基数就是其元素的个数。这里约定空集的基数为0。有限集合A的基数记为|A|;A和B的基数相同记为|A|=|B|。而对一般集合，如果两个集合能够建立双射函数，则两集合元素间必一一对应，称A和B的基数相同。没有一个自然数能作为N的基数,因此今后我们将记K[N]为0,读作阿列夫零。例:设N与I之间有如下一一对应:N:0,1,2,3,4,5,6,…I:0,1,-1,2,-2,3,-3,…即存在双射f:N→I,使对nN,为奇数为偶数nnnnnf)1(2121)(所以K[I]=0。例:设E={0,2,4,…},因为存在f:N→E,对任何nN有f(n)=2n,显然f是N→E的双射。这里E是N的真子集,然而K[E]=K[N]=0。这一事实揭示了无限集的一个重要特征:即无限集可以与它的一个真子集对等。定理4-4.4:无限集必与它的一个真子集对等。证明：设A是任意的无限集，从中取一元素记为a1，则A-{a1}为非空无限集，再在A-{a1}中取一元素记为a2，A-{a1,a2}还是非空无限集，取元素过程一直进行下去，从A中可取出一列元素a1,a2,，将A-{a1,a2,}记为A'，则A=A'∪{a1,a2,}。在A中取真子集B=A'∪{a2,a4,}。现构造函数f：AB')(2Axxaxaxfii则f是双射。所以A～B。推论:凡不能与自身的任一真子集对等的集合为有限集。凡能与自身的某一真子集对等的集合称为无限集,否则称为有限集。前面的例子和定理说明了这样的事实：在无穷大的世界里，部分可能等于全部。那么是否无穷大数都是相等的？4-5可数集与不可数集定义4-5.1：若存在从N到A的双射,则称A为可数无限集,简称可数集或可列集,K[A]=0。定理4-5.1：(1)设A是无限可数集,若存在从A到B的双射,则B也是可数集。(2)集合A是可数集的充要条件是集合A中的元素可以排成一个无穷序列的形式:a0,a1,a2,a3,a4,…。这里要注意：定理中的“无限”两字不能去掉。这是因为可数集是指可数无限集。定理4-5.2：可数集中加入有限个元素(或删去有限个元素),仍为可数集。定理4-5.3：两个可数集之并仍为可数集。推论：有限个可数集之并仍为可数集。定理4-5.4：可数个两两不相交的可数集的并集仍为可数集。定理4-5.5:[0,1]是不可数集。这样[0,1]的基数就不是0,我们称[0,1]为连续统,基数记为或c,有时也记为1.定理4-5.6:设A是有限集或可数集,B是任一无限集,则K[A∪B]=K[B]。构造(0,1)到R的双射f:f(x)=tg(x-/2)。因此我们可以知道K[R]=K[(0,1)]=。由此可以发现，线段上的点数和实数轴上的点数是一样的。现在，我们知道整数集，非负整数集，正整数集，有理数集，它们的基数是0。实数集为。那么无理数集？设P表示无理数集，显然P是无限集，而R=P∪Q,因为K[Q]=0,所以由定理4-5.6知，K[R]=K[P∪Q]=K[P],所以P的基数是。实数集R的基数4-6基数的比较定义4-6.1：设A和B是两个集合,若存在从A到B的入射,则称A的基数小于或等于B的基数,记为K[A]≦K[B]或K[B]≧K[A]。若K[A]≦K[B]且K[A]≠K[B],则称A的基数小于B的基数,记为K[A]K[B]。这定义是比较两个有限集的元素个数的推广。定理4-6.1：设A,B,C是任意集合,那么(1)若AB,则K[A]≦K[B]。(2)若K[A]≦K[B],K[B]≦K[C],则K[A]≦K[C]。定理4-6.2伯恩斯坦(F.Bernstein)定理设A和B是两个集合,若K[A]≦K[B],又K[B]≦K[A],则K[A]=K[B]。这个定理常用来证明两个集合有相同的基数。作一入射f:A→B,得到K[A]≦K[B],再作一入射g:B→A,得到K[B]≦K[A],从而得到K[A]=K[B]。伯恩斯坦定理告诉我们:在从A到B和从B到A的两个入射的基础上,可以得出存在从A到B的双射。找出两个入射往往比直接证明从A到B存在双射要来得容易。例：证明(0,1)与[0,1]有相同的基数。证明：作入射g:[0,1]→(0,1),g(x)=0.25+x/2，故[0,1]的基数小于等于(0,1)的基数,作入射f:(0,1)→[0,1],f(x)=x，故(0,1)的基数≦[0,1]的基数,由伯恩斯坦定理即证得。有限集基数、可数集基数和连续统基数