数学的帰納法
定理 1
命題 について、 が真であり、 を仮定した時、 が成り立てば、 も真である。
説明
ある式が自然数に対して成り立つ時、特に強力な証明法として、「ペアノの第5公理」とも呼ばれるか、あるいは、単に’数学的’という言葉を取り除いて、ただの帰納法とも言われる。もともと帰納法は、現象や実体を経験的に集めて何かの結論を出すことだが、数学では、このような解説がなくとも、ただの帰納法と言われても、自然に数学的帰納法と理解される。
数学的帰納法は、理解する前は難しく、理解するととても簡単な証明法である。ペアノの第5公理という別名からもわかるように、「公理」と呼べるほど自明な論理だからである。 数学的帰納法 数学的帰納法は、よくドミノに例えられる:
- (1) ドミノの最初のブロックが倒れる。 通常、最初のブロックが倒れるのは、自明な事実である。なぜなら、自分で倒せばいいからである。同じように、証明をする時も、普通は命題に を代入することで、簡単に示すことができる。
- (2) 一つ前のブロックが倒れることで、次のブロックを倒す。 番目のブロックが倒れるとするならば、このブロックが倒れることで、 番目のブロックも倒す。ドミノでは、ブロックを一列に並べて、前のブロックが次のブロックを倒すから、事実であろう。これを示すのが、数学的帰納法の本質であり、最も難しい部分である。
- **(3) 上記の通りならば、最初のブロックを倒すと、すべてのブロックが倒れる。
- 最初のブロックを倒したとしよう。
- (2)により、 番目のブロックが、 番目のブロックを倒す。
- 更に(2)により、 番目のブロックが倒れることで、 番目のブロックを倒す。
- 更に(2)により、 番目のブロックが倒れることで、 番目のブロックを倒す。
- このように、すべてのブロックが次のブロックを倒すので、ブロックの数がどれだけ多くても、すべて倒れる。
数学的帰納法に戻ると、 が成り立つ時、、すなわち が成り立つ。 が成り立つ時、 が成り立ち、 が成り立つ時、 が成り立つ。
でも、 が成り立つことを仮定するのは、循環論法じゃないの?
最初に数学的帰納法に出会った時に、なぜ が成り立つことを仮定してもいいのか、わからなくなることがあり、私も高校時代にこの部分が紛らわしかった。しかし、実際に示すのは、 が自体が成り立つことではなく、 が成り立つ時に、 も成り立つことを示すことである。だから、数学的帰納法は間接証明法の一つとされる。
- 率直に言って、全ての において が成り立たなくても、どうでもいい。偽の仮定から偽の結論が導かれても、その間の論理に問題がなければいい。
- もし、それが成り立つなら、 も成り立つので、すべての自然数に対して成り立つということになる。これが、証明の真の結論である。少なくとも一つ真の命題 が存在して、すべての自然数に対する を正当化できる。
李興天 訳、林有豊 (2011). 集合論(Set Theory: An Intuitive Approach): p63, 367. ↩︎