5.3 数学的帰納法 vs 強い数学的帰納法 vs 整列原理

強い数学的帰納法は通常の数学的帰納法より「強く」見える ── 帰納ステップで利用できる仮定が多いからである。通常の数学的帰納法は強い数学的帰納法の特殊ケースだから、通常の数学的帰納法を個別に扱うのはどうしてかと思った読者もいるかもしれない。

しかし、強い数学的帰納法による任意の証明は本質的に同じ議論を使った通常の数学的帰納法による証明に書き換えられる！ それも、定理証明の機能を一切持たない単純なテキスト操作プログラムで書き換えられる。具体的には、強い帰納法の仮定が \(P(n)\) のとき、通常の帰納法の仮定を \(Q(n) ::= \forall k \leq n.\ P(k)\) と定めればよい。

ただ、二つの数学的帰納法の区別が無意味なわけではない。\(P(n + 1)\) が \(P(n)\) だけから従うのか、それとも \(P(1)\), \(\ldots\), \(P(n)\) を全て仮定して初めて従うのかを前もって示しておけば、読者は証明を追いやすくなる。

実は、整列原理に対しても同じことが言える。数学的帰納法と整列原理では証明のテンプレートが大きく異なるものの、数学的帰納法による任意の証明を整列原理による証明に (そして逆方向に) 書き換える数学的に定義された操作が存在する。この書き換えの詳細を理解する必要はない。ただ、本章で示した証明のいくつかは以前に整列原理で証明していた事実を思い出してほしい (例えば第 2.2.1 項と第 5.1.4 項)。重要なのは、これら三つの証明技法 ── 整列原理、通常の数学的帰納法、強い数学的帰納法 ── が理論的には同じ数学的推論規則の別表現に過ぎないという事実である！

どうして本質的に同じ証明技法が三つもあるのだろうか？ まず、数学的帰納法を使うと背理法を使わないで済むので証明の流れが簡潔になる場合がある。また、数学的帰納法による証明の多くは小規模な問題に対する解答から大規模な問題に対する解答を作成する手続きを与える。一方、整列原理による証明の方が短く、初学者にとって自然で理解しやすい場合がある。

どの証明技法を使うべきだろうか？ 単純な解答は存在しない。実際に複数の証明を書いて比較するまで解答が分からないケースもある。どの証明技法を使うにしても、その技法を証明の最初に表明して読者の理解を助けることを忘れてはいけない。