「数学的帰納法」の版間の差分
削除された内容 追加された内容
編集の要約なし |
編集の要約なし |
||
3行目:
:#任意の自然数 ''k'' に対して、''P''(''k'') ⇒ ''P''(''k'' + 1) が成り立つ。
:よって任意の自然数 ''n'' について ''P''(''n'') が成り立つ。
イメージとしては、2. により次々と命題の正しさが"伝播"されていくことになる。つまり、1. によりまず ''P''(0) は正しく、これと 2. により ''P''(1) は正しく、これと再び 2. により ''P''(2) は正しく、これと...、のように以下これが無限に続いていく。このことによって任意の自然数 ''n'' について ''P''(''n'') が成り立つことが直観的に確かめられる。ただし、これは数学的帰納法を正当化するための厳密な議論ではない。正式には、数学的帰納法の正しさは自然数の性質の一つである'''数学的帰納法の原理'''によって
なお、数学的「[[帰納]]法」という名前がつけられているが、数学的帰納法を用いた証明は帰納法ではなく[[演繹]]法である。先に述べた 2. により次々と命題の正しさが"伝播"されていき、すべての自然数に対して命題が証明されていく様子が帰納のように見えるためこのような名前がつけられたにすぎない。
== 数学的帰納法の原理 ==
数学的帰納法の正しさ
:次の条件をみたす自然数の集合 ''A'' は、自然数全体の集合 '''N''' と等しい：
:#0 ∈ ''A'' 。
:#''A'' は ''S''(''n'') = ''n'' + 1 で定義される関数 ''S'' : '''N''' → '''N''' に関して閉じている。
この原理を用い
#''P''(0) が成り立つ。
#任意の自然数 ''k'' に対して、''P''(''k'') ⇒ ''P''(''k'' + 1) が成り立つ。
31行目:
== バリエーション ==
数学的帰納法には次のようなバリエーションもあ
=== 対偶論法を組み合わせたもの ===
49行目:
=== 0 以外から始める ===
ある
:#''P''(''
:#''
:よって ''
''m'' = 1 の場合が特に頻繁に用いられる。
=== 先立つすべての結果を用いる ===
58 ⟶ 59行目:
:任意の自然数 ''k'' をとったとき、''k'' より小さなすべての自然数 ''m'' に対して ''P''(''m'') が真であれば、''P''(''k'') も真である。
:よって任意の自然数 ''n'' について ''P''(''n'') は真である。
この議論の正しさは自然数全体の集合 '''N''' が通常の大小関係 < によって整列されていることによる。< が '''N''' 上の整列順序であることは、最初に述べた形の数学的帰納法を用いることで証明される。
== 超限帰納法 ==
| |||