集合论与图论：第10讲 自然数

第10讲自然数内容提要1.Peano系统2.后继,归纳集,自然数,自然数集3.数学归纳法原理4.传递集

5.自然数的运算6.自然数上的序关系2023/1/111《集合论与图论》第10讲封闭封闭:设f是函数,Adomf,若x(xAf(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下是封闭的2023/1/112《集合论与图论》第10讲Peano系统Peano系统:<M,F,e>,F:MM(1)eM(2)M在F下封闭(3)eranF(4)F是单射的(5)(极小性公理)AMeAA在F下封闭A=MeF(e)F2(e)F3(e)2023/1/113《集合论与图论》第10讲为何如此定义?2023/1/114《集合论与图论》第10讲如何实现?如何利用集合来构造Peano系统?----借助于下面两个概念后继归纳集2023/1/115《集合论与图论》第10讲后继(successor)后继(successor):设A是集合,A+=A{A}称为A的后继.特征:AA+AA+在公理集合论中,无序对公理({a,b})和并集公理(UA)保证了后继的存在2023/1/116《集合论与图论》第10讲后继(举例)A=A+=+={}={}A++={}+={}{{}}={,{}}A+++={,{}}+={,{}}{{,{}}}={,{},{,{}}}A={a,b}A+={a,b}{A}={a,b,A}={a,b,{a,b}}2023/1/117《集合论与图论》第10讲归纳集归纳集:若A满足(1)A(2)x(xAx+A)则称A为归纳集.A是归纳集A含有且对后继封闭在公理集合论中,无穷公理(无穷集存在)保证了归纳集的存在2023/1/118《集合论与图论》第10讲归纳集(举例)A={,+,++,+++,…}A={,+,++,+++,…,a,a+,a++,a+++,…}A={+,++,+++},少A={,+,++,+++,…,a},少a+,a++,a+++,…2023/1/119《集合论与图论》第10讲自然数自然数:自然数是属于每个归纳集的集合例:,+={},++

={,{}},+++={,{},{,{}}

},++++={,{},{,{}},{,{},{,{}}}

},……2023/1/1110《集合论与图论》第10讲0,1,2,…,n,…0=1=+={}={0}

2=++={,{}}={0,1}3=+++={0,1,2}……n={0,1,2,…,n-1}2023/1/1111《集合论与图论》第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…0123…2023/1/1112《集合论与图论》第10讲自然数集自然数集N:设D={v|v是归纳集},N=∩DD不是集合,否则导致悖论!在公理集合论中,由无穷公理保证N存在(即保证N是集合).2023/1/1113《集合论与图论》第10讲定理1定理1:N是归纳集.证明:N=∩D=∩{v|v是归纳集}={x|v(v是归纳集xv)}.(1)N:

v,v是归纳集

v.2023/1/1114《集合论与图论》第10讲定理1(续):证明(续):(2)n(nNn+N).利用xN

v(v是归纳集xv)以及v(v是归纳集

n(nvn+v)):n,nNv(v是归纳集nv)v(v是归纳集n+v)n+N.#2023/1/1115《集合论与图论》第10讲N=?N是最小的归纳集v(v是归纳集)NvN={0,1,2,3,…}对比:自然数是属于每个归纳集的集合自然数集是包含于每个归纳集的归纳集2023/1/1116《集合论与图论》第10讲后继函数后继函数::NN,nN,(n)=n+例:(0)=0+=1,(1)=1+=2=0++,

(2)=2+=3=1++=0+++,……#2023/1/1117《集合论与图论》第10讲N是否Peano系统?定理2:<N,,0>是Peano系统.证明:(1)N:定理1.(2)n(nNn+N):定理1.(3)ran:(n)=n+=n{n}(4)是单射的:下面定理3(5)SNSnS(n+S)S=N:SnS(n+S)S是归纳集NS.#称(5)为数学归纳法原理.证(5)时没有利用(4),故可用(5)证(4).2023/1/1118《集合论与图论》第10讲数学归纳法原理数学归纳法分两个步骤:1.令S={n|nNP(n)}2.证明(1)S;(2)n(nSn+S).2023/1/1119《集合论与图论》第10讲定理3定理3:任何自然数的元素均为它的子集.证明:1.令S={n|nNx(xnxn)}.2.(1)S:Nx(xx)(2)设nS,要证n+S,即要证n+Nx(xn+xn+).x,设xn+=n{n},分两种情况:(a)x=nx=nn+,(n+=n{n})(b)xnxnn+,(归纳假设)S=N.#2023/1/1120《集合论与图论》第10讲定理4定理4:m,nN,m+n+

mn.证明:()定理3()归纳法.#2023/1/1121《集合论与图论》第10讲定理5:定理5:任何自然数都不是自己的元素.证明:S={n|nNnn}.#2023/1/1122《集合论与图论》第10讲定理6定理6:属于除0外的任何自然数.证明:S={0}S’,S’={n|nNn0n}.(1)S,(2)nSn+S.#2023/1/1123《集合论与图论》第10讲定理7(三歧性)定理7(三歧性):m,nN,下面三式成立且仅成立一式.mn,m=n,nm证明:(1).至多成立一式:定理5.(2).至少成立一式:S={n|nNm(mNmnm=nnm)}.#2023/1/1124《集合论与图论》第10讲传递集传递集:A为传递集xy(xyyAxA)定理10:A为传递集

UAAx(xAxA)AP(A).#自然数及自然数集都是传递集.2023/1/1125《集合论与图论》第10讲自然数的运算加法:+:NNN,+(<2,3>)=5,2+3=5乘法::NNN,(<2,3>)=6,23=62023/1/1126《集合论与图论》第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+)102342023/1/1127《集合论与图论》第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.

2023/1/1128《集合论与图论》第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.#递归定理保证如此定义是有意义的2023/1/1129《集合论与图论》第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.#2023/1/1130《集合论与图论》第10讲m,nN,

m+n+=(m+n)+m,nN,m+n+=(m+n)+证明:m+n+=Am(n+)(+定义)=(Am(n))+(Am定义)=(m+n)+(+定义).#2023/1/1131《集合论与图论》第10讲m,nN,m++n=(m+n)+证明:(数学归纳法).对任意mN,

令S={n|nNm++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.#2023/1/1132《集合论与图论》第10讲加法交换律加法交换律:m,nN,

m+n=n+m.证明:对任意mN,令S={n|nNm+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.#2023/1/1133《集合论与图论》第10讲加法性质加法单位元0:0+n=n+0=n交换律:n+m=m+n结合律:(m+n)+k=m+(n+k)2023/1/1134《集合论与图论》第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.#2023/1/1135《集合论与图论》第10讲乘法性质1是乘法单位元:1n=n1=n交换律:nm=mn结合律:(mn)k=m(nk)分配律:m(n+k)=(mn)+(mk)2023/1/1136《集合论与图论》第10讲自然数的序“属于等于”:mnmnm=n“小于等于”:

mnm<nm=nm<nmnm>nnmmnmnmnnm2023/1/1137《集合论与图论》第10讲总结1.Peano系统2.后继,归纳集,自然数,自然数集3.数学归纳法原理4.传递集5.自然数的运算6.自然数上的序关系2023/1/1138《集合论与图论》第10讲作业讲解(#1)p25,习题一,3,7,10,163.TF,FT,TT,FT,TFF7.10.TT,FT,TF16.{{3},{4},3,4},,{,{}}ABCABCABCABC2023/1/1139《集合论与图论》第10讲作业讲解(#2)p27,习题一,11,13,14,2011.A-B=AAB=证一:利用A=(A-B)(AB),(A-B)(AB)=证二:A~Bx(xAxB)x(xAxB)AB=AB2023/1/1140《集合论与图论》第10讲作业讲解(#2)13.(1)证一:直接证.证二:利用XY=YXY

(2)AC=(利用文氏图)14.利用X=(X-Y)(XY)20.类似14题.2023/1/1141《集合论与图论》第10讲习题讲解(#3)

p80,习题二,6,7,11,126.(1)(2)7.(1)(2)-----------OK2023/1/1142《集合论与图论》第10讲习题讲解(#3)11.(1)R1R2={<a,b>,<b,d>,<c,c>,<c,d>,<a,c>,<d,b>,<d,d>}R1R2={<b,d>}R1R2={<a,b>,<c,c>,<c,d>,<a,c>,<d,b>,<d,d>}(2)domR1={a,b,c}domR2={a,b,d}

dom(R1R2)={a,b,c,d}2023/1/1143《集合论与图论》第10讲习题讲解(#3)11.(3)ranR1={b,c,d}ranR2={b,c,d}ranR1ranR2={b,c,d}(4)R1A={<a,b>,<c,c>,<c,d>}R1{c}={<c,c>,<c,d>}(R1R2)A={<a,b>,<c,c>,<c,d>,<a,c>}R2A={<a,c>}2023/1/1144《集合论与图论》第10讲习题讲解(#3)11.(5)R1[A]={b,c,d}R2[A]={c}(R1R2)[A]=(6)R1○R2={<a,c>,<a,d>,<d,d>}R2○R1={<a,d>,<b,b>,<b,d>,<c,d>,<c,b>}R1○R1={<a,d>,<c,c>,<c,d>}.#2023/1/1145《集合论与图论》第10讲习题讲解(#3)p80,习题二,12.(1)R-1={<{,{}},>,<,{}>,<,>}(2)R○R={<{},{,{}}>,<{},>,

<,{,{}}>,<,>}(3)