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

《數(shù)學(xué)歸納原理和最小數(shù)原理的等價(jià)性證明》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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元集有最小元素，對于n+1元集，新加入的元素與n元集中的最小數(shù)比較，若新加入的元素不大于該最小數(shù)，則新加入的元素為最小數(shù)，否則，原來的n元集中的最小數(shù)仍是n+1元集的最小數(shù)。由數(shù)學(xué)歸納原理，含任意個(gè)自然數(shù)數(shù)目的自然數(shù)子集都有

2、最小數(shù)。得證。二：用最小數(shù)原理證數(shù)學(xué)歸納原理：p(o)成立，且p(n)成立可導(dǎo)出p(n+1)成立，則對于一切自然數(shù)n,p(n)成立。否則，若對于若干個(gè)（可能有限個(gè)，也可能無限個(gè)）自然數(shù)m1,……mi……(i≥1）使命題不成立，由最小數(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)成立。矛盾。故對于一切自然數(shù)n,p(n)成立。證畢。其實(shí)以上發(fā)現(xiàn)也沒啥大不了的，很

3、直觀淺顯。這兩個(gè)原理的等價(jià)性得證后，兩者中的任意一條都可以作為皮亞杰五條公理中的一條嗎？不行！因?yàn)樽钚?shù)原理中的小于最開始還是沒有定義的！。還有，該等價(jià)關(guān)系非我第一次發(fā)現(xiàn)，由于其十分簡單，在我發(fā)現(xiàn)等價(jià)性后，我在華羅庚的《數(shù)學(xué)歸納法》最后找到了同樣的結(jié)論。歸納原理和數(shù)學(xué)歸納法1．?dāng)?shù)學(xué)歸納法的理論依據(jù)　　歸納法和演繹法都是重要的數(shù)學(xué)方法．歸納法中的完全歸納法和演繹法都是邏輯方法；不完全歸納法是非邏輯方法，只適用于數(shù)學(xué)發(fā)現(xiàn)思維，不適用數(shù)學(xué)嚴(yán)格證明．　　數(shù)學(xué)歸納法既不是歸納法，也不是演繹法，是一種遞歸推理，其理論依據(jù)是下列佩亞諾公理Ⅰ—

4、Ⅴ中的歸納公理：　?、瘢嬖谝粋€(gè)自然數(shù)0∈N；　?、颍總€(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è)元素的后繼元素，則M＝N　　自然數(shù)就是滿足上述佩亞諾公理的集合N中的元素．關(guān)于自然數(shù)的所有性質(zhì)都是這些公理的直接推論．由佩亞諾公理可知，0是自然數(shù)關(guān)于“后繼”的起始元素，如果記0′＝1，1′=2，2′=3，…，n′=n＋1，…，則N=｛0，1，2，…，n，…｝　

5、　由佩亞諾公理所定義的自然數(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=｛n｜n∈N且n≤m，對任意m∈A｝　　由于A非空，至少有一自然數(shù)a∈A，而a＋1(＞a)不在M中．所然，就有　　1°0∈M(0不大

6、于任一自然數(shù))；　　2°若m∈M，則m＋1∈M．根據(jù)歸納公理，應(yīng)有M＝N．此與M≠N相矛盾．　　這個(gè)自然數(shù)m0就是集合A的最小數(shù)．因?yàn)閷θ魏蝍∈A，都有m0意a∈A，于是m0＋1∈M，這又與m0的選取相矛盾．　　反之，利用最小數(shù)原理也可以證明歸納公理．因此，最小數(shù)原理與歸納公理是等價(jià)的．　　定理2(數(shù)學(xué)歸納法原理)一個(gè)與自然數(shù)相關(guān)的命題T(n)，如果　　　1°T(n0)(n0≥0)為真；　　　2°假設(shè)T(n)(n≥n0)為真，則可以推出T(n＋1)也為真．　　那么，對所有大于等于n0的自然數(shù)n，命題T(n)為真．　　證用反證法．

7、若命題T(n)不是對所有自然數(shù)n為真，則M=｛m｜m∈N，m≥n0且T(m)不真｝非空．根據(jù)定理1，M中有最小數(shù)m0．由1°，m0＞n0，從而m0－1≥n0且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°對某一自然數(shù)n0≥0，T(n0)為真；　　　2°假設(shè)對n0≤k≤n的k，T(k)為

8、真，則可以推出T(n＋1)也真．那么．對所有大于等于n0的自然數(shù)，命題T(n)都真．　　定理3Ⅰ型數(shù)學(xué)歸納法和Ⅱ型數(shù)學(xué)歸納法等價(jià)．　　證假設(shè)命題T(n)對n=n0為真，于是只須證明“由T(n)(n≥n0)為真，可以推出T(n＋1)也為真”的充要條件為“由T(k)