19/09/08 11:00:20.98 KY2miv9A.net
>>850
つづき
URLﾘﾝｸ(ja.wikipedia.org)
数学的帰納法
(抜粋)
数学的帰納法は自然数に関する命題 P(n) が全ての自然数 n に対して成り立っている事を証明するための、次のような証明手法である[注 1]。
1.P(1) が成り立つ事を示す。
2.任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つ事を示す。
3.以上の議論から任意の自然数 n について P(n) が成り立つ事を結論づける。
上で1と2から3を結論づける所が数学的帰納法に当たる。自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。
高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。
以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
数学的帰納法の形式的な取り扱い
有限回のステップでは有限個の n に対してしか P(n) を結論づける事ができず、「無限個ある自然数全てに対して P(n) が成り立つ」という数学的帰納法の結論について有限の長さの証明が与えられたとはいえない。これが前述した直観的説明におけるギャップである。
ペアノ算術などの形式的な体系では、数学的帰納法を証明に用いてよいことが公理として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。
(引用終り)
以上