「数学的帰納法」の版間の差分

削除された内容 追加された内容
m →‎直観的説明: リンク付加
Makotoy (会話 | 投稿記録)
公理論的な部分の説明を修正、構成替え
1行目:
'''数学的帰納法'''(すうがくてききのうほう、mathematical induction)は、[[自然数]]に関する命題や、自然数をパラメータとして含むような命題を証明するための[[数学]]の論法の一つである。自然数 ''n'' に関する[[条件]] ''P''(''n'') がすべての自然数 ''n'' に対して成り立つことを、次のような手順で[[証明]]する方法をいうである
 
# 最小の自然数 1. に関して、''P''(1) が成り立つ事を示す。
2.# 任意の自然数 ''k'' に対して、''P''(''k'') ⇒ ''P''(''k'' + 1) が成り立つ事を示す。
3.# 以上の議論から任意の自然数 ''n'' について ''P''(''n'') が成り立つ事を結論づける。
 
上で1.と2.から3.を結論づける所が数学的帰納法に当たる。<!--この項目を読むのは高校生変数変換によって明らかなように、変数''n''多そ表す範囲は''n'' &rarr; ''n'' + 1といなの操作、高校教科書に合わせ閉じ0いれば {1, 2, ... } である必要なく、0を自然数でないものに含めるこして説明したり、あるいは任意の整数 m に関する {m, m+1, ...} という範囲でもよいことになる-->
<!-- 教科書ではないので、「高校生にわかるように」特定の情報を隠すべきではないと思う -->
 
== 歴史 ==
15 ⟶ 16行目:
 
== 直観的説明 ==
 
数学的帰納法の妥当性は以下のように説明できる。
以上の論法が成り立つ直観的理由は以下の通りである。
まず1.より
 
23 ⟶ 25行目:
次に ''k'' = 1, 2, ...に対し2. を適応する事で、
 
: (b) ''P''(''1'') &rArr; ''P''(''2''),
: (c) ''P''(''2'') &rArr; ''P''(''3''),
: (d) ''P''(''3'') &rArr; ''P''(''4'')
: (e) ''P''(''4'') &rArr; ''P''(''5'')
: …
 
が分かる。(a), (b)より、''P''(''2'') が成り立ち、この事実と(c)を組み合わせる事により''P''(''3'')が従う。以下同様に ''P(5)'', ''P(6)'', …も従い、結局3.の
が分かる。
 
: 全ての整数''n'' に対し''P(n)'' が成り立つ
(a), (b)より、
 
が結論づけられる。
: ''P''(''2'')
 
ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であってただし以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1.,2.と3.の間にはギャップがある。
が成り立ち、この事実と(c)を組み合わせる事により
 
なお、数学的「[[帰納]]法」という名前がつけられているが、数学的帰納法を用いた証明は帰納法ではなく[[演繹]]法である。先に述べた 2. により次々と命題の正しさが"伝播"されていき、すべての自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。
: ''P''(''3'')
 
== バリエーション ==
が従う。さらにこの事実を(d)と組み合わせる事で
数学的帰納法には次のようなバリエーションもあり、場合によってはこちらを用いた方が議論が容易になる。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。
 
=== 背理法を組み合わせたもの ===
: ''P''(''4'')
次の証明は、[[無限降下法]]と呼ばれる証明とほぼ同等である。
:''P''(''n'') が成立しないような自然数 ''n'' が存在すると仮定し、その中で最小のものを ''k'' とする。このとき ''P''(''k'' - 1) も成り立たないことを示す。
:これは矛盾であるから ''P''(''n'') が成立しないような自然数 ''n'' は存在しない。すなわち、すべての自然数 ''n'' に対して ''P''(''n'') が成り立つ。
この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 '''N''' が通常の大小関係 &lt; によって整列されていることによる。&lt; が '''N''' 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
 
=== 先立つすべての結果を用いる ===
が従う。以下同様に
仮定として ''P''(''k'') だけでなく ''P''(0) から ''P''(''k - 1'') までのすべて(もしくは一部)を用いる。
 
:任意の自然数 ''k'' をとったとき、''k'' より小さなすべての自然数 ''m'' に対して ''P''(''m'') が真であれば、''P''(''k'') も真である。
: ''P(5)'', ''P(6)'', …
:よって任意の自然数 ''n'' について ''P''(''n'') は真である。
 
も従い、結局3.の
 
: 全ての整数''n'' に対し''P(n)'' が成り立つ
 
が結論づけられる。
 
ただし以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1., 2. と 3.の間にはギャップがある。厳密には数学的帰納法の正しさは自然数の性質の一つである'''[[数学的帰納法#数学的帰納法の原理|数学的帰納法の原理]]'''によって示される。
 
