北大集合論與圖論

北大集合論與圖論第1頁/共52頁2023/3/22

牛牛文庫文檔分享2封閉封閉:設(shè)f是函數(shù),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下是封閉的第2頁/共52頁2023/3/22

牛牛文庫文檔分享3Peano系統(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)第3頁/共52頁2023/3/22

牛牛文庫文檔分享4為何如此定義?第4頁/共52頁2023/3/22

牛牛文庫文檔分享5如何實現(xiàn)?如何利用集合來構(gòu)造Peano系統(tǒng)?----借助于下面兩個概念后繼歸納集第5頁/共52頁2023/3/22

牛牛文庫文檔分享6后繼(successor)后繼(successor):設(shè)A是集合,A+=A{A}稱為A的后繼.特征:AA+AA+在公理集合論中,無序?qū)?{a,b})和并集公理(UA)保證了后繼的存在第6頁/共52頁2023/3/22

牛牛文庫文檔分享7后繼(舉例)A=A+=+={}={}A++={}+={}{{}}={,{}}A+++={,{}}+={,{}}{{,{}}}={,{},{,{}}}A={a,b}A+={a,b}{A}={a,b,A}={a,b,{a,b}}第7頁/共52頁2023/3/22

牛牛文庫文檔分享8歸納集歸納集:若A滿足(1)A(2)x(xAx+A)則稱A為歸納集.A是歸納集A含有且對后繼封閉在公理集合論中,無窮公理(無窮集存在)保證了歸納集的存在第8頁/共52頁2023/3/22

牛牛文庫文檔分享9歸納集(舉例)A={,+,++,+++,…}A={,+,++,+++,…,a,a+,a++,a+++,…}A={+,++,+++},少A={,+,++,+++,…,a},少a+,a++,a+++,…第9頁/共52頁2023/3/22

牛牛文庫文檔分享10自然數(shù)自然數(shù):自然數(shù)是屬于每個歸納集的集合例:,+={},++

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

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

},……第10頁/共52頁2023/3/22

牛牛文庫文檔分享110,1,2,…,n,…0=1=+={}={0}

2=++={,{}}={0,1}3=+++={0,1,2}……n={0,1,2,…,n-1}第11頁/共52頁2023/3/22

牛牛文庫文檔分享120,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…第12頁/共52頁2023/3/22

牛牛文庫文檔分享13自然數(shù)集自然數(shù)集N:設(shè)D={v|v是歸納集},N=∩DD不是集合,否則導(dǎo)致悖論!在公理集合論中,由無窮公理保證N存在(即保證N是集合).第13頁/共52頁2023/3/22

牛牛文庫文檔分享14定理1定理1:N是歸納集.證明:N=∩D=∩{v|v是歸納集}={x|v(v是歸納集xv)}.(1)N:

v,v是歸納集

v.第14頁/共52頁2023/3/22

牛牛文庫文檔分享15定理1(續(xù)):證明(續(xù)):(2)n(nNn+N).利用xNv(v是歸納集xv)以及v(v是歸納集

n(nvn+v)):n,nNv(v是歸納集nv)v(v是歸納集n+v)n+N.#第15頁/共52頁2023/3/22

牛牛文庫文檔分享16N=?N是最小的歸納集v(v是歸納集)NvN={0,1,2,3,…}對比:自然數(shù)是屬于每個歸納集的集合自然數(shù)集是包含于每個歸納集的歸納集第16頁/共52頁2023/3/22

牛牛文庫文檔分享17后繼函數(shù)后繼函數(shù)::NN,nN,(n)=n+例:(0)=0+=1,(1)=1+=2=0++,

(2)=2+=3=1++=0+++,……#第17頁/共52頁2023/3/22

牛牛文庫文檔分享18N是否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)時沒有利用(4),故可用(5)證(4).第18頁/共52頁2023/3/22

牛牛文庫文檔分享19數(shù)學(xué)歸納法原理數(shù)學(xué)歸納法分兩個步驟:1.令S={n|nNP(n)}2.證明(1)S;(2)n(nSn+S).第19頁/共52頁2023/3/22

牛牛文庫文檔分享20定理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.#第20頁/共52頁2023/3/22

牛牛文庫文檔分享21定理4定理4:m,nN,m+n+

mn.證明:()定理3()歸納法.#第21頁/共52頁2023/3/22

牛牛文庫文檔分享22定理5:定理5:任何自然數(shù)都不是自己的元素.證明:S={n|nNnn}.#第22頁/共52頁2023/3/22

牛牛文庫文檔分享23定理6定理6:屬于除0外的任何自然數(shù).證明:S={0}S’,S’={n|nNn0n}.(1)S,(2)nSn+S.#第23頁/共52頁2023/3/22

