數(shù)學(xué)歸納原理和最小數(shù)原理的等價(jià)性證明

1、.數(shù)學(xué)歸納原理和最小數(shù)原理的等價(jià)性證明這兩個(gè)原理都是自然數(shù)公理系統(tǒng)中最基本的原理，人們常常用最小數(shù)原理證明數(shù)學(xué)歸納原理。我發(fā)現(xiàn)用數(shù)學(xué)歸納原理也可以證最小數(shù)原理。所謂的最小數(shù)原理是指：自然數(shù)集合的任意非空子集必有最小元素。一：用數(shù)學(xué)歸納原理證最小數(shù)原理。 當(dāng)自然數(shù)的非空子集只含一個(gè)元素時(shí)，這個(gè)元素就是最小元素。設(shè)n元集有最小元素，對(duì)于n+1元集，新加入的元素與n元集中的最小數(shù)比較，若新加入的元素不大于該最小數(shù)，則新加入的元素為最小數(shù)，否則，原來的n元集中的最小數(shù)仍是n+1元集的最小數(shù)。由數(shù)學(xué)歸納原理，含任意個(gè)自然數(shù)數(shù)目的自然數(shù)子集都有最小數(shù)。得證。二：用最小數(shù)原理證數(shù)學(xué)歸納原理：p(o)成立，且

2、p(n)成立可導(dǎo)出p(n+1)成立，則對(duì)于一切自然數(shù)n,p(n)成立。否則，若對(duì)于若干個(gè)（可能有限個(gè)，也可能無限個(gè)）自然數(shù)m1,mi(i1）使命題不成立，由最小數(shù)原理，這若干個(gè)自然數(shù)有最小數(shù)記為w，而且，w一定是正數(shù)，那么，就一定存在唯一的自然數(shù)b,b+1=w.b不屬于這個(gè)使命題不成立的元素組成的集合，因?yàn)閎比最小數(shù)還小。則p(b)是成立的，由規(guī)則，p(b+1)也成立即p(w)成立。矛盾。故對(duì)于一切自然數(shù)n,p(n)成立。證畢。其實(shí)以上發(fā)現(xiàn)也沒啥大不了的，很直觀淺顯。這兩個(gè)原理的等價(jià)性得證后，兩者中的任意一條都可以作為皮亞杰五條公理中的一條嗎？不行！因?yàn)樽钚?shù)原理中的小于最開始還是沒有定義的！

3、。還有，該等價(jià)關(guān)系非我第一次發(fā)現(xiàn)，由于其十分簡(jiǎn)單，在我發(fā)現(xiàn)等價(jià)性后，我在華羅庚的數(shù)學(xué)歸納法最后找到了同樣的結(jié)論。歸納原理和數(shù)學(xué)歸納法1數(shù)學(xué)歸納法的理論依據(jù)歸納法和演繹法都是重要的數(shù)學(xué)方法歸納法中的完全歸納法和演繹法都是邏輯方法；不完全歸納法是非邏輯方法，只適用于數(shù)學(xué)發(fā)現(xiàn)思維，不適用數(shù)學(xué)嚴(yán)格證明數(shù)學(xué)歸納法既不是歸納法，也不是演繹法，是一種遞歸推理，其理論依據(jù)是下列佩亞諾公理中的歸納公理：存在一個(gè)自然數(shù)0N；每個(gè)自然數(shù)a有一個(gè)后繼元素a，如果a是a的后繼元素，則a叫做a的生成元素；自然數(shù)0無生成元素；如果a=b，則a=b；(歸納公理)自然數(shù)集N的每個(gè)子集合M，如果M含有0，并且含有M內(nèi)每個(gè)元素的后

4、繼元素，則MN自然數(shù)就是滿足上述佩亞諾公理的集合N中的元素關(guān)于自然數(shù)的所有性質(zhì)都是這些公理的直接推論由佩亞諾公理可知，0是自然數(shù)關(guān)于“后繼”的起始元素，如果記01，1=2，2=3，n=n1，則N=0，1，2，n，由佩亞諾公理所定義的自然數(shù)與前面由集合所定義的自然數(shù)，在本質(zhì)上是一致的90年代以前的中學(xué)數(shù)學(xué)教材中，將自然數(shù)的起始元素視作1，則自然數(shù)集即為正整數(shù)集現(xiàn)在已統(tǒng)一采取上面的記法，將0作為第一個(gè)自然數(shù)定理1(最小數(shù)原理)自然數(shù)集N的任一非空子集A都有最小數(shù)這本是自然數(shù)集N關(guān)于序關(guān)系()為良序集的定義現(xiàn)在用歸納公理來證明證 設(shè)M是不大于A中任何數(shù)的所有自然數(shù)的集合，即M=nnN且nm，對(duì)任意m

