数学的帰納法のソースを表示

'''数学的帰納法'''（すうがくてききのうほう、{{lang-en-short|''mathematical induction''}}）は、[[数学]]における[[証明 (数学)|証明]]の手法の一つである。

例えば[[自然数]]に関する命題 {{math|''P''(''n'')}} が全ての自然数 {{mvar|n}} に対して成り立つことを証明するために、次のような手続きを行う<ref group="注">自然数の定義は {{math|0}} を含む流儀とそうでない流儀があるが、ここでは後者を採用した。{{math|0}}を含むとする場合には、{{math|''P''(1)}} が成り立つことを示す代わりに{{math|''P''(0)}} が成り立つことを示す。</ref>。
# {{math|''P''(1)}} が成り立つことを示す。
# 任意の自然数 {{mvar|k}} に対して、「{{math|''P''(''k'') &rArr; ''P''(''k'' + 1)}}」が成り立つことを示す。
# 1と2の議論から任意の自然数 {{mvar|n}} について {{math|''P''(''n'')}} が成り立つことを結論づける。

== 概要 ==
[[自然数]]に関する[[ペアノの公理]]の中に、ほぼ等価なものが含まれている。

なお、数学的「帰納」法という名前がつけられているが、数学的帰納法を用いた証明は[[帰納]]ではなく、純粋に自然数の構造に依存した[[演繹]]論理の一種である。2 により次々と命題の正しさが"伝播"されていき、任意の自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられた<ref>[https://www.nli-research.co.jp/report/detail/id=68448?site=nli 「数学的帰納法」って何でしたっけ－「帰納法」と「演繹法」－] - [[ニッセイ基礎研究所]]</ref>。[[ジョン・ウォリス]]によって、彼の著作''Arithmetica Infinitorum''の中で、この方法にinductionという名前が与えられたとされる<ref>{{cite web|title=Mathematical Induction Provides A Tool For Proving Large Problems By Proceeding Through The Solution Of Smaller Increments |website= Encyclopedia.com |url=https://www.encyclopedia.com/science/encyclopedias-almanacs-transcripts-and-maps/mathematical-induction-provides-tool-proving-large-problems-proceeding-through-solution-smaller |accessdate=2020-09-08}}</ref><ref>{{Cite journal |title= Origin of the Name "Mathematical Induction" |author=Florian Cajori |publisher= Taylor & Francis, Ltd |url=https://www.jstor.org/stable/2972638?seq=2#page_scan_tab_contents |journal=The American Mathematical Monthly|volume= 25 |number=5 |year=1918 |doi=10.2307/2972638 |authorlink=フロリアン・カジョリ}}</ref>。<!--
教科書ではないので、「高校生にわかるように」特定の情報を隠すべきではないと思う -->
<!--これは誤解を招きかねないので、やめたほうがよい -->

== 直観的説明 ==
高校の教科書等の初等的な解説書では[[ドミノ倒し]]に例えて数学的帰納法を説明しているものも多い。{{math|''P''(''n'')}} を「{{mvar|n}} 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる：
# 1枚目のドミノが倒れることを示す。
# 任意の自然数 {{mvar|k}} に対して、「{{mvar|k}} 枚目のドミノが倒れるならば {{math|''k'' + 1}} 枚目のドミノが倒れる」ことを示す。
# 以上の議論から全てのドミノが倒れることが結論づけられる。

数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より
: (a) {{math|''P''(1)}}
が正しいことが分かる。次に {{math|1=''k'' = 1, 2, ...}} に対して 2 を適用することで、
: (b) {{math|''P''(1) &rArr; ''P''(2)}},
: (c) {{math|''P''(2) &rArr; ''P''(3)}},
: …
が分かる。(a), (b) より、{{math|''P''(2)}} が成り立ち、この事実と (c) を組み合わせることにより {{math|''P''(3)}} が従う。以下同様に {{math2|''P''(4), ''P''(5), …}} も従い、結局3の
: 全ての自然数 {{mvar|n}} に対し {{math|''P''(''n'')}} が成り立つ
が結論づけられる。

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

== 証明 ==
数学的帰納法が成り立つことを数学的帰納法の原理といい、ペアノの公理Ⅴ<ref group="注">リンク先のペアノの公理5.は数学的帰納法そのままの形をしているが、そうではなく、本稿で言うところの公理Vは原典に類似した次のような形式のものである:「集合 <math>M</math> が (1) <math>1\in M</math>、および (2) すべての自然数 <math>r</math> において、<math>r\in M \Rightarrow r+1 \in M</math>、を満たすならば <math>\mathbb{N}\subseteq M</math> である。」</ref>が数学的帰納法の原理そのものを表している。もし、公理Vを用いて、数学的帰納法をあえて証明するならば、以下のように示すことができる。

　自然数の集合を <math>\mathbb{N}</math> とし、命題 <math>P(n)</math> が成り立つ <math>n</math> の集合を <math>M</math> とする。

　　　　　　　　　　　　　<math>M \equiv \{ n \in \mathbb{N} \mid P(n) \}</math>

　(1) 数学的帰納法の仮定により、<math>1</math> は <math>M</math> の要素である。

　　　　　　　　　　　　　<math>1 \in M</math>

　(2) 任意に自然数 <math>r</math> をとる。<math>r\in M</math> を仮定すると、<math>M</math> の定義によって <math>P(r)</math> が成り立つ。このとき、数学的帰納法の手順より、<math>P(r+1)</math> も成り立つ。ふたたび、<math>M</math> の定義によって <math>r+1\in M</math> である。これにより <math>\forall r.\,r\in M \Rightarrow r+1 \in M</math> が示されたことになる。

　(1) および (2) により、ペアノの公理Vによって <math>\mathbb{N} \subseteq M</math> が得られる。部分集合の定義により、これは <math>\forall n\in\mathbb{N}.\, P(n)</math> であることを意味する。(証明終)

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

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

=== +1以外 ===
例えば {{math|''n'' &rarr; ''n'' + 1}} ではなく、{{math|''n'' &rarr; ''n'' + 2}} で証明し、開始点が {{math|''P''(2)}} であれば、全ての正の偶数で証明できる。バリエーションとしては、{{math|''P''(2)}} から {{math|''n'' &rarr; ''n'' + 2}} で正の偶数を証明し、{{math|''P''(1)}} から {{math|''n'' &rarr; ''n'' + 2}} で正の奇数を証明し、よって全ての自然数で成立するという証明方法もある。他にも、{{math|''P''(0)}} から {{math|''n'' &rarr; ''n'' + 1}} と {{math|''n'' &rarr; ''n'' &minus; 1}} を両方証明し、全ての整数で成立することを証明するという場合もある。

=== 先立つすべての結果を用いる ===
仮定として {{math|''P''(''k'')}} だけでなく {{math|''P''(1)}} から {{math|''P''(''k'' − 1)}} までのすべて（もしくは一部）を用いる。これを'''[[完全帰納法]]'''（{{lang-en-short|complete induction}}、これは同じく完全帰納法と訳される [[:w:proof by exhaustion|perfect induction]] とは別物）もしくは'''[[累積帰納法]]'''（{{lang-en-short|[[:w:Course-of-values recursion|course of values induction]]}}）という。
:任意の自然数 {{mvar|k}} をとったとき、{{mvar|k}} より真に小さなすべての自然数 {{mvar|m}} に対して {{math|''P''(''m'')}} が真であれば、{{math|''P''(''k'')}} も真である<ref group="注">{{math|1=''k'' = 1}} のときは、{{mvar|k}} より真に小さい自然数は存在しないので、{{math|''P''(1)}} が真であることを意味する。</ref>。
:よって任意の自然数 {{mvar|n}} について {{math|''P''(''n'')}} は真である。

=== 背理法を組み合わせたもの ===
{{main|無限降下法}}
無限降下法とは、背理法を用いて <math>\forall n\in\mathbb{N}.\,P(n)</math> を証明する、次のようなパターンのことである。
:<math>P(n)</math> が成立しないような自然数 <math>n</math> が存在すると仮定し、その中で最小のものを <math>k</math> とする。次に、<math>P(k)</math> を仮定すると、「ある自然数 <math>k'<k</math> が存在して <math>P(k')</math> ではないこと」を導けることを示す。これは <math>k</math> の最小性に矛盾するから、背理法により、<math>P(n)</math> が成立しないような自然数 <math>n</math> は存在しない。すなわち、すべての自然数 <math>n</math> に対して <math>P(n)</math> が成り立つ。
この議論と前に述べた「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 <math>\mathbb{N}</math> が通常の大小関係 <math><</math> によって整列されていることによる。<math><</math> が <math>\mathbb{N}</math> 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。

