FC2ブログ
わんこら日記
甘くて切ない日記。わんこら式数学の勉強法、解説記事

数学的帰納法は何故証明したことになるか?
高校数学で習う数学的帰納法については今日は語るか。


まあ証明でよく使うわけやけど、もちろん大学入っても使うメジャーな証明方法やねん。

数学的帰納法はnを自然数として、自然数に関するある命題があって

1,n=1のとき命題が成立

2,n=kの時、命題が成立すると仮定すると,n=k+1の時にも命題が成立

を示すとその命題はすべての自然数nに対して成立するってことを示すってやつやったわけやん。


数学的帰納法を使った証明の例を言うと(以下x^nはxのn乗を示すとする)
例えば

1+3+5+…+2n-1=n^2…(A)

って命題がすべての自然数nで成立することを証明するときに

(i),n=1の時は

左辺=1
右辺=1

で(A)は成立

(ii),n=kの時に(A)が成立すると仮定すると

1+3+5+…+2k-1=k^2

が成立していて、この両辺に2k+1を足すと

1+3+5+…+2k-1+2k+1=k^2+2k+1=(k+1)^2

よってn=k+1の時も(A)は成立。

(i),(ii)より(A)はすべての自然数nで成立する。



こういう風にn=1で成り立つことを示して、n=kで成り立つことを仮定したのを使ってn=k+1でも成り立つことを証明する使い方をするわけやけど、この数学的帰納法を使えば何故その命題は正しいことが言えるのかって言う証明が高校の教科書とかにないと思わん?


直感的には

n=1で成立して、n=kで成立したらn=k+1でも成立したって言えたら

まずn=1が成立することがわかっていて

n=1で成立するからn=2で成立(k=1を代入)

だから
n=2で成立するからn=3も成立(k=2を代入)

n=3で成立するからn=4も成立(k=3を代入)



って永遠と続くからすべての自然数nに対して成り立つんやろなって感じやな。


でも数学的帰納法を使うと何故命題は正しいと証明できるかの証明は実はちゃんとできるねん。
どうするかと言うと背理法を使うわけや。


[証明]
自然数に関するある命題P(n)が

(i)P(1)が真

(ii)任意の自然数kに対してP(k)が真ならばP(k+1)が真

であった時、P(n)がある自然数nに対して真でないと仮定する。

そのP(n)が真ではない自然数のうち最小のものをmとする。

(i)よりP(1)は真だからm≠1(⇔m≧2)

またmはP(n)が真でない最小の自然数だから、P(m-1)は真。

よって(ii)よりP(m)は真となり矛盾する。


従って

自然数に関するある命題P(n)が

(i)P(1)が真

(ii)任意の自然数kに対してP(k)が真ならばP(k+1)が真

であった時、P(n)はすべての自然数nに対して真であると言える。//


こんな感じや。
結構単純なわけやな。

(この証明は余り意味がない→数学的帰納法は何故証明したことになるか?は証明になってない)

ちなみに
(i),n=1のとき命題が成立
(ii),n≦kの時、命題が成立すると仮定すると,n=k+1の時にも命題が成立

とか
(i),n=1,2のとき命題が成立
(ii),n=k,k+1の時、命題が成立すると仮定すると,n=k+2の時にも命題が成立

とか言う形で数学的帰納法を使うことも受験ではよくある話やな。

それでこっから大学レベルになってくるけど、数学的帰納法をもっと一般化した超限帰納法って言うのがあるねん。

自然数に関する命題じゃなくても、整列集合に関する命題なら使えるねん。


(A,≦)を整列集合としてAの各元aについてある命題P(a)が与えられているとする。
(i)P(min A)が真
(ii)Aの各元a(≠min A)についてmすべてのb∈A<a>についてP(b)が真ならばP(a)も真である、

これを示すとAのすべての元aについてP(a)は真であると言える。
(A<a>={x∈A}|x<a})


整列集合とは

半順序集合(X,≦)がXの空でない部分集合が常に最小限をもつとき、整列集合であると言う。


半順序集合とは集合Xについて直積集合X×Xの各元(a,b)について二項関係ρを与える。

つまり(a,b)が二項関係ρを満たすことはaρbと書く。

この集合X上の二項関係ρについて

各元xについてxρxであるとき、ρは反射律を満たすと言い

xρyかつyρz⇒xρzであると言う命題が成り立つ時、ρは推移律を満たすと言い

xρyかつyρx⇒x=yであると言う命題が成り立つ時、ρは反対称律を満たすと言い、

ρがこの反射律と推移律、反対称律をを満たす時ρを順序関係と言い、対(X,ρ)を半順序集合と言う。



わけわからことなったかもしれんけど、とりあえずこういう整列集合なら使えるわけや。
自然数は普通の大小関係において典型的な整列集合になってるわけやねんな。

でも任意の集合は整列可能って言う定理があって、例えば整数になると最小値が存在しないから普通の大小関係では整列集合にならへんけど、例えば0<-1<1<-2<2<…とか順序を決めると整列集合になるわけや。

ついでに有理数も
0<-1<1<-2<2<1/2<-1/2<3<-3<1/3<-1/3<4<-4<3/2<-3/2<2/3<-2/3<1/4<-1/4<…とか順序を決めると強引やけど整列集合になるわけや。


そしたら実数はどうなるんか言われると、実数は

1/66<√2<5<543734<3√5<π<…

とか適当に無理やり順序作ったら一応出来ることは出来るってことなんちゃう。

たぶんな。


実数は対角線論法によって非可算やのに整列可能定理から順番に並べられるのはおかしいやないか!って思うかもしれんけど、それはたぶん可算と整列可能がごっちゃになってるんちゃうかな。


可算は自然数と全単射(1対1に対応している)が存在することで、

整列可能はただ単に並べられると言うことだけやから
1/66<√2<5<543734<3√5<π<…

こんなわけわからん規則性のない順序やったら自然数と対応してないやん。
でも一応順序は無理やり決められると。


有理数は

0,-1,1,-2,2,1/2,-1/2,3,-3,1/3,-1/3,4,-4,3/2,-3/2,2/3,-2/3,1/4,-1/4,…

こうやって自然数との全単射が存在するような並び方できるわけやから可算やねん。


こんな話は得意じゃない癖に、最後の話は実数を具体的に整列する方法は知られていないらしくて、そんな危ない議論まで足突っ込んでるから間に受けんといてくれ。

高校数学の公式や問題の解説

数理物理

関連記事

テーマ:日記 - ジャンル:日記

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://wankora.blog31.fc2.com/tb.php/1824-1f89c4ac
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

わんこら

Author:わんこら
京都大学理学部を数学専攻で卒業した数学と物理講師

現在、東京で働いています。

かずスクール
で数学を教えてます。

わんこら式数学の勉強法
数学の勉強方法や仕方を説明

詳しいプロフィール


メッセージはこちらへ
メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください

勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてはわんこら式診断プログラムを参考にしてメールください
都合がつかず遅れたり返せなかったりする場合があるのは申し訳ないです

リンクはばりばりのフリー
一言メールくれれば相互リンクします。


カテゴリーと名作集
読者に受けが良かった記事を集めてたり、今までの記事をカテゴリー別にまとめてます。



水と空気と街並とからだ
中学時代からの親友てつろうのブログ。
今年、滋賀医科に合格した医学生です。

リンク集
リンク集はこっちです。

このブログは携帯でも見られます。

カテゴリー

メール

リンク

ブロとも申請フォーム

この人とブロともになる

FC2カウンター

月別アーカイブ

ブログ内検索

RSSフィード