资源描述
第10讲 自然数内容提要 1.Peano系统 2.后继,归纳集,自然数,自然数集 3.数学归纳法原理 4.传递集 5.自然数的运算 6.自然数上的序关系2024/7/81集合论与图论第10讲封闭封闭:设f是函数,Adomf,若x(xA f(x)A)则称A在f下是封闭的(closed)等价条件:f(A)A例:f:NN,f(x)=x+1,A=0,2,4,6,在f下不是封闭的B=2,3,4,在f下是封闭的2024/7/82集合论与图论第10讲Peano系统Peano系统:,F:MM(1)eM(2)M在F下封闭(3)eranF(4)F是单射的(5)(极小性公理)AM eA A在F下封闭 A=MeF(e)F2(e)F3(e)2024/7/83集合论与图论第10讲为何如此定义?2024/7/84集合论与图论第10讲如何实现?如何利用集合来构造Peano系统?-借助于下面两个概念后继归纳集2024/7/85集合论与图论第10讲后继(successor)后继(successor):设A是集合,A+=AA称为A的后继.特征:AA+AA+在公理集合论中,无序对公理(a,b)和并集公理(UA)保证了后继的存在2024/7/86集合论与图论第10讲后继(举例)A=A+=+=A+=+=,A+=,+=,=,A=a,b A+=a,bA=a,b,A=a,b,a,b2024/7/87集合论与图论第10讲归纳集归纳集:若A满足 (1)A (2)x(xA x+A)则称A为归纳集.A是归纳集 A含有且对后继封闭在公理集合论中,无穷公理(无穷集存在)保证了归纳集的存在2024/7/88集合论与图论第10讲归纳集(举例)A=,+,+,+,A=,+,+,+,a,a+,a+,a+,A=+,+,+,少A=,+,+,+,a,少a+,a+,a+,2024/7/89集合论与图论第10讲自然数自然数:自然数是属于每个归纳集的集合例:,+=,+=,+=,+=,2024/7/810集合论与图论第10讲0,1,2,n,0=1=+=0 2=+=,=0,13=+=0,1,2 n=0,1,2,n-1 2024/7/811集合论与图论第10讲0,1,2,作为集合23=2=min(2,3),23=3=max(2,3)3-2=2,2-3=0 (-是集合运算)Un=U 0,1,2,n-1 =n-1 =max(0,1,n-1),n=0,1,2,n-1 =0 =min(0,1,n-1),0123 01232024/7/812集合论与图论第10讲自然数集自然数集N:设D=v|v是归纳集,N=DD 不是集合,否则导致悖论!在公理集合论中,由无穷公理保证 N 存在(即保证 N 是集合).2024/7/813集合论与图论第10讲定理1定理1:N是归纳集.证明:N=D=v|v是归纳集 =x|v(v是归纳集xv).(1)N:v,v是归纳集 v.2024/7/814集合论与图论第10讲定理1(续):证明(续):(2)n(nN n+N).利用 xN v(v是归纳集xv)以及v(v是归纳集 n(nv n+v):n,nN v(v是归纳集nv)v(v是归纳集n+v)n+N.#2024/7/815集合论与图论第10讲N=?N是最小的归纳集v(v是归纳集)NvN=0,1,2,3,对比:自然数 是 属于每个归纳集的集合自然数集是包含于每个归纳集的归纳集2024/7/816集合论与图论第10讲后继函数后继函数:NN,nN,(n)=n+例:(0)=0+=1,(1)=1+=2=0+,(2)=2+=3=1+=0+,#2024/7/817集合论与图论第10讲N是否Peano系统?定理2:是Peano系统.证明:(1)N:定理1.(2)n(nNn+N):定理1.(3)ran:(n)=n+=nn(4)是单射的:下面定理3(5)SNSnS(n+S)S=N:SnS(n+S)S是归纳集NS.#称(5)为数学归纳法原理.证(5)时没有利用(4),故可用(5)证(4).2024/7/818集合论与图论第10讲数学归纳法原理数学归纳法分两个步骤:1.令 S=n|nN P(n)2.证明 (1)S;(2)n(nS n+S).2024/7/819集合论与图论第10讲定理3定理3:任何自然数的元素均为它的子集.证明:1.令S=n|nN x(xnxn).2.(1)S:N x(xx)(2)设nS,要证n+S,即要证 n+N x(xn+xn+).x,设xn+=nn,分两种情况:(a)x=n x=nn+,(n+=nn)(b)xn xnn+,(归纳假设)S=N.#2024/7/820集合论与图论第10讲定理4定理4:m,nN,m+n+mn.证明:()定理3 ()归纳法.#2024/7/821集合论与图论第10讲定理5:定理5:任何自然数都不是自己的元素.证明:S=n|nN nn.#2024/7/822集合论与图论第10讲定理6定理6:属于除0外的任何自然数.证明:S=0S,S=n|nN n0 n.(1)S,(2)nS n+S.#2024/7/823集合论与图论第10讲定理7(三歧性)定理7(三歧性):m,nN,下面三式成立且仅成立一式.mn,m=n,nm证明:(1).至多成立一式:定理5.(2).至少成立一式:S=n|nNm(mNmnm=nnm).#2024/7/824集合论与图论第10讲传递集传递集:A为传递集 xy(xy yA xA)定理10:A为传递集 UAA x(xA xA)A P(A).#自然数及自然数集都是传递集.2024/7/825集合论与图论第10讲自然数的运算加法:+:NNN,+()=5,2+3=5乘法:NNN,()=6,23=6 2024/7/826集合论与图论第10讲N上的递归定理N上的递归定理:设A为集合,aA,F:AA,则存在唯一函数h:NA,使得h(0)=a,且nN,h(n+)=F(h(n).#F(a)=F(h(0)=h(1)=h(0+)a=h(0)F2(a)=F(F(a)=F(h(1)=h(2)=h(1+)F3(a)=F(F2(a)=F(h(2)=h(3)=h(2+)F4(a)=F(F3(a)=F(h(3)=h(4)=h(3+)102342024/7/827集合论与图论第10讲一元函数加法:“加m”“加m”:m固定,Am:NN,Am(0)=m,Am(n+)=(Am(n)+.例:A2(3)=A2(2+)=A2(2)+=A2(1+)+=A2(1)+=A2(0+)+=A2(0)+=2+=3+=4+=5.2024/7/828集合论与图论第10讲二元函数加法加法:+:NNN,m+n=Am(n)例:3+3=A3(3)=A3(2+)=A3(2)+=A3(1+)+=A3(1)+=A3(0+)+=A3(0)+=3+=4+=5+=6.#递归定理保证如此定义是有意义的2024/7/829集合论与图论第10讲加法单位元0mN,0+m=m,m+0=m证明:(1)0+m=A0(m)(+定义)=0(m)(Am定义)=IN(m),(R0定义)=m (2)m+0=Am(0)=m.#2024/7/830集合论与图论第10讲m,nN,m+n+=(m+n)+m,nN,m+n+=(m+n)+证明:m+n+=Am(n+)(+定义)=(Am(n)+(Am定义)=(m+n)+(+定义).#2024/7/831集合论与图论第10讲m,nN,m+n=(m+n)+证明:(数学归纳法).对任意mN,令 S=n|nN m+n=(m+n)+.(1)0S:m+0=m+=(m+0)+.(2)n(nSn+S):设nS,下证n+S.m+n+=Am+(n+)=Am+(n)+(+与Am定义)=(m+n)+=(m+n)+(归纳假设)=(m+n+)+(定理:m+n+=(m+n)+)S=N.#2024/7/832集合论与图论第10讲加法交换律加法交换律:m,nN,m+n=n+m.证明:对任意mN,令S=n|nN m+n=n+m.(1)0S:m+0=m=0+m.(0是加法单位元)(2)n(nSn+S):设nS,下证n+S.m+n+=Am(n+)=Am(n)+=(m+n)+=(n+m)+(归纳假设)=n+m (性质:m+n=(m+n)+)S=N.#2024/7/833集合论与图论第10讲加法性质加法单位元0:0+n=n+0=n交换律:n+m=m+n结合律:(m+n)+k=m+(n+k)2024/7/834集合论与图论第10讲乘法“乘m”:m固定,Mm:NN,Mm(0)=0,Mm(n+)=Mm(n)+m.例:M2(3)=M2(2+)=M2(2)+2=M2(1+)+2=M2(1)+2+2=M2(0)+2+2+2=0+2+2+2=6.乘法:NNN,mn=Mm(n)例:32=M3(2)=M3(1)+3=M3(0)+3+3 =0+3+3=3+=6.#2024/7/835集合论与图论第10讲乘法性质1是乘法单位元:1n=n1=n交换律:nm=mn结合律:(mn)k=m(nk)分配律:m(n+k)=(mn)+(mk)2024/7/836集合论与图论第10讲自然数的序“属于等于”:mn mn m=n“小于等于”:mn mn m=n mn nm mn mn mn nm2024/7/837集合论与图论第10讲总结 1.Peano系统 2.后继,归纳集,自然数,自然数集 3.数学归纳法原理 4.传递集 5.自然数的运算 6.自然数上的序关系2024/7/838集合论与图论第10讲作业讲解(#1)p25,习题一,3,7,10,163.TF,FT,TT,FT,TFF7.10.TT,FT,TF16.3,4,3,4,ABCABCABCABC2024/7/839集合论与图论第10讲作业讲解(#2)p27,习题一,11,13,14,2011.A-B=AAB=证一:利用 A=(A-B)(AB),(A-B)(AB)=证二:AB x(xAxB)x(xAxB)AB=AB2024/7/840集合论与图论第10讲作业讲解(#2)13.(1)证一:直接证.证二:利用XY=Y XY (2)AC=(利用文氏图)14.利用X=(X-Y)(XY)20.类似14题.2024/7/841集合论与图论第10讲习题讲解(#3)p80,习题二,6,7,11,126.(1)(2)7.(1)(2)-OK2024/7/842集合论与图论第10讲习题讲解(#3)11.(1)R1R2=,R1R2=R1R2=,(2)domR1=a,b,c domR2=a,b,d dom(R1R2)=a,b,c,d2024/7/843集合论与图论第10讲习题讲解(#3)11.(3)ranR1=b,c,d ranR2=b,c,d ranR1ranR2=b,c,d(4)R1A=,R1c=,(R1R2)A=,R2A=2024/7/844集合论与图论第10讲习题讲解(#3)11.(5)R1A=b,c,d R2A=c (R1R2)A=(6)R1R2=,R2R1=,R1R1=,.#2024/7/845集合论与图论第10讲习题讲解(#3)p80,习题二,12.(1)R-1=,(2)RR=,(3)R=R=,R=R,=,2024/7/846集合论与图论第10讲习题讲解(#3)12.(4)R=R=,R=R,=,(5)domR=,ranR=,fldR=,#2024/7/847集合论与图论第10讲习题讲解(#4)p81,习题二,15,16,17,22,2315.R:反自反,反对称,传递 S:对称 T:对称 (严格说,应按|A|分情形讨论)16.|R|=11,对称|S|=5,反对称2024/7/848集合论与图论第10讲习题讲解(#4)17.自反,对称01232024/7/849集合论与图论第10讲习题讲解(#4)22.利用 R传递 RRR R自反 IAR.反例:,(RR=RR传递,反例只能破坏自反性)23.利用 (RS)-1=S-1R-1,R对称 R-1=R.2024/7/850集合论与图论第10讲作业(#8)p125,习题四,3,7今天交作业#5,#6,#72024/7/851集合论与图论第10讲
展开阅读全文