数学的帰納法
P(n)を自然数nの命題（お題）としましょう。
P(0)が定義されており、
「P(n)が成立するならば、P(n+1)も成立する」ことが約束されているならば、すべての自然数nについてP(n)は成り立つことを確認しましょう。
明らかに、お題P(0)→P(1)→P(2)…とどんどんお題が成立していきます。
これを数学的帰納法と名付けましょう。
数学的帰納法の変法
0が定義できない場合もあるでしょう。
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-bn｜n∈ℤ｝を考えます。
自然数の部分集合は最小元をただ一つもつので、Ａの最小元を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)が成り立つことになります。