=== より一般の集合への拡張 ===
数学的帰納法は自然数に関する論法だが、自然数以外の集合に対しても、集合の元を適切に順序づけることで数学的帰納法を適用できることがある。例えば[[直積集合]] {{math|'''N''' × '''N'''}} 上に[[辞書式順序]]
: {{math|(''x'', ''y'') > (''x''&prime;, ''y''&prime;)}}
: : ⇔ ({{math2|''x'' > ''x''&prime;}}) または ({{math|1=''x'' = ''x''&prime;}} かつ {{math2|''y'' > ''y''&prime;}})
を入れることで {{math|'''N''' × '''N'''}} 上でも数学的帰納法が使える。

== 数学的帰納法の例 ==
次の等式が成り立つという命題を {{math|''P''(''n'')}} とし、この命題が任意の自然数 {{mvar|n}} について成立することを数学的帰納法を用いて証明する。
: <math>1 + 2 + \cdots + n = \frac{n(n+1)}{2}.</math>
まず、{{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'') が成り立つ」という数学的帰納法の結論について無''限の長さの証明''が与えられたとはいえない。これが前述した直観的説明におけるギャップである。

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

=== 同値な定式化 ===
[[集合論]]の枠組みでは、数学的帰納法の原理を次のように表すことができる<ref>Causey, Robert L., ''Logic, Sets, and Recursion'' (1994), pp. 223–224.</ref>。
: 自然数 '''N''' の部分集合 ''A'' が空でないとき、''A'' に属する最小の自然数が存在する。
この原理からもともとの形の数学的帰納法が導かれることは，次のようにして示せる。帰納法の仮定 1., 2. を満たす論理式 ''P''(''n'') が与えられたとする。自然数の部分集合 ''A'' を ''A'' = { ''n'' &isin; '''N''': &not; ''P''(''n'') } によって定める。この ''A'' が空集合であるということを示したい。そうでないと仮定すると、''A''に属する最小の自然数 ''a'' を取ることができるが、''P''(0)は成り立っていることから ''a'' は0でない。従って、ある自然数 ''b'' について ''a'' = ''b'' + 1となっているが、''a'' は ''A'' に属する最小の自然数であったということから、''b'' &notin; ''A'' であり、''P''(''b'') は成り立つことになる。帰納法の仮定から ''P''(''a'') も成り立つことになり、これは矛盾である。

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

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

;超限帰納法: {{math|(''A'' , &le;)}} を整列集合とし、{{math|''P''(''x'')}} を {{mvar|A}} 上で定義された命題関数とする。もし次の条件が成立するならば、任意の {{math|''x'' &isin; ''A''}} について {{math|''P''(''x'')}} は真である。
;条件: {{mvar|a}} を {{mvar|A}} の任意の元とする。{{math|''x'' &lt; ''a''}} を満たす {{mvar|A}} の全ての元 {{mvar|x}} について {{math|''P''(''x'')}} が真ならば、{{math|''P''(''a'')}} も真である。

ただし、"{{math|&lt;}}" は {{math2|''a'' < ''b'' &hArr; ( ''a'' &le; ''b'' &and; ''a'' &ne; ''b'')}} で定義される[[二項関係]]とする。

=== 証明 ===
{{Mvar|A}} を全体集合とする。{{Mvar|A}} の各元 {{Mvar|a}} に対して {{math|''A''(''a'')&nbsp;{{=}}&nbsp;{{mset|&nbsp;''x''∈''A''&nbsp;|&nbsp;''x''&nbsp;&lt;&nbsp;''a''&nbsp;}}}} とし、{{math|''A''<sub>1</sub>&nbsp;{{=}}&nbsp;{{mset|&nbsp;''x''∈''A''&nbsp;|&nbsp;''P''(''x'')&nbsp;}}}} とする。そのとき、超限帰納法の'''条件'''は
{{NumBlk|:|<math>\forall a\in A(A(a)\subseteq A_1\Rightarrow a\in A_1)</math>|{{EquationRef|1}}}}
と[[同値]]である。また、補集合に関する法則から ({{EquationNote|1}}) は
{{NumBlk|:|<math>\forall a\in A(A(a)\cap A_1^c=\varnothing\Rightarrow a\in A_1)</math>|{{EquationRef|2}}}}
と同値である。これらの条件が満たされているという前提の下で、{{math|''A''<sub>1</sub>&nbsp;{{=}}&nbsp;''A''}} すなわち {{math|''A''<sub>1</sub><sup>c</sup>&nbsp;{{=}}&nbsp;&empty;}} が成り立つことを示せばよい。

いま、{{math|''A''<sub>1</sub><sup>c</sup>&nbsp;≠&nbsp;&empty;}}
と仮定して矛盾を導く。[[背理法]]の仮定と整列集合の定義より、{{math|min&nbsp;''A''<sub>1</sub><sup>c</sup>&nbsp;{{=}}&nbsp;''a''}} が存在する。この ''a'' について、最小元の定義より {{math|''A''(''a'')∩''A''<sub>1</sub><sup>c</sup>&nbsp;{{=}}&nbsp;&empty;}} が成り立つので、 ({{EquationNote|2}}) より {{math|''a'' ∈ ''A''<sub>1</sub>}} もまた成り立つ。しかし、これは {{math|''a'' ∈ ''A''<sub>1</sub><sup>c</sup>}} であることに反する。（証明終）

== 整礎帰納法 ==
{{main|整礎帰納法}}
無限下降列が存在しない[[二項関係]]を'''[[整礎関係]]'''という。整礎関係が定義された集合に対して次が成り立つ。これを'''整礎帰納法'''（{{lang-en-short|well-founded induction}}）という。
: ''R'' を集合 ''A'' 上の整礎関係とし、''P''(''x'') を ''A'' の元 ''x'' に関する命題とする。もし次が成立するならば、任意の ''x'' &isin; ''A'' について ''P''(''x'') は真である。
::任意の ''a'' &isin; ''A'' をとる。''x'' ''R'' ''a'' なる任意の ''A'' の元 ''x'' について ''P''(''x'') が真ならば、''P''(''a'') も真である。
超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に'''最小元'''が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に'''極小元'''が存在する、という性質に対応している。

== ハゲ頭のパラドックス ==
数学的帰納法を意図的に誤用したジョークとして、次のようなものがある<ref>例えば次の文献：草場公邦『数理と発想』創拓社、1978年</ref>：
:髪の毛が一本もない人は[[ハゲ]]である。ハゲの人に髪の毛を一本足してもやっぱりハゲである<ref group="注">ここでは「髪の毛が少ない人」の意味で「ハゲ」という言葉を用いている。髪の毛の本数が0本である必要はない。</ref>。よって数学的帰納法により、全ての人はハゲている。

もちろんこの「証明」には理論上の根本的な問題点がある。この「証明」の問題点は、「ハゲ」の[[定義]]を厳密に毛が何本以下であるかで与えることができない点、もしくは「ハゲ」を定義できたとして、[[任意]]の「ハゲ」に髪の毛を一本足したときに、必ず「ハゲ」になるわけではない点にある。以上のような論法の起源は、古代ギリシャの哲学者ミレトスの[[エウブリデス]] ([[:en:Eubulides|en]]) が作ったとされる'''ハゲ頭のパラドックス''' (Paradox of the Bald Man)<ref> Hyde, Dominic, [http://plato.stanford.edu/entries/sorites-paradox/ "Sorites Paradox"], [[The Stanford Encyclopedia of Philosophy ]](Fall 2005 Edition), [[エドワード・ザルタ|Edward N. Zalta]] (ed.)</ref>に帰せられる。これは[[砂山のパラドックス]]の起源としても知られる。

前述の[[ジョーク]]にはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という[[誤謬]]を利用している。<!--
この「証明」には「''P''(0)（もしくは ''P''(''a'')）」が成り立つことを示しているものの、「''P''(''k'') が成り立つならば ''P''(''k'' + 1) でも成り立つ」ということを示していない。これが根本的に間違いである。
↑
一旦削除。「ハゲ」の定義が曖昧なことが根本原因だと思われるため。
たとえばハゲの定義として「全ての人はハゲ」を採用すれば、
「''P''(''k'') が成り立つならば ''P''(''k'' + 1)でも成り立つ」もちゃんと示される。-->

== 歴史 ==
初期の例としては、[[プラトン]]による[[パルメニデス]]（紀元前 370年）において暗黙に帰納法を使用した証明がみられる<ref>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</ref>。また数学的帰納法としての痕跡は、素数が無限個あることを示したユークリッドの証明や、[[バースカラ2世]]による "{{仮リンク|cyclic method|en|Chakravala method}}"<ref>Cajori, Florian (1918). ''Origin of the Name "Mathematical Induction"''. The American Mathematical Monthly '''25''' (5): 197–201. doi:10.2307/2972638. JSTOR 2972638.</ref> に見ることができる。通常とは逆に、パラメータとなる自然数が減少していく逐次的な論法は、[[砂山のパラドックス]]にみられる。つまり、10,000粒の砂粒が砂山を形成し、そこから一粒の砂を取り除いても砂山が残るならば、一粒だけ残った砂(或いは全ての粒を取り去った後)でもなお砂山を形成するといえる。

[[等差数列]]について暗黙に数学的帰納法を用いた証明は、紀元 1000年ごろに{{仮リンク|アブ・バクル・カラジ|en|al-Karaji|label=アル＝カラジ}}による "''al-Fakhri''" に扱われている。アル＝カラジは[[二項定理]]や[[パスカルの三角形]]を示すのに数学的帰納法を用いた。

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

== 関連項目 ==
*[[構造的帰納法]]
*[[帰納]]
*[[演繹]]
*[[自然数]]
*[[整列集合]]
*[[整礎関係]]
*[[無限降下法]]
*[[再帰]]

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Reflist|group="注"}}
=== 出典 ===
{{Reflist|2}}

{{Normdaten}}
{{DEFAULTSORT:すうかくてききのうほう}}
[[Category:数学的帰納法|*]]
[[Category:帰納]]
[[Category:順序構造]]
[[Category:自然数論]]
[[Category:数学に関する記事]]