「数学的帰納法」の版間の差分
削除された内容 追加された内容
m →直観的説明: リンク付加 |
公理論的な部分の説明を修正、構成替え |
||
1行目:
'''数学的帰納法'''(すうがくてききのうほう、mathematical induction)は、[[自然数]]に関する命題や、自然数をパラメータとして含むような命題を証明するための[[数学]]の論法の一つである。自然数 ''n'' に関する[[条件]] ''P''(''n'') がすべての自然数 ''n'' に対して成り立つことを、次のような手順で[[証明]]する方法
上で1.と2.から3.を結論づける所が数学的帰納法に当たる。
<!-- 教科書ではないので、「高校生にわかるように」特定の情報を隠すべきではないと思う -->
== 歴史 ==
15 ⟶ 16行目:
== 直観的説明 ==
以上の論法が成り立つ直観的理由は以下の通りである。
まず1.より
23 ⟶ 25行目:
次に ''k'' = 1, 2, ...に対し2. を適応する事で、
: (b) ''P''(''1'') ⇒ ''P''(''2''),
: (c) ''P''(''2'') ⇒ ''P''(''3''),
: …
が分かる。(a), (b)より、''P''(''2'') が成り立ち、この事実と(c)を組み合わせる事により''P''(''3'')が従う。以下同様に ''P(5)'', ''P(6)'', …も従い、結局3.の
: 全ての整数''n'' に対し''P(n)'' が成り立つ
が結論づけられる。
ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であってただし以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1.,2.と3.の間にはギャップがある。
なお、数学的「[[帰納]]法」という名前がつけられているが、数学的帰納法を用いた証明は帰納法ではなく[[演繹]]法である。先に述べた 2. により次々と命題の正しさが"伝播"されていき、すべての自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。
== バリエーション ==
数学的帰納法には次のようなバリエーションもあり、場合によってはこちらを用いた方が議論が容易になる。これらのバリエーションの正しさは、上で述べた標準的な形の数学的帰納法を用いて示すことができる。
=== 背理法を組み合わせたもの ===
次の証明は、[[無限降下法]]と呼ばれる証明とほぼ同等である。
:''P''(''n'') が成立しないような自然数 ''n'' が存在すると仮定し、その中で最小のものを ''k'' とする。このとき ''P''(''k'' - 1) も成り立たないことを示す。
:これは矛盾であるから ''P''(''n'') が成立しないような自然数 ''n'' は存在しない。すなわち、すべての自然数 ''n'' に対して ''P''(''n'') が成り立つ。
この議論と次に述べる「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 '''N''' が通常の大小関係 < によって整列されていることによる。< が '''N''' 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
=== 先立つすべての結果を用いる ===
仮定として ''P''(''k'') だけでなく ''P''(0) から ''P''(''k - 1'') までのすべて(もしくは一部)を用いる。
:任意の自然数 ''k'' をとったとき、''k'' より小さなすべての自然数 ''m'' に対して ''P''(''m'') が真であれば、''P''(''k'') も真である。
:よって任意の自然数 ''n'' について ''P''(''n'') は真である。
== 数学的帰納法の例 ==
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'') を結論づけ、
さらにそれと(d)を組み合わせる事で ''P''(''4'') を結論づけた。
以上の議論から分かるように、''P''(''2'')を結論づける為には2ステップの推論、
107 ⟶ 93行目:
従って有限回のステップでは有限個の''n'' に対してしか ''P''(''n'') を結論づける事ができず、
「無限個ある自然数全てに対して''P''(''n'') が成り立つ」という数学的帰納法の結論
そこで、[[ペアノ算術]]などの形式な体系では、数学的帰納法を証明に用いてよいことが[[公理]]として仮定されるのが普通である。つまり、形式的には、自然数の性質から数学的帰納法の正しさが証明できるのではなく、逆に自然数の本質的な性質を与える推論規則として数学的帰納法が仮定される、ということになる。
=== 集合論における定式化 ===
: 自然数の部分集合 ''A'' が空でないとき、''A'' に属する最小の自然数が存在する。
この原理からもともとの形の数学的帰納法が導かれることは,次のようにして示せる。帰納法の仮定 1., 2. を満たす論理式 ''P''(''n'') が与えられたとする。自然数の部分集合 ''A'' を ''A'' = { ''n'' ∈ '''N''' : ¬ ''P''(''n'') } によって定める。この ''A'' が空集合であるということを示したい。そうでないと仮定すると、''A''に属する最小の自然数 ''a'' を取ることができるが、''P''(0)は成り立っていることから ''a'' は0でない。従って、ある自然数 ''b'' について ''a'' = ''b'' + 1となっているが、''a'' は ''A'' に属する最小の自然数であったということから、''b'' ∉ ''A'' であり、''P''(''b'') は成り立つことになる。帰納法の仮定から''P''(''a'') も成り立つことになり、これは矛盾である。
逆に、「''n''以下の任意の自然数''k''について''k'' ∉ ''A''」という形の命題 ''P''(''n'') を考えることで、数学的帰納法から上の原理を導くことができる。
=== 超限帰納法 ===
上記の形で自然数について定式化された数学的帰納法は、任意の[[整列集合]]に対して次のように一般化することができる。この一般化を'''超限帰納法''' (ちょうげんきのうほう、'''{{lang-en-short|transfinite induction}}''')という。任意[[濃度 (数学)|濃度]]の集合は[[選択公理]]と同値な[[整列可能定理]]により整列順序を持つとすることができるので、選択公理を含む[[公理系]]であれば超限帰納法は任意濃度の集合に対して成立すると主張できる。
''命題'' : (''A'' , ≤ ) を整列集合とし、''P'' (''x'' ) を ''A'' の元 ''x'' に関する命題とする。 ''A'' は整列集合であるから "≤" について最小元を持つ。これを 、''a<sub>0</sub>'' とする。もし次の2つの条件が成立するならば、任意の ''x'' ∈ ''A'' について ''P'' (''x'' ) が成り立つ。
168 ⟶ 117行目:
ただし、"<" は ''a'' < ''b'' ⇔ ( ''a'' ≤ ''b'' ∧ ''a'' ≠ ''b'') で定義される順序関係とする。
==== 証明 ====
(1) ''命題'' が偽と仮定する。これは ''条件 1'' 、''条件 2'' が満たされても ''P'' (''x'' ) が偽となる ''x'' ∈ ''A'' の元が存在することを意味する。そのような元の全ての集合を ''A<sub>a</sub>'' とする。''A'' は整列集合であるからその部分集合である ''A<sub>a</sub>'' も最小元を持つ。これを ''b'' とする。
|