なお、数学的「[[帰納]]法」という名前がつけられているが、数学的帰納法を用いた証明は帰納法ではなく[[演繹]]法である。先に述べた 2. により次々と命題の正しさが"伝播"されていき、すべての自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。
 
== 数学的帰納法の例 ==
75 ⟶ 71行目:
: 1 = 1 (1+1)/2
 
は右辺を直接計算することができ、正しいことが確かめられる。
は正しい。
 
次に、任意の自然数 ''k'' をとる。今、''P''(''k'') が正しいと仮定すると ''P''(''k'' + 1) も正しい。実際、仮定''P''(''k'') より
87 ⟶ 83行目:
である。すなわち ''P''(''k'' + 1) が成立する。
 
以上から、数学的帰納法により、任意の自然数 ''n'' について命題 ''P''(''n'') が成立する。(証明終)
 
==数学的帰納法の形式的な取り扱い==
 
数学的帰納法の原理を説明する前に、まず前述した直観的説明のどこにギャップがあったのかを説明する。前述の説明では、まず我々は ''P''(''1'') を結論づけ、次に(a), (b)から ''P''(''2'') を結論づけ、さらにそれと(c)を組み合わせる事で ''P''(''3'') を結論づけ、
 
== 数学的帰納法の原理 ==
 
数学的帰納法が成り立つ直観的理由を前の節で説明したが、
これは厳密なものではなく、不備がある。
正式には数学的帰納法の正しさは自然数の性質の一つである'''数学的帰納法の原理'''によって示される。
本節ではこの原理について説明する。
 
=== 直観的説明の不備 ===
 
数学的帰納法の原理を説明する前に、まず前述した直観的説明のどこに不備があったのかを説明する。
前述した説明でまず我々は ''P''(''1'') を結論づけ、次に(a), (b)から ''P''(''2'') を結論づけ、さらにそれと(c)を組み合わせる事で ''P''(''3'') を結論づけ、
さらにそれと(d)を組み合わせる事で ''P''(''4'') を結論づけた。
以上の議論から分かるように、''P''(''2'')を結論づける為には2ステップの推論、
107 ⟶ 93行目:
 
従って有限回のステップでは有限個の''n'' に対してしか ''P''(''n'') を結論づける事ができず、
「無限個ある自然数全てに対して''P''(''n'') が成り立つ」という数学的帰納法の結論を結論づける事について''有限の長さの証明''が与えられたとできいえない。これが前述した直観的説明におけるギャップである
これが前述した直観的説明の不備である。
 
そこで、[[ペアノ算術]]などの形式な体系では、数学的帰納法を証明に用いてよいことが[[公理]]として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。
=== 原理 ===
 
=== 集合論における定式化 ===
数学的帰納法の原理とは次のような命題である。
:次の条件をみたす自然数の集合 ''A'' は、自然数全体の集合 '''N''' と等しい:
:#0 &isin; ''A'' 。
:#''A'' は ''S''(''n'') = ''n'' + 1 で定義される写像 ''S'' : '''N''' → '''N''' に関して閉じている。
 
[[集合論]]原理を用いて枠組みでは、数学的帰納法の正しさは原理を次のようにして示すことができる。すべての自然数 ''n'' に対して ''P''(''n'') が成り立つことを示したいとする。いま、
: 自然数の部分集合 ''A'' が空でないとき、''A'' に属する最小の自然数が存在する。
#''P''(0) が成り立つ。
この原理からもともとの形の数学的帰納法が導かれることは,次のようにして示せる。帰納法の仮定 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'') も成り立つことになり、これは矛盾である。
#任意の自然数 ''k'' に対して、''P''(''k'') &rArr; ''P''(''k'' + 1) が成り立つ。
が示されたとしよう。ここで ''A'' = { ''n'' &isin; '''N''' | ''P''(''n'') } とおけば、この 1. と 2. はまさに ''A'' が 0 を要素に持ち、''S'' に関して閉じているということに他ならないので、数学的帰納法の原理より ''A'' = '''N''' である。したがって、すべての自然数 ''n'' に対して ''n'' &isin; ''A''、つまり ''P''(''n'') が成り立つことが示された。
 
逆に、「''n''以下の任意の自然数''k''について''k'' &notin; ''A''」という形の命題 ''P''(''n'') を考えることで、数学的帰納法から上の原理を導くことができる。
自然数を他の対象(集合、実数など)を用いて定義する立場では、自然数全体の集合は、 0 を要素に持ち、後続者演算("+1" をする演算)に関して閉じているような最小の集合として定義されるので、数学的帰納法の原理は[[定理]]として証明される。一方、自然数を公理的に扱う立場([[ペアノの公理]]など)では、自然数に関する[[公理]]の一つとして数学的帰納法の原理が採用される。
 
