資源描述：
《離散數(shù)學(xué)第六章 集合-自然數(shù)與自然數(shù)集》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第六章集合6.1集合的基本概念6.2集合的基本運(yùn)算6.3全集和集合的補(bǔ)6.4自然數(shù)與自然數(shù)集6.5包含與排斥原理后繼：A+=A∪{A}定義1A是一個給定的集合，存在一個集合叫做A的后繼，記為A+。例設(shè)A={a},則A+={a}∪{{a}}={a,{a}}例設(shè)B={a,b},則B+={a,b}∪{{a,b}}={a,b,{a,b}}自然數(shù)(馮·諾伊曼JohnvonNeumann,1903年12月28日生于匈牙利,1957年2月8日卒于美國)0=?1={?}2={?，{?}}3={?，{?}，{?，{?}}}4={?，{?}，{?，
2、{?}}，{?，{?}，{?，{?}}}}┅┅┅┅1={0}2={0，1}=1+3={0，1，2}=2+4={0，1，2，3}=3+┅┅┅┅自然數(shù)的定義定義2對于一個集合S，如果它是空集?（亦即0），或者有一個自然數(shù)n，使得S=n+，則稱S為一個自然數(shù)。0=?1={0}=0+2={0，1}=1+3={0，1，2}=2+4={0，1，2，3}=3+┅┅┅┅后繼、前驅(qū)對于任意兩個自然數(shù)m和n，如果m=n+，即m=n∪{n}，稱m為n的后繼，可以記為m=n+1，也稱n為m的前驅(qū)，也可以記為n=m-1。自然數(shù)集N定義3存在一個由所有自然
3、數(shù)組成的集合叫自然數(shù)集，記為N皮亞諾公設(shè)(Peano’sAxioms)設(shè)N表示自然數(shù)集。則：1．0?N2．如果n?N，那么n+?N，3．0不是任何自然數(shù)集的后繼，即不存在自然數(shù)m?N，使得0=m+。4．n和m均是自然數(shù)，如果n+=m+，那么n=m。5．如S是N的子集，有性質(zhì)(1)0?S,(2)如果n?S，那么n+?S，則有S=N。數(shù)學(xué)歸納法——皮亞諾公設(shè)的第5條設(shè)n是一個自然數(shù)，P(n)表示一個與n有關(guān)的公式或命題，令S={n?N│P(n)為真}。若證明了P(0)為真，也即0?S(歸納基礎(chǔ))；若P(n)為真，則P(n+)也為真，
4、即若n?S，則n+?S(歸納步驟)。則由皮亞諾公設(shè)第5條,得S=N。第二歸納法若n=0時命題成立，假定當(dāng)n小于等于k時命題成立，可以證明n等于k+1時命題也成立。則對于一切自然數(shù)命題成立。這種歸納方法又叫第二歸納法。性質(zhì)①設(shè)n1,n2和n3是三個任意的自然數(shù)，若n1?n2,n2?n3，則n1?n3。②設(shè)n1和n2是兩個任意的自然數(shù)，則下述三個式中有一個成立：n1?n2,n1=n2,n2?n1③設(shè)S是自然數(shù)集的任意非空子集，則存在n0?S，使得n0∩S=?。例1(傳遞性)設(shè)n是一個自然數(shù)，求證：若n1和n2為兩個集合，且n1?n2
5、，n2?n，則n1?n。設(shè)S={n?N│若有n1,n2,且n1?n2，n2?n，則n1?n}，要證S=N。證明思路：0?S?若n?S，n+=n+1?S??例1證（續(xù)）若n?S，要證n+=n+1?S。設(shè)有兩個集合n1和n2，且n1?n2，n2?n+=n∪{n}。因n2?n∪{n}，所以n2?n或者n2?{n}。若n2?n，由于n?S，所以n1?n。若n2?{n}，則n2=n，即n1?n2=n。綜上所述n1?n?n∪{n}=n+,故n+=n+1?S。所以歸納得證S=N。1908年Zermelo(蔡梅羅)定義的自然數(shù)0=?1={?}2
6、={{?}}3={{{?}}}4={{{{?}}}}┅┅顯然，0?1?2?3?4?┅┅但“?”不滿足傳遞性，未能準(zhǔn)確刻畫出自然數(shù)本身所固有的良好性質(zhì)。例求證：對于任意自然數(shù)m和n， 若n?m,則n+?m或者n+=m之一成立.證明：對m用歸納法。若m=n+，則n?m成立,此時有n+=m。歸納假設(shè)對任意的m，若n?m，則n+=m，或者n+?m之一成立。考察m+=m∪{m},若n?m+={m}∪m，n?{m}∪mn?mn=mn+=m+n+?mn+?m+n+=m例求證：對于任意自然數(shù)m和n， 若n?m,則n+?m或者n+=m之一成立.證
7、明：對m用歸納法。若m=n+，則n?m成立,此時有n+=m。歸納假設(shè)對任意的m，若n?m，則n+=m，或者n+?m之一成立?？疾靘+=m∪{m},若n?m+={m}∪m，則n=m，或者n?m。于是有n+=m+,或者n+=m，或者n+?m之一成立。從而分別有n+=m+，或者n+=m?m+,或者n+?m?m+之一成立,即有n+=m+或者n+?m+之一成立。所以歸納得證結(jié)論成立。例2(p69)證明：對于任意自然數(shù)m和n，都有m?n或者m=n或者n?m之一成立。證明：對n用歸納法。當(dāng)n=0時，n=?.顯然,對于任意的自然數(shù)m,只有兩種情
8、況：m=?,或者??m(對于非0自然數(shù))即有m=n,或者n?m之一成立.可以對m運(yùn)用數(shù)學(xué)歸納法證明(詳見教材)例2(p69)證明：對于任意自然數(shù)m和n，都有m?n或者m=n或者n?m之一成立。當(dāng)n=0時，已經(jīng)證明了結(jié)論成立。對n作歸納假設(shè)，假設(shè)對任意自然數(shù)m,有
