资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,定理(二)：设,S,是自然数集,N,的非空子集，如果0,S，,且当,n,Sn+1,S，,则,S=N。,定理(三)：设,S,是自然数集,N,的非空子集，如果0,S，,且当,0,1,2,n,Sn+1,S，,则,S=N。,数学归纳法，有两种形式：,(1)第一数学归纳法,要证一个结论对所有自然数都真，只须做两件事：1)当,n=0,时，结论成立。,2)若当,n=k,结论成立，则当,n=k+1,结论也成立。,1,(2)第二数学归纳法,要证一个结论对所有自然数都真，只须做两件事：,当,n=0,时，结论成立。,若当,n,k,结论成立，则当,n=k+1,结论也成立,定理(四)：设,P(n),是一个与自然数,n,有关的结论。若对于自然数0，结论成立；并且当对自然数,k,结论成立时，对于自然数,k+1,结论也成立，则该结论对所有自然数都成立。,2,定理(五)：设,P(n),是一个与自然数,n,有关的结论。若对于自然数0，结论成立；并且当对自然数,0,1,2,k,结论成立时，对于自然数,k+1,结论也成立，则该结论对所有自然数都成立。,3,二、集合的递归定义,定义4.1:集合,A,的递归(归纳)定义由三部分组成:,(1)基础:设置某些对象是在所要定义的集合,A,中的,(2)归纳(递归):建立一种由集合,A,的现有元素产生,A,中新元素的方法。,(3)闭合：除了有限次应用(1)和(2)产生集合,A,的元素外,A,中再没有其它元素。,4,例：设整数集,Z,是全集,非负偶整数集,E,+,=x|x0,且,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的正整数倍全体。,5,设,是一个有限非空字符集,称为,字母表,。,从,中选取有限个字符组成的串称为,上的,字符串,或,字,。,设,x,是,上的一个字,x=a,1,a,2,a,n,其中,a,i,1in,n,是正整数,表示字的长度。长度为0的字称为,空串,记为,。,若,x,y,是,上的两个字,x=a,1,a,2,a,n, y=b,1,b,2,b,m,其中,a,i,b,j,(1in, 1jm),则由,x,和,y,毗连得到新的字记为,xy。,即:,xy=a,1,a,2,a,n,b,1,b,2,b,m,。,6,例:设,是一个字母表,上所有的有限非空字符串集合记为,+,递归定义如下:,(1)(基础)如果,a,则,a,+,。,(2)(,归纳)如果,x,+,且,a,则,ax,+,(ax,表示字符,a,与字,x,毗连得到的新的字。,(3)(闭合)除有限次应用(1)和(2)产生,+,中的字外,+,中再没有其它字。,集合,+,包含长度为1,2,3,的字,即,+,包含无限个字, 但每个字的字符个数是有限的。,7,例:设,是一个字母表,上所有的有限字符串集合记为,*,*,包含空串，即,*,=,+,可递归定义如下:,(1)(基础),*,。,(2)(,归纳)如果,x,*,且,a,则,ax,*,。,(3)(,闭合)除有限次应用(1)和(2)产生,*,中的字外,*,中再没有其它字。,例如,若,=0,1,则,*,=,0,1,00,01, 10,11,000,001,是有限二进制序列的集合, 其中包含空序列。,8,算术表达式集合是包含整数, 一元运算符+,-, 以及二元运算符+,-,* ,/的符号序列所组成的集合,(3+5)/4),(-5)+6)*3),9,算术表达式集合的递归定义如下:,(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)而得到。,10,后继集合的概念:,设,A,是任一给定集合,AA,称为,A,的后继集合, 简称后继, 记为,A,+,。,定义4.2:设,N,为自然数集, 它的递归定义如下:,(1)(基础),N。,(2)(,归纳)如果,n,N,则,n,+,N(,这里,n,+,=nn)。,(3)(,闭合)如果,S,N,且,S,满足(1)、(2)则,S=N,。,11,自然数集的元素为:,+,(,+,),+,(,+,),+,),+,即为:,可以简化为:,用记号:=给这些集合命名,例如,命名为0,记为0:=,0:=,;,1:=0,+,=,=0;,2:=1,+,=,=0,1;,3:=2,+,=,=0,1,2,若已给出,n,则,n+1:=n,+,=0,1,2,n,12,定理4.1:(1)0不是任何自然数的后继。,(2)任何自然数的后继是唯一的。,(3)如果,n,+,=m,+,则,n=m。,贝安诺(,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。,13,4.2 基数,一、基数概念,在棋盘的第一个方格内放一粒米，以后每一小格内都比前一小格加一倍，最后摆满所有64格,1+2+2,2,+,+2,63,=2,64,-1,约合140亿升,所有整数的个数，,一条线上所有几何点个数(即区间,a,b,上 个数),14,比较一堆珠子和一堆铜币哪个多，,把珠子和铜币逐个比较，最后看哪堆有多余，若同时没有则两者相同。,定义4.3：设,A,B,是任意两个集合,若存在一个双射,f,:AB,则称,A,和,B,对等,(或,等势,),记为,AB;,或称,A,和,B,的,基数相同,。,A,的基数记为|,A|;A,和,B,的基数相同记为|,A|=|B|,15,二、无限集,定义4.4：设,A,为一个集合, 若,A,为空集或与集合0,1,2,n-1,的基数相同, 则称,A,为,有限集,且|,A|=n,N。,若集合,A,不是有限集, 则称,A,为,无限集,。,定理4.2:自然数集,N,是无限集。,没有一个自然数能作为,N,的基数,因此今后将记|,N|,为,0,读作阿列夫零。,16,定理4.2:自然数集,N,是无限集。,即证明,N,不是有限集.,关键证明对任何,n,N，,不存在从0,1,2,n-1,到,N,的双射。,证明：设,n,是,N,中任一元素，,f,是从0,1,2,n-1,到,N,的任一函数，,没有一个自然数能作为,N,的基数,因此今后我们将记|,N|,为,0,读作阿列夫零。,17,例:设,N,与,Z,之间有如下一一对应:,N: 0,1, 2,3, 4,5, 6,Z: 0,1,-1,2,-2,3,-3,即存在双射,f,:NZ,使对,n,N,所以|,Z|=,0,。,18,例:设,E=0,2,4,因为存在,f,: NE,对任何,n,N,有,f,(n)=2n ,显然,f,是,NE,的双射。,这里,E,是,N,的真子集,然而|,E|=|N|=,0,。,这一事实揭示了无限集的一个重要特征:,即无限集可以与它的一个真子集对等。,19,定理4.3:无限集必与它的一个真子集对等。,证明：基本思路,A,是构造一个真子集,然后证明两者之间存在双射,推论:凡不能与自身的任一真子集对等的集合为有限集。,凡能与自身的某一真子集对等的集合称为无限集,否则称为有限集。,前面的例子和定理说明了这样的事实：在无穷大的世界里，部分可能等于全部。那么是否无穷大数都是相等的？,20,4.3 可列集与不可列集,定义4.5：若存在从,N,到,A,的双射, 则称,A,为,可列无限集, 简称,可列集,或,可数集, |,A|=,0,。,定理(一)：设,A,是可列集, 若存在从,A,到,B,的双射,则,B,也是可列集。,目标证明存在,N,到,A,的双射.,21,定理(二)：集合,A,是可列集的充要条件是集合,A,中的元素可以排成一个无穷序列的形式:,a,0,a,1,a,2,a,3,a,4,。,利用自然数有序性,目标证明存在,N,到,A,的双射,。,定理4.4：任何无限集必含有一个可列子集。,采用构造方法,从无限集中构造一个无穷序列,22,定理4.5：可列集的任何无限子集必为可列集。,定理4.6：可列集中加入有限个元素(或删去有限个元素), 仍为可列集。,23,作业:,P76 1,补充:,证明定理(五)：设,P(n),是一个与自然数,n,有关的结论。若对于自然数0，结论成立；并且当对自然数,0,1,2,k,结论成立时，对于自然数,k+1,结论也成立，则该结论对所有自然数都成立。,24,1.,设,A,和,B,是集合，证明：,A=B,当且仅当,AB=AB,2.,一个,A,上的二元关系,R,称为循环的，如果对任意的,a,b,c,A,若,aRb,bRc,必有,cRa.,证明,:R,是自反和循环的当且仅当,R,是等价关系,25,
展开阅读全文