「数学的帰納法」の版間の差分
削除された内容 追加された内容
m ロボットによる 変更: ro:Inducție matematică |
編集の要約なし |
||
1行目:
'''数学的帰納法'''（すうがくてききのうほう、mathematical induction）は、
:#''P''(0)
:#任意の
:よって任意の自然数 ''n'' について ''P''(''n'')
イメージとしては、2 により次々と次の命題の正しさが"伝播"されていくことになる。つまり、1. によりまず ''P''(0) は正しく、''P''(0) と 2. により ''P''(1) は正しく、''P''(1) と 2. により ''P''(2) は正しく、以下これが果てしなく続いていく。このことによって任意の自然数 ''n'' について ''P''(''n'') が正しいことが保証される。
なお、数学的「[[帰納]]法」という名前がつけられているが、数学的帰納法の解法プロセス自体は帰納法ではなく[[演繹]]法である。先に述べた、2. により次々と次の命題の正しさが"伝播"されていった結果証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。
==
数学的帰納法の正しさは厳密には
:次の条件をみたす自然数の集合 ''A'' は、自然数全体の集合 '''N''' と等しい：
:#0 ∈ ''A'' 。
:#''A'' は ''S''(''n'') = ''n'' + 1 で定義される関数 ''S'' : '''N''' → '''N''' に関して閉じている。
この原理を用いると、数学的帰納法の正しさは次のようにして示すことができる。すべての自然数 ''n'' に対して ''P''(''n'') が成り立つことを示したいとする。いま、
#''P''(0) が成り立つ。
#任意の自然数 ''k'' に対して、''P''(''k'') ⇒ ''P''(''k'' + 1) が成り立つ。
が示されたとしよう。ここで ''A'' = { ''n'' ∈ '''N''' | ''P''(''n'') } とおけば、この 1. と 2. はまさに ''A'' が 0 を要素に持ち、''S'' に関して閉じているということに他ならないので、数学的帰納法の原理より ''A'' = '''N''' である。したがって、すべての自然数 ''n'' に対して ''n'' ∈ ''A''、つまり ''P''(''n'') が成り立つことが示された。
自然数を他の対象（集合、実数など）を用いて定義する立場では、自然数全体の集合は、 0 を要素に持ち、後続者演算（"+1" をする演算）に関して閉じているような最小の集合として定義されるので、数学的帰納法の原理は[[定理]]として証明される。一方、自然数を公理的に扱う立場（[[ペアノの公理]]など）では、自然数に関する公理の一つとして数学的帰納法の原理が採用される。
任意の自然数 ''n'' について、0 + 1 + 2 + … + ''n'' = ''n''(''n''+1)/2 であることを証明する。自然数 ''k'' によって定まる命題 P(''k'') を 「0 + 1 + … + ''k'' = ''k''(''k''+1)/2 である」 とすればよい。▼
== 数学的帰納法の例 ==
まず、P(0)、つまり「0 = 0(0+1)/2」は正しい。次に、任意の自然数 ''k'' をとる。今、P(''k'') が正しいと仮定すると P(''k''+1) も正しい。実際、P(''k'') より▼
▲任意の自然数 ''n'' について、0 + 1 + 2 + … + ''n'' = ''n''(''n'' + 1)/2 であることを証明する。自然数 ''
▲まず、''P''(0)、つまり「0 = 0(0+1)/2」は正しい。次に、任意の自然数 ''k'' をとる。今、''P''(''k'') が正しいと仮定すると ''P''(''k'' + 1) も正しい。実際、''P''(''k'') より
:<math>0 + 1 + \dots + k + (k+1) = (0 + 1 + \dots + k) + (k+1) = \frac{k(k+1)}{2} + (k+1)</math>
となり、更にこれは
:<math> = \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2}</math>
となるので ''P''(''k'' + 1) が成立する。
以上から、数学的帰納法により、任意の自然数 ''n'' について命題 ''P''(''n'') が成立する。（証明終）
== バリエーション ==
数学的帰納法には次のようなバリエーションもある。場合によってはこちらを用いた方が議論が容易になる。これらのバリエーションはいずれも同値であるので、本質的には上と変わらない。
===
:#''P''(0) は真である。
:#''P''(''k'' + 1) が偽であれば、''P''(''k'') も偽である。
:よって任意の自然数 ''n'' について ''P''(''n'') は真である。
【補足】2. において、対偶を取ることで、
''P''(''k'') が真であれば、''P''(''k'' + 1) も真である。
という結果が得られるから、前記と同様になる。
=== 背理法を組み合わせたもの
次の証明は、[[無限降下法]]と呼ばれる証明とほぼ同等である。
:''P''(''n'') が成立
:これは矛盾であるから ''P''(''n'') が成立
=== 0 以外から始める ===
ある[[整数]] ''a'' から議論を始める。すなわち、次の2つを確かめることにより ''a'' 以上の任意の[[整数]] ''
:#''P''(''a'') は真である。
:#''a'' 以上の任意の整数 ''k'' に対し、''P''(''k'') が真であれば、''P''(''k'' + 1) も真である。
:よって ''a'' 以上の任意の自然数 ''n'' について ''P''(''n'') は真である。
=== 先立つすべての結果を用いる ===
仮定として ''P''(''k'') だけでなく ''P''(0) から ''P''(''k - 1'') までのすべて（もしくは一部）を用いる。
:任意の自然数 ''k'' をとったとき、''k'' より小さなすべての自然数 ''m'' に対して ''P''(''m'') が真であれば、''P''(''k'') も真である。
:
== 超限帰納法 ==
自然数について定義された数学的帰納法は、任意の[[整列集合]]に対して一般化される。この一般化を'''超限帰納法'''という。
:(''
:
''
== 整礎帰納法 ==
無限下降列が存在しない[[二項関係]]を'''整礎関係'''という。整礎関係が定義された集合に対して次が成り立つ。これを'''整礎帰納法'''という。
: < を集合 ''
::任意の ''a'' ∈ ''
超限帰納法は整礎帰納法の特殊な場合である。特に、超限帰納法においては、任意の空でない部分集合に'''最小元'''が存在する、という性質が、整礎帰納法においては、任意の空でない部分集合に'''極小元'''が存在する、という性質に対応している。
75 ⟶ 80行目:
前述のジョークにはさまざまなバリエーションがあるが、いずれも「少量の増加程度では大差ない。よって数学的帰納法より沢山の増加でも差はない」という誤謬を利用している。
<!--
この「証明」には「''P''(0)（もしくは ''P''(a)）」が成り立つことを示しているものの、「''P''(''k'') が成り立つならば ''P''(''k'' + 1) でも成り立つ」ということを示していない。これが根本的に間違いである。
↑
一旦削除。「ハゲ」の定義が曖昧な事が根本原因だと思われる為。
たとえばハゲの定義として「全ての人はハゲ」を採用すれば、
「''P''(''k'') が成り立つならば ''P''(''k'' + 1)でも成り立つ」もちゃんと示される。
-->
85 ⟶ 90行目:
*[[帰納]]
*[[演繹]]
*[[自然数]]
*[[整列集合]]
*[[整礎関係]]
*[[無限降下法]]
*[[再帰]]
| |||