📂集合論

数学的帰納法

定理 ¹

$$ \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, \cdots )$ について、$p(1)$ が真であり、$p(n)$ を仮定した時、$p(n+1)$ が成り立てば、$p(n)$ も真である。

説明

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

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

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

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

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

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

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