過去のtwitterのつぶやきより引用。
まずは下記の通り定義する。
--------------------------------------------------------------------------------------------------
(定義1:非負整数)
Zを整数の集合、
Nを1以上の整数の集合とし、
0以上の整数を非負整数と呼ぶことにする。
--------------------------------------------------------------------------------------------------
また非負整数において、
「空でない任意の非負整数の集合は最小元をもつ。」
という性質がある事を認め、これを「整列性」と呼ぶことにする。
するとこの性質より、次の数学的帰納法と呼ばれる命題が成り立つ。
(集合に関する定義、命題は、集合の定義及び命題 - MathTriangleの雑記帳を参照されたい。)
--------------------------------------------------------------------------------------------------
(命題1:非負整数)
P(x)を非負整数xに関する命題とし、
∃m∈N∪{0}、∃n∈N、N_m:={x∈Z|x≧m}、S_m:={x∈N_m|P(x)は真}
として、次の2つの条件
(i) {m,m+1,...,m+n-1}⊂S_m
(ii) {k,k+1,...,k+n-1}⊂S_m⇒k+n∈S_m
が成り立つとする。
このときm以上の任意の非負整数xについて、P(x)が成り立つ。
(但しここで言う「命題」とは、「原理的に真か偽かいずれか１つに定まる主張の事」を表す。)
[証]
N_m＝S_mが成り立てば、(定義3,4:集合)より∀x∈N_m⇒x∈S_mとなり、m以上の任意の非負整数xについてP(x)が真となるので、N_m＝S_mが成り立つことを示す。実際、S_m,N_mの定義よりS_m⊂N_mは明らかであり、
N_m＼S_mの任意の元が非負整数であることも定義より明らかである。よってもしN_m＼S_m≠Φとすると、
整列性よりN_m＼S_mに最小元lが存在して、
l∈N_m＼S_m・・・①
が成り立ち、
(定義8:集合)よりl∈N_mなので、N_mの定義よりm≦lであり、
もしl≦m+n-1とすると、m≦lなので、(i)よりl∈S_mとなって、①に反する。
よってm+n-1＜lとなり、m∈N∪{0}⊂Z,n∈N⊂Z,l∈N_m⊂Zより
m+n-1、lは整数なので、
m+n-1≦l-1
m≦l-1-n+1＝l-n・・・②
となり、n∈Nなので、Nの定義より、
n≧1
-n≦-1
l-n≦l-1＜l・・・③
となるので、
A:={(l-n),(l-n)+1,(l-n)+2,...,(l-n)+n-1＝l-1}
とおけば、②及びN_mの定義よりA⊂N_mとなり、③及びAの定義より、
∀k∈A⊂N_m⇒k＜l・・・④
となる。ここでもし∃k∈N_m;k＜l,￢(k∈S_m)とすると、
k∈N_m,￢(k∈S_m)が成り立つので、N_m＼S_mの定義より
k∈N_m＼S_mとなり、k＜lよりlがN_m＼S_mの最小元であることに反するので、
∀k∈N_m;k＜l⇒k∈S_mとなる。よって④より∀k∈A⇒k∈S_mとなって、(定義3:集合)より
A⊂S_m、即ち
{(l-n),(l-n)+1,...,(l-n)+n-1＝l-1}⊂S_m
となるので、(ii)よりl∈S_mとなって、①に反するので、
N_m＼S_m＝Φである。よってS_m⊂N_m,N_m＼S_m＝Φが成り立つので、(命題1:集合)よりN_m＝S_mが成り立つ。■
--------------------------------------------------------------------------------------------------
