關於《陶哲軒實分析》一書中對強數學歸納法原理的理解和疑問…?

以下是書本原文:

以下是我對該定理的理解,為避免誤解,被我寫成了邏輯表達式的形式:

也即要證明我打?的那個蘊含關係恆真。

但我發現,如果對於任意m&>=m0,P(m)都假的話,以上那個有?的蘊含關係就是假的了,就不恆真了。求解釋~謝謝…


謝邀。

題主的問題是:「如果對於任意m&>=m0,P(m)都假的話,以上那個有?的蘊含關係就是假的了」。

事實上這裡面看上去有個問題:這個歸納法似乎沒有初始條件: P(m_0) 到底對不對?我們首先要知道 P(m_0) 是對的,然後才能往下歸納。然而這個歸納法的條件實際蘊含了 P(m_0) 。為什麼呢?因為,它的假設是:「如果 P(m) 對任何 m_0leq m<m 成立,那麼 P(m) 成立」;取 m=m_0 的時候,不存在這樣的 m ;然而,邏輯學裡面說,假的前件推出任何結論;所以「 m_0leq m<m 推出 P(m) 」這件事情對 m=m_0 仍然成立,所以 P(m_0) 。所以我們有了歸納的初始條件,所以我們可以開始歸納,over。

當然我承認這裡不把初始條件明確寫出來確實對初學者來說容易造成誤解,但是他那個命題邏輯上仍然是對的。


@Yuhang Liu 講了命題中帶括弧內容的理解。這裡直接回答題主的問題:

如果定理中給定的 P 對於所有的 mgeqslant m_0m 為自然數)都不成立(例如, P(x)=x 為無理數),那麼這個定理是否仍為真?

回答是肯定的。

題中的那個「邏輯表達式」少了量詞,是有問題的。(後面貼的那個分享的手寫的「證明」也沒有量詞,是錯的。)這裡重寫。記

R:=forall(min{f N}).(mgeqslant m_0
ightarrow P(m))

Q(m):=forall(min{f N}).(m_0leqslant m<m
ightarrow P(m))

S(m):=Q(m)
ightarrow P(m)

T:=forall(min{f N}).(mgeqslant m_0
ightarrow S(m))

那麼定理可以表示為T
ightarrow R 。嚴格地講,應該寫成

forall P.(forall(m_0in{f N}).(T
ightarrow R))

但是這裡不討論二階邏輯的問題。

假設 P 對所有的 mgeqslant m_0 都是假的。要證明 T
ightarrow R 成立只需要證明 T 為假,即

exists(min{f N}).
eg(mgeqslant m_0
ightarrow S(m))

現在只需要注意到 m_0geqslant m_0 為真,但 S(m_0) 為假(因為 Q(m_0) 真, P(m_0) 假),所以 T 為假。證畢。

--------------------------------------------------------------------------------------------------------

當然,也可以不需要這一堆符號的演算,一句話就可以證明。只需要重讀括弧裡面的內容:定理的假設要求 P(m_0) 為真。若 P(m_0) 為假,定理自然成立。


強歸納法,普通歸納法,well-ordering property這3者都是等價的。

用well-ordering property證明:

(從 P(m_0)land [forall m (P(m_0)land...P(m-1)	o P(m))] 推導出 forall(mge m_0)P(m) 。)

假設存在一些大於等於 m_0 的且不具有性質P的自然數 。那麼所有這些數構成的集合S是非空集。那麼S中存在一個最小元素t。那麼所有大於等於 m_0 並且比t還小的自然數不屬於S(具有性質P)。那麼由給出條件可以推出P(t)成立。這與t屬於S相矛盾。

用普通歸納法證明:

定義一個性質Q(n) := 「對於所有 m_0 le m < n,P(m)成立」。顯然Q(m_0)成立(不可能同時滿足既大於等於又小於 m_0 。前提始終為假)。然後假設Q(n)成立,換句話說就是「對於所有 m_0 le m < n ,P(m)成立」。那麼由給出條件可推出P(n)成立。那麼「對於所有 m_0 le m < n+1 ,P(m)成立」。這相當於在說「Q(n+1)」。於是我們有Q(m_0)和Q(n) 	o Q(n+1),用普通歸納法可得「 forall (nge m_0)Q(n) 」。所以性質P對於所有大於等於 m_0 的自然數都成立。


這是我閱讀了本問題的一位匿名答主的回答後,重新整理的證明過程,供大家參考:

再次感謝那位匿名答主…


這些問題的回答中都缺少了對核心問題本質的揭示,數學歸納法的核心是序關係,特別是整數集的序關係的構造才能更深刻的即使事物的本質。


我對另一個問題的回答,貼過來:

沒有什麼強歸納法和普通歸納法,普通歸納法就能保證每個自然數n都成立。

你所謂的強歸納法,只不過是證明過程中需要不只前一項,比如斐波那契數列(遞歸式包括前兩項),根據需要而做的假設而已。

當然為了放心,做了多的假設,驗證初始項時,不妨多驗證幾項,保證歸納的前提是正確的就可以了。


暈,打完發現盡然是一個月以前的問題,白答了

竟然沒有人正面回應題主的問題?

題主請加上量詞,不然的話只能理解成在最前面加量詞

感受一下

for all m,m0,m` ,

(m≥m0)→(((m0≤m`<m)→p(m`))→p(m))

for all m≥m0 ,

(for all m0≤m`<m,p(m`))→p(m)

有什麼區別


推薦閱讀:

如何理解雅克比矩陣?
函數的凹凸性漫談|高等數學漫步(二)
自學數學分析,教材上的定理初學時不會證明正常嗎?

TAG:數學分析 | 數理邏輯SymbolicLogic |