数学的帰納法

提供: miniwiki
移動先:案内検索

数学的帰納法(すうがくてききのうほう、: mathematical induction)は自然数に関する命題 P(n) が全ての自然数 n に対して成り立っている事を証明するための、次のような証明手法である[注 1]

  1. P(1) が成り立つ事を示す。
  2. 任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つ事を示す。
  3. 以上の議論から任意の自然数 n について P(n) が成り立つ事を結論づける。

上で1と2から3を結論づける所が数学的帰納法に当たる。自然数に関するペアノの公理の中に、ほぼ等価なものが含まれている。

なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は帰納ではなく、純粋に自然数の構造に依存した演繹論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。

直観的説明

高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。P(n) を「n 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる:

  1. 1枚目のドミノが倒れる事を示す。
  2. 任意の自然数 k に対して、「k 枚目のドミノが倒れるならば k + 1 枚目のドミノが倒れる」ことを示す。
  3. 以上の議論から全てのドミノが倒れる事が結論づけられる。

数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より

(a) P(1)

が正しい事が分かる。次に k = 1, 2, ... に対して 2 を適用する事で、

(b) P(1) ⇒ P(2),
(c) P(2) ⇒ P(3),

が分かる。(a), (b) より、P(2) が成り立ち、この事実と (c) を組み合わせる事により P(3) が従う。以下同様に P(4), P(5), …も従い、結局 3 の

全ての自然数 n に対し P(n) が成り立つ

が結論づけられる。

ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。

バリエーション

数学的帰納法には次のようなバリエーションもあり、場合によってはこれらを用いる必要がある。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。

1以外から始める

変数変換によって明らかなように、変数 n が表す範囲は nn + 1 という操作で閉じていれば {1, 2, ...} である必要はなく、0 を自然数に含めることにしたり、あるいは任意の整数 m に関する {m, m + 1, ...} という範囲でもよいことになる。

+1以外

例えば nn + 1 ではなく、nn + 2 で証明し、開始点が P(2) であれば、全ての正の偶数で証明できる。バリエーションとしては、P(2) から nn + 2 で正の偶数を証明し、P(1) から nn + 2 で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、P(0) から nn + 1nn − 1 を両方証明し、全ての整数で成立することを証明するというのもある。

先立つすべての結果を用いる

仮定として P(k) だけでなく P(1) から P(k − 1) までのすべて(もしくは一部)を用いる。これを完全帰納法: complete induction、これは同じく完全帰納法と訳される perfect induction とは別物)もしくは累積帰納法: course of values induction)という。

任意の自然数 k をとったとき、k より真に小さなすべての自然数 m に対して P(m) が真であれば、P(k) も真である[注 2]
よって任意の自然数 n について P(n) は真である。

背理法を組み合わせたもの

無限降下法とは、次のような証明のパターンのことである。

P(n) が成立しないような自然数 n が存在すると仮定し、その中で最小のものを k とする。次に、与えられた設定から P(k − 1) も成り立たないことを示す。これは k の取り方に矛盾するから、そもそも P(n) が成立しないような自然数 n は存在しない。すなわち、すべての自然数 n に対して P(n) が成り立つ。

この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 N が通常の大小関係 < によって整列されていることによる。<N 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。

より一般の集合への拡張

数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づける事で数学的帰納法を適応できる事がある。例えば直積集合 N × N 上に辞書式順序

(x, y) > (x′, y′)
 :⇔ (x > x) または (x = x かつ y > y)

を入れる事で N × N 上でも数学的帰納法が使える。

数学的帰納法の例

次の等式が成り立つという命題を P(n) とし、この命題が任意の自然数 n について成立することを数学的帰納法を用いて証明する。

[math]1 + 2 + \cdots + n = \frac{n(n + 1)}{2}.[/math]

まず、P(1) は右辺を計算することで、正しいことが確かめられる。

右辺 = (1(1+1))/2 = 1 = 左辺。

次に、任意の自然数 k をとる。P(k) は下記の通りであり、これが成立すると仮定する。

[math]1 + 2 + \cdots + k = \frac{k(k+1)}{2}.[/math]

これが成立することを使いて P(k + 1) の左辺を計算すると、P(k + 1) も成立することが分かる。

[math]1 + 2 + \cdots + k + (k+1) = (1 + 2 + \cdots + k) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}[/math]

