帰納法の亜種
まず帰納法をおさらいしましょう. 自然数における数学的帰納法は,
「(i) P(0) が成立する.
(ii) P(n) が成立するならば, P(n+1) も成立する.
以上の 2 条件が満たされるならば, 全ての n で P(n) が成立する.」
というものでした.
(i), (ii) の 2 条件から "全ての n で P(n) が成立する" ことが妥当 であることをまず見てみます.
(i) から P(0) が成立し, (ii: n = 0) から P(1) が成立, (ii: n = 1) から P(2) が成立, (ii: n = 2) から P(3) が成立, ...
"これを無限に続けることでどんな自然数に対しても成立するであろう" 事は感覚的にもうなずけると思います. 無限に並んだドミノ倒しという例えが良くされます.
"無限に続ける" とはどういうことか? など, ここから話は広がりますが, 上の一連の流れを少し分析してみましょう.
例えば P(3) は, P(0) ⇒ P(1) ⇒ P(2) と来てその次に成立することが確認されますが, この時点で P(0), P(1), P(2) の三つが成立しています.
(ii: n = 3) では P(2) だけから P(3) を導出していますが, 問題によっては P(2) だけから P(3) を示すのが難しく, P(0), P(1), P(2) からなら P(3) を示すことが出来る, という状況がしばしばあるのです.
ドミノ倒しの例えでいえば, "ひとつ手前のドミノだけの重さでは次のドミノが倒れないけれども, 既に倒れたドミノ全ての重さをかければ倒れる" という感じですね.
(ii') n 未満の全ての k で P(k) が成立するならば, P(n) も成立する.
つまり, 普通の帰納法の条件 (ii) を (ii') に変更しても, "全ての n で P(n) が成立する" ことを結論付けられるのです. (ちなみに余談ですが, (ii') で n = 0 とすると P(0) が出るので, (ii') の帰納法では条件 (i) は外せます.)
さて, ここまであまり無限が活躍しない話を長々としたのは, 自然数以外の集合での帰納法が, ほとんど (ii') のタイプで行われるからです.
次回は帰納法が適用できる例と出来ない例を見て, どのようなときに帰納法が使えるのかを見ていく予定です.
