Willst du ins Unendliche schreiten, Geh nur im Endlichen nach allen Seiten.
— Johann Wolfgang von Goethe
- ハシゴをどこまででも登っていけることを示す。
- ハシゴのどこにいても一番下まで降りていけることを示す。
でも歴史的には下向きの見方が先に登場しているみたい。
ヴィクター・J・カッツ『数学の歴史』によると、10世紀ごろのイスラーム数学者カラジーは、
13+23+ … +n3 = (1+2+ … +n)2
カラジーは、一辺の長さが1+2+…+10の正方形の面積を考えることにより
(1+2+ ... +10)2 = (1+2+ ... +9)2+2×10×(10×9)/2+102
= (1+2+ ... +9)2+103
(1+2+ ... +9)2 = (1+2+ ... +8)2 + 93
(1+2+ ... +8)2 = (1+2+ ... +7)2 + 83
(1+2+ ... +7)2 = (1+2+ ... +6)2 + 73
(1+2+ ... +6)2 = (1+2+ ... +5)2 + 63
(1+2+ ... +5)2 = (1+2+3+4)2 + 53
(1+2+3+4)2 = (1+2+3)2 + 43
(1+2+3)2 = (1+2)2 + 33
(1+2)2 = 12 + 23
12 = 13
(1+2+ ... +10)2 = 13+23+ … +103
カラジーの議論は実質的には、現代の帰納法における二つの基本要素を含んでいる。二つの要素とは、まずn=1について問題の命題が成り立つことであり、次にn=k-1からn=kが成り立つということを導き出すことである。無論、この第二の要素というのは、カラジーの議論でははっきりとは述べられていない。ある意味においては、彼の議論は逆になっているからである。つまり彼はn=10から始め1までおりてくるのであり、その逆ではないからである。
一方、カラジーより後のイスラーム数学者レヴィについて次のように書いている。
証明の中でレヴィは、先行するイスラームの数学者よりもはっきりと数学的帰納法の核心部分を使用している。彼はこの操作を「1段1段限りなく上昇してゆくこと」と呼んでいる。レヴィが帰納法的議論を使うときは、一般に帰納の段階、すなわちkからk+1へと移行する段階を最初に行ない、つぎのこの過程がkのある小さな値で始まると述べ、最後に完全な形で答を与える。
ただしレヴィの著作にも下向きの証明は含まれていて、それについては
現代人が想像するような帰納法による証明とはやや異なっている。彼はnの場合からn+1の場合へと議論せずに、カラジーのようにnの場合からn-1の場合へと議論する。
と述べている。
『数学の歴史』では、nからn-1へという下向きではなくnからn+1へという上向きで考えることを数学的帰納法の核心部分だとみなしているけど、確かに下向きの証明から上向きの証明に移るには考え方の飛躍がいる。
下向きの証明では、どんな事例が与えられてもそこから順に一番下まで降りていくことができるという形で証明をおこなう。この時必要なのはその事例について有限の繰り返しによって証明をおこなうことであり、「限りなく」「どこまでも」続けるというような無限に続くプロセスは登場しない。下向きの証明は、単一の証明というよりも、どんな事例が与えられてもそれについての証明を生成するための手続きを与えていると考えることもできる。その手続きを使えば、どんな事例(どんな数)が与えられても、そこから繰り返し簡単化していくことによって望みの証明(あるいは式の変形や具体的な計算)が遂行できる。
一方、上向きの証明では「この過程は限りなく続けることができる」といった「無限に続くプロセス」への言及が含まれる。
「しかし無限に続くプロセスはいつまでも終わらないから、証明も終わらないではないか」
- 応答1: 個別の具体的事例について、このプロセスによって必ず到達できる。終わりを考える必要はない。
- 応答2: 任意の数についてプロセスを適用することができるので、実際にこのプロセスを無限に続けていかなくても、全ての数について成り立つことが理解される。nからn+1へのステップが示されれば、限りなく続けるというプロセスをへなくても、全ての数についての証明が完了する。
広瀬 書くときの気持で《すべて》の場合と《任意》の場合とがあり、その気持を正確に伝えるという意味では統一すべきでない。たとえば私は、帰納法の説明をするときにはこの二つを完全に書き分ける。
倉田 我々ははっきり区別して了解しているからな。帰納法は[P(0)∧∀n[P(n)→P(n+1)] ]→∀n[P(n)]と書くが、心の中では最初の∀は《任意》であり、あとの∀は《すべて》だ。
(齋藤正彦『超積と超準解析』付録)
同じ証明を下向きに見れば個別の事例についての証明手続きを与えているように解釈でき、上向きに見れば「証明のプロセスを限りなく続けていく」さらにはより強く「無限にある事例の全てを一挙に証明する」と解釈できる。このように数学的帰納法は、有限と無限の狭間、可能無限(限りないプロセスとしての無限)と実無限(完結した総体としての無限)の狭間にある手法だと思うことができる。
再帰アルゴリズムの提示と数学的帰納法
有限の手続きにとどまる下向き解釈よりも上向き解釈の方が強力で優れているようにも見えるけど、必ずしもそうとは限らない。
数学的帰納法の証明の中には、証明と同時に解を求めるためのアルゴリズムも示されている場合があるのだけど、上向きの数学的帰納法ではアルゴリズムが見えなくなってしまうことが多い。
たとえばよく知られた次の定理を、下向きに証明してみる。
グラフが次の2つの条件を満たしているとする。
- グラフ全体が繋がっている。
- グラフの奇数点(その点から出ている辺の数が奇数である点)が2個以下。
この時、グラフを一筆書きすることができる。
これは次のようにすると一筆書きが行える(と同時に証明が完結する)。
まず、グラフの奇数点の総数は必ず偶数個になるので「奇数点が2個以下」というのは「奇数点が2個か0個」と同じになることに注目する。なぜ偶数個になるのかというと、各点から出ている辺の本数を数えてそれを全部足すと(ひとつの辺について2回数えることになるので)必ず偶数になるけど、奇数点が奇数個あるとすると足した総数が奇数になってしまうから。
グラフの奇数点の数に応じて、次のA、Bのどちらかを行う。
- A. 奇数点の総数が2個の場合。奇数点のどちらかから一筆書きを始める。
奇数点から出る辺のうち、その辺を取り除くとグラフが分断するような辺は多くても1個しかない(奇数点が2個なことから導ける。くわしいことは略)。分断しない辺を選んで一筆書きを一歩進めて今通った辺は消す。
移動先の点が元の(辺を消す前の)グラフでは奇数点だった場合、新しいグラフは奇数点0個のグラフになるので次にBを適用する。元のグラフでは偶数点だった場合は、移動先の点が新しい奇数点になる。この場合、奇数点の総数が2個で奇数点から一筆書きを始める形になるので、Aを再び適用する。 - B. 奇数点の総数が0個の場合。任意の一点から一筆書きを始める。
奇数点が0個のときはグラフから辺をひとつ取り除いてもグラフが分断することはない(説明略)。そのため、任意に辺を選んで一筆書きを一歩進め通った辺を消す。するとグラフ全体は繋がっていて奇数点は2個以下のグラフになる。そして奇数点が2個になった場合は、移動先の点が2つの奇数点の片方になっている。奇数点の数に応じてAかBを適用する。
AかBを1回適用すると通っていない辺の数が一つ減るので、繰り返し適用していけば一筆書きが完成する。証明終。
この証明では、一筆書きの再帰アルゴリズムを示し、その各ステップがうまくいくことを説明している。
この証明を上向き、つまり普通の数学的帰納法の形に書き換えた場合、辺の数がn以下で条件を満たすグラフについては一筆書きできることを仮定してn+1の場合でも成り立つことを示すことになる。でも、そのようにしておこなった証明では「条件を満たす任意のグラフで一筆書きできる」ことが主眼になり、与えられたグラフに対する具体的な一筆書きアルゴリズムは表立っては見えなくなってしまう。
この例に限らず、数学的帰納法の証明の中に再帰的アルゴリズムが埋まっていても上向きの証明ではそれが見えにくくなる。再帰的アルゴリズム(の正しさ)が数学的帰納法と対応しているということもあまり意識されていないかもしれない。
