自然數(shù)與自然數(shù)集課件

1/386.4自然數(shù)與自然數(shù)集6.4.1后繼6.4.2自然數(shù)、自然數(shù)集6.4.3皮亞諾公理假設6.4.4自然數(shù)集的性質(zhì)6.4.5集合的遞歸定義與遞歸子程序2/38后繼：A+=A∪{A}

定義6.9A是一個給定的集合，存在一個集合叫做A的后繼，記為A+。例設A={a},則

A+={a}∪{{a}}={a,{a}}例設A={1,2},則A+={1,2}∪{{1,2}}={1,2,{1,2}}3/38自然數(shù)(馮·諾伊曼JohnvonNeumann,1903年12月28日生于匈牙利,1957年2月8日卒于美國)

0=?1={?}2={?，{?}}3={?，{?}，{?，{?}}}4={?，{?}，{?，{?}}，{?，{?}，{?，{?}}}}┅┅┅┅1={0}2={0，1}=1+3={0，1，2}=2+4={0，1，2，3}=3+┅┅┅┅4/38自然數(shù)的定義定義6.10對于一個集合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+┅┅┅┅5/38后繼、前驅(qū)對于任意兩個自然數(shù)m和n，如果m=n+，即m=n∪{n}，稱m為n的后繼，可以記為

m=n+1，也稱n為m的前驅(qū)，也可以記為n=m-1。6/38自然數(shù)集N定義6.11存在一個由所有自然數(shù)組成的集合叫自然數(shù)集，記為N7/38皮亞諾公理(Peano’sAxioms)設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ì)

(i)0?S,

(ii)如果n?S，那么n+?S

，則有S=N。8/38數(shù)學歸納法——皮亞諾公理的第5條設n是一個自然數(shù)，P(n)表示一個與n有關的公式或命題，令S={n?N│P(n)為真}。若證明了P(0)為真，也即0?S(歸納基礎)；若P(n)為真，則P(n+)也為真，即若n?S，則n+?S(歸納步驟)。則由皮亞諾公理第5條,得S=N。9/38例6.6(p106)求證：對于任意的自然數(shù)m,只有兩種情況：m=0,或者0?m。證明：對m用歸納法。當m=0時，結論自然成立。歸納假設對于自然數(shù)m，結論成立?？疾旖Y論是否對于m+成立。由歸納假設，m=0,或者0?m之一成立。容易說明0?m+成立，即結論對于m+成立，證畢。當m=0時，m+=0∪{0},故0?m+成立。當0?m時，0?m+=m∪{m}成立。10/38例6.7(p107,傳遞性)設n是一個自然數(shù)，求證：若n1和n2為兩個集合，且n1?n2，n2?n，則n1?n。設

S={n?N│若有n1,n2,且n1?n2，n2?n，則n1?n}，要證S=N。證明思路：0?S

?若n?S，n+=n+1?S?

?11/38例6.7的證明：顯然，0?S。

歸納假設n?S，下面要證n+=n+1?S。設有兩個集合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。所以由數(shù)學歸納法，S=N得證。歸納假設12/381908年Zermelo(蔡梅羅)定義的自然數(shù)

0=? 1={?} 2={{?}} 3={{{?}}} 4={{{{?}}}}

┅┅顯然，0?1?2?3?4?┅┅但“?”不滿足傳遞性，未能準確刻畫出自然數(shù)本身所固有的良好性質(zhì)。13/38第二歸納法若n=0時命題成立，假定當n小于等于k時命題成立，可以證明n等于k+1時命題也成立。則對于一切自然數(shù)命題成立。這種歸納方法又叫第二歸納法。14/38例6.8設有數(shù)目相等的兩堆棋子，兩人輪流從任一堆里取出任意顆棋子，但不能不取，也不能同時在兩堆里取。規(guī)定誰最后取完，誰勝利。求證可以保證讓后取者必勝。15/38例6.8的證明：對每堆棋子數(shù)目n作歸納。當n=1時，兩堆中各有一粒。先取者必須取走一粒，且僅能取一粒，后者取剩下一粒。后取者勝。歸納假設若n≤k時，命題成立?？疾靚=k+1時的情況。先取者只能在一堆中取，若全部取完一堆，那么后取者取完另一堆，后取者勝。若先取者取r粒(0<r<k+1)，則后取者在另一堆也取r粒。此時該先取者取，而兩堆數(shù)目仍舊相等，但數(shù)目個數(shù)為k+1-r≤k，由歸納假定先取者無論怎樣取，后取者一定可以勝。16/38自然數(shù)集的性質(zhì)①設n1,n2和n3是三個任意的自然數(shù)，若n1?n2,n2?n3，則n1?n3

。②設n1和n2是兩個任意的自然數(shù)，則下述三個式中有一個成立：n1?n2,n1=n2,n2?n1③設S是自然數(shù)集的任意非空子集，則存在n0?S，使得n0∩S=?。例6.9(p108)求證：對于任意自然數(shù)m和n，若n?m,

則n+?m或者n+=m之一成立.證明：對m用歸納法。

若m=n+，則n?m成立,有n+=m。即結論成立。

歸納假設對任意的m>n+，結論成立:若n?m，則n+=m，或者n+?m之一成立。

考察m+=m∪{m}時結論是否成立:若n?m+={m}∪m，n?{m}∪mn?mn=mn+=m+n+?mn+?m+n+=m則顯然,當n=m時,有n+=m+;當n?m時,有n+?

m+;

所以歸納得證結論成立。18/38例6.10(p118)證明：對于任意自然數(shù)m和n，都有

