読者です 読者をやめる 読者になる 読者になる

MathTriangleの雑記帳

主に数学について書いていくブログです。数学の他にパズル、謎解き、音楽にも興味があります。

整列性及び数学的帰納法

過去の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)が成り立つ。

(但しここで言う「命題」とは、「原理的に真か偽かいずれか1つに定まる主張の事」を表す。)
[証]

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が成り立つ。■

--------------------------------------------------------------------------------------------------