自然数の全体{1,2,…}は数直線に離散的に並んでいるが、この自然数の中から任意に有限個または無限個の元を選んで集合Aを作ると、Aには必ず最小数mが存在する。
[定理]自然数の整列性
自然数の、空でない任意の集合Aには最小数が存在する。
これは自然数の集合が持つ著しい特徴である。有理数の集合Q、整数の集合Z、実数の集合Rにはこのような特徴を持っていない。
[例]A={x|x∈R∧0＜x＜1}とおいた場合、Aは開区間(0,1)と一致する。(0,1)は下限0、上限1を持つが、最小数は持たない。なぜならば、どのような小さい正数を取っても、それよりさらに小さい正数が存在するからである。 ◇
この自然数の整列と数学的帰納法の原理は同値である。
[定理]自然数の整列性⇔数学的帰納法の原理
[証明]
[1]←を示す
Nの空でない部分集合A(≠φ)が与えられたとき、Aに最小数が存在することを示す。
そこで、∀a∈Aに対して、S:={x|x≦a∧x∈N}（これはAの下界である）とする。
まず、明らかに1∈Sである。
また、∃m∈Nに対して、m∈Aではあるが、である。
なぜならば、もしすべての自然数kに対して、「k∈Aならば、k+1∈S」であるとすれば、数学的帰納法の原理からS=Nとなり、Aが空ではないという仮定に矛盾する。
よって、m∈Aである。
なぜならば、もしそうでないとすれば、すべてのa∈Aに対して、m＜aである。即ち、m+1≦aとなり、m+1∈Sとなって、に矛盾するからである。
こうして、すべてのa∈Aに対して、m≦aとなり、mはAの最小数となる。
したがって、Aは最小数を含む。
[2]⇒を示す
数学的帰納法の条件(1)(2)を満たす自然数の集合Sが与えられたとき、自然数の整列性が成り立つと仮定して、S=Nとなることを示す。
NにおけるSの補集合をAとする。
もし、Aが空でないならば、自然数の整列性より、Aは最小数mを含んでいる。
1∈Sより、m≠1である。
すると、m-1∈Sとなり、帰納法の条件より、m∈Sとなる。
これはm∈Aに矛盾する。
よって、S=Nでなければならない。