牛牛文庫文檔分享24定理7(三歧性)定理7(三歧性):m,nN,下面三式成立且僅成立一式.mn,m=n,nm證明:(1).至多成立一式:定理5.(2).至少成立一式:S={n|nNm(mNmnm=nnm)}.#第24頁/共52頁2023/3/22

牛牛文庫文檔分享25傳遞集傳遞集:A為傳遞集xy(xyyAxA)定理10:A為傳遞集

UAAx(xAxA)AP(A).#自然數(shù)及自然數(shù)集都是傳遞集.第25頁/共52頁2023/3/22

牛牛文庫文檔分享26自然數(shù)的運算加法:+:NNN,+(<2,3>)=5,2+3=5乘法::NNN,(<2,3>)=6,23=6第26頁/共52頁2023/3/22

牛牛文庫文檔分享27N上的遞歸定理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+)10234第27頁/共52頁2023/3/22

牛牛文庫文檔分享28一元函數(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.

第28頁/共52頁2023/3/22

牛牛文庫文檔分享29二元函數(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.#遞歸定理保證如此定義是有意義的第29頁/共52頁2023/3/22

牛牛文庫文檔分享30加法單位元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.#第30頁/共52頁2023/3/22

牛牛文庫文檔分享31m,nN,

m+n+=(m+n)+m,nN,m+n+=(m+n)+證明:m+n+=Am(n+)(+定義)=(Am(n))+(Am定義)=(m+n)+(+定義).#第31頁/共52頁2023/3/22

牛牛文庫文檔分享32m,nN,m++n=(m+n)+證明:(數(shù)學(xué)歸納法).對任意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.#第32頁/共52頁2023/3/22

牛牛文庫文檔分享33加法交換律加法交換律: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):設(shè)nS,下證n+S.m+n+=Am(n+)=Am(n)+=(m+n)+=(n+m)+(歸納假設(shè))=n++m(性質(zhì):m++n=(m+n)+)S=N.#第33頁/共52頁2023/3/22

牛牛文庫文檔分享34加法性質(zhì)加法單位元0:0+n=n+0=n交換律:n+m=m+n結(jié)合律:(m+n)+k=m+(n+k)第34頁/共52頁2023/3/22

牛牛文庫文檔分享35乘法“乘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.#第35頁/共52頁2023/3/22

牛牛文庫文檔分享36乘法性質(zhì)1是乘法單位元:1n=n1=n交換律:nm=mn結(jié)合律:(mn)k=m(nk)分配律:m(n+k)=(mn)+(mk)第36頁/共52頁2023/3/22

牛牛文庫文檔分享37自然數(shù)的序“屬于等于”:mnmnm=n“小于等于”:

mnm<nm=nm<nmnm>nnmmnmnmnnm第37頁/共52頁2023/3/22

牛牛文庫文檔分享38總結(jié)1.Peano系統(tǒng)2.后繼,歸納集,自然數(shù),自然數(shù)集3.數(shù)學(xué)歸納法原理4.傳遞集5.自然數(shù)的運算6.自然數(shù)上的序關(guān)系第38頁/共52頁2023/3/22

牛牛文庫文檔分享39作業(yè)講解(#1)p25,習(xí)題一,3,7,10,163.TF,FT,TT,FT,TFF7.10.TT,FT,TF16.{{3},{4},3,4},,{,{}}ABCABCABCABC第39頁/共52頁2023/3/22

牛牛文庫文檔分享40作業(yè)講解(#2)p27,習(xí)題一,11,13,14,2011.A-B=AAB=證一:利用A=(A-B)(AB),(A-B)(AB)=證二:A~Bx(xAxB)x(xAxB)AB=AB第40頁/共52頁2023/3/22

牛牛文庫文檔分享41作業(yè)講解(#2)13.(1)證一:直接證.證二:利用XY=YXY(2)AC=(利用文氏圖)14.利用X=(X-Y)(XY)20.類似14題.第41頁/共52頁2023/3/22

牛牛文庫文檔分享42習(xí)題講解(#3)

p80,習(xí)題二,6,7,11,126.(1)(2)7.(1)(2)-----------OK第42頁/共52頁2023/3/22

牛牛文庫文檔分享43習(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}第43頁/共52頁2023/3/22

牛牛文庫文檔分享44習(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>}第44頁/共52頁2023/3/22

牛牛文庫文檔分享45習(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>}.#第45頁/共52頁2023/3/22

牛牛文庫文檔分享46習(xí)題講解(#3)p80,習(xí)題二,12.(1)R-1={<{,{}},>,<,{}>,<,>}(2)R○R={<{},{,{}}>,<{},>,