5、A由于A非空，至少有一自然數(shù)aA，而 a1(a)不在M中所然，就有 1 0M(0不大于任一自然數(shù))；2 若mM，則m1M根據(jù)歸納公理，應(yīng)有MN此與MN相矛盾這個(gè)自然數(shù)m0就是集合A的最小數(shù)因?yàn)閷?duì)任何aA，都有m0意aA，于是m01M，這又與m0的選取相矛盾反之，利用最小數(shù)原理也可以證明歸納公理因此，最小數(shù)原理與歸納公理是等價(jià)的定理2(數(shù)學(xué)歸納法原理)一個(gè)與自然數(shù)相關(guān)的命題T(n)，如果1 T(n0)(n00)為真；2 假設(shè)T(n)(nn0)為真，則可以推出T(n1)也為真 那么，對(duì)所有大于等于n0的自然數(shù)n，命題T(n)為真 證 用反證法若命題T(n)不是對(duì)所有自然數(shù)n為真，則M=mmN，mn

6、0且T(m)不真非空根據(jù)定理1，M中有最小數(shù)m0由1， m0n0，從而m01n0且T(m0-1)為真由2，取n=m0-1即知T(m0)為真此與T(m0)不真相矛盾從而證明了定理2在具體運(yùn)用數(shù)學(xué)歸納法進(jìn)行數(shù)學(xué)證明時(shí)，有多種不同形式運(yùn)用定理2中兩個(gè)步驟進(jìn)行證明的，為型數(shù)學(xué)歸納法經(jīng)常使用的還有型數(shù)學(xué)歸納法，型數(shù)學(xué)歸納法是：如果命題T(n)滿足1 對(duì)某一自然數(shù)n00，T(n0)為真；2 假設(shè)對(duì)n0kn的k， T(k)為真，則可以推出 T(n1)也真那么對(duì)所有大于等于n0的自然數(shù)，命題T(n)都真定理3 型數(shù)學(xué)歸納法和型數(shù)學(xué)歸納法等價(jià)證 假設(shè)命題 T(n)對(duì)n=n0為真，于是只須證明“由T(n)(nn0

7、)為真，可以推出T(n1)也為真”的充要條件為“由T(k)(n0kn)為真，可以推出T(n+1)也為真”1 充分性若“由T(n)(nn0)為真，可以推出 T(n1)也為真”，則對(duì)n0kn，T(k)為真，特別 T(n)為真，因此 T(n1)也為真2 必要性用反證法若“由 T(k)(n0kn)為真，可以推出 T(n1)也為真”，但并非對(duì)所有大于等于n0的自然數(shù)n，由T(n)為真，可以推出 T(n1)也為真，則 M=mmN， mn0且由T(n)為真推不出T(n1)也為真非空由定理1，M中有最小數(shù)m0，且對(duì)n0km0的k，由T(k)為真，可以推出T(k1)也為真特別由 T(n0)為真可知 T(n0+1

8、)為真，由T(n01)為真可知 T(n02)為真，由T(m01)為真可知 T(m0)為真現(xiàn)已知T(n0)為真，所以T(n0)， T(n0+1)， T(m0)都為真，由此可知 T(m01)也為真，所以由 T(m0)為真推出了T(m01)也為真這與m0的選取矛盾由定理3可知，型數(shù)學(xué)歸納法也是合理的推理方法2數(shù)學(xué)歸納法在應(yīng)用中要注意的問題第一，證明的兩個(gè)步驟缺一不可第一步是歸納的基礎(chǔ)，第二步是歸納的傳遞尤其是不可忽視第一步的驗(yàn)證例1試證135(2n1)(n1)21證 假設(shè)當(dāng)n=k時(shí)公式成立，則135(2n-1)(2n+1)135(2n-1)(2n1)n212n1(n1)21完成了數(shù)學(xué)歸納法的第二步，