以上から、数学的帰納法により、任意の自然数 n について命題 P(n) が成立する。

数学的帰納法の形式的な取り扱い

数学的帰納法の原理を説明する前に、まず前述した直観的説明のどこにギャップがあったのかを説明する。前述の説明では、まず我々は P(1) を結論づけ、次に (a), (b) から P(2) を結論づけ、さらにそれと (c) を組み合わせる事で P(3) を結論づけ、さらにそれと(d)を組み合わせる事で P(4) を結論づけた。以上の議論から分かるように、P(2) を結論づける為には2ステップの推論、P(3) を結論づけるには3ステップの推論、…、P(100) を結論づけるには100ステップの推論が必要となる。

従って有限回のステップでは有限個の n に対してしか P(n) を結論づける事ができず、「無限個ある自然数全てに対して P(n) が成り立つ」という数学的帰納法の結論について有限の長さの証明が与えられたとはいえない。これが前述した直観的説明におけるギャップである。

そこで、ペアノ算術などの形式的な体系では、数学的帰納法を証明に用いてよいことが公理として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。

同値な定式化

集合論の枠組みでは、数学的帰納法の原理を次のように表すことができる[1]

自然数 N の部分集合 A が空でないとき、A に属する最小の自然数が存在する。

この原理からもともとの形の数学的帰納法が導かれることは,次のようにして示せる。帰納法の仮定 1., 2. を満たす論理式 P(n) が与えられたとする。自然数の部分集合 AA = { nN : ¬ P(n) } によって定める。この A が空集合であるということを示したい。そうでないと仮定すると、Aに属する最小の自然数 a を取ることができるが、P(0)は成り立っていることから a は0でない。従って、ある自然数 b について a = b + 1となっているが、aA に属する最小の自然数であったということから、bA であり、P(b) は成り立つことになる。帰納法の仮定から P(a) も成り立つことになり、これは矛盾である。

逆に、「n 以下の任意の自然数 k について kA」という形の命題 P(n) を考えることで、数学的帰納法から上の原理を導くことができる。A を自然数のある集合とし、A に属する最小の自然数が存在しないと仮定する。もし P(0) が成り立たないと、0 が A に属する最小の自然数となって仮定に反するから、P(0) は成り立つ。P(n) が成り立つとし、もし P(n + 1) が成り立たないとすると、n + 1 が A の最小の自然数となって仮定に反するから、P(n + 1) も成り立つ。よって数学的帰納法により A は空となる。

超限帰納法

上記の形で自然数について定式化された数学的帰納法は、任意の整列集合に対して次のように一般化することができる。この一般化を超限帰納法 (ちょうげんきのうほう、: transfinite induction)という。任意濃度の集合は選択公理と同値な整列可能定理により整列順序を持つとすることができるので、選択公理を含む公理系であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。

超限帰納法
(A , ≤) を整列集合とし、P(x)A 上で定義された命題関数とする。もし次の条件が成立するならば、任意の xA について P(x) は真である。
条件
aA の任意の元とする。x < a を満たす A の全ての元 x について P(x) が真ならば、P(a) も真である。

ただし、"<" は a < b ⇔ ( abab) で定義される二項関係とする。

証明

(1) A は整列集合であるから順序 "" について最小元を持つ。これを、a0 とする。定理の条件において a = a0 と置けば、x < a を満たす A の元は存在しないので、「x < a を満たす A の全ての元 x について P(x) が真」という命題は無条件に真であり、従って、定理の条件を満たすためにはP(a0) は真でなければならない[2]

(2) つぎに超限帰納法の言明が偽と仮定する。これはある整列集合Aおよび、その上で定義された命題関数 P の組が存在して、定理の条件を満たしても P(x) が偽となる A の元 x が存在することを意味する。Pが偽となる A の元全ての集合を Af とする。A は整列集合であるからその部分集合である Af も最小元を持つ。これを a とする。当然 P(a) は偽である。

(3) (1)で証明したように、定理の条件を満たしている限り A の最小元a0 についてP(a0) は真であるから aa0 ではあり得ない。従って、Aa = {x | xAx < a} と置けば、Aa は空ではない (少なくとも a0 を含む)。

(4) aP が偽となる A の最小元であるから、xAa であれば、P(x) は真である。従って、定理の条件により P(a) は真とならねばならないが、これは前言と矛盾する。