=== 超限帰納法 ===
なお、自然数全体の集合は無限集合ではあっても「無限大」そのものを含んでおらず、数学的帰納法によって「すべての自然数 ''n'' に対して」示せたからといって、''P''(''n'') が ''n'' の無限大の極限をとっても成り立つとは限らない。
 
== バリエーション ==
数学的帰納法には次のようなバリエーションもあり、場合によってはこちらを用いた方が議論が容易になる。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。
 
=== 1 以外から始める ===
ある(1 でないかもしれない)整数 ''m'' から議論を始める。すなわち、次の2つを確かめることにより ''m'' 以上の任意の整数 ''n'' について ''P''(''n'') が成立することを示す。
:#''P''(''m'') が成り立つ。
:#''m'' 以上の任意の整数 ''k'' に対して、''P''(''k'') &rArr; ''P''(''k'' + 1) が成り立つ。
:よって ''m'' 以上の任意の整数 ''n'' について ''P''(''n'') が成り立つ。
''m'' = 1 の場合が特に頻繁に用いられる。
 
=== 対偶論法を組み合わせたもの ===
対偶ともとの命題は同値であるという事実を組み合わせて、次のような証明ができる。
:#''P''(1) は真である。
:#''P''(''k'' + 1) が偽であれば、''P''(''k'') も偽である。
:よって任意の自然数 ''n'' について ''P''(''n'') は真である。
 
【補足】2. において、対偶を取ることで、
''P''(''k'') が真であれば、''P''(''k'' + 1) も真である。
という結果が得られるから、前記と同様になる。
 
=== 背理法を組み合わせたもの ===
次の証明は、[[無限降下法]]と呼ばれる証明とほぼ同等である。
:''P''(''n'') が成立しないような自然数 ''n'' が存在すると仮定し、その中で最小のものを ''k'' とする。このとき ''P''(''k'' - 1) も成り立たないことを示す。
:これは矛盾であるから ''P''(''n'') が成立しないような自然数 ''n'' は存在しない。すなわち、すべての自然数 ''n'' に対して ''P''(''n'') が成り立つ。
この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 '''N''' が通常の大小関係 &lt; によって整列されていることによる。&lt; が '''N''' 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
 
=== 先立つすべての結果を用いる ===
仮定として ''P''(''k'') だけでなく ''P''(0) から ''P''(''k - 1'') までのすべて(もしくは一部)を用いる。
:任意の自然数 ''k'' をとったとき、''k'' より小さなすべての自然数 ''m'' に対して ''P''(''m'') が真であれば、''P''(''k'') も真である。
:よって任意の自然数 ''n'' について ''P''(''n'') は真である。
 
上記の形で自然数について定式化された数学的帰納法は、任意の[[整列集合]]に対して次のように一般化することができる。この一般化を'''超限帰納法''' (ちょうげんきのうほう、'''{{lang-en-short|transfinite induction}}''')という。任意[[濃度 (数学)|濃度]]の集合は[[選択公理]]と同値な[[整列可能定理]]により整列順序を持つとすることができるので、選択公理を含む[[公理系]]であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。
== 超限帰納法 ==
自然数について定義された数学的帰納法は、任意の[[整列集合]]に対して次の ''命題'' のように一般化される。この一般化を'''超限帰納法''' (ちょうげんきのうほう、'''{{lang-en-short|transfinite induction}}''')という。任意[[濃度 (数学)|濃度]]の集合は[[選択公理]]と同値な[[整列可能定理]]により整列順序を持つとすることができるので、選択公理を含む[[公理系]]であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。
 
''命題'' : (''A'' , &le; ) を整列集合とし、''P'' (''x'' ) を ''A'' の元 ''x'' に関する命題とする。 ''A'' は整列集合であるから "&le;" について最小元を持つ。これを 、''a<sub>0</sub>'' とする。もし次の2つの条件が成立するならば、任意の ''x'' &isin; ''A'' について ''P'' (''x'' ) が成り立つ。
168 ⟶ 117行目:
ただし、"&lt;" は ''a'' < ''b'' &hArr; ( ''a'' &le; ''b'' &and; ''a'' &ne; ''b'') で定義される順序関係とする。
 
==== 証明 ====
(1) ''命題'' が偽と仮定する。これは ''条件 1'' 、''条件 2'' が満たされても ''P'' (''x'' ) が偽となる ''x'' &isin; ''A'' の元が存在することを意味する。そのような元の全ての集合を ''A<sub>a</sub>'' とする。''A'' は整列集合であるからその部分集合である ''A<sub>a</sub>'' も最小元を持つ。これを ''b'' とする。