数学的帰納法
フランス人、ブレーズ・パスカル。「パスカルの三角形」の性質を証明する際、数学的帰納法を現代と同じ考え方で初めて用いた人物。このことは、彼の死後発行された「Traité du triangle arithmétique (算術三角形論, 1655) 」の12番目の系の証明から確認できるようだ。 Blaise Pascal (1623 - 1662)
この記事では、数学的帰納法と、それにまつわる
・数学的帰納法の仮定だけでは数学的帰納法自体が成り立つとは言えないこと
・実は数学的帰納法は数学の公理の1つであること
の3つのテーマについて書いています。
数学的帰納法
数学的帰納法とは？
（1）$ P(1)$ が成り立つ。
（2）任意の自然数 $ k$ に対し、「$ P(k)$ ならば $ P(k+1)$」が成り立つ。
上の2つが同時に成り立つならば、任意の自然数 $ n$ に対して $ P(n)$ が成り立ちます。
（1）と（2）が同時に満たされるならば、
「$ P(1)$ は正しい」→「$ P(2)$ は正しい」→「$ P(3)$ は正しい」→・・・
という永遠に続く *2 正しさの連鎖が成り立つので、いかなる自然数 $ n$ に対しても「$ P(n)$ は正しい」ということが言えます。これが数学的帰納法です。
数学的帰納法は帰納ではなく演繹
帰納とは、個別のものに対して成り立つことを、一般の状況でも成り立つのではないか？と考える推論方法のことです。
演繹とは、一般的に成り立つ法則を、個別に適用する推論方法のことです。
「ある自然数 $ n$ に対して、命題 $ P(n)$ が成り立つか考えたい。数学的帰納法の条件（1）、（2）は成り立っている。」という状況を考えましょう。この状況で数学的帰納法を適用することは、
個別での正しさ：「$ P(1)$ は正しい」、「$ P(2)$ も正しい」、・・・
一般への適用：ゆえに、$ P(n)$ も正しい。
という推論をしているように見えるので、一見帰納です。しかし、正しくは
一般的法則：（1）、（2）が成り立つならば全ての自然数に対して $ P$ が成り立つ（数学的帰納法）。
個別への適用：ゆえに、今興味のある $ n$ に対しても $ P(n)$ が成り立つ。
という論理展開になっているので、実は数学的帰納法を用いた推論は演繹なのです。
先ほど述べたように、数学的帰納法を用いた推論は帰納と似ているため、数学的”帰納”法という名称が付けられたものと思われます。
数学的帰納法は成り立たない？
仮定と結論の間の壁
数学的帰納法の仮定（1）と（2）から、数学的帰納法が成り立つことは示せるでしょうか？仮定が成り立つならば、例えば
「$ P(1)$ は正しい」→「$ P(2)$ は正しい」→「$ P(3)$ は正しい」
という並びを作ることができます。なので、「$ P(1),P(2),P(3)$ は全て正しい」という結論が得られます。これをもっと繰り返せば、
「$ P(1)$ は正しい」→「$ P(2)$ は正しい」→・・・→「$ P(100)$ は正しい」
という並びをつくることができるので、「$ P(1),P(2),\dots,P(100)$ は全て正しい」という結論も得られます。しかしこのようなことをいくらやっても、（1）と（2）から導けるのは有限個の自然数 $ 1,2,\dots,n$ に対する有限個の命題 $ P(1),P(2),\dots, P(n)$ の正しさだけです。なので、（1）と（2）の仮定だけで
「任意の自然数 $ n$ に対して $ P(n)$ が成り立つ」
つまり、
「無限集合である $ \mathbb{N}$（自然数全体の集合）自体が、その全ての元が $ P$ を満たすような集合である」
という結論を下すことは原理的にできません *3 。
これは、1つずつの自然数に対して（1）と（2）を繰り返し適用しその正しさを示していっても、全ての自然数をチェックする作業は永遠に終わらないということをイメージしてもらえれば納得いただけると思います。つまり、仮定（1）、（2）だけから数学的帰納法自体が成り立つという結論を導くことはできないのです。
では、なぜ数学的帰納法が数学のいたるところで用いられている（したがって正しいものとされている）のでしょうか？
数学的帰納法は公理
実は、数学的帰納法は自然数の定義（ペアノの公理）で仮定された公理のうちの1つなのです。
公理（数学的帰納法の原理） $ P$ を自然数に関する命題とします。
（1）$ P(1)$ が成り立つ。
（2）任意の自然数 $ k$ に対し、「$ P(k)$ ならば $ P(k+1)$」が成り立つ。
上の2つが同時に成り立つならば、任意の自然数 $ n$ に対して $ P(n)$ が成り立つ。
つまり、数学的帰納法は定理ではなくルールだったのです *4 。直感的には成り立っているような気がする数学的帰納法ですが、他の事からは証明ができないので、公理として採用されたものと思われます。
数学では「無限」という概念について扱おうとすると、このように公理レベルの話に入り込んでしまうことが結構あります・・・。（おわり）
*1:厳密には命題関数の意味です。つまり、任意の自然数 $ n$ に対して、命題 $ P(n)$ を対応させる規則のことです。
*2:ここは直感的な説明になっており厳密ではありません。詳しくは、数学的帰納法は成り立たない？のセクションをご覧ください。
*3:直後の本文で書いたこととほとんど同じ内容を繰り返すことになりますが、この話は直感に反すると思われるので、数式を用いた言い換えを述べておきます。（1）と（2）が成り立つならば、「$ P(1)$ は正しい→$ P(2)$ は正しい→$ P(3)$ は正しい→・・・」という有限の長さの並びを作ることはできるので、これを $ n$ 回繰り返すことで、$ P$ を満たす $ n+1$ 個の自然数からなる有限集合 $ A_{n}=\{1,2,\dots,n,n+1\} $ を作り出すことができます。しかし $ \mathbb{N}$ は無限集合なので、いくら $ n$ を大きく取ったとしても、必ず $ A_n\subsetneq \mathbb{N}$ です（有限集合と無限集合が等しくなることはありえないため）。したがって、「「（1）かつ（2）」ならば $ A_n=\mathbb{N}$ である（数学的帰納法）」は導けません。このような事が起こってしまう理由は、有限と無限の違いがある議論を結びつけてしまおうとするところにあります。（1）と（2）だけから得られる結論は、$ n$ がいくらでも大きく取れるとはいえ有限の範囲に収まっている話であり、一方数学的帰納法の結論は無限集合である $ \mathbb{N}$ 全体に関する言及であるので、この2つの論理の間には有限と無限のギャップが存在しているのです。
*4:なお、より抽象的な立場から考えれば数学的帰納法は超限帰納法（ざっくりいうと、自然数に限らない、ある順序に関する特別なルールが定まっている集合に適用できる一般化された数学的帰納法）というものの特別な例だということはできます。しかし、集合論の公理の1つである選択公理という無限に関する取り決めを仮定すること無しには、超限帰納法自体にかなりの制限がかかってしまいます（もちろん選択公理を仮定しない場合、$\mathbb{N}$ には超限帰納法が適用できない）。 また、「$\mathbb{N}$ に超限帰納法が適用できるということさえ言えればいいから、選択公理の仮定を回避したい」と考えたとしても、その場合は数学的帰納法の原理と同値な「$\mathbb{N}$ の整列性」と呼ばれる仮定が必要となってしまい、結局数学的帰納法の原理を認めたことと同じになってしまいます。 つまり、数学的帰納法から超限帰納法へ視野を広げたとしても、公理としてなんらかの無限に関するルールを仮定する必要性は残ってしまうのです。