m?n或者m=n或者n?m之一成立。證明：對n用歸納法。當n=0時，n=?.顯然,對于任意的自然數(shù)m,只有兩種情況：m=?,或者??m(對于非0自然數(shù))即有m=n,或者n?m之一成立.可以對m運用數(shù)學歸納法證明(詳見例6.6)例6.10(p108)證明：對于任意自然數(shù)m和n，都有

m?n或者m=n或者n?m之一成立。對n作歸納假設，假設對任意自然數(shù)m,有n?m,或者n=m，或者m?n三者之一成立?，F(xiàn)在考察對于n+=n+1的情況。n?mn=mm?nn+?mn+=mm?n+例6.9例6.10(p108)證明：對于任意自然數(shù)m和n，都有

m?n或者m=n或者n?m之一成立?，F(xiàn)在考察對于n+=n+1的情況。n+=n∪{n}，對于任意自然數(shù)m，若n?m,則由對m用歸納法可以證明n+?m或者n+=m之一成立(見例4)。若n=m，則m?{m}={n}，即m?n∪{n}=n+。若m?n，則m?n∪{n}=n+。即對n+

滿足:對于任意自然數(shù)m,有m?n+,或者m=n+，或者n+?m三者之一成立。21/38集合的歸納定義（遞歸定義）基礎條款——指出某些事物屬于集合，給集合以基本元素，使所定義的集合非空。歸納條款——指出由集合的已有元素構造新元素的方法。最小性條款——斷言一個事物除非能有限次應用基礎條款和歸納條款構成外，那么這個事物不是集合的成員。注：最小性條款形式可能不同，結果可能是等價的，全部服務于一個目的，既指明所定義的集合是滿足基礎條款與歸納條款的最小集合。22/38例6.11(p108)用歸納定義集合S={n?N│5整除n}

設S是一個集合，它滿足以下三條：①0?S；②如果x?S，那么x+5?S；③S中的元素均是有限次地運用①和②得到的。注：第③條也可改為：A是一個任意集合，若A滿足①②,則S?A。S是滿足①②的最小集合。23/38例6.11

求證：A=S,這里A={5n|n?N}.證明：先證A?S

?？梢杂脷w納法證明5n屬于S。當n=1時，5*1=3屬于S（依據(jù)基礎條款①

）。歸納假設n=k時，5k屬于S。則當n=k+1時，

5*(k+1)=5k+5也屬于S（依據(jù)歸納條款②

）

。歸納法證得A?S

。再證明S?A。 顯然，0是5的倍數(shù)，故0屬于A,即A滿足基礎條款①。

假定x屬于A，即它是5的倍數(shù)，則x+5也是5的倍數(shù)，故x+5也屬于A，即A滿足歸納條款②。

由S的最小性，知S?A得證。

24/38例設∑是一個字母表?！?是包含空字Λ的所有∑中字母組成的字符串為元素的集合。給出∑*的歸納定義。∑*是一個滿足以下三個條件的集合：①Λ

?∑*

；②若x?∑*，且a?∑，則ax?∑*

；③∑*中元素均是有限次地運用條款①②所得。25/38例6.12(p109)已知∑={a,

b,

c}是一個字母表。寫出∑上每個a均有b緊跟其后的所有符號串的集合的遞歸定義?？沾情L度為0的唯一字符串，記為ε或λ，它在“串接”運算中起單位元的作用。26/38歸納定義的例子命題演算的合式公式（p5）謂詞演算的合式公式（p38）27/386.5包含與排斥原理6.5.1有限集6.5.2加法公式6.5.3一般加法公式6.5.4減法公式28/38有限集定義一個集合A，如果它所包含的元素個數(shù)是有限個，比如n個，我們說A是有限集，且記為

│A│=n本節(jié)所涉及的集合一般均為有限集。29/38加法公式設A1，A2是兩個有限集，則：

│A1∪A2│=│A1│+│A2│–│A1∩A2│例某班第一次英語測驗有12個同學得優(yōu)，第二次測驗有18個同學得優(yōu)，有5個同學兩次測驗都得優(yōu)。至少有一次測驗得優(yōu)的同學數(shù)目為多少? │A1∪A2│=│A1│+│A2│–│A1∩A2│=12+18-5=25

30/38加法公式設A1,A2,A3是3個有限集。則31/38一般加法公式定理設A1,A2,…,Ar是r個有限集。則可以用對集合的個數(shù)用歸納法來證明。顯然，當r=2時，結論成立。歸納假定r時結論成立,于是│A1∪┅∪Ar∪Ar+1│=│A1∪┅∪Ar

│+│Ar+1│–│(A1∪┅∪Ar)∩Ar+1│對第一項與第三項分別運用歸納假設即可以得到定理的證明。32/38倆倆交集為空情況下的一般加法公式推論設A1,A2,…,Ar是r個有限集，并且則例設A為一個有限集，|A|=r,則

|ρ(A)|=2r提示：ρ(A)=A0∪A1∪A2∪……∪Ar這里，Ai為具有i個元素的子集所組成的集合。33/38減法公式|A-B|=|A|-|A∩B|34/38例6.15(p111)求出在1和300之間，試求：

（1）不能被2、3、5、7中任意一個整除的整數(shù)的個數(shù)。分析：A2表示1和300之間能被2整除的整數(shù)集合A3表示1和300之間能被3整除的整數(shù)集合A5表示1和300之間能被5整除的整數(shù)集合A7表示1和300之間能被7整除的整數(shù)集合│A2∪A3∪A5∪A7│=?解：設Ai表示1和300之間能被i整除的整數(shù)的集合。故有：│A2│=150

│A3│=100

│A5│=60

│A7│=42│A2∩A3∩A5│=│A30│=10

│A2∩A3∩A7│=│A42│=7│A2∩A5∩A7│=│A70│=4