9、但結(jié)論顯然是錯(cuò)誤的為什么？因?yàn)槿鄙俚谝徊绞聦?shí)上，當(dāng)n=0時(shí)，公式不成立如果缺了第二步，則不論對(duì)多少個(gè)自然數(shù)來驗(yàn)證命題T(n)的正確性，都不能肯定命題對(duì)所有自然數(shù)都正確例如，哥德巴赫猜想“任何不小于6的偶數(shù)都可以表成兩個(gè)奇素?cái)?shù)之和”，雖然對(duì)大量偶數(shù)進(jìn)行了具體驗(yàn)證，但因缺少第二步歸納傳遞，所以仍只停留在歸納的第一步上它至今仍只是個(gè)猜想而已第二，第二步在證明T(n1)為真時(shí)，一定要用到歸納假設(shè)，即要把“T(n)為真推出 T(n1)為真”或“T(n0)， T(n01)，T(k-1)為真推出T(k)為真”的實(shí)質(zhì)蘊(yùn)含真正體現(xiàn)出來否則不是數(shù)學(xué)歸納法證明例2 設(shè)a1，an為n個(gè)正數(shù)，b1，bn是它的一個(gè)排列試

10、證證1當(dāng)n=1時(shí)，命題顯然成立2假設(shè)(*)式對(duì)n=k成立，則當(dāng)n=k1時(shí)根據(jù)數(shù)學(xué)歸納法原理，(*)式對(duì)所有大于等于1的自然數(shù)n都成立這里雖然形式上完成了數(shù)學(xué)歸納法的兩個(gè)步驟，但第二步在證(*)式對(duì)n1成立的過程中，并沒用到(*)對(duì)n成立的歸納假設(shè)因此，不能說上述證法是采用了數(shù)學(xué)歸納法事實(shí)上，在上述證明中無須用數(shù)學(xué)歸納法，用平均值不等式證明就行了第三，并不是凡與自然數(shù)相關(guān)的命題T(n)，都要用數(shù)學(xué)歸納法來證明；而且也不是所有這類命題都能用數(shù)學(xué)歸納法給以證明的這一命題是與自然數(shù)相關(guān)的命題，盡管可以對(duì)n0，1，2，進(jìn)行驗(yàn)證，但無法實(shí)現(xiàn)數(shù)學(xué)歸納法的第二步，因此不能用數(shù)學(xué)歸納法進(jìn)行證明事實(shí)上，數(shù)學(xué)歸納法

11、只適用于具有遞歸性的命題T(n)3遞歸函數(shù)一個(gè)定義在自然數(shù)集N上的函數(shù)f(n)，如果它對(duì)于每個(gè)自然數(shù)n的值可以用如下方式確定：(1)f(0)=a(a為已知數(shù))；(2)存在遞推關(guān)系組S，當(dāng)已知/f(0)，f(1)，f(n-1)值以后，由S唯一地確定出f(n)的值：f(n)=Sf(0)，f(1)，f(n-1)那么，就把這個(gè)函數(shù)f(n)，稱作歸納定義的函數(shù)簡(jiǎn)稱遞歸函數(shù)在具體的遞歸函數(shù)例子中，關(guān)系組S可能有幾個(gè)表達(dá)式，或者沒有明確的解析表達(dá)式，也可能需要給出f(n)的開頭若干個(gè)值這樣定義函數(shù)是合理的，因?yàn)槲覀冇校憾ɡ? 當(dāng)遞推關(guān)系組S給定后，定義在N上的滿足上述條件(1)、(2)的函數(shù)f(n)是存在而

12、且唯一的證 首先指出：對(duì)任一自然數(shù)k，總可以在片斷0，k上定義一個(gè)函數(shù)fk(n)，使fk(0)=a，對(duì)于片斷上其他自然數(shù) n，f(n)=Sf(0)，f(n-1)這個(gè)函數(shù)fk(n)是在0，k上唯一確定的現(xiàn)對(duì)k進(jìn)行歸納證明：1 當(dāng)k0時(shí)，f0(0)a是唯一確定的；2假定在0，k上已經(jīng)由(1)、(2)定義了一個(gè)唯一確定的函數(shù)fk(n)，令則fk+1(n)在片斷0，k1上有定義，且(1)fk+1 (0)=fk(0)=a；(2)fk+1(n)=Sfk(0)，fk(n1) =Sfk+1(0)，fk+1(n1)， n=1，2，k因此，函數(shù)人fk+1(n)滿足條件(1)、(2)由數(shù)學(xué)歸納法知，對(duì)任何自然數(shù)k，

13、函數(shù)fk(n)在片斷0，k上唯一確定，且滿足(1)、(2)又若k1k2，則 fk1(n)與fk2(n)在片斷0，k1上完全一致現(xiàn)作一新的函數(shù)：f(n)=fn(n)， nN首先，函數(shù)f(n)對(duì)任一nN都有定義，且f(n)=fn(n)=Sfn1(0)，fn-1(n1)=Sf0(0)，fn-1(n-1)=Sf(0)，f(n-1)又顯然f(0)f0(0)=a故函數(shù)f(n)是定義在N上且滿足(1)、(2)的唯一確定的函數(shù)例4 設(shè)函數(shù)fNN，且(1) f(0)=2，f(1)=3；(2) f(n1)3f(n)2f(n1)，n1證明： f( n)2n1這里給出的遞歸函數(shù)由f(0)、f(1)兩個(gè)值和一個(gè)關(guān)系式給

14、定的關(guān)系組S確定但有的遞歸函數(shù)f(0)的值隱含于關(guān)系組S之中而未直接給出例5(IMO19試題)設(shè)f：N+N，且(S) f(n1) f(f(n)， nN+求證：對(duì)于任意nN，f(n)n證 先用數(shù)學(xué)歸納法證明命題An：任意正整數(shù)n，若mn，則f(m) n顯然 A1真假設(shè)An-1真，則對(duì)任意mn，f(m1)n-1，故f(m)f(f(m1)2n1，于是f(m)n，從而 An真由此可知，f(n)n，f(n1)f(f(n)f(n)于是f單調(diào)增加又如果有一個(gè)n使f(n)n，則f(n)n+1，f(f(n)f(n+1)，與已知條件(S)矛盾故只能有 f(n)=n本題給出的遞歸函數(shù)，f(1)的值沒有明顯給出，但實(shí)

15、際上隱含于關(guān)系組(S)中4遞歸命題一個(gè)與自然數(shù)相關(guān)的命題T(n)，一般來說，它未必是一個(gè)函數(shù)問題現(xiàn)在采取如下方式來構(gòu)造命題T(n)的真值函數(shù)fN1，0 如果命題T(n)的真值函數(shù)f(n)是遞歸函數(shù)，即1 f(0)=1；2 f(n1)= Sf(0)，f(n)，且當(dāng)f(0)=f(n)=1時(shí)， f( n1)=1那么就稱T(n)是具有遞歸性質(zhì)的命題，或簡(jiǎn)稱遞歸命題實(shí)際上，所謂遞歸命題，就是一個(gè)與自然數(shù)相關(guān)的命題T(n)，開頭(如n=0時(shí))為真，且真值可傳遞并不是所有與自然數(shù)相關(guān)的命題都是遞歸命題例如本節(jié)例3中的命題是與自然數(shù)相關(guān)的命題，而且對(duì)任何nN，它都為真，但卻不具有遞歸性，它的真值是不可傳遞的一

16、般而言，大多數(shù)數(shù)論問題，如哥德巴赫猜想、費(fèi)馬問題、孿生素?cái)?shù)問題等，都不是遞歸命題只有遞歸命題才能用數(shù)學(xué)歸納法來證明因此判別一個(gè)與自然數(shù)相關(guān)的命題T(n)是不是遞歸命題，是運(yùn)用數(shù)學(xué)歸納法的前提判別的關(guān)鍵在于，探究和發(fā)現(xiàn)T(n)的真值對(duì)于T(0)，T(n-1)真值的依賴性而這種探究本身對(duì)于數(shù)學(xué)歸納法第二步證明，也有直接幫助例6(1963年北京市競(jìng)賽題)2n(nN)個(gè)球分成若干堆，從中任選兩堆：甲堆p個(gè)球，乙堆q個(gè)球；若pq，則從甲堆取出q個(gè)加于乙堆；這作為一次挪動(dòng)(變換)證明：總可以經(jīng)過有限次挪動(dòng)，使所有球都?xì)w為一堆這是一個(gè)與自然數(shù)相關(guān)的命題，記為T(n)當(dāng)n=1時(shí)，只有兩個(gè)球，或已是一堆；或兩堆，每堆一個(gè)球若后者，只須挪動(dòng)一次，就變?yōu)橐欢阉訲(1)為真T(n)真值是否有傳遞性呢