簡単に教えろ
#
一つ以上の自然数の集まりを考えると必ず最小の数が存在する。
例えば
{10, 432534, 8, 42, 1, 99999999, 1}
という自然数の集まりを考えると、1がその中の最小のものである。
直感的にはまあ当たり前の話だ。
整列原理(Well-Ordering Principle)
#
任意の空でないN(自然数全体の集合)の部分集合Sは最小元をもつというのが整列原理の主張だ。
紛らわしいので記号でも書いておく
S⊂N∧S=∅
であればSは最小元をもつ。
大した違いはないがここでは0∈Nであるとする。
証明
#
0∈Sであれば0は最小の自然数であり、Nの最小元なのでSは最小元をもつ。
0≦k≦n∧k∈SのときSが最小元をもつと仮定する。
そのとき0≦k≦n+1∧k∈SであればSが最小元をもつことを示す。
Sがn+1未満の元を持たなければ、n+1が最小元である。
それ以外の場合は、S=∅なので仮定より主張が成立する。
補足
#
帰納法が分かりにくかったので帰納の具体例を書いておく。
0≦k≦0∧k∈SならばSは最小元0をもつ。
つぎに0≦k≦1∧k∈Sの場合を考える。
0∈Sであれば0がSの最小元である。
0∈/Sであれば1がSの最小元である。
つぎに0≦k≦2∧k∈Sの場合を考える。
Sが2未満の元を持たない場合、2がSの最小元である。
その他の場合、先程のステップでSが最小元を持つことが示されている。
これを繰り返せばSが空でなければ最小元をもちそうなことがわかる。
感想
#
重要らしいが自分のレベルが低いのでよくわからなかった。
