数学的帰納法が証明になる事の証明

質問

言葉遊びみたいですが、数学的帰納法が証明となる証明はあるでしょうか
1とkとk+1で成り立てば成り立つ、と言われてもすっきりしません
教えてください

回答No.5

kabaokaba · ベストアンサー

ペアノの公理そのものといっていいです．

帰納法の本質は，1から始まるだの0から始まるだのではなく

パラメータXに依存した
ある性質P(X)がなりたつときに
Xの「次の」パラメータYについても
P(Y)が成立する

ということです．
＃実際はもっと色々なバリエーションがあるんだけど
＃まあ，これくらいで

>1とkとk+1で成り立てば成り立つ、と言われてもすっきりしません

これですっきりするわけはないでしょう．
まったくの間違いだもん．

1で成り立つ
kで成り立てば，k+1で成り立つ
だから，任意の自然数で成り立つ

というわけで，決して「1,k,k+1で成り立つ」ではありません．
この微妙な違いが分からない，もしくは「なあなあ」にしてはいけません．
＃実際は1で始まる必要はないし，k+1である必要もいない

で，数学的帰納法そのものの証明はきっちり存在しますが
これは，集合論とかをきっちり処理しないといけない
かなーり厳しいものです
すでに指摘があるように
「ペアノの公理」のうち「帰納法の公理」というのを使いますが
ほんと，うっかりすると，わけがわからなくなる話です．

素朴に考えると
「自然数の集合の任意の部分集合には最小元が存在する」
という性質を使って，数学的帰納法を証明したくなりますが
この性質そのものが数学的帰納法で証明されるという事実もあります(^^;

実はこれは本質的に「自然数とは何か？」という問題に直結するお話です．
それを丁寧に追いかけると
自然数とは「数学的帰納法が成り立つ体系のことをいう」なんていう
本末転倒っぽいことが分かります(^^;

ということで実用的には
「自然数の集合とは数学的帰納法が使える集合」
という，ある意味開きの直りのざっくりとした理解で十分です．

どーしても「証明」を追いかけたいというなら
数学基礎論の本とか，ゲーデルに不完全性定理を証明している本を
探せば証明は見つかります．

=========
ちなみに・・・この帰納法ってやつは「専門家」からみても
十分「胡散臭い」ものらしいので
かなーり色々研究されてるようですよ．

お礼

とても詳しくありがとうございました
本屋で数学基礎の本を探してみます

回答No.4

MagicianKuma

私の理解では、これは公理で、数学的には証明されるものではないのでは？
ちがっているのかな？

回答No.3

Ae610

数学的帰納法
仮定1:n=1のとき成立
仮定2:n=kのとき成立すればn=k+1の時も成立
仮定1,2の成立によってNの全ての数に対して成立すること。

結論を否定してみる。
Nの全ての数について成立たないと仮定する。すると結論が成り立たなくなる最初の数が存在
しなければならない。それをmとする。
仮定1.によってmは1ではない。するとmの前の数が存在する。
（それを*mとする）
mは仮定が成立しなくなる最初の数であるからmの前の数*mに対しては仮定が成立するはずである。
従って仮定2により、*mの後の数mに対しても成立しなければならないはずだが、mは仮定が成立
しない最初の数としたことに矛盾する。
よって数学的帰納法は、Nの全ての数について成立する事が分かる。

お礼

数学的帰納法を背理法で証明する方法があるんですね
ありがとうございました

回答No.2

アウストラロ ピテクス（@ngkdddjkk）

数学的帰納法は、n=1とkが成り立つと仮定して、n=kのときからn=k+1のときが成り立つといった証明法です。

kが成り立てばk+1が成り立つことを証明しておけば、
n=1が成り立てば、n=2が成り立つ。
n=2が成り立てば、n=3が成り立つ。
n=3が成り立てば、n=4が成り立つ。
…
n=k-1が成り立てば、n=kが成り立つ。
n=kが成り立てば、n=k+1が成り立つ。
…

というように、n=1の時を基本として、
どんなnの値にたいしても成り立つということを証明する方法です。

したがって、(1)n=1が成り立つことを示す、と(2)n=kが成り立つと仮定してn=k+1が成り立つことを示すという２つの事柄に分けて考えると理解しやすいです。

お礼

分かりました
ありがとうございました

回答No.1

Tacosan

ふつうは「ドミノ倒し」と行くかもしれんがあえて「ペアノの公理」と言ってみよう.

補足

検索してみたところ
「 0, a ∈ M ⇒ a の後者 ∈ M 」であれば、 M は自然数の集合である
というのが数学的帰納法に似ている気がします、というかこれが成り立つなら数学的帰納法も成り立つと言える気がします
ただ数学的帰納法では0では考えないし、そもそもこの公理自体がなぜ成り立つのか分かりません
教えてください