logo

数学的帰納法 📂集合論

数学的帰納法

定理 1

[p(1)(p(n)    p(n+1))]    nN:p(n) \left[ p(1) \land \left( p(n) \implies p(n+1) \right) \right] \implies \forall n \in \mathbb{N} : p(n) 命題 p(n)(n=1,2,3,)p(n) (n=1,2,3, \cdots ) について、p(1)p(1) が真であり、p(n)p(n) を仮定した時、p(n+1)p(n+1) が成り立てば、p(n)p(n) も真である。

説明

ある式が自然数に対して成り立つ時、特に強力な証明法として、「ペアノの第5公理」とも呼ばれるか、あるいは、単に’数学的’という言葉を取り除いて、ただの帰納法とも言われる。もともと帰納法は、現象や実体を経験的に集めて何かの結論を出すことだが、数学では、このような解説がなくとも、ただの帰納法と言われても、自然に数学的帰納法と理解される。

数学的帰納法は、理解する前は難しく、理解するととても簡単な証明法である。ペアノの第5公理という別名からもわかるように、「公理」と呼べるほど自明な論理だからである。 数学的帰納法 数学的帰納法は、よくドミノに例えられる:

  • (1) ドミノの最初のブロックが倒れる。 通常、最初のブロックが倒れるのは、自明な事実である。なぜなら、自分で倒せばいいからである。同じように、証明をする時も、普通は命題に11 を代入することで、簡単に示すことができる。
  • (2) 一つ前のブロックが倒れることで、次のブロックを倒す。 nn 番目のブロックが倒れるとするならば、このブロックが倒れることで、(n+1)(n+1) 番目のブロックも倒す。ドミノでは、ブロックを一列に並べて、前のブロックが次のブロックを倒すから、事実であろう。これを示すのが、数学的帰納法の本質であり、最も難しい部分である。
  • **(3) 上記の通りならば、最初のブロックを倒すと、すべてのブロックが倒れる。
    • 最初のブロックを倒したとしよう。
    • (2)により、11 番目のブロックが、22 番目のブロックを倒す。
    • 更に(2)により、22 番目のブロックが倒れることで、33 番目のブロックを倒す。
    • 更に(2)により、nn 番目のブロックが倒れることで、(n+1)(n+1) 番目のブロックを倒す。
    • このように、すべてのブロックが次のブロックを倒すので、ブロックの数がどれだけ多くても、すべて倒れる。

数学的帰納法に戻ると、p(1)p(1) が成り立つ時、p(1+1)p(1+1)、すなわちp(2)p(2) が成り立つ。p(2)p(2) が成り立つ時、p(2+1)p(2+1) が成り立ち、p(n)p(n) が成り立つ時、p(n+1)p(n+1) が成り立つ。

でも、p(n)p(n) が成り立つことを仮定するのは、循環論法じゃないの?

最初に数学的帰納法に出会った時に、なぜp(n)p(n) が成り立つことを仮定してもいいのか、わからなくなることがあり、私も高校時代にこの部分が紛らわしかった。しかし、実際に示すのは、p(n)p(n) が自体が成り立つことではなく、p(n)p(n) が成り立つ時に、p(n+1)p(n+1) も成り立つことを示すことである。だから、数学的帰納法は間接証明法の一つとされる。

  • 率直に言って、全てのnn においてp(n)p(n) が成り立たなくても、どうでもいい。偽の仮定から偽の結論が導かれても、その間の論理に問題がなければいい。
  • もし、それが成り立つなら、p(1)p(1) も成り立つので、すべての自然数に対して成り立つということになる。これが、証明の真の結論である。少なくとも一つ真の命題 p(1)p(1) が存在して、すべての自然数に対するp(n)p(n) を正当化できる。

  1. 李興天 訳、林有豊 (2011). 集合論(Set Theory: An Intuitive Approach): p63, 367. ↩︎