Welcome to math2.work!
【只今】math2.workへようこそ!数学をわかりやすくお伝えしていきます!【サイト大改造中!】

数学的帰納法

数学
スポンサーリンク

数学的帰納法

P(n)を自然数nの命題(お題)としましょう。

P(0)が定義されており、

「P(n)が成立するならば、P(n+1)も成立する」ことが約束されているならば、すべての自然数nについてP(n)は成り立つことを確認しましょう。

明らかに、お題P(0)→P(1)→P(2)…とどんどんお題が成立していきます。

これを数学的帰納法と名付けましょう。

数学的帰納法の変法

0が定義できない場合もあるでしょう。

a以上の自然数についても数学的帰納法を定義することができます。

背理法

背理法とは、「命題Aが間違っている」と仮定して、

矛盾が生じることを示して、

「命題Aが間違っている」という仮定が間違っていたことを述べて、

であれば、排中律により、「命題Aは正しい」のだ、という論法のことです。

排中律というのは、命題というものは、真か偽かのいずれかである、という理屈です。場合による、とか、どちらでもない、とかいうものを許さないという理屈です。

自然数の部分集合の最小元の存在

自然数の部分集合Sに最小元が存在しないとすると、矛盾が生じます。

直感的な証明としては、

最小の元が存在しないということは、

Sの任意の元xについて、xは最小の元ではないのだから、

kn(n=1,2,3…)として、xより小さいSの元x-k1が存在することになる。

同様に、元x-k1より小さいSの元x-k2が存在する。

これを繰り返すと、結局、最も「1との差」が小さいSの元x-knが存在することになり、この元は最小の元となり、矛盾する。

ゆえに、任意の自然数の部分集合(厳密には空集合ではない)は最小元をただひとつ持つ。

除法の原理

任意の整数a,b(b≠0)について、

自然数の部分集合A={a-bn|n∈ℤ}を考えます。

自然数の部分集合は最小元をただ一つもつので、Aの最小元をrとします。

Aの定義から、r=a-bq | q∈ℤとなる整数qがただ一つ存在します。また、そのようなrは、自然数の部分集合の元なので、0以上です。

また、q以外のあらゆるn∈ℤについて、rはただ一つの最小元なので、

0≦r=a-bq<a-bnとなります。

さて、rは自然数なので、絶対値をとっても不等号は変わりません。

あらゆる整数nに対して、r=a-bq<a-bn=|a-bn|となっていますので、

a=0のときは、n=1を適用して、r<|0-b|=|-b|=|b|

a>0、b>0のときは、n=-1を適用して、r<|a+b|<|b|

a>0、b<0のときは、-b>0なので、n=1として、r<|a+(-b)|<|-b|=|b|

同じく、a<0、b<0のときは、-a>0、-b>0なので、n=-1を適用して、r<|a+b|=|(-a)+(-b)|<|-b|=|b|

 

a<0、b>0のときは、-a>0なので、n=1として、r<|a+(-b)|=|(-a)+b|<|b|

したがって、いずれの場合も、r<|b|である。

「除法の原理」

ゆえに、まとめると、a,bを任意の整数(ただしb≠0)のとき、

a=bq+rかつ0≦r<|b|となる整数q,rがただ一組だけ存在する。

これは、つまり、整数の割り算をすると、その商と余りはただ一組だけ存在するという意味です。

無限降下法

数学的帰納法の、おりていくバージョンです。

自然数kについて命題P(k)がなりたつときに、

自然数k'<kについて、必ず命題P(k’)がなりたつならば、

無限降下法によって、いずれはP(1)が成り立つことになります。