2013年10月15日 星期二

數學歸納法

數學歸納法 

 在《數學傳播》第七卷第四期裡有一篇文章〈一些不可能無限延長的數學遊戲〉，這篇文章亦收在數學傳播季刊選輯《離散數學(二)》之內，文中介紹了一些看起來好像永遠玩不完的遊戲，這些遊戲裡有一個希臘神話中的九頭怪蛇難題，這個問題初看我們會覺得怪蛇的頭似乎越砍越多，要砍的話永遠砍不完，但卻被「證明」了一次砍一個，不論怎麼砍，遲早能將怪蛇的頭全部砍掉。現在我們就來談談這個結果的證明，使我們能多知道一些這個遊戲裡的數學。 上面的這個結果是 Kirby 和 Paris 所證明的，為要說明他們證明這個結果的動機，我們必須回到自然數的「皮阿諾公設」。義大利數學家皮阿諾 (G. Peano) 於1889年以拉丁文印一本小書，整本書共有36頁，書名為《算數原理，以一個新方法表示》(The principles of arithmetic, presented by a new method)。這本書中將自然數的一些性質抽象化而得到一組公設，盼望由這些公設藉著邏輯的演繹而得到所有自然數的性質，即將自然數「公設化」。皮阿諾把每一個自然數的下一個稱為這數的「後繼者」(successor)，用後繼者的說法，這組皮阿諾公設可以寫成下面的形式（括弧裡是用符號的寫法，其中 n+ 表示自然數 n 的後繼者）:
一、
1 是自然數 ($1 \in N$)
二、
每一個自然數有一個自然數作他的後繼者 ( $n \in N \Rightarrow n^+\in N$)
三、
1不是一個後繼者 ( $\forall n \in N \;\; 1\neq n^+$)
四、
不同數不可能有相同的後繼者 ( $m\neq n\Rightarrow m^+\neq n^+$)
五、
設 S 是 N 的子集，若 1 是 S 的元素，且 S 中的每一個元素的後繼者也是 S 的元素，則 S 就是 N ($S\subseteq N$, $1\in S$ 且 $n\in S\Rightarrow n^+\in S$，則 S=N)
上面的第五個公設，也就是「數學歸納法原理」，為了加強對這原理的認識，我們將此一原理重寫成為下列的形式：
數學歸納法原理：設 $S\subseteq N$，若 S 有下列兩性質：
(一)
$1\in S$
(二)
$n\in S\Rightarrow n^+\in S$
則 S=N 當我們使用數學歸納法來證明一些對所有自然數都成立的敘述時，我們常用下列方式，我們用 P(n) 來表示這個敘述，我們證明
(一)
P(1) 成立
(二)
由 P(n) 成立可以推得 P(n+1) 成立。
我們用這個方法來證明時，有一點我們必須注意，即敘述 P(n) 是有一些限制的，不可以是任意的敘述。徐道寧教授所著《數學歸納法》裡有一個這樣的例子，用 P(n) 表示 n 粒沙子不成沙堆，用「數學歸納法」可得到「沙堆」不存在，這個結果當然是不合理的，原因就是「沙堆」這一個觀念，不是數學上能明確定義的，也就是無法用數學符號來表示「沙堆」這個觀念，所以對敘述 P(n) 我們要求是可以用數學符號表示出來，以避免一些無法正確定義的觀念如沙堆跑進來。

[轉]董世平http://episte.math.ntu.edu.tw/articles/mm/mm_10_4_06/
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)