第10講自然數(shù)內(nèi)容提要1.Peano系統(tǒng)2.后繼,歸納集,自然數(shù),自然數(shù)集3.數(shù)學(xué)歸納法原理4.傳遞集

5.自然數(shù)的運(yùn)算6.自然數(shù)上的序關(guān)系2023/1/111《集合論與圖論》第10講封閉封閉:設(shè)f是函數(shù),Adomf,若x(xAf(x)A)則稱A在f下是封閉的(closed)等價(jià)條件: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系統(tǒng)Peano系統(tǒng):<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講如何實(shí)現(xiàn)?如何利用集合來構(gòu)造Peano系統(tǒng)?----借助于下面兩個(gè)概念后繼歸納集2023/1/115《集合論與圖論》第10講后繼(successor)后繼(successor):設(shè)A是集合,A+=A{A}稱為A的后繼.特征:AA+AA+在公理集合論中,無序?qū)?{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含有且對(duì)后繼封閉在公理集合論中,無窮公理(無窮集存在)保證了歸納集的存在2023/1/118《集合論與圖論》第10講歸納集(舉例)A={,+,++,+++,…}A={,+,++,+++,…,a,a+,a++,a+++,…}A={+,++,+++},少A={,+,++,+++,…,a},少a+,a++,a+++,…2023/1/119《集合論與圖論》第10講自然數(shù)自然數(shù):自然數(shù)是屬于每個(gè)歸納集的集合例:,+={},++

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

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

},……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(-是集合運(yùn)算)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講自然數(shù)集自然數(shù)集N:設(shè)D={v|v是歸納集},N=∩DD不是集合,否則導(dǎo)致悖論!在公理集合論中,由無窮公理保證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(續(xù)):證明(續(xù)):(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,…}對(duì)比:自然數(shù)是屬于每個(gè)歸納集的集合自然數(shù)集是包含于每個(gè)歸納集的歸納集2023/1/1116《集合論與圖論》第10講后繼函數(shù)后繼函數(shù)::NN,nN,(n)=n+例:(0)=0+=1,(1)=1+=2=0++,

(2)=2+=3=1++=0+++,……#2023/1/1117《集合論與圖論》第10講N是否Peano系統(tǒng)?定理2:<N,,0>是Peano系統(tǒng).證明:(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)為數(shù)學(xué)歸納法原理.證(5)時(shí)沒有利用(4),故可用(5)證(4).2023/1/1118《集合論與圖論》第10講數(shù)學(xué)歸納法原理數(shù)學(xué)歸納法分兩個(gè)步驟:1.令S={n|nNP(n)}2.證明(1)S;(2)n(nSn+S).2023/1/1119《集合論與圖論》第10講定理3定理3:任何自然數(shù)的元素均為它的子集.證明:1.令S={n|nNx(xnxn)}.2.(1)S:Nx(xx)(2)設(shè)nS,要證n+S,即要證n+Nx(xn+xn+).x,設(shè)xn+=n{n},分兩種情況:(a)x=nx=nn+,(n+=n{n})(b)xnxnn+,(歸納假設(shè))S=N.#2023/1/1120《集合論與圖論》第10講定理4定理4:m,nN,m+n+

mn.證明:()定理3()歸納法.#2023/1/1121《集合論與圖論》第10講定理5:定理5:任何自然數(shù)都不是自己的元素.證明:S={n|nNnn}.#2023/1/1122《集合論與圖論》第10講定理6定理6:屬于除0外的任何自然數(shù).證明: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).#自然數(shù)及自然數(shù)集都是傳遞集.2023/1/1125《集合論與圖論》第10講自然數(shù)的運(yùn)算加法:+:NNN,+(<2,3>)=5,2+3=5乘法::NNN,(<2,3>)=6,23=62023/1/1126《集合論與圖論》第10講N上的遞歸定理N上的遞歸定理:設(shè)A為集合,aA,F:AA,則存在唯一函數(shù)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講一元函數(shù)加法:“加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講二元函數(shù)加法加法:+: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)+證明:(數(shù)學(xué)歸納法).對(duì)任意mN,

令S={n|nNm++n=(m+n)+

}.(1)0S:m++0=m+=(m+0)+.

(2)n(nSn+S):設(shè)nS,下證n+S.m++n+=Am+(n+)=Am+(n)+(+與Am定義)=(m++n)+=(m+n)++(歸納假設(shè))=(m+n+)+(定理:m+n+=(m+n)+)S=N.#2023/1/1132《集合論與圖論》第10講加法交換律加法交換律:m,nN,

m+n=n+m.證明:對(duì)任意mN,令S={n|nNm+n=n+m}.(1)0S:m+0=m=0+m.(0是加法單位元)(2)n(nSn+S):設(shè)nS,下證n+S.m+n+=Am(n+)=Am(n)+=(m+n)+=(n+m)+(歸納假設(shè))=n++m(性質(zhì):m++n=(m+n)+)S=N.#2023/1/1133《集合論與圖論》第10講加法性質(zhì)加法單位元0:0+n=n+0=n交換律:n+m=m+n結(jié)合律:(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講乘法性質(zhì)1是乘法單位元:1n=n1=n交換律:nm=mn結(jié)合律:(mn)k=m(nk)分配律:m(n+k)=(mn)+(mk)2023/1/1136《集合論與圖論》第10講自然數(shù)的序“屬于等于”:mnmnm=n“小于等于”:

mnm<nm=nm<nmnm>nnmmnmnmnnm2023/1/1137《集合論與圖論》第10講總結(jié)1.Peano系統(tǒng)2.后繼,歸納集,自然數(shù),自然數(shù)集3.數(shù)學(xué)歸納法原理4.傳遞集5.自然數(shù)的運(yùn)算6.自然數(shù)上的序關(guān)系2023/1/1138《集合論與圖論》第10講作業(yè)講解(#1)p25,習(xí)題一,3,7,10,163.TF,FT,TT,FT,TFF7.10.TT,FT,TF16.{{3},{4},3,4},,{,{}}ABCABCABCABC2023/1/1139《集合論與圖論》第10講作業(yè)講解(#2)p27,習(xí)題一,11,13,14,2011.A-B=AAB=證一:利用A=(A-B)(AB),(A-B)(AB)=證二:A~Bx(xAxB)x(xAxB)AB=AB2023/1/1140《集合論與圖論》第10講作業(yè)講解(#2)13.(1)證一:直接證.證二:利用XY=YXY

(2)AC=(利用文氏圖)14.利用X=(X-Y)(XY)20.類似14題.2023/1/1141《集合論與圖論》第10講習(xí)題講解(#3)

p80,習(xí)題二,6,7,11,126.(1)(2)7.(1)(2)-----------OK2023/1/1142《集合論與圖論》第10講習(xí)題講解(#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講習(xí)題講解(#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講習(xí)題講解(#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講習(xí)題講解(#3)p80,習(xí)題二,12.(1)R-1={<{,{}},>,<,{}>,<,>}(2)R○R={<{},{,{}}>,<{},>,

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