(5) 以上から、定理の条件を満たしても P(x) が偽となる xA が存在するような整列集合 A と、その上で定義される命題関数 P の組は存在し得ないことになる。従って超限帰納法の言明は真である。

整礎帰納法

無限下降列が存在しない二項関係整礎関係という。整礎関係が定義された集合に対して次が成り立つ。これを整礎帰納法: well-founded induction)という。

R を集合 A 上の整礎関係とし、P(x) を A の元 x に関する命題とする。もし次が成立するならば、任意の xA について P(x) は真である。
任意の aA をとる。x R a なる任意の A の元 x について P(x) が真ならば、P(a) も真である。

超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に最小元が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に極小元が存在する、という性質に対応している。

ハゲ頭のパラドックス

数学的帰納法を意図的に誤用したジョークとして、次のようなものがある[3]

髪の毛が一本もない人はハゲである。ハゲの人に髪の毛を一本足してもやっぱりハゲである[注 3]。よって数学的帰納法により、全ての人はハゲている。

以上のような論法の起源は、古代ギリシャの哲学者ミレトスのエウブリデス (en) が作ったとされるハゲ頭のパラドックス (Paradox of the Bald Man)[4]に帰せられる。これは砂山のパラドックスの起源としても知られる。

前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。

歴史

初期の例としては、プラトンによるパルメニデス(紀元前 370年)において暗黙に帰納法を使用した証明がみられる[5]。また数学的帰納法としての痕跡は、素数が無限個あることを示したユークリッドの証明や、バースカラ2世による "cyclic methodEnglish版"[6] に見ることができる。通常とは逆に、パラメータとなる自然数が減少していく逐次的な論法は、砂山のパラドックスにみられる。つまり、10,000粒の砂粒が砂山を形成し、そこから一粒の砂を取り除いても砂山が残るならば、一粒だけ残った砂(或いは全ての粒を取り去った後)でもなお砂山を形成するといえる。

等差数列について暗黙に数学的帰納法を用いた証明は、紀元 1000年ごろにal-KarajiEnglish版による "al-Fakhri" に扱われている。al-Karaji は二項定理パスカルの三角形を示すのに数学的帰納法を用いた。

しかし、これらの古代の数学者たちは帰納法の仮定を明示することはしていない。別の似た例としては(Freudenthal が注意深く示したように、Vacca が著したものとは対立するが)、Francesco MaurolicoEnglish版が 1575年の著作 "Arithmeticorum libri duo" にて最初の n 個の奇数の和が n2 に等しいことを示す際にこの技術を用いている。明示された形での数学的帰納法の原理はパスカルがその著作 "Traité du triangle arithmétique" (1655)にて与えた。フランス人フェルマーは、帰納法と関連する、無限降下法による間接的な証明をうまく使っている。帰納法の仮定はヤコブ・ベルヌーイによっても使われ、以後多少よく知られるようになった。現代的な厳密さをもち体系的な数学的帰納法の原理の扱いは 19世紀に入ってジョージ・ブールオーガスタス・ド・モルガンチャールズ・サンダース・パースジュゼッペ・ペアノリヒャルト・デーデキントによって為された。

関連項目

  1. 自然数の定義は 0 を含む流儀とそうでない流儀があるが、ここでは後者を採用した。
  2. k = 1 のときは、k より真に小さい自然数は存在しないので、P(1) が真であることを意味する。
  3. ここでは「髪の毛が少ない人」の意味で「ハゲ」という言葉を用いている。髪の毛の本数が0本である必要は無い。

参考文献

  1. Causey, Robert L., Logic, Sets, and Recursion (1994), pp. 223–224.
  2. 松村英之、『集合論入門』、朝倉書店〈基礎数学シリーズ 5〉、1966年、p. 128。
  3. 例えば次の文献:草場公邦『数理と発想』創拓社、1978年
  4. Hyde, Dominic, "Sorites Paradox", The Stanford Encyclopedia of Philosophy (Fall 2005 Edition), Edward N. Zalta (ed.)
  5. Acerbi, F. (2000). Plato: Parmenides 149a7-c3. A Proof by Complete Induction?, Archive for History of Exact Sciences 55: 57–76. doi:10.1007/s004070000020
  6. Cajori, Florian (1918). Origin of the Name "Mathematical Induction". The American Mathematical Monthly 25 (5): 197–201. doi:10.2307/2972638. JSTOR 